Pamięć i pamięć podręczna
Literatura
- Randall Hyde, Zrozumieć komputer. Profesjonalne programowanie, część 1, Helion, Gliwice 2005,
rozdziały 6 (Organizacja pamięci i dostęp do niej) i 11 (Architektura pamięci i jej organizacja).
Na tej książce oparte są oryginalne slajdy: ASI5.pdf (2014).
- Ulrich Drepper, What Every Programmer Should Know About Memory (2007) - wciąż najlepsze wprowadzenie do cache i DRAM.
- Hennessy, Patterson, Computer Architecture: A Quantitative Approach - rozdział o hierarchii pamięci.
- Agner Fog, The microarchitecture of Intel, AMD and VIA CPUs - dokładne dane o cache i opóźnieniach konkretnych procesorów.
- Dokumentacja producentów: Intel 64 and IA-32 Architectures Optimization Reference Manual, AMD Software Optimization Guide.
- Strony z pomiarami: Chips and Cheese, uops.info, WikiChip.
Co się zmieniło od czasu pierwszej wersji tego wykładu
Zasady (hierarchia, lokalność, stronicowanie) pozostały te same. Zmieniły się liczby i szczegóły.
| zegar procesora | 3-4 GHz | 4-6 GHz w trybie turbo. Wzrost zatrzymał się około 2005 r., przyrost mocy daje liczba rdzeni i szerokość wykonania |
| rdzenie | 1-4 | 8-24 i więcej, często hybrydowe (rdzenie wydajne P i energooszczędne E) |
| pamięć główna | DDR3, DDR4 | DDR5 (4800-8000+ MT/s), LPDDR5X w laptopach, pamięć scalona w jednym opakowaniu z procesorem (Apple), HBM w akceleratorach |
| pamięć podręczna | L1 32 KB, L2 256 KB, L3 kilka MB | L1 32-64 KB, L2 1-3 MB na rdzeń, L3 32-96 MB i więcej (także układana warstwami: 3D V-Cache) |
| kontroler pamięci | w układzie zewnętrznym (northbridge) | w procesorze. Procesory z kilku układów (chiplety) |
| adresy | 32 bity, 4 GB | 48 bitów wirtualnych (57 w 5-poziomowym stronicowaniu), do 52 bitów fizycznych |
| dysk | HDD, ms | SSD NVMe (PCIe 4/5), dziesiątki µs. Pamięć nieulotna Optane została wycofana w 2022 r. |
| połączenia | AGP, PCI | PCIe 5.0, CXL (rozszerzanie pamięci przez PCIe), Infinity Fabric, interkonekty chipletów |
| problem | procesor czeka na pamięć | ten sam, ale gorszy: DRAM to setki cykli. Dochodzą bezpieczeństwo (Spectre/Meltdown) i spójność pamięci podręcznych wielu rdzeni |
Konkretne liczby w tym wykładzie to rzędy wielkości dla typowych komputerów PC.
Dokładne wartości zależą od modelu, więc zawsze warto zmierzyć własny sprzęt (patrz ostatnie slajdy).
Podstawowe elementy systemu komputerowego
Podstawową architekturą komputera pozostaje architektura von Neumanna (VNA, von Neumann architecture):
program i dane leżą w tej samej pamięci. Obowiązuje ona także w rodzinie komputerów 80x86.
Podstawowe elementy architektury VNA:
- jednostka centralna (procesor, CPU),
- pamięć,
- urządzenia wejścia-wyjścia.

- Od strony programisty wciąż wygląda to tak, ale wewnątrz procesora pamięć podręczna pierwszego poziomu jest rozdzielona
na osobną pamięć instrukcji (L1I) i danych (L1D), jak w architekturze Harvardzkiej (tzw. zmodyfikowana architektura Harvardzka).
- Kontroler pamięci, a często także układ graficzny i kontroler PCIe, są zintegrowane w jednym układzie z procesorem (SoC, APU).
Magistrala systemowa
Magistrala systemowa łączy poszczególne składniki maszyny VNA. Główne magistrale CPU:
- magistrala danych - przeznaczona do wymiany danych między składnikami systemu. Kanał pamięci ma 64 bity (8 bajtów),
a dane przesyła się w paczkach (burst) po 64 bajty, czyli tyle, ile wynosi wiersz pamięci podręcznej,
- magistrala adresowa - przeznaczona do przesyłania adresów danych umieszczonych w pamięci.
Jedna linia przenosi jeden bit. Pierwsze procesory miały 20 linii adresowych, co dawało 1 MB pamięci (220).
Dziś architektura x86-64 przewiduje do 52 bitów adresu fizycznego (4 PB), a implementacje mają zwykle 39-52 bity.
Ograniczeniem jest raczej to, ile pamięci da się zamontować (typowo 16-128 GB w PC, terabajty w serwerach),
- magistrala sterująca - sygnały odczytu i zapisu, gotowości, przerwań itp.
Dziś pamięć jest podłączona do procesora bezpośrednio, przez kontroler pamięci wbudowany w procesor,
a nie przez układ zewnętrzny (FSB, northbridge) jak dawniej. Do urządzeń prowadzą szybkie łącza szeregowe (PCIe).
Przepustowość pamięci
Przepustowość = szerokość kanału x liczba transferów na sekundę.
DDR4-3200: 3200 MT/s x 8 B = 25,6 GB/s na kanał 64-bitowy
DDR5-6400: 6400 MT/s x 8 B = 51,2 GB/s na moduł (kanał 64-bitowy)
PC z dwoma modułami DDR5-6400: 2 x 51,2 = ok. 102 GB/s (szczytowo)
PC z dwoma modułami DDR4-3200: 2 x 25,6 = ok. 51 GB/s
- MT/s to megatransfery na sekundę. Pamięć DDR (double data rate) przesyła dane na obu zboczach sygnału,
więc rzeczywista częstotliwość zegara jest dwa razy mniejsza, np. DDR5-6400 pracuje z zegarem 3200 MHz.
- Moduł DDR5 ma dwa niezależne 32-bitowe podkanały, co pozwala obsługiwać więcej żądań naraz. Ma też wbudowaną korekcję błędów w układach (on-die ECC).
- Laptopy i telefony używają LPDDR5/LPDDR5X (mniejsze zużycie energii), często lutowanej na płycie lub w jednym opakowaniu z procesorem.
Procesory Apple (seria M) mają pamięć zunifikowaną: procesor, GPU i inne układy współdzielą te same układy pamięci.
Wersje wyższe osiągają kilkaset GB/s.
- Karty graficzne używają GDDR6/GDDR7, a akceleratory obliczeniowe HBM: pamięć ułożona w stosach tuż obok procesora,
z interfejsem o szerokości 1024 bitów na stos. Pojedynczy stos HBM3E to ponad 1 TB/s.
- Przepustowość rośnie szybciej niż opóźnienie maleje: opóźnienie DRAM ( 60-100 ns) prawie się nie zmieniło od lat.
Fizyczna organizacja pamięci
Dla programisty pamięć jest nadal tablicą bajtów.
Pamiec: array[0..1048575] of byte; (* 1 MB *)
Pamiec[125] := 0; (* zapis do pamięci *)
CPU := Pamiec[125]; (* odczyt z pamięci *)
Zapis
 |
Odczyt
 |
Przy zapisie procesor wystawia na magistrali adresowej adres (np. 125), na magistrali danych wartość,
a na magistrali sterującej ustawia sygnał zapisu. Przy odczycie ustawia sygnał odczytu i odczytuje wartość z magistrali danych.
Pamięć jest jednak odczytywana porcjami (wierszami po 64 B). Odczyt jednego bajtu sprowadza do pamięci podręcznej cały wiersz.
Wynika z tego, że pojedynczy bajt "kosztuje" tyle samo, co 64 bajty leżące obok.
Dane wielobajtowe
Problem: w jaki sposób zapisać większe ilości danych niż jeden bajt?
- Bajt, słowo (2 bajty) i podwójne słowo (4 bajty) zajmują kolejne komórki pamięci. Adresem danej jest adres jej pierwszego bajtu.
- Przykład (procesory 80x86): bajt pod adresem 186, słowo pod adresem 188 (bajty 188 i 189),
podwójne słowo pod adresem 192 (bajty 192, 193, 194, 195).
- W 64 bitach dochodzi poczwórne słowo (QWORD, 8 bajtów), a w SSE/AVX wektory 16, 32 i 64 bajty.
adres zawartość
195 bajt 3 podwójnego słowa
194 bajt 2
193 bajt 1
192 bajt 0 <- podwójne słowo pod adresem 192
191
190
189 bajt 1 słowa
188 bajt 0 <- słowo pod adresem 188
187
186 bajt <- bajt pod adresem 186
section .data
align 4
liczba dd 1234 ; adres podzielny przez 4
align 16
wektor dd 1.0, 2.0, 3.0, 4.0 ; wymagane przez movaps
Dane wyrównane do swojego rozmiaru (adres podzielny przez 4 dla int, 8 dla double) nie przekraczają granicy wiersza
pamięci podręcznej. Dane niewyrównane mogą wymagać dwóch dostępów, a instrukcje wektorowe z wyrównaniem (movaps, vmovaps)
zgłaszają wyjątek. W C++ służy do tego alignas.
Kolejność bajtów: little endian i big endian
Little endian (procesory Intel i AMD x86): najmłodszy bajt pod najniższym adresem.

Big endian: najstarszy bajt pod najniższym adresem.

Konwersja między little endian a big endian polega na odwróceniu kolejności bajtów obiektu (lustrzane odbicie).

- Dziś niemal wszystkie procesory ogólnego przeznaczenia pracują jako little endian: x86-64, ARM (w praktyce zawsze w telefonach, komputerach Apple, serwerach), RISC-V.
Dawne komputery Apple z procesorami PowerPC były big endian.
- Big endian to wciąż kolejność sieciowa (nagłówki IP, TCP, UDP), niektóre formaty plików oraz architektura IBM z/Architecture.
Dlatego w programach sieciowych stosuje się
htonl, ntohl, a w nowszym C++ std::byteswap (C++23).
section .data
liczba dd 0x12345678 ; w pamięci: 78 56 34 12 (little endian)
section .text
mov eax, [liczba] ; EAX = 0x12345678
mov bl, [liczba] ; BL = 0x78 (najmłodszy bajt pod najniższym adresem)
bswap eax ; EAX = 0x78563412 - zamiana kolejności bajtów
movbe ecx, [liczba] ; wczytanie z odwróceniem bajtów (rozszerzenie MOVBE)
Zegar systemowy
Zegar systemowy to sygnał elektryczny pojawiający się na magistrali sterującej, który regularnie zmienia swój stan między zerem a jedynką.
Wszelkie działania procesora są zsynchronizowane z przełączeniami sygnału zegara.
Częstotliwość, z jaką zegar zmienia stany, to częstotliwość zegara systemowego,
a czas przełączenia z zera na jedynkę i z powrotem na zero to okres zegara (cykl zegara).
- Procesory z lat 2010-tych pracowały z zegarem 3-4 GHz (cykl około 0,3 ns).
- Dziś procesory biurkowe osiągają w trybie turbo do około 5-6 GHz (cykl około 0,17-0,2 ns),
laptopowe i serwerowe pracują wolniej. Częstotliwość zmienia się dynamicznie zależnie od obciążenia, temperatury i zużycia energii.
- Przy 5 GHz światło w próżni przebywa w jednym cyklu zaledwie 6 cm, a sygnał w układzie scalonym jeszcze mniej.
To jeden z powodów, dla których nie opłaca się dalej podnosić zegara.
- Kolejne generacje procesorów przyspieszają głównie dzięki większej liczbie rdzeni, szerszemu wykonywaniu
(kilka instrukcji na cykl) i większym pamięciom podręcznym.

Liczbę cykli licznika TSC zwraca instrukcja rdtsc (wynik w EDX:EAX). Pozwala to mierzyć czas w cyklach:
#include <x86intrin.h>
#include <cstdio>
int main() {
unsigned long long start = __rdtsc();
// ... mierzony fragment kodu ...
unsigned long long koniec = __rdtsc();
printf("%llu cykli\n", koniec - start);
}
- Licznik TSC tyka ze stałą częstotliwością, która nie musi być równa aktualnej częstotliwości rdzenia (turbo, oszczędzanie energii).
- Wykonywanie poza kolejnością zaburza pomiar, więc w dokładnych testach dodaje się
lfence lub cpuid.
- Liczniki sprzętowe:
perf stat -e cycles,instructions ./program.
Dostęp do pamięci a zegar systemowy
Czas dostępu do pamięci to liczba cykli upływających między żądaniem odczytu lub zapisu pamięci a zakończeniem tej operacji.
- Dawniej (Pentium 3 GHz, pamięć 500 MHz, dostęp około 2 ns) procesor czekał kilka cykli.
- Dziś dostęp do DRAM trwa zwykle 60-100 ns, a procesor ma w tym czasie cykl około 0,2 ns.
Daje to kilkaset cykli bezczynności na jeden odczyt, w czasie których można by wykonać ponad tysiąc instrukcji.
- Przyczyny: czas dotarcia sygnału do modułu i z powrotem, odczyt komórki DRAM, układy sterujące.
Opóźnienie fizyczne DRAM prawie nie maleje, mimo że przepustowość rośnie.
- To zjawisko nazywa się ścianą pamięci (memory wall): procesor jest o rzędy wielkości szybszy niż pamięć.
Zapis i odczyt z pamięci wykonywany w jednym cyklu zegara procesora (uproszczony model dla pamięci szybkiej jak procesor):

Stany oczekiwania i jak radzą sobie z nimi współczesne procesory
Stan oczekiwania to dodatkowy cykl zegara, który pozwala urządzeniu odpowiedzieć na żądanie procesora.
Obwody dekodujące ustawiały sygnał, aby dać pamięci potrzebny jej czas.

Obecnie procesor nie "stoi" na jednym żądaniu. Stosuje kilka technik ukrywania opóźnień:
- pamięć podręczna - większość odczytów kończy się w L1/L2/L3 (następne slajdy),
- wykonanie poza kolejnością (out-of-order) - gdy jedna instrukcja czeka na dane, procesor wykonuje następne niezależne instrukcje (okno kilkuset instrukcji),
- wiele równoległych żądań (memory-level parallelism) - rdzeń może mieć kilkanaście oczekujących chybień naraz (bufory MSHR/LFB),
- sprzętowe wstępne pobieranie (prefetching) - procesor wykrywa regularny wzorzec dostępów (np. kolejne adresy) i sprowadza dane wcześniej,
- wielowątkowość (SMT, Hyper-Threading) - gdy jeden wątek czeka, rdzeń wykonuje drugi,
- programista może sam podpowiedzieć:
prefetcht0, __builtin_prefetch.
Wniosek: dostęp sekwencyjny jest o rząd wielkości szybszy niż losowy, nawet jeśli liczba odczytów jest taka sama.
Pamięć podręczna
- Pamięć podręczna (bufor, cache) znajduje się pomiędzy procesorem a pamięcią główną.
- W przeciwieństwie do zwykłej pamięci poszczególne bajty bufora nie mają stałych adresów, lecz można im przypisywać różne adresy.
Dzięki temu procesor może przechowywać dane ostatnio wykorzystywane.
- Adresy, z których procesor w ogóle nie korzystał lub z których korzystał stosunkowo dawno, pozostają w powolnej pamięci głównej.
- Pamięć podręczna ogranicza problem stanów oczekiwania zwalniających procesor. Dziś zajmuje większość powierzchni układu scalonego procesora.
for i := 0 to 10 do
A[i] := 0; // wielokrotnie te same zmienne: i oraz tablica A[]
Pamięć podręczna jest niewidoczna dla programu: nie ma instrukcji "wczytaj do cache", cała obsługa jest w sprzęcie.
Widać ją tylko po czasie wykonania.
Dwupoziomowy system pamięci podręcznej L1 i L2 (dziś zwykle trzy poziomy):

Współczesne pamięci podręczne: poziomy L1, L2, L3
| L1 (dane i instrukcje osobno) | 32-64 KB na rdzeń | około 4-5 cykli | prywatna dla rdzenia, 8-12-drożna |
| L2 | 0,25-3 MB na rdzeń | około 12-16 cykli | prywatna dla rdzenia (w niektórych układach współdzielona przez grupę rdzeni) |
| L3 (LLC, last level cache) | 8-96 MB i więcej, wspólna | około 40-70 cykli | współdzielona przez wszystkie rdzenie (lub grupę). Często victim cache: zawiera dane wypchnięte z L2 |
| DRAM | 16-128 GB | 60-100 ns (300-500 cykli) | po L3 - dopiero tu sięga się do pamięci głównej |
Przykłady (dane producentów, mogą się różnić w zależności od wersji procesora):
- AMD Ryzen 9000 (Zen 5): L1D 48 KB, L2 1 MB na rdzeń, L3 32 MB na układ rdzeni (CCD).
Wersje X3D dodają stos 64 MB pamięci L3 ułożony nad układem (3D V-Cache), np. 9800X3D ma łącznie 96 MB L3.
- Intel Core Ultra 200S (Arrow Lake): do 36 MB L3, po 3 MB L2 na rdzeń wydajny.
Rdzenie energooszczędne mają L2 współdzieloną w czwórkach (po 4 MB).
- Apple M-seria: duże L2 współdzielone przez grupę rdzeni i wiersz pamięci podręcznej 128 B (zamiast 64 B).
- Wszystkie procesory x86 mają wiersz pamięci podręcznej 64 bajty. To najważniejsza liczba dla programisty: dane lokalne w obrębie 64 B są "za darmo".
- Opóźnienia zwykle podaje się w cyklach, bo zegar rdzenia się zmienia.
Dostęp procesora do pamięci: tryby adresowania
- Bezpośredni tryb adresowania - adres zmiennej w pamięci jest zakodowany jako część instrukcji maszynowej sięgającej do tej zmiennej.
- Pośredni tryb adresowania - rejestr przechowuje adres w pamięci. Metoda stosowana przy zmiennych wskaźnikowych.
- Tryb adresowania indeksowanego - instrukcja koduje zarówno offset (adresowanie bezpośrednie), jak i identyfikator rejestru.
Procesor wylicza sumę tych dwóch składników, tworząc adres efektywny. Metoda stosowana przy tablicach i strukturach.
- Skalowane indeksowane tryby adresowania - do adresowania indeksowanego dodana jest możliwość mnożenia rejestru przez stałą.
Metoda stosowana przy sięganiu do elementów tablic.
- Adresowanie względem RIP (tylko x86-64) - adres = RIP + przesunięcie 32-bitowe. Pozwala pisać kod niezależny od położenia (PIC),
dlatego jest domyślny w 64-bitowych programach (patrz wykład o PIC).
mov eax, [zmienna] ; bezpośrednie (w 32 bitach)
mov eax, [ebx] ; pośrednie (wskaźnik w EBX)
mov eax, [tab + ebx] ; indeksowane: offset + rejestr
mov eax, [tab + 4*ecx] ; skalowane: tab[ecx] dla elementów 4-bajtowych
mov eax, [ebx + 4*ecx + 8] ; ogólnie: baza + indeks * skala + przesunięcie
mov eax, [rel zmienna] ; względem RIP (64 bity)
lea rax, [rbx + 4*rcx + 8] ; LEA: tylko liczy adres efektywny, nie czyta pamięci
Hierarchia pamięci

Im wyżej w hierarchii, tym szybciej i drożej na bajt, ale mniejsza pojemność. Im niżej, tym tańsza, wolniejsza i większa pamięć.
- Do hierarchii należą też: pamięć dołączona przez NUMA lub CXL, pamięć GPU oraz pamięć wirtualna (plik wymiany, swap)
- patrz kolejny wykład (pamięć wirtualna).
- Pamięć Optane (nieulotna, między DRAM a SSD) została wycofana w 2022 r.
Ile to trwa: skala opóźnień
| instrukcja na rejestrach | 0,2 ns | 1 | 1 s |
| odczyt z L1 | 1 ns | 4-5 | 5 s |
| odczyt z L2 | 3 ns | 14 | 15 s |
| odczyt z L3 | 10-15 ns | 50-70 | 1 minuta |
| odczyt z DRAM | 80 ns | 400 | 7 minut |
| odczyt z SSD NVMe | 10-100 µs | 50 tys. - 500 tys. | 14 godzin - 6 dni |
| odczyt z dysku HDD | 5-10 ms | 25-50 mln | 10 miesięcy - 1,6 roku |
| pakiet w sieci lokalnej | 100 µs - 1 ms | 0,5-5 mln | 6 dni - 2 miesiące |
Przepustowość: L1 - setki GB/s na rdzeń, DRAM (dwa kanały DDR5) około 100 GB/s, SSD NVMe PCIe 4/5 x4 około 7-14 GB/s, HDD około 0,2 GB/s.
Kto nie zna tych liczb, ten pisze programy, które "wyglądają dobrze", a działają kilkadziesiąt razy wolniej niż mogłyby.
Jak działa hierarchia pamięci
- Celem hierarchii pamięci jest umożliwienie szybkiego dostępu do dużych ilości danych.
- Wykorzystuje ona zasady przestrzennej lokalności odwołań (po adresie x prawdopodobnie użyjemy adresów bliskich x)
oraz czasowej lokalności odwołań (dane niedawno użyte prawdopodobnie zostaną użyte ponownie).
Dane często używane przenosi się do szybszych podsystemów pamięci, a rzadko używane do wolniejszych.
- Procesor najczęściej korzysta z pamięci podręcznej L1. Jeżeli nie znajdzie tam szukanych danych (chybienie, cache miss),
przekazuje żądanie do L2, potem do L3, następnie do pamięci głównej, a na końcu do dysku (pamięć wirtualna).
Za obsługę pamięci wirtualnej odpowiada system operacyjny.
- Znalezienie danych to trafienie (cache hit). Średni czas dostępu = czas trafienia + współczynnik chybień x kara za chybienie.
Przy trafieniach w L1 równych 99% i karze 400 cykli średnio mamy 4 + 0,01 x 400 = 8 cykli, czyli dwa razy więcej niż sam L1.
// Lokalność przestrzenna: kolejne elementy leżą obok siebie - szybko
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
suma += a[i][j];
// Brak lokalności: skoki co n elementów - wiele chybień w pamięci podręcznej
for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
suma += a[i][j];
Porównanie czasów obu pętli: patrz przykład cache.cpp (Pokaż/ukryj kod)
.
Budowa pamięci podręcznej
- Pamięć podręczna jest podzielona na bloki zwane wierszami pamięci podręcznej.
Każdy wiersz zawiera ustaloną liczbę bajtów (dawniej 16 lub 32, obecnie 64, a w procesorach Apple 128).
- Wiersz o wielkości np. 64 bajtów zawiera 64 bajty z 64-bajtowego, wyrównanego zakresu pamięci głównej.
- Systemy wczytywania wiersza z pamięci głównej do pamięci podręcznej:
- pamięć odwzorowana bezpośrednio,
- pamięć w pełni powiązana,
- pamięć powiązana n-krotnie.
Przykład: L1 o pojemności 32 KB i wierszu 64 B składa się z 512 wierszy (32 KB / 64 B).
Wiersz jest najmniejszą porcją danych, jaka przenosi się między poziomami pamięci.
Pamięć odwzorowana bezpośrednio
- Blok pamięci głównej jest zawsze ładowany dokładnie do tego samego wiersza pamięci podręcznej.
- Przykład: pamięć 32 KB z wierszami 64 B ma 512 wierszy, więc 9 bitów adresu (bity 6-14) wybiera wiersz. Bity 0-5 to przesunięcie w wierszu, a pozostałe (15 i wyższe) tworzą znacznik, który porównuje się z zapamiętanym.
- Rozwiązanie szybkie i proste, ale dwa często używane obszary pamięci mogą wypierać się nawzajem, jeżeli trafią do tego samego wiersza
(tzw. konflikt, thrashing).
- Dziś w procesorach ogólnego przeznaczenia stosuje się je rzadko (np. w niektórych małych mikrokontrolerach).
Pamięć w pełni powiązana
- Sterownik pamięci podręcznej może umieścić blok bajtów w dowolnym jej wierszu.
- Dodatkowe obwody pozwalające zrealizować takie powiązanie są kosztowne i mogą spowalniać działanie całości,
dlatego w pamięciach L1, L2 i L3 nie stosuje się tej metody. Stosuje się ją w małych buforach, np. w niektórych poziomach TLB.
Pamięć powiązana n-krotnie
- Pamięć jest podzielona na zbiory wierszy. Procesor wybiera używany zbiór na podstawie wybranych bitów adresu, jak w odwzorowaniu bezpośrednim.
- W każdym zbiorze znajduje się n wierszy. Sterownik pamięci podręcznej wykorzystuje algorytm w pełni powiązanego odwzorowania,
aby wybrać jeden z n wierszy (zwykle według przybliżonej reguły LRU, wypieranie najdawniej używanego).
- Przykład: L1 32 KB, 8-drożna, wiersz 64 B ma 512 / 8 = 64 zbiory, więc 6 bitów adresu (bity 6-11) wybiera zbiór (następny slajd).
- Jest to kompromis stosowany w praktyce we wszystkich współczesnych procesorach. Liczba n (drożność) wynosi zwykle 8-16
(L1: 8-12, L2: 8-16, L3: 12-20).
Jak adres trafia do pamięci podręcznej - przykład współczesnego L1
L1 dla danych: 32 KB, 8-drożna, wiersz 64 B.

liczba wierszy = 32 KB / 64 B = 512
liczba zbiorów = 512 / 8 drożność = 64
adres: | znacznik (tag) | indeks zbioru | przesunięcie w wierszu |
bity: | 47 ... 12 | 11 ... 6 | 5 ... 0 |
szerokość:| reszta | 6 bitów | 6 bitów |
- Bity 0-5 wskazują bajt w wierszu (64 = 26), bity 6-11 wybierają jeden z 64 zbiorów,
a pozostałe bity są zapisywane jako znacznik i porównywane z znacznikami wszystkich 8 wierszy w zbiorze.
- Adresy różniące się o wielokrotność 4096 B (
64 zbiory x 64 B) trafiają do tego samego zbioru.
Jeżeli program używa więcej niż 8 takich adresów naraz (np. kolumna tablicy o szerokości 4096 B), dochodzi do konfliktów,
mimo że cache jest prawie pusty.
- Indeks (bity 6-11) mieści się w granicach strony 4 KB (bity 0-11), więc L1 można przeszukiwać równolegle z tłumaczeniem adresu
(VIPT). Stąd ograniczenie: rozmiar L1 = liczba dróg x 4 KB (32 KB = 8 x 4 KB, 48 KB = 12 x 4 KB).
Polityka zapisu i spójność pamięci podręcznych
- Zapis: write-back - zmieniony wiersz jest oznaczany jako brudny (dirty) i zapisywany do pamięci dopiero przy wypchnięciu
(stosowany w pamięciach podręcznych CPU), w odróżnieniu od write-through (zapis natychmiast do niższego poziomu).
- Chybienie przy zapisie: write-allocate - najpierw wiersz jest sprowadzany do cache, potem modyfikowany.
Dlatego zapis do nowej pamięci też "czyta" ją z DRAM. Instrukcje
movnt* (non-temporal) omijają cache.
- Każdy rdzeń ma własną L1 i L2, więc ten sam wiersz pamięci może istnieć w kilku kopiach.
Sprzęt utrzymuje ich spójność protokołem typu MESI (Modified, Exclusive, Shared, Invalid):
gdy jeden rdzeń zapisuje do wiersza, kopie w pozostałych rdzeniach są unieważniane.
- Spójność działa na poziomie całych wierszy (64 B), a nie pojedynczych zmiennych. Prowadzi to do zjawiska fałszywego współdzielenia (false sharing) na następnym slajdzie.
Fałszywe współdzielenie (false sharing)
Dwa wątki zwiększają dwa różne liczniki, które leżą obok siebie w tym samym wierszu cache.
Wiersz "wędruje" między rdzeniami przy każdym zapisie.
struct Blisko { atomic<long> a; atomic<long> b; }; // ten sam wiersz
struct Daleko { alignas(64) atomic<long> a; alignas(64) atomic<long> b; }; // osobne wiersze
// wątek 1: a.fetch_add(1) 50 mln razy, wątek 2: b.fetch_add(1) 50 mln razy
Wynik na laptopie z procesorem Intel i9-8950HK (2018), wątki na dwóch różnych rdzeniach:
liczniki w jednym wierszu cache: 1.16 s
liczniki w osobnych wierszach: 0.22 s // ponad 5 razy szybciej
(te same wątki wymuszone na dwóch logicznych procesorach tego samego rdzenia:
0.48 s i 0.50 s - współdzielą L1, więc różnicy nie ma)
- Wynika stąd zasada: dane często modyfikowane przez różne wątki układaj w osobnych wierszach (
alignas(64), w C++17
std::hardware_destructive_interference_size).
- Kod: falsesharing.cpp (Pokaż/ukryj kod)
. Uruchom przez
taskset -c 0,2 ./falsesharing i porównaj z innymi parami procesorów
(lscpu -e pokazuje, które procesory logiczne należą do tego samego rdzenia).
Bezpieczeństwo a pamięć podręczna: Spectre i Meltdown
- Pamięć podręczna zmienia czas dostępu, a czas można zmierzyć (
rdtsc). Tworzy to kanał boczny:
program może wywnioskować, jakie dane były niedawno używane przez inny program, w tym przez jądro.
- W 2018 r. odkryto Meltdown i Spectre: procesor spekulatywnie wykonuje instrukcje (np. za nieprzewidzianym skokiem),
a ich skutki uboczne pozostają w pamięci podręcznej, nawet po wycofaniu wyniku.
- Skutki: system Linux od tego czasu izoluje tablice stron jądra (KPTI), kompilatory dodają zabezpieczenia (
-mretpoline),
a procesory mają sprzętowe poprawki. Często odbywa się to kosztem wydajności.
- Wniosek: wydajność i bezpieczeństwo pamięci podręcznej są powiązane, a informacje o aktualnych zabezpieczeniach są w
/sys/devices/system/cpu/vulnerabilities/.
Jak sprawdzić parametry własnego komputera
lscpu # model, rdzenie, rozmiary cache, NUMA
lscpu -e # procesory logiczne, rdzenie, cache
lscpu -C # tabela pamięci podręcznych (L1d, L1i, L2, L3)
getconf -a | grep -i CACHE # rozmiary i wiersze cache
cat /sys/devices/system/cpu/cpu0/cache/index0/{level,type,size,ways_of_associativity,coherency_line_size}
sudo dmidecode -t memory # moduły RAM: typ (DDR5), prędkość, liczba kanałów
numactl --hardware # węzły NUMA
lstopo # rysunek topologii (pakiet hwloc)
getconf PAGESIZE; grep -i huge /proc/meminfo # rozmiar strony, strony duże
perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./program
Przykład dla komputera, na którym powstał ten wykład (Intel i9-8950HK, 2018):
L1d: 32 KB, 8-drożna, 64 zbiory, wiersz 64 B (6 rdzeni)
L2: 256 KB, 4-drożna na rdzeń
L3: 12 MB, 16-drożna, wspólna
RAM: 32 GB, strona 4096 B, strony duże 2 MB
Pomiar opóźnienia pamięci
Prosty program mierzy czas odczytu w funkcji rozmiaru tablicy, odwołując się do niej w losowej kolejności i tak, aby każdy odczyt zależał od poprzedniego
(pointer chasing). Skoki czasu pokazują granice poziomów pamięci podręcznej.
p = tab[p * 8]; // adres następnego odczytu zależy od poprzedniego - brak równoległości i brak prefetch
Przykładowy wynik (i9-8950HK, jeden rdzeń):
rozmiar ns/odczyt
16 KB 2.3 <- L1 (32 KB)
32 KB 1.8
256 KB 5.5 <- L2 (256 KB)
1024 KB 11
4096 KB 12-17 <- L3 (12 MB)
8192 KB 16-29
32768 KB 70-90 <- DRAM
262144 KB 83
- Wynik zgadza się z rozmiarami z poprzedniego slajdu: widać schody na 32 KB, 256 KB i 12 MB.
Dostęp do pamięci głównej jest około 40 razy wolniejszy niż do L1.
- Kod: latency.cpp (Pokaż/ukryj kod)
. Uruchom na własnym komputerze (najlepiej
taskset -c 2 ./latency).
Pojedynczy pomiar bywa zaburzony przez inne procesy, więc powtórz go kilka razy.
Podsumowanie: zasady dla programisty
- Pamięć to najwolniejszy element. Liczy się nie liczba instrukcji, lecz liczba chybień w pamięci podręcznej.
- Przeglądaj dane sekwencyjnie i po kolei, a nie losowo i z dużymi skokami.
- Układaj dane zwarcie (tablica struktur lub struktura tablic,
std::vector zamiast std::list), tak aby użyteczne dane mieściły się w jak najmniejszej liczbie wierszy 64 B.
- Zadbaj o wyrównanie, a dane modyfikowane przez różne wątki trzymaj w osobnych wierszach.
- Pracuj na fragmentach mieszczących się w L1/L2 (blocking, tiling), np. mnożenie macierzy blokami.
- Duże zbiory danych: strony duże, NUMA (alokuj i przetwarzaj dane w tym samym węźle), unikaj kopiowania.
- Mierz (
perf, valgrind --tool=cachegrind), zamiast zgadywać.
Ćwiczenia
- Sprawdź za pomocą
lscpu i /sys/devices/system/cpu/cpu0/cache rozmiary, drożność i wiersz każdego poziomu pamięci podręcznej na swoim komputerze.
Oblicz liczbę zbiorów L1 oraz podaj, które bity adresu wybierają zbiór.
- Uruchom
latency.cpp, naszkicuj wykres opóźnienia od rozmiaru tablicy i odczytaj z niego rozmiary L1, L2 i L3. Porównaj z lscpu.
- Uruchom
falsesharing.cpp dla różnych par procesorów logicznych. Dlaczego dla dwóch procesorów logicznych tego samego rdzenia nie ma różnicy?
- Zmierz za pomocą
cache.cpp sumowanie macierzy wierszami i kolumnami dla rozmiarów 256, 1024, 4096. Przy którym rozmiarze różnica jest największa i dlaczego?
- Zmodyfikuj
latency.cpp tak, aby przeglądał tablicę kolejno (bez losowania). Jaki jest czas odczytu dla DRAM? Dlaczego jest mniejszy?
- Oblicz średni czas dostępu do pamięci, jeżeli trafienia w L1 wynoszą 95%, w L2 4% (czas 14 cykli), a w DRAM 1% (400 cykli), a czas L1 to 4 cykle.
Zadania laboratoryjne do tego wykładu: Laboratorium: pomiary pamięci.
Przykładowe programy
Tomasz Kapela, Kraków 2011-2020