Hierarchie paměti CPU: zpoždění a optimalizace

# Hierarchie paměti v moderních procesorech: od registrů po DRAM

V moderních systémech cache missy vyžadují 100–200 taktů, zatímco hity trvají 1–4 takty. To určuje výkon kódu. Podívejme se na reálný případ: optimalizace ovladače síťového rozhraní na RISC-V s frekvencí 1 GHz. Očekávané zpracování paketů — 2 mil./s při 500 instrukcích na paket (500 ns). Ve skutečnosti dosaženo 200 tis./s.

Profilování odhalilo:

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

500 tis. instrukcí vyžaduje 500 tis. taktů při IPC=1, ale spotřebováno 5 milionů. Rozdíl — 45 tis. missů × 100 taktů = 4,5 mil. taktů. Výpočty zabraly 10 %, čekání na paměť — 90 %.

Struktura hierarchie paměti

Paměť je organizována jako hierarchie s klesající rychlostí a rostoucím objemem:

| Úroveň | Typ | Zpoždění | Velikost |

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

| Registry | 32 registrů | 1 takt | ~128 B |

| Cache L1 | Instrukce/data | 3–4 takty | 32–64 KB |

| Cache L2 | Společný | 12–15 taktů | 256–512 KB |

| Cache L3 | Sdílený | 40–50 taktů | 2–32 MB |

| DRAM | Hlavní | 100–200 taktů | GB–TB |

Klíčové vlastnosti:

• Rychlost klesá z 1 na 200 taktů.
• Objem roste od 128 B po TB.
• DRAM je 100–200× pomalejší než L1.

V mikrokontrolérech (RISC-V RV32IMC, 100 MHz) je hierarchie zjednodušená:

| Úroveň | Typ | Zpoždění | Velikost |

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

| Registry | 32 registrů | 1 takt | 128 B |

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

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

| Flash | Kód | ~10 taktů | 128 KB–1 MB |

| DRAM | Data | 50–100 taktů | 8–64 MB |

Rozdíly: malé cache, absence L2/L3, flash místo DRAM, omezený objem.

Cache linky a přístup k datům

Cache fungují bloky po 64 bajtech. Přístup k 1 bajtu načte celou linku.

Příklad přístupu k int:

int x = array[0];  // 4 bajty na 0x1000
// Načte se 64 bajtů: 0x1000–0x103F (16 int)

Sekvenční přístup je efektivní:

for (int i = 0; i < 16; i++) {
    sum += array[i];  // 1 miss, 15 hitů
}

Náhodný — ne:

for (int i = 0; i < 16; i++) {
    sum += array[random_index[i]];  // Spousta missů
}

Organizace cache: sady a cesty

Cache je rozdělena na sady (set) a cesty (way). Přímé mapování:

Bity adresy: [Tag | Index | Offset]

Pro 32 KB, 64 B/linka: 512 linek, 9 bitů indexu, 6 bitů offsetu, 17 bitů tagu (32bitová adresa).

Konflikty: pole a[1024] (0x10000) a b[1024] (0x18000) mapují do stejných sad.

Sadu asociativní (N-cestný): sada obsahuje N linek, snižuje konflikty.

Typické parametry:

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

V embedded: přímé nebo 2-cestné, vysoká pravděpodobnost konfliktů.

Lokalita přístupu

Prostorová: sousední adresy.

Dobře:

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

Špatně:

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

Časová: opakovaný přístup.

Dobře:

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

Špatně:

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

Optimální kód (měření maticí):

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 a jeho omezení

Prefetcher předem načítá data podle vzorů.

• Sekvenční: pro for(i) sum += array[i];
• Stride: pro sum += array[i*2];

Omezení:

• Nefunguje na náhodných přístupech.
• Omezeno na 10–20 linek.
• Zklamává se střídáním polí.

V mikrokontrolérech — jednoduchý nebo chybí.

Propustnost a vícejádrovost

DDR4-3200: 25,6 GB/s/kanál, dvoukanálový — 51,2 GB/s. L1: ~1000 GB/s.

Embedded: SRAM 1–4 GB/s, DRAM 100–500 MB/s. Držte pracovní sadu v SRAM.

MESI protokol (x86/ARM):

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

Falešné sdílení:

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

Řešení:

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

RISC-V: slabý model, použijte fence:

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

Atomární: lr.w/sc.w.

Co je důležité

• Cache missy dominují: 90 % času na čekání.
• Linky 64 B: sekvenční přístup dává 15 zdarma hitů.
• Lokalita (prostorová/časová) — klíč k optimalizaci.
• Embedded systémy: zjednodušená hierarchie, žádný prefetcher.
• MESI a padding zabraňují ping-pongu v multi-core.

— Editorial Team