Spójność pamięci podręcznej na podstawie katalogów - Directory-based cache coherence
W inżynierii komputerowej , katalog oparty na spójność cache jest rodzajem mechanizmu spójności cache , gdzie katalogi są używane do zarządzania pamięci podręcznej zamiast metod Snoopy ze względu na ich skalowalność. Metody podsłuchiwania autobusów skalują się słabo ze względu na wykorzystanie nadawania . Te metody mogą służyć do określania wydajności i skalowalności systemów katalogowych.
Pełny format wektorowy
W pełnym formacie wektorowym, dla każdej możliwej linii pamięci podręcznej w pamięci , bit jest używany do śledzenia, czy każdy pojedynczy procesor ma tę linię przechowywaną w pamięci podręcznej . Pełno-bitowy format wektorowy jest najprostszą strukturą do wdrożenia, ale najmniej skalowalną. SGI Origin 2000 wykorzystuje połączenie pełnej bitowym wektorem i grubej bitowym wektorem zależności od liczby procesorów.
Każda pozycja katalogu musi mieć 1 bit na procesor na wiersz pamięci podręcznej, wraz z bitami służącymi do śledzenia stanu katalogu. Prowadzi to do całkowitego wymaganego rozmiaru wynoszącego (liczba procesorów) × liczba linii pamięci podręcznej , przy współczynniku narzutu pamięci wynoszącym (liczba procesorów) / (rozmiar bloku pamięci podręcznej × 8) .
Można zauważyć, że narzut katalogu skaluje się liniowo wraz z liczbą procesorów. Chociaż może to być dobre w przypadku niewielkiej liczby procesorów, po wdrożeniu w dużych systemach wymagania dotyczące rozmiaru katalogu stają się nadmierne. Na przykład w przypadku bloku o rozmiarze 32 bajtów i 1024 procesorów współczynnik obciążenia pamięci wynosi 1024 / (32 × 8) = 400%.
Zgrubny bitowy format wektorowy
Zgrubny format wektora bitowego ma podobną strukturę do formatu pełnego wektora bitowego, chociaż zamiast śledzenia jednego bitu na procesor dla każdej linii pamięci podręcznej, katalog grupuje kilka procesorów w węzły , przechowując, czy linia pamięci podręcznej jest przechowywana w węźle, a nie w linia. Poprawia to wymagania dotyczące rozmiaru kosztem oszczędności ruchu magistrali (procesory na węzeł) × (łączna liczba linii) bitów przestrzeni. Zatem narzut współczynnika jest taki sam, wystarczy zastąpić liczbę procesorów liczbą grup procesorów. Gdy żądanie magistrali jest wysyłane do linii pamięci podręcznej, którą ma jeden procesor w grupie, katalog transmituje sygnał do każdego procesora w węźle, a nie tylko do pamięci podręcznych, które go zawierają, co prowadzi do niepotrzebnego ruchu do węzłów, które nie mają danych w pamięci podręcznej.
W tym przypadku pozycja katalogu używa 1 bitu dla grupy procesorów dla każdej linii pamięci podręcznej. W tym samym przykładzie, co w przypadku formatu Full Bit Vector, jeśli weźmiemy pod uwagę 1 bit na 8 procesorów jako grupę, to narzut pamięci wyniesie 128 / (32 × 8) = 50%. Jest to znacząca poprawa w stosunku do formatu Full Bit Vector.
Rzadki format katalogu
Pamięć podręczna przechowuje tylko niewielki podzbiór bloków w pamięci głównej w określonym czasie. Dlatego większość wpisów w katalogu będzie należeć do niezbuforowanych bloków. W rzadkim formacie katalogu marnotrawstwo jest redukowane poprzez przechowywanie w katalogu tylko bloków z pamięci podręcznej. Rozważmy procesor z pamięcią podręczną o rozmiarze 64 KB, blokiem o rozmiarze 32 bajtów i wielkością pamięci głównej 4 MB. Maksymalna liczba wpisów, jakie może mieć katalog w formacie katalogu rzadkiego, to 2048. Jeśli katalog zawiera wpisy dla wszystkich bloków w pamięci, liczba wpisów w katalogu wyniesie 131072. Jest więc oczywiste, że poprawa pamięci dostarczany przez rzadki format katalogów jest bardzo istotny.
Format drzewa binarnego z równoważeniem liczb
W tym formacie katalog jest zdecentralizowany i rozdzielony między pamięci podręczne, które współużytkują blok pamięci. Różne pamięci podręczne, które współużytkują blok pamięci, są ułożone w formie drzewa binarnego . Pamięć podręczna, która jako pierwsza uzyskuje dostęp do bloku pamięci, jest węzłem głównym . Każdy blok pamięci zawiera informacje o węźle głównym (HEAD) i pole licznika udostępniania (SC). Pole SC zawiera liczbę pamięci podręcznych, które współużytkują blok. Każdy wpis pamięci podręcznej zawiera wskaźniki do następnych współdzielonych pamięci podręcznych znanych jako L-CHD i R-CHD. Warunkiem dla tego katalogu jest to, że drzewo binarne powinno być zrównoważone liczbowo, tj. Liczba węzłów w lewym poddrzewie musi być równa lub o jeden większa niż liczba węzłów w prawym poddrzewie. Wszystkie poddrzewa również powinny być zrównoważone liczbowo.
Format katalogu połączonego
W tym formacie pamięć przechowuje wskaźnik katalogu do najnowszej pamięci podręcznej, która uzyskała dostęp do bloku, a każda pamięć podręczna ma wskaźnik do poprzedniej pamięci podręcznej, która uzyskała dostęp do bloku. Kiedy więc procesor wysyła żądanie zapisu do bloku w pamięci, wysyła unieważnienia w dół łańcucha wskaźników. W tym katalogu, gdy zastępowany jest blok pamięci podręcznej, musimy przejść przez listę , aby zmienić katalog, co zwiększa opóźnienie . Aby zapobiec tym podwójnie połączonym listom, są obecnie szeroko stosowane, w których każda buforowana kopia ma wskaźniki do poprzedniej i następnej pamięci podręcznej, która uzyskuje dostęp do bloku.
Ograniczony format wskaźnika
Ograniczony format wskaźnika wykorzystuje określoną liczbę wskaźników do śledzenia procesorów, które buforują dane. Gdy nowy procesor buforuje blok, z puli wybierany jest wolny wskaźnik wskazujący na ten procesor. Istnieje kilka możliwości obsługi przypadków, w których liczba osób udostępniających przekracza liczbę bezpłatnych wskaźników. Jedną z metod jest unieważnienie jednego z współużytkujących, używając jego wskaźnika dla nowego żądającego, chociaż może to być kosztowne w przypadkach, gdy blok ma dużą liczbę czytników, na przykład blokadę. Inną metodą jest udostępnienie oddzielnej puli bezpłatnych wskaźników dla wszystkich bloków. Ta metoda jest zwykle skuteczna, ponieważ liczba bloków współdzielonych przez dużą liczbę procesorów zwykle nie jest zbyt duża.