Pamięć i pamięć podręczna
Literatura
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.

TematDawniej (slajdy z 2014)Dziś (2024-2026)
zegar procesora3-4 GHz4-6 GHz w trybie turbo. Wzrost zatrzymał się około 2005 r., przyrost mocy daje liczba rdzeni i szerokość wykonania
rdzenie1-48-24 i więcej, często hybrydowe (rdzenie wydajne P i energooszczędne E)
pamięć głównaDDR3, DDR4DDR5 (4800-8000+ MT/s), LPDDR5X w laptopach, pamięć scalona w jednym opakowaniu z procesorem (Apple), HBM w akceleratorach
pamięć podręcznaL1 32 KB, L2 256 KB, L3 kilka MBL1 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ęciw układzie zewnętrznym (northbridge)w procesorze. Procesory z kilku układów (chiplety)
adresy32 bity, 4 GB48 bitów wirtualnych (57 w 5-poziomowym stronicowaniu), do 52 bitów fizycznych
dyskHDD, msSSD NVMe (PCIe 4/5), dziesiątki µs. Pamięć nieulotna Optane została wycofana w 2022 r.
połączeniaAGP, PCIPCIe 5.0, CXL (rozszerzanie pamięci przez PCIe), Infinity Fabric, interkonekty chipletów
problemprocesor 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:

Architektura von Neumanna

Magistrala systemowa

Magistrala systemowa łączy poszczególne składniki maszyny VNA. Główne magistrale CPU:

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
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
Zapis do pamięci
Odczyt
Odczyt z pamięci

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?

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.

Little endian

Big endian: najstarszy bajt pod najniższym adresem.

Big endian

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

Konwersja kolejności bajtów

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).

Sygnał zegarowy

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);
}
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.

Zapis i odczyt z pamięci wykonywany w jednym cyklu zegara procesora (uproszczony model dla pamięci szybkiej jak procesor):

Odczyt i zapis w jednym cyklu zegara

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.

Stan oczekiwania

Obecnie procesor nie "stoi" na jednym żądaniu. Stosuje kilka technik ukrywania opóźnień:

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
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):

Pamięć podręczna L1 i L2

Współczesne pamięci podręczne: poziomy L1, L2, L3
PoziomTypowy rozmiarOpóźnienieUwagi
L1 (dane i instrukcje osobno)32-64 KB na rdzeńokoło 4-5 cykliprywatna dla rdzenia, 8-12-drożna
L20,25-3 MB na rdzeńokoło 12-16 cykliprywatna dla rdzenia (w niektórych układach współdzielona przez grupę rdzeni)
L3 (LLC, last level cache)8-96 MB i więcej, wspólnaokoło 40-70 cykliwspółdzielona przez wszystkie rdzenie (lub grupę). Często victim cache: zawiera dane wypchnięte z L2
DRAM16-128 GB60-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):

Dostęp procesora do pamięci: tryby adresowania
        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

Hierarchia pamięci: rozmiary i opóźnienia

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ęć.

Ile to trwa: skala opóźnień
OperacjaCzas (rząd wielkości)Cykle przy 5 GHzGdyby 1 cykl = 1 s
instrukcja na rejestrach0,2 ns11 s
odczyt z L11 ns4-55 s
odczyt z L23 ns1415 s
odczyt z L310-15 ns50-701 minuta
odczyt z DRAM80 ns4007 minut
odczyt z SSD NVMe10-100 µs50 tys. - 500 tys.14 godzin - 6 dni
odczyt z dysku HDD5-10 ms25-50 mln10 miesięcy - 1,6 roku
pakiet w sieci lokalnej100 µs - 1 ms0,5-5 mln6 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
// 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

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
Pamięć w pełni powiązana
Pamięć powiązana n-krotnie
Jak adres trafia do pamięci podręcznej - przykład współczesnego L1

L1 dla danych: 32 KB, 8-drożna, wiersz 64 B.

Odwzorowanie adresu na zbiór w L1

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         |
Polityka zapisu i spójność pamięci podręcznych
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)
Bezpieczeństwo a pamięć podręczna: Spectre i Meltdown
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
Podsumowanie: zasady dla programisty
  1. Pamięć to najwolniejszy element. Liczy się nie liczba instrukcji, lecz liczba chybień w pamięci podręcznej.
  2. Przeglądaj dane sekwencyjnie i po kolei, a nie losowo i z dużymi skokami.
  3. 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.
  4. Zadbaj o wyrównanie, a dane modyfikowane przez różne wątki trzymaj w osobnych wierszach.
  5. Pracuj na fragmentach mieszczących się w L1/L2 (blocking, tiling), np. mnożenie macierzy blokami.
  6. Duże zbiory danych: strony duże, NUMA (alokuj i przetwarzaj dane w tym samym węźle), unikaj kopiowania.
  7. Mierz (perf, valgrind --tool=cachegrind), zamiast zgadywać.
Ćwiczenia
  1. 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.
  2. Uruchom latency.cpp, naszkicuj wykres opóźnienia od rozmiaru tablicy i odczytaj z niego rozmiary L1, L2 i L3. Porównaj z lscpu.
  3. Uruchom falsesharing.cpp dla różnych par procesorów logicznych. Dlaczego dla dwóch procesorów logicznych tego samego rdzenia nie ma różnicy?
  4. 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?
  5. Zmodyfikuj latency.cpp tak, aby przeglądał tablicę kolejno (bez losowania). Jaki jest czas odczytu dla DRAM? Dlaczego jest mniejszy?
  6. 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