Spójność pamięci podręcznej oparta na katalogach
W inżynierii komputerowej spójność pamięci podręcznej oparta na katalogach jest rodzajem mechanizmu spójności pamięci podręcznej , w którym katalogi są używane do zarządzania pamięciami podręcznymi zamiast podsłuchiwania magistrali . Metody szpiegowania magistrali słabo się skalują ze względu na wykorzystanie rozgłaszania . Tych metod można używać do określania zarówno wydajności , jak i skalowalności systemów katalogowych.
Pełnobitowy format wektorowy
W pełnym formacie wektorów bitowych, 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 swojej pamięci podręcznej . Format pełnego wektora bitowego jest strukturą najprostszą do zaimplementowania, ale najmniej skalowalną. SGI Origin 2000 wykorzystuje kombinację pełnego wektora bitowego i grubego wektora bitowego w zależności od liczby procesorów.
Każdy wpis katalogu musi mieć 1 bit przechowywany na procesor na linię pamięci podręcznej, wraz z bitami do śledzenia stanu katalogu. Prowadzi to do tego, że całkowity wymagany rozmiar wynosi (liczba procesorów) × liczba wierszy 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 obciążenie katalogów skaluje się liniowo wraz z liczbą procesorów. Chociaż może to być dobre dla niewielkiej liczby procesorów, po zaimplementowaniu w dużych systemach wymagania dotyczące rozmiaru katalogu stają się nadmierne. Na przykład przy rozmiarze bloku 32 bajtów i 1024 procesorach współczynnik narzutu pamięci wynosi 1024/(32×8) = 400%.
Grubo bitowy format wektorowy
Zgrubny format wektora bitowego ma podobną strukturę do pełnego formatu 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, zapamiętując, czy linia pamięci podręcznej jest przechowywana w węźle, a nie w linia. Poprawia to wymagania dotyczące rozmiaru kosztem magistrali (procesory na węzeł) × (całkowita liczba linii) bitów przestrzeni. Zatem narzut proporcji jest taki sam, po prostu zastępując liczbę procesorów liczbą grup procesorów. Kiedy wysyłane jest żądanie magistrali dla linii pamięci podręcznej, którą ma jeden procesor w grupie, katalog rozgłasza sygnał do każdego procesora w węźle, a nie tylko do pamięci podręcznej, która go zawiera, co prowadzi do niepotrzebnego ruchu do węzłów, które nie mają danych buforowane.
W tym przypadku pozycja katalogu wykorzystuje 1 bit 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 dla 8 procesorów jako grupę, wówczas 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 bloków niebuforowanych. W formacie katalogu rzadkiego marnotrawstwo jest redukowane dzięki przechowywaniu w katalogu tylko buforowanych bloków. Rozważmy procesor z pamięcią podręczną o wielkości 64 KB, blokiem o wielkości 32 bajtów i pamięcią główną o wielkości 4 MB. Maksymalna liczba wpisów, jakie może mieć katalog w formacie rzadkiego katalogu, wynosi 2048. Jeśli katalog zawiera wpis dla wszystkich bloków w pamięci, liczba wpisów w katalogu wyniesie 131072. Jest zatem oczywiste, że poprawa przechowywania dostarczany przez format katalogu rzadkiego jest bardzo znaczący.
Format drzewa binarnego o zrównoważonych liczbach
W tym formacie katalog jest zdecentralizowany i rozdzielony między pamięci podręczne, które współdzielą blok pamięci. Różne pamięci podręczne, które współdzielą blok pamięci, są ułożone w postaci 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 współdzielenia (SC). Pole SC zawiera liczbę pamięci podręcznych współdzielących blok. Każdy wpis w 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, aby drzewo binarne było zrównoważone liczbowo, tzn. liczba węzłów w lewym poddrzewie musi być równa lub o jeden większa od liczby węzłów w prawym poddrzewie. Wszystkie poddrzewa powinny być również zrównoważone liczbowo.
Format katalogów łańcuchowych
W tym formacie pamięć przechowuje wskaźnik katalogu do ostatniej pamięci podręcznej, która uzyskała dostęp do bloku, a każda pamięć podręczna zawiera 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 blok pamięci podręcznej zostanie zastąpiony, musimy przejść przez listę , aby zmienić katalog, co zwiększa opóźnienie . Aby temu zapobiec, obecnie szeroko stosuje się listy z podwójnymi linkami , w których każda kopia w pamięci podręcznej ma wskaźniki do poprzedniej i następnej pamięci podręcznej, która uzyskuje dostęp do bloku.
Ograniczony format wskaźnika
Format ograniczonego wskaźnika używa określonej liczby wskaźników do śledzenia procesorów buforujących dane. Gdy nowy procesor umieszcza blok w pamięci podręcznej, z puli wybierany jest wolny wskaźnik wskazujący ten procesor. Istnieje kilka opcji obsługi przypadków, gdy liczba współuczestników przekracza liczbę bezpłatnych wskaźników. Jedną z metod jest unieważnienie jednego z współuczestników przy użyciu jego wskaźnika dla nowego żądającego, chociaż może to być kosztowne w przypadkach, gdy blok ma dużą liczbę czytelników, takich jak blokada. Inną metodą jest posiadanie oddzielnej puli wolnych wskaźników dostępnych dla wszystkich bloków. Ta metoda jest zwykle skuteczna, ponieważ liczba bloków współdzielonych przez dużą liczbę procesorów zwykle nie jest bardzo duża.