Spójność pamięci podręcznej — Cache coherence

Ilustracja przedstawiająca wiele pamięci podręcznych pewnej pamięci, która działa jako zasób współdzielony
Niespójne pamięci podręczne: Pamięci podręczne mają różne wartości dla jednej lokalizacji adresu.

W komputerowym architektury , cache koherencji jest jednolitość danych współdzielonych zasobów, które kończy się przechowywane w wielu lokalnych skrytek . Gdy klienci w systemie przechowują pamięci podręczne wspólnego zasobu pamięci, mogą pojawić się problemy z niespójnymi danymi, co ma miejsce szczególnie w przypadku procesorów w systemie wieloprocesorowym .

Na ilustracji po prawej rozważmy, że obaj klienci mają w pamięci podręcznej kopię określonego bloku pamięci z poprzedniego odczytu. Załóżmy, że klient na dole aktualizuje/zmienia ten blok pamięci, klient na górze może pozostać z nieprawidłową pamięcią podręczną pamięci bez powiadomienia o zmianie. Spójność pamięci podręcznej ma na celu zarządzanie takimi konfliktami poprzez zachowanie spójnego widoku wartości danych w wielu pamięciach podręcznych.

Spójne pamięci podręczne: Wartość we wszystkich kopiach pamięci podręcznych jest taka sama.

Przegląd

W systemie wieloprocesorowym z pamięcią współdzieloną z oddzielną pamięcią podręczną dla każdego procesora możliwe jest posiadanie wielu kopii danych współdzielonych: jednej kopii w pamięci głównej i jednej w lokalnej pamięci podręcznej każdego procesora, który o to poprosił. Gdy jedna z kopii danych zostanie zmieniona, pozostałe kopie muszą odzwierciedlać tę zmianę. Spójność pamięci podręcznej to dyscyplina, która zapewnia, że ​​zmiany wartości współdzielonych operandów (danych) są propagowane w systemie w odpowiednim czasie.

Oto wymagania dotyczące spójności pamięci podręcznej:

Propagacja zapisu
Zmiany danych w dowolnej pamięci podręcznej muszą być propagowane do innych kopii (tej linii pamięci podręcznej) w równorzędnych pamięciach podręcznych.
Serializacja transakcji
Odczyty/zapisy w jednej lokalizacji pamięci muszą być widoczne dla wszystkich procesorów w tej samej kolejności.

Teoretycznie, spójność mogą być wykonywane na obciążenia / sklep ziarnistości . Jednak w praktyce jest to zwykle wykonywane na poziomie szczegółowości bloków pamięci podręcznej.

Definicja

Koherencja określa zachowanie odczytów i zapisów w jednej lokalizacji adresowej.

Jeden rodzaj danych występujących jednocześnie w różnych pamięciach podręcznych nazywa się spójnością pamięci podręcznej lub w niektórych systemach pamięcią globalną.

W systemie wieloprocesorowym należy wziąć pod uwagę, że więcej niż jeden procesor buforował kopię lokalizacji pamięci X. Aby osiągnąć spójność pamięci podręcznej, konieczne są następujące warunki:

  1. W odczycie wykonanym przez procesor P do lokalizacji X, który następuje po zapisie przez ten sam procesor P do X, bez zapisów do X przez inny procesor występujących między instrukcjami zapisu i odczytu wykonanymi przez P, X musi zawsze zwrócić wartość napisany przez P.
  2. W odczycie dokonanym przez procesor P1 do lokalizacji X, który następuje po zapisie przez inny procesor P2 do X, bez innych zapisów do X dokonanych przez dowolny procesor między dwoma dostępami i przy wystarczającym oddzieleniu odczytu i zapisu, X musi zawsze zwróć wartość zapisaną przez P2. Warunek ten definiuje pojęcie spójnego spojrzenia na pamięć. Propagacja zapisów do lokalizacji pamięci współdzielonej zapewnia, że ​​wszystkie pamięci podręczne mają spójny widok pamięci. Jeśli procesor P1 odczytuje starą wartość X, nawet po zapisie przez P2, możemy powiedzieć, że pamięć jest niespójna.

Powyższe warunki spełniają kryteria propagacji zapisu wymagane dla spójności pamięci podręcznej. Nie są one jednak wystarczające, ponieważ nie spełniają warunku serializacji transakcji. Aby lepiej to zilustrować, rozważmy następujący przykład:

System wieloprocesorowy składa się z czterech procesorów - P1, P2, P3 i P4, z których wszystkie zawierają buforowane kopie wspólnej zmiennej S, której wartość początkowa wynosi 0. Procesor P1 zmienia wartość S (w swojej buforowanej kopii) na 10, po czym procesor P2 zmienia wartość S we własnej pamięci podręcznej na 20. Jeśli zapewnimy tylko propagację zapisu, to P3 i P4 z pewnością zobaczą zmiany wprowadzone w S przez P1 i P2. Jednak P3 może zobaczyć zmianę dokonaną przez P1 po zobaczeniu zmiany dokonanej przez P2, a zatem zwrócić 10 przy odczycie do S . Z drugiej strony P4 może zobaczyć zmiany dokonane przez P1 i P2 w kolejności, w jakiej zostały wykonane, a zatem zwrócić 20 przy odczycie do S . Procesory P3 i P4 mają teraz niespójny widok pamięci.

W związku z tym, aby zapewnić serializację transakcji, a tym samym osiągnąć spójność pamięci podręcznej, następujący warunek wraz z dwoma poprzednimi wymienionymi w tej sekcji musi zostać spełniony:

  • Zapisy w tej samej lokalizacji muszą być sekwencjonowane. Innymi słowy, jeśli lokalizacja X otrzymała dwie różne wartości A i B, w tej kolejności, z dowolnych dwóch procesorów, procesory nigdy nie mogą odczytać lokalizacji X jako B, a następnie odczytać jej jako A. Lokalizacja X musi być widziana z wartościami A i B w tej kolejności.

Alternatywną definicją spójnego systemu jest definicję sekwencyjnego modelu pamięci spójności : „spójny system pamięci podręcznej musi pojawić się, aby wykonać wszystkie wczytywania wątków i przechowywać je w jednym miejscu pamięci w całkowitej kolejności, która respektuje kolejność programu każdego wątku” . Tak więc jedyną różnicą między systemem koherentnej pamięci podręcznej a systemem spójnym sekwencyjnie jest liczba lokalizacji adresowych, o których mówi definicja (pojedyncza lokalizacja pamięci dla systemu spójnego z pamięcią podręczną i wszystkie lokalizacje pamięci dla systemu spójnego sekwencyjnie).

Inna definicja brzmi: „wieloprocesor jest spójny z pamięcią podręczną, jeśli wszystkie zapisy w tej samej lokalizacji pamięci są wykonywane w pewnej kolejności sekwencyjnej”.

Rzadko, ale szczególnie w algorytmach, koherencja może zamiast tego odnosić się do lokalizacji odniesienia . Wiele kopii tych samych danych może znajdować się jednocześnie w różnych pamięciach podręcznych, a jeśli procesory mogą swobodnie aktualizować własne kopie, może to spowodować niespójny obraz pamięci.

Mechanizmy spójności

Główny artykuł: protokoły spójności pamięci podręcznej (przykłady)

Dwa najczęstsze mechanizmy zapewniania spójności to podsłuchiwanie i oparte na katalogach , z których każdy ma swoje wady i zalety. Protokoły oparte na szpiegowaniu są zwykle szybsze, jeśli dostępna jest wystarczająca przepustowość , ponieważ wszystkie transakcje są żądaniem/odpowiedzią widzianym przez wszystkie procesory. Wadą jest to, że podsłuchiwanie nie jest skalowalne. Każde żądanie musi być rozgłaszane do wszystkich węzłów w systemie, co oznacza, że ​​wraz z powiększaniem się systemu rozmiar magistrali (logicznej lub fizycznej) i zapewniana przez nią przepustowość muszą rosnąć. Z drugiej strony katalogi mają zwykle dłuższe opóźnienia (z żądaniem/przeskokiem/odpowiedzią z 3 przeskokami), ale zużywają znacznie mniej przepustowości, ponieważ wiadomości są przesyłane punkt do punktu i nie są rozgłaszane. Z tego powodu wiele większych systemów (>64 procesory) używa tego typu spójności pamięci podręcznej.

Wścibianie nosa

Główny artykuł: węszenie autobusów
Po raz pierwszy wprowadzony w 1983 r. Szpiegowanie to proces, w którym poszczególne pamięci podręczne monitorują linie adresowe pod kątem dostępu do lokalizacji pamięci, które przechowują w pamięci podręcznej. Te protokoły zapisu unieważnić i protokoły zapisu aktualizacji skorzystać z tego mechanizmu.
W przypadku mechanizmu snooping filtr snoop zmniejsza ruch snooping przez utrzymywanie wielu wpisów, z których każdy reprezentuje linię pamięci podręcznej, która może być własnością jednego lub większej liczby węzłów. Gdy wymagana jest zamiana jednego z wpisów, filtr snoop wybiera do zastąpienia wpisu reprezentującego linię lub linie pamięci podręcznej należące do najmniejszej liczby węzłów, jak określono na podstawie wektora obecności w każdym z wpisów. Jeśli do najmniejszej liczby węzłów należy więcej niż jedna linia pamięci podręcznej, używany jest algorytm tymczasowy lub inny.

Oparte na katalogach

Główny artykuł: Oparta na katalogach spójność pamięci podręcznej
W systemie opartym na katalogach udostępniane dane są umieszczane we wspólnym katalogu, który zapewnia spójność między pamięciami podręcznymi. Katalog działa jak filtr, przez który procesor musi poprosić o pozwolenie na załadowanie wpisu z pamięci podstawowej do swojej pamięci podręcznej. Po zmianie wpisu katalog aktualizuje lub unieważnia inne pamięci podręczne za pomocą tego wpisu.

Rozproszone systemy pamięci współdzielonej naśladują te mechanizmy, próbując zachować spójność między blokami pamięci w luźno powiązanych systemach.

Protokoły spójności

Protokoły koherencji stosują spójność pamięci podręcznej w systemach wieloprocesorowych. Intencją jest, aby dwaj klienci nigdy nie widzieli różnych wartości dla tych samych udostępnionych danych.

Protokół musi realizować podstawowe wymagania dotyczące spójności. Może być dostosowany do docelowego systemu lub aplikacji.

Protokoły można również sklasyfikować jako snoopy lub oparte na katalogach. Zazwyczaj wczesne systemy wykorzystywały protokoły oparte na katalogach, w których katalog śledził udostępniane dane i osoby udostępniające. W protokołach snoopy żądania transakcji (odczyt, zapis lub aktualizacja) są wysyłane do wszystkich procesorów. Wszystkie procesory śledzą żądanie i odpowiednio reagują.

Propagację zapisu w protokołach snoopy można zaimplementować za pomocą jednej z następujących metod:

Zapis-unieważnij
Gdy obserwuje się operację zapisu do lokalizacji, której kopię ma pamięć podręczna, kontroler pamięci podręcznej unieważnia własną kopię podsłuchiwanej lokalizacji pamięci, co wymusza odczyt z pamięci głównej nowej wartości przy następnym dostępie.
Zapis aktualizacji
Po zaobserwowaniu operacji zapisu w lokalizacji, której kopię ma pamięć podręczna, kontroler pamięci podręcznej aktualizuje swoją własną kopię podsłuchiwanej lokalizacji pamięci o nowe dane.

Jeśli projekt protokołu stanowi, że za każdym razem, gdy jakakolwiek kopia udostępnionych danych zostanie zmieniona, wszystkie pozostałe kopie muszą zostać „zaktualizowane”, aby odzwierciedlić zmianę, jest to protokół zapisu aktualizacji. Jeśli projekt stwierdza, że ​​zapis do kopii w pamięci podręcznej przez dowolny procesor wymaga od innych procesorów odrzucenia lub unieważnienia ich kopii w pamięci podręcznej, jest to protokół unieważniający zapis.

Skalowalność jest jednak jedną z wad protokołów rozgłoszeniowych.

Opracowano różne modele i protokoły w celu utrzymania spójności, takie jak MSI , MESI (aka Illinois), MOSI , MOESI , MERSI , MESIF , write-once , Synapse, Berkeley, Firefly i Dragon . W 2011 roku firma ARM Ltd zaproponowała AMBA 4 ACE do obsługi spójności w SoC . Specyfikacja AMBA CHI (Coherent Hub Interface) firmy ARM Ltd , należąca do grupy specyfikacji AMBA5, definiuje interfejsy do podłączenia w pełni spójnych procesorów.

Zobacz też

Bibliografia

Dalsza lektura