Hierarchia pamięci CPU: opóźnienia i optymalizacja

# Hierarchia pamięci w nowoczesnych procesorach: od rejestrów do DRAM

W nowoczesnych systemach chybienia kache'a kosztują 100–200 taktów, podczas gdy trafienia zajmują 1–4 takty. To determinuje wydajność kodu. Rozważmy realny przypadek: optymalizacja sterownika interfejsu sieciowego na RISC-V o częstotliwości 1 GHz. Oczekiwana obróbka pakietów — 2 mln/s przy 500 instrukcjach na pakiet (500 ns). Faktycznie osiągnięto 200 tys./s.

Profilowanie ujawniło:

$ perf stat -e cycles,instructions,cache-misses ./driver_test
  Performance counter stats:
    5,000,000 cycles
      500,000 instructions
       45,000 cache-misses

500 tys. instrukcji wymaga 500 tys. taktów przy IPC=1, ale zużyto 5 mln. Różnica — 45 tys. chybień × 100 taktów = 4,5 mln taktów. Obliczenia zajęły 10%, oczekiwanie na pamięć — 90%.

Struktura hierarchii pamięci

Pamięć jest zorganizowana jako hierarchia o malejącej prędkości i rosnącym rozmiarze:

| Poziom | Typ | Opóźnienie | Rozmiar |

|---------|-----|----------|--------|

| Rejestry | 32 rejestry | 1 takt | ~128 B |

| Cache L1 | Instrukcje/dane | 3–4 takty | 32–64 KB |

| Cache L2 | Jednolity | 12–15 taktów | 256–512 KB |

| Cache L3 | Wspólny | 40–50 taktów | 2–32 MB |

| DRAM | Główna | 100–200 taktów | GB–TB |

Kluczowe właściwości:

• Prędkość spada z 1 do 200 taktów.
• Rozmiar rośnie od 128 B do TB.
• DRAM jest 100–200 razy wolniejsze od L1.

W mikrokontrolerach (RISC-V RV32IMC, 100 MHz) hierarchia jest uproszczona:

| Poziom | Typ | Opóźnienie | Rozmiar |

|---------|-----|----------|--------|

| Rejestry | 32 rejestry | 1 takt | 128 B |

| I-cache L1 | Instrukcje | 1 takt | 16 KB |

| D-cache L1/SRAM | Dane | 1–2 takty | 8–32 KB |

| Flash | Kod | ~10 taktów | 128 KB–1 MB |

| DRAM | Dane | 50–100 taktów | 8–64 MB |

Różnice: małe kache, brak L2/L3, flash zamiast DRAM, ograniczony rozmiar.

Linie kache i dostęp do danych

Kache działają blokami po 64 bajty. Dostęp do 1 bajtu ładuje całą linię.

Przykład dostępu do int:

int x = array[0];  // 4 bajty po 0x1000
// Ładuje się 64 bajty: 0x1000–0x103F (16 int)

Sekwencyjny dostęp jest efektywny:

for (int i = 0; i < 16; i++) {
    sum += array[i];  // 1 chybienie, 15 trafień
}

Proizwolny — nie:

for (int i = 0; i < 16; i++) {
    sum += array[random_index[i]];  // Wiele chybień
}

Organizacja kache: zestawy i drogi

Cache dzieli się na zestawy (set) i drogi (way). Bezpośrednie mapowanie:

Bity adresu: [Tag | Indeks | Offset]

Dla 32 KB, 64 B/linia: 512 linii, 9 bitów indeksu, 6 bitów offsetu, 17 bitów tagu (32-bitowy adres).

Konflikty: tablice a[1024] (0x10000) i b[1024] (0x18000) mapują się do tych samych zestawów.

Zestawowo-asocjacyjny (N-drogowy): zestaw zawiera N linii, zmniejsza konflikty.

Typowe parametry:

• L1: 8-drogowy, 32–64 KB.
• L2: 8–16-drogowy, 256–512 KB.
• L3: 16-drogowy, 2–32 MB.

Wbudowane: bezpośrednie lub 2-drogowe, wysoka szansa konfliktów.

Lokalność dostępu

Przestrzenna: sąsiednie adresy.

Dobrze:

for (int i = 0; i < n; i++) sum += array[i];

Źle:

for (int i = 0; i < n; i++) sum += array[random[i]];

Czasowa: powtarzalny dostęp.

Dobrze:

int temp = array[0];
for (int i = 0; i < 1000; i++) result += temp * i;

Źle:

for (int i = 0; i < 1000; i++) result += array[i % 10] * i;

Optymalny kod (mnożenie macierzowe):

for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];
        }
    }
}

Prefetcher i jego ograniczenia

Prefetcher wstępnie ładuje dane według wzorców.

• Sekwencyjny: dla for(i) sum += array[i];
• Stride'owy: dla sum += array[i*2];

Ograniczenia:

• Nie działa na losowych dostępach.
• Ograniczony do 10–20 linii.
• Zbijany przeplataniem tablic.

W mikrokontrolerach — prosty lub brak.

Przepustowość i wielordzeniowość

DDR4-3200: 25,6 GB/s/kanał, dwukanałowy — 51,2 GB/s. L1: ~1000 GB/s.

Wbudowane: SRAM 1–4 GB/s, DRAM 100–500 MB/s. Trzymajcie zbiór roboczy w SRAM.

Protokół MESI (x86/ARM):

• M: Modified.
• E: Exclusive.
• S: Shared.
• I: Invalid.

Fałszywe współdzielenie:

struct { int c0, c1; } shared;  // Ping-pong

Rozwiązanie:

struct { int c0; char pad[60]; int c1; } shared;

RISC-V: słaby model, używajcie fence:

sw a0, 0(a1)
fence w, w
sw a2, 0(a3)

Atomowe: lr.w/sc.w.

Co jest ważne

• Chybienia kache dominują: 90% czasu na oczekiwanie.
• Linie 64 B: sekwencyjny dostęp daje 15 darmowych trafień.
• Lokalność (przestrzenna/czasowa) — klucz do optymalizacji.
• Systemy wbudowane: uproszczona hierarchia, brak prefetchera.
• MESI i padding zapobiegają ping-pongowi w multi-core.

— Editorial Team