Nowa koncepcja pracy pamięci cache

[KopalniaWiedzy.pl 317]

Podczas International Conference on Parallel Architectures and Compilation Techniques naukowcy z MIT-u zaprezentowali pierwszą od 30 lat nową koncepcję utrzymania spójności pamięci cache w układach elektronicznych.

We współczesnych procesorach każdy rdzeń ma przydzieloną własną pamięć cache. Obok niej funkcjonuje jednak współdzielony cache, do której dostęp mają wszystkie rdzenie. Gdy jeden z rdzeni uaktualnia dane we współdzielonej cache, inne rdzenie muszą o tym wiedzieć. Tworzony jest więc katalog z informacjami o tym, który rdzeń ma kopie których danych. Ten katalog może zajmować olbrzymią część współdzielonej pamięci. Na przykład z układzie 64-rdzeniowym może on zajmować aż 12% cache'u, a im więcej rdzeni tym większy odsetek zajętej pamięci. Obecnie udział zajętej pamięci cache rośnie proporcjonalnie do liczby rdzeni. Tymczasem zgodnie z nową koncepcją MIT-u udział ten rośnie logarytmicznie. Przy układach składających się z 72 rdzeni korzyść ze zmiany obecnie stosowanej metodologii na tę zaproponowaną przez MIT jest czysto hipotetyczna. Jednak wraz z rosnącą liczbą rdzeni staje się ona wyraźna. Przy 128 rdzeniach można dzięki nowemu podejściu zaoszczędzić 30% pamięci, przy 256 rdzeniach oszczędności sięgają 80%, a przy 1000 rdzeniach jest to 96%.

Gdy wiele rdzeni wyłącznie składuje dane w pamięci cache, nie ma problemu. Jednak pojawia się on, gdy któryś z rdzeni chce zmienić już przechowywane dane. Dzięki wspomnianemu katalogowi rdzeń ten wie, które rdzenie pracują na danych, które ma zamiar zmienić i wysyła im odpowiednie informacje, dzięki którym unieważniane są kopie danych przechowywanych lokalnie przez te rdzenie. Dzięki katalogowi mamy pewność, że gdy dochodzi do zmiany współdzielonych danych, żaden z rdzeni nie przechowuje starej kopii i nie nadpisze nowych informacji starymi. Po zmianie danych nie powinno dojść do sytuacji, że gdziekolwiek zostanie odczytana stara wersja danych. Nadpisanie danych odbywa się więc po tym, jak wcześniejsze dane zostaną pobrane przez wszystkie rdzenie, które ich potrzebują - mówi magistrant Xiangyao Yu z MIT-u.

Yu i jego promotor, profesor Srini Devadas, zdali sobie sprawę, że kolejność odczytu w czasie nie jest istotna, o ile zostanie zachowana logiczna kolejność odczytu. Oznacza to, że na przykład rdzeń A może wciąż pracować na danych, które już zostały zmienione przez rdzeń B o ile pozostałe rdzenie wiedzą o tym, że praca wykonywana przez rdzeń A jest wcześniejsza od pracy rdzenia B. Yu i Devadas postanowili więc znaleźć prosty system pozwalający na zastąpienie porządku czasowego porządkiem logicznym. W zaproponowanym przez nich systemie każdy z rdzeni ma własny licznik i każdy fragment danych w pamięci również ma własny licznik. Gdy jest uruchamiany program, wszystkie liczniki zostają ustawione na zero. Gdy rdzeń sięga po jakieś dane, dochodzi do zmiany licznika. Dopóki licznik nie przekroczy okreslonej wartości skojarzone z nim dane zachowują ważność. Gdy któryś z rdzeni chce nadpisać dane staje się ich właścicielem. Inne rdzenie mogą wciąż pracować na własnych kopiach niezmodyfikowanych danych, ale muszą skoordynować swoje działania z właścicielem danych. Z kolei właściciel, czyli rdzeń dokonujący nadpisania danych, ustawia swój własny licznik na wartość wyższa, niż ostatnia wartość licznika wspomnianych danych.

Przypuśćmy, że rdzenie od A do D pracują na tych samych danych. W związku z tym wszystkie ustawiły swoje liczniki na 1, a licznik danych został ustawiony na 10. Gdy rdzeń E chce nadpisać te dane, przejmuje je na własność i ustawia swój licznik na 11. W ten sposób licznik rdzenia E wskazuje, że pracuje on na - logicznie - późniejszej wersji danych niż inne rdzenie, których liczniki są ustawione na 1. Jeśli teraz rdzeń A chce uzyskać dostęp do danych, dowiaduje się, że ich właścicielem jest rdzeń E. Wysyła mu więc wiadomość. Rdzeń E przesyła więc dane do współdzielonej pamięci. Są one stamtąd odczytywane przez rdzeń A, który ustawia swój licznik na 11 lub więcej. Jako, że system opiera się na następstwie logicznym, a nie czasowym, twórcy nazwali go Tardis, od podróżującego w czasie pojazdu Doktora Who.

Tardis nie tylko pozwalana zaoszczędzeniu pamięci, ale eliminuje też potrzebę wysyłania do rdzeni informacji o unieważnieniu danych. W układach składających się z setek czy tysięcy rdzeni doprowadzi to do zwiększenia wydajności samych kości.
Christopher Hughes, główny inżynier w Intel Labs, jest pod wrażeniem osiągnięć uczonych z MIT-u. Wiem, że wiele osób miało podobne pomysły, ale - o ile mi wiadomo - wszystkie one polegały na następstwie czasowym. Dane były udostępniane jakiemuś rdzeniowi z gwarancją, że nie zostaną zmienione np. przez 100 cykli. Problem w tym, że gdy zaraz po udostępnieniu inny rdzeń chciał zmienić te dane, to musiał czekać 100 cykli. Natomiast tutaj nie ma z tym problemu. Po prostu wystarczy zmienić ustawienie licznika. O ile wiem, nikt tego nie próbował wcześniej zrobić. To bardzo elegancki pomysł - cieszy się inżynier. Zaraz jednak dodaje, że projektanci układów scalonych są z natury konserwatystami. Niemal wszystkie masowo produkowane komercyjne systemy opierają się na protokołach korzystających z katalogów. Nie ruszamy tego, bo podczas zmiany implementacji bardzo łatwo o pomyłkę. Z drugiej jednak strony zaletą nowej koncepcji jest fakt, że jest to prostszy system. Dodatkowo mamy tutaj nie tylko przedstawiony jakiś pomysł, ale również szczegółowy opis dowodzący, że całość została prawidłowo zaprojektowana. To bardzo ważne dla projektantów układów scalonych.

« powrót do artykułu

[pogo 102]

Ciekawy jestem jak ma się zachować cały system gdy liczniki osiągną maksymalną możliwą do zapisania wartość. Jeśli licznik jest 32-bitowy, to limit pojawi się już przy trochę ponad 4mld. Ciekawe ile czasu współczesny procesor potrzebuje na osiągnięcie takiej wartości? Żeby nie było jak z tymi samolotami, co potrzebowały restartu komputera co kilka dni, bo na serwerach może być z tym problem.

[darekp 80]

Ciekawy jestem jak ma się zachować cały system gdy liczniki osiągną maksymalną możliwą do zapisania wartość

 

Raz na 4 miliardy to można nawet resetować te liczniki do wartości początkowej i rozsyłać najbardziej aktualną wersję cache'a do kopii lokalnych. To pewnie nie będzie miało żadnego wpływu na wydajność (w końcu raz na x miliardów). Oczywiście, gdy rdzeni jest niedużo, powiedzmy kilkadziesiąt. A jeśli jest więcej (dajmy na to miliony), to cóż, trzeba by wydłużyć licznik chyba.

Edytowane 11 września 2015 przez darekp

[pogo 102]

Oby tylko o ty nie zapomnieli, bo gdy przyjdą setki rdzeni to i 64-bitowy licznik (limit na ok 18,4 * 10^30) może się skończyć nim dojdzie do restartu maszyny.

 

Ciekawe ile operacji zapisu i odczytu z cache wykonują obecnie procesory w ciągu sekundy i ile realnie czasu zająłby reset liczników.