Jak działają linie pamięci podręcznej?

Rozumiem, że procesor przenosi dane do pamięci podręcznej za pośrednictwem linii pamięci podręcznej, które - na przykład w moim procesorze Atom - dostarczają jednorazowo około 64 bajtów, niezależnie od rozmiaru faktycznie odczytywanych danych.

Moje pytanie brzmi:

Wyobraź sobie, że musisz odczytać jeden bajt z pamięci, który 64 bajty zostanie przeniesiony do pamięci podręcznej?

Widzę dwie możliwości, że albo 64 bajty zaczynają się od najbliższej granicy 64 bajtów poniżej bajtu będącego przedmiotem zainteresowania, albo 64 bajty są rozmieszczone wokół bajtu w określony z góry sposób (na przykład połowa poniżej, połowa powyżej lub wszystko powyżej).

Który to jest?

Jeśli linia pamięci podręcznej zawierająca bajt lub słowo, które ładujesz, nie jest już obecna w pamięci podręcznej, twój procesor zażąda 64 bajtów, które zaczynają się od granicy linii pamięci podręcznej (największy adres poniżej tego, którego potrzebujesz, to wielokrotność 64) .

Nowoczesne moduły pamięci PC przesyłają 64 bity (8 bajtów) naraz, w serii ośmiu transferów , więc jedno polecenie wyzwala odczyt lub zapis pełnej linii pamięci podręcznej z pamięci. (Rozmiar transferu seryjnego DDR1 / 2/3/4 SDRAM można konfigurować do 64B; procesory wybiorą rozmiar transferu seryjnego, aby pasował do rozmiaru linii pamięci podręcznej, ale 64B jest powszechne)

Z reguły, jeśli procesor nie może przewidzieć dostępu do pamięci (i pobrać go z wyprzedzeniem), proces pobierania może zająć ~ 90 nanosekund lub ~ 250 cykli zegara (od CPU znającego adres do CPU odbierającego dane).

Natomiast trafienie w pamięci podręcznej L1 ma opóźnienie użycia obciążenia wynoszące 3 lub 4 cykle, a przeładowanie magazynu ma opóźnienie przekazywania magazynu wynoszące 4 lub 5 cykli na nowoczesnych procesorach x86. Podobnie jest w przypadku innych architektur.

Dalsza lektura: Co każdy programista powinien wiedzieć o pamięci Ulricha Dreppera . Porady dotyczące pobierania wstępnego oprogramowania są nieco przestarzałe: nowoczesne moduły pobierania wstępnego HW są inteligentniejsze, a hiperwątkowość jest znacznie lepsza niż w dniach P4 (więc wątek pobierania wstępnego jest zwykle marnotrawstwem). Ponadtox86 tag wiki zawiera wiele linków wydajnościowych dla tej architektury.

Jeśli linie pamięci podręcznej mają szerokość 64 bajtów, to odpowiadają one blokom pamięci, które rozpoczynają się od adresów, które są podzielne przez 64. Najmniej znaczące 6 bitów dowolnego adresu to przesunięcie w linii pamięci podręcznej.

Zatem dla dowolnego bajtu wiersz pamięci podręcznej, który ma zostać pobrany, można znaleźć, usuwając najmniej znaczące sześć bitów adresu, co odpowiada zaokrągleniu w dół do najbliższego adresu, który jest podzielny przez 64.

Chociaż jest to wykonywane sprzętowo, możemy pokazać obliczenia przy użyciu pewnych referencyjnych definicji makr w języku C:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

Przede wszystkim dostęp do pamięci głównej jest bardzo drogi. Obecnie procesor 2GHz (najwolniejszy raz) ma taktyki (cykle) 2G na sekundę. CPU (obecnie wirtualny rdzeń) może pobierać wartość ze swoich rejestrów raz na takt. Ponieważ wirtualny rdzeń składa się z wielu jednostek przetwarzających (ALU - jednostka arytmetyczno-logiczna, FPU itp.), Może on faktycznie przetwarzać pewne instrukcje równolegle, jeśli to możliwe.

Dostęp do pamięci głównej kosztuje około 70ns do 100ns (DDR4 jest nieco szybszy). Tym razem po prostu wyszukuje pamięć podręczną L1, L2 i L3, a następnie trafia do pamięci (wyślij polecenie do kontrolera pamięci, który wysyła je do banków pamięci), poczekaj na odpowiedź i gotowe.

100ns oznacza około 200 kleszczy. Zasadniczo, jeśli program zawsze pomija pamięci podręczne, do których każdy uzyskuje dostęp do pamięci, procesor spędziłby około 99,5% swojego czasu (jeśli tylko czyta pamięć) bezczynnie, czekając na pamięć.

Aby przyspieszyć działanie, istnieją pamięci podręczne L1, L2, L3. Wykorzystują pamięć umieszczoną bezpośrednio na chipie i wykorzystują różnego rodzaju układy tranzystorowe do przechowywania danych bitów. Zajmuje to więcej miejsca, więcej energii i jest bardziej kosztowne niż pamięć główna, ponieważ procesor jest zwykle wytwarzany przy użyciu bardziej zaawansowanej technologii, a awaria produkcyjna w pamięci L1, L2, L3 może spowodować, że procesor stanie się bezwartościowy (wada), więc duże pamięci podręczne L1, L2, L3 zwiększają współczynnik błędów, co zmniejsza wydajność, co bezpośrednio zmniejsza zwrot z inwestycji. Istnieje więc ogromny kompromis, jeśli chodzi o dostępny rozmiar pamięci podręcznej.

(obecnie tworzy się więcej pamięci podręcznych L1, L2, L3, aby móc dezaktywować pewne części, aby zmniejszyć prawdopodobieństwo, że rzeczywistą wadą produkcyjną są obszary pamięci podręcznej, które renderują defekt procesora jako całości).

Aby dać wyobrażenie o czasie (źródło: koszty dostępu do pamięci podręcznych i pamięci )

• Pamięć podręczna L1: 1ns do 2ns (2-4 cykle)
• Pamięć podręczna L2: od 3ns do 5ns (6-10 cykli)
• Pamięć podręczna L3: 12ns do 20ns (24-40 cykli)
• RAM: 60ns (120 cykli)

Ponieważ mieszamy różne typy procesorów, są to tylko szacunki, ale dają dobre wyobrażenie o tym, co naprawdę się dzieje, gdy wartość pamięci jest pobierana i możemy mieć trafienie lub chybienie w określonej warstwie pamięci podręcznej.

Tak więc pamięć podręczna zasadniczo znacznie przyspiesza dostęp do pamięci (60 ns w porównaniu do 1 ns).

Pobieranie wartości, przechowywanie jej w pamięci podręcznej w celu ponownego odczytania jest dobre dla zmiennych, które są często używane, ale w przypadku operacji kopiowania pamięci byłoby nadal zbyt wolne, ponieważ po prostu czyta się wartość, zapisuje ją gdzieś i nigdy nie czyta wartości znowu ... brak trafień w pamięci podręcznej, śmiertelnie wolne (poza tym może się to zdarzyć równolegle, ponieważ mamy wykonanie poza kolejnością).

Ta kopia pamięci jest tak ważna, że ​​istnieją różne sposoby jej przyspieszenia. We wczesnych latach pamięć często była w stanie kopiować pamięć poza CPU. Był obsługiwany bezpośrednio przez kontroler pamięci, więc operacja kopiowania pamięci nie zanieczyszczała pamięci podręcznych.

Ale oprócz zwykłej kopii pamięci, dość powszechny był inny dostęp szeregowy do pamięci. Przykładem jest analiza szeregu informacji. Posiadanie tablicy liczb całkowitych i obliczanie sumy, średniej, średniej lub nawet prostsze znalezienie określonej wartości (filtr / wyszukiwanie) to kolejna bardzo ważna klasa algorytmów uruchamianych za każdym razem na dowolnym procesorze ogólnego przeznaczenia.

Zatem analizując wzorzec dostępu do pamięci, okazało się, że dane są bardzo często odczytywane sekwencyjnie. Istniało duże prawdopodobieństwo, że jeśli program odczyta wartość pod indeksem i, to program odczyta również wartość i + 1. To prawdopodobieństwo jest nieco większe niż prawdopodobieństwo, że ten sam program odczyta również wartość i + 2 i tak dalej.

Tak więc mając adres pamięci, dobrym pomysłem było (i nadal jest) czytanie z wyprzedzeniem i pobieranie dodatkowych wartości. To jest powód, dla którego istnieje tryb doładowania.

Dostęp do pamięci w trybie boost oznacza, że ​​adres jest wysyłany i wiele wartości jest wysyłanych sekwencyjnie. Każde dodatkowe wysłanie wartości zajmuje tylko około dodatkowych 10ns (lub nawet mniej).

Kolejnym problemem był adres. Wysłanie adresu wymaga czasu. Aby zaadresować dużą część pamięci, należy wysłać duże adresy. Na początku oznaczało to, że magistrala adresowa nie była wystarczająco duża, aby wysłać adres w jednym cyklu (tik) i potrzeba więcej niż jednego cyklu, aby wysłać adres, dodając więcej opóźnienia.

Na przykład wiersz pamięci podręcznej o wielkości 64 bajtów oznacza, że ​​pamięć jest podzielona na odrębne (nie nakładające się) bloki pamięci o rozmiarze 64 bajtów. 64 bajty oznaczają, że adres początkowy każdego bloku ma najniższe sześć bitów adresu, które zawsze są zerami. Zatem wysyłanie tych sześciu bitów zerowych za każdym razem nie jest potrzebne, zwiększając przestrzeń adresową 64 razy dla dowolnej liczby szerokości szyny adresowej (efekt powitalny).

Kolejnym problemem, który rozwiązuje linia pamięci podręcznej (poza czytaniem z wyprzedzeniem i zapisywaniem / zwalnianiem sześciu bitów na szynie adresowej) jest sposób organizacji pamięci podręcznej. Na przykład, jeśli pamięć podręczna byłaby podzielona na 8-bajtowe (64-bitowe) bloki (komórki), należy przechowywać adres komórki pamięci, dla której ta komórka pamięci podręcznej przechowuje wartość wraz z nią. Jeśli adres byłby również 64-bitowy, oznacza to, że połowa rozmiaru pamięci podręcznej jest zużywana przez adres, co powoduje 100% narzut.

Ponieważ linia pamięci podręcznej ma 64 bajty, a procesor może używać 64 bitów - 6 bitów = 58 bitów (nie ma potrzeby przechowywania zerowych bitów zbyt dobrze), oznacza to, że możemy buforować 64 bajty lub 512 bitów z narzutem 58 bitów (11% narzutu). W rzeczywistości przechowywane adresy są jeszcze mniejsze, ale istnieją informacje o statusie (takie jak linia pamięci podręcznej jest ważna i dokładna, brudna i musi zostać zapisana w pamięci RAM itp.).

Innym aspektem jest to, że mamy pamięć podręczną z ustawieniami asocjacji. Nie każda komórka pamięci podręcznej może przechowywać określony adres, ale tylko ich podzbiór. To sprawia, że ​​niezbędne przechowywane bity adresu są jeszcze mniejsze, umożliwia równoległy dostęp do pamięci podręcznej (dostęp do każdego podzbioru można uzyskać tylko raz, ale niezależnie od innych podzbiorów).

Jest to szczególnie ważne, jeśli chodzi o synchronizację dostępu do pamięci podręcznej / pamięci między różnymi wirtualnymi rdzeniami, ich niezależnymi wieloma jednostkami przetwarzającymi na rdzeń i wreszcie wieloma procesorami na jednej płycie głównej (na której znajdują się płyty zawierające aż 48 procesorów i więcej).

To jest w zasadzie obecny pomysł, dlaczego mamy linie pamięci podręcznej. Korzyści z czytania z wyprzedzeniem są bardzo duże, a najgorszy przypadek odczytu pojedynczego bajtu z linii pamięci podręcznej i nigdy ponownego odczytu reszty jest bardzo niewielki, ponieważ prawdopodobieństwo jest bardzo małe.

Rozmiar linii pamięci podręcznej (64) jest mądrze dobranym kompromisem między większymi wierszami pamięci podręcznej, co sprawia, że ​​jest mało prawdopodobne, aby ostatni jej bajt został odczytany również w najbliższej przyszłości, czas potrzebny do pobrania całej linii pamięci podręcznej z pamięci (i zapisywać ją z powrotem), a także narzut w organizacji pamięci podręcznej i równoległości dostępu do pamięci podręcznej i pamięci.

Procesory mogą mieć wielopoziomowe pamięci podręczne (L1, L2, L3), różniące się rozmiarem i szybkością.

Jednak, aby zrozumieć, co dokładnie trafia do każdej pamięci podręcznej, musisz przestudiować predyktor gałęzi używany przez ten konkretny procesor i jak zachowują się w stosunku do niego instrukcje / dane twojego programu.

Przeczytaj o predyktorze gałęzi , pamięci podręcznej procesora i zasadach wymiany .

To nie jest łatwe zadanie. Jeśli na koniec dnia wszystko, czego chcesz, to test wydajności, możesz użyć narzędzia takiego jak Cachegrind . Ponieważ jednak jest to symulacja, jej wynik może się w pewnym stopniu różnić.

Nie mogę powiedzieć na pewno, ponieważ każdy sprzęt jest inny, ale zwykle jest to „początek 64 bajtów w najbliższej granicy 64 bajtów poniżej”, ponieważ jest to bardzo szybka i prosta operacja dla procesora.