CPU-Speicherhierarchie: Latenzzeiten und Optimierung

# Speicherhierarchie in modernen Prozessoren: Von Registern bis DRAM

In modernen Systemen kosten Cache-Verfehlungen 100–200 Zyklen, während Treffer 1–4 Zyklen benötigen. Dies bestimmt die Code-Leistung. Betrachten Sie einen realen Fall: Optimierung eines Netzwerkschnittstellen-Treibers auf RISC-V bei 1 GHz. Erwartete Paketverarbeitung — 2 Millionen/s bei 500 Anweisungen pro Paket (500 ns). Tatsächlich erreicht: 200 Tausend/s.

Profiling ergab:

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

500 Tausend Anweisungen erfordern bei IPC=1 500 Tausend Zyklen, aber 5 Millionen wurden verbraucht. Der Unterschied — 45 Tausend Verfehlungen × 100 Zyklen = 4,5 Millionen Zyklen. Berechnungen nahmen 10 %, Wartezeit auf Speicher — 90 %.

Struktur der Speicherhierarchie

Der Speicher ist als Hierarchie organisiert, mit abnehmender Geschwindigkeit und zunehmender Größe:

| Stufe | Typ | Latenz | Größe |

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

| Register | 32 Register | 1 Zyklus | ~128 B |

| L1 Cache | Instruction/Data | 3–4 Zyklen | 32–64 KB |

| L2 Cache | Unified | 12–15 Zyklen | 256–512 KB |

| L3 Cache | Shared | 40–50 Zyklen | 2–32 MB |

| DRAM | Main | 100–200 Zyklen | GB–TB |

Wichtige Eigenschaften:

• Geschwindigkeit sinkt von 1 auf 200 Zyklen.
• Größe wächst von 128 B auf TB.
• DRAM ist 100–200-mal langsamer als L1.

In Mikrocontrollern (RISC-V RV32IMC, 100 MHz) ist die Hierarchie vereinfacht:

| Stufe | Typ | Latenz | Größe |

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

| Register | 32 Register | 1 Zyklus | 128 B |

| I-cache L1 | Instructions | 1 Zyklus | 16 KB |

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

| Flash | Code | ~10 Zyklen | 128 KB–1 MB |

| DRAM | Data | 50–100 Zyklen | 8–64 MB |

Unterschiede: kleine Caches, kein L2/L3, Flash statt DRAM für Code, begrenzte Größe.

Cache-Zeilen und Datenzugriff

Caches arbeiten mit 64-Byte-Blöcken. Der Zugriff auf 1 Byte lädt die gesamte Zeile.

Beispielzugriff auf int:

int x = array[0];  // 4 bytes at 0x1000
// Loads 64 bytes: 0x1000–0x103F (16 ints)

Sequentieller Zugriff ist effizient:

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

Zufälliger Zugriff — nicht:

for (int i = 0; i < 16; i++) {
    sum += array[random_index[i]];  // Many misses
}

Cache-Organisation: Sets und Ways

Der Cache ist in Sets und Ways unterteilt. Direkt gemappt:

Address bits: [Tag | Index | Offset]

Für 32 KB, 64 B/Zeile: 512 Zeilen, 9-Bit-Index, 6-Bit-Offset, 17-Bit-Tag (32-Bit-Adresse).

Konflikte: Arrays a[1024] (0x10000) und b[1024] (0x18000) werden auf dieselben Sets gemappt.

Set-assoziativ (N-Way): Ein Set enthält N Zeilen, reduziert Konflikte.

Typische Parameter:

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

Eingebettet: direkt oder 2-Way, hohe Konfliktwahrscheinlichkeit.

Zugriffs-Lokalität

Räumlich: benachbarte Adressen.

Gut:

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

Schlecht:

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

Zeitlich: wiederholter Zugriff.

Gut:

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

Schlecht:

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

Optimaler Code (Matrixmultiplikation):

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 und seine Einschränkungen

Der Prefetcher lädt Daten basierend auf Mustern vorab.

• Sequentiell: für for(i) sum += array[i];
• Stride: für sum += array[i*2];

Einschränkungen:

• Funktioniert nicht bei zufälligen Zugriffen.
• Begrenzt auf 10–20 Zeilen.
• Täuschbar durch Array-Verflechtung.

In Mikrocontrollern — einfach oder abwesend.

Bandbreite und Multi-Core

DDR4-3200: 25.6 GB/s/Kanal, Dual-Channel — 51.2 GB/s. L1: ~1000 GB/s.

Eingebettet: SRAM 1–4 GB/s, DRAM 100–500 MB/s. Arbeitsmenge in SRAM halten.

MESI-Protokoll (x86/ARM):

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

Falsches Teilen:

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

Lösung:

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

RISC-V: schwaches Speichermodell, Fence verwenden:

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

Atomare Operationen: lr.w/sc.w.

Was ist wichtig

• Cache-Verfehlungen dominieren: 90 % Zeit auf Warten.
• 64-B-Zeilen: sequentieller Zugriff gibt 15 kostenlose Treffer.
• Lokalität (räumlich/zeitlich) — Schlüssel zur Optimierung.
• Eingebettete Systeme: vereinfachte Hierarchie, kein Prefetcher.
• MESI und Padding verhindern Ping-Pong im Multi-Core.

— Editorial Team