Cache-Lokalität: Warum die Lesereihenfolge zählt

Eine 8 × 8-Matrix aus int-Werten liegt Zeile für Zeile im Speicher. Zwischen ihr und dem Prozessor sitzt ein Cache mit acht Cachezeilen zu je 16 Byte. Summiere die Matrix zeilenweise oder spaltenweise und verfolge die Lesezugriffe Schritt für Schritt. Jede Zelle zeigt, welcher Cachezeile ihre Adresse zugeordnet ist: orange bei einem Fehlzugriff, grün bei einem Treffer. Hell markiert sind benachbarte Werte, die bei einem Fehlzugriff mitgeladen wurden.

Rechenbeispiel — Cache-Lokalität: Warum die Lesereihenfolge zählt

Lesezugriffe je Reihenfolge	64
Berührte 16-Byte-Blöcke	16
Maximal mögliche Treffer	48 von 64 (75,0 %)
Treffer beim zeilenweisen Lesen	48 von 64 (75,0 %)
Treffer beim spaltenweisen Lesen	0 von 64 (0,0 %)
Cachezeilen für Spalte 0	4 von 8

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Cache-Lokalität: Warum die Lesereihenfolge zählt

Ein Cache ist ein kleiner, schneller Speicher. Er hält Kopien von Daten aus dem Hauptspeicher in Cachezeilen. Jede Cachezeile enthält einen ausgerichteten Speicherblock von L Byte. Liegt der Block eines Lesezugriffs bereits im Cache, ist der Zugriff ein Treffer. Andernfalls ist er ein Fehlzugriff, und der gesamte Block wird geladen. In einem direkt abbildenden Cache mit S Cachezeilen ist für den Block, der die Adresse a enthält, nur eine Cachezeile vorgesehen: ⌊a / L⌋ mod S. Liest eine Schleife benachbarte Adressen nacheinander, kann sie jeden geladenen Block für mehrere Zugriffe nutzen. Das nennt man räumliche Lokalität.

Was die einzelnen Symbole bedeuten

L: die Größe einer Cachezeile in Byte: hier 16, bei den meisten Desktop- und Serverprozessoren 64
S: die Anzahl der Cachezeilen: hier 8

Setzt voraus: Wir betrachten einen anfangs leeren, direkt abbildenden Cache, int-Werte von 4 Byte und eine zeilenweise gespeicherte Matrix, wie in C üblich. Fortran speichert Matrizen spaltenweise; dort ist die andere Reihenfolge schneller. Gezählt werden nur die Lesezugriffe auf die Matrix. Reale Datencaches der ersten Ebene sind größer und satzassoziativ, typischerweise 8-fach: Ein Block kann in einer beliebigen der 8 Cachezeilen seines Satzes liegen. Das verhindert die meisten der hier gezeigten Konflikte, behebt aber keinen Platzmangel. Hardware-Prefetching, das die nächste Cachezeile schon vor dem ersten Zugriff lädt, berücksichtigen wir hier nicht.

Dieselben 64 Additionen ergeben 48 Treffer oder keinen einzigen 🖖

Klick auf 8 × 8 zeilenweise, dann auf 8 × 8 spaltenweise. Beide Durchläufe lesen dieselben 64 int-Werte an denselben 64 Adressen. Nur die Reihenfolge ändert sich. Beim zeilenweisen Lesen führt der erste Zugriff auf jeden 16-Byte-Block zu einem Fehlzugriff und lädt vier int-Werte. Die nächsten drei sind damit schon im Cache: 48 Treffer. Beim spaltenweisen Lesen liegt der nächste Wert eine Matrixzeile weiter, 32 Byte entfernt, und gehört zu einer anderen Cachezeile. Eine Matrixzeile ist hier genau zwei Cachezeilen lang. Deshalb nutzt Spalte 0 ausschließlich die Cachezeilen 0, 2, 4 und 6. Der Zugriff auf a[4][0] verdrängt den Block, den a[0][0] geladen hat. Wenn die Schleife später a[0][1] liest, ist dessen Block bereits verschwunden. Alle 64 Lesezugriffe sind Fehlzugriffe. Ulrich Drepper hat 2007 eine entsprechende Messung mit einer großen Matrix durchgeführt: Eine 1.000 × 1.000-Matrixmultiplikation auf einem Intel Core 2 benötigte nur noch 23,4 % der Taktzyklen, nachdem die zuvor spaltenweise gelesene Matrix transponiert worden war. Dadurch ließen sich beide Matrizen zeilenweise lesen.

Solange die Matrix in den Cache passt, spielt die Reihenfolge keine Rolle 🖖

Stell die Größe auf 5 und wechsle die Reihenfolge: In beiden Fällen ergeben sich 18 Treffer bei 25 Zugriffen. Die Matrix umfasst 100 Byte, der Cache 128 Byte. Ihre sieben Blöcke liegen in sieben verschiedenen Cachezeilen. Ein geladener Block wird deshalb nicht mehr verdrängt. Unabhängig von der Reihenfolge gibt es für jeden Block genau einen Fehlzugriff, beim ersten Lesen. Bei 6 × 6 umfasst die Matrix 144 Byte. Zwei ihrer Blöcke müssen sich eine Cachezeile teilen, und die Ergebnisse unterscheiden sich: 27 Treffer beim zeilenweisen Lesen, 25 beim spaltenweisen. Ohne zusätzliche Füllwerte bleibt die spaltenweise Reihenfolge von dieser Größe an bis 16 × 16 immer zurück.

Vier ungenutzte int-Werte pro Zeile machen aus 0 Treffern 48 🖖

Klick auf Aufgefüllte Zeilen. Du liest dieselbe 8 × 8-Matrix spaltenweise, doch hinter jeder Matrixzeile stehen nun vier int-Werte, auf die nie zugegriffen wird. Eine Matrixzeile umfasst dadurch 48 Byte und belegt drei statt zwei Cachezeilen. Drei und acht sind teilerfremd. Spalte 0 verteilt sich deshalb jetzt auf alle acht Cachezeilen. Ihre acht Blöcke bleiben gleichzeitig im Cache, sodass die nächsten drei Spalten sie dort vorfinden: 48 Treffer bei 64 Zugriffen, genauso viele wie beim zeilenweisen Lesen. Dafür brauchst du zusätzlich 128 Byte, die nie gelesen werden. Das Auffüllen beseitigt Konfliktfehlzugriffe: Zwei Blöcke konkurrieren um dieselbe Cachezeile, während andere leer bleiben. Zusätzlichen Platz im Cache schafft es nicht. Am Ende der Beispielaufgabe begegnest du einer Matrix, bei der genau dieser Platzmangel das Problem ist.

Aufgabe vollständig gelöst

Wie viel zusätzlichen Speicherverkehr verursacht die ungünstige Reihenfolge? 4 Schritte
Klick auf 8 × 8 spaltenweise und erkläre, warum es 0 Treffer gibt. Betrachte anschließend eine 1.024 × 1.024-Matrix aus int-Werten von 4 Byte und einen direkt abbildenden Cache mit 32 KiB und Cachezeilen von 64 Byte. Wie viele Bytes werden aus dem Hauptspeicher übertragen, wenn du die Matrix zeilenweise summierst? Wie viele sind es beim spaltenweisen Summieren? Hilft es, jede Matrixzeile um eine Cachezeile aufzufüllen?

Öffne diese Aufgabe im Tool
1. In der Simulation umfasst eine Matrixzeile 8 × 4 = 32 Byte, also zwei Cachezeilen. Matrixzeile i beginnt deshalb in Cachezeile 2i mod 8, und Spalte 0 nutzt nur die Cachezeilen 0, 2, 4 und 6. a[4][0] belegt die Cachezeile, in der zuvor a[0][0] lag. Wenn die Schleife a[0][1] erreicht, ist dessen Block bereits verdrängt: 0 Treffer bei 64 Zugriffen. Beim zeilenweisen Lesen gibt es pro 16-Byte-Block einen Fehlzugriff, insgesamt 16. Damit bleiben 48 Treffer, also 1 − 4/16 = 75 %.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. Der große Cache hat 32.768 / 64 = 512 Cachezeilen. Beim zeilenweisen Lesen enthält jede 64-Byte-Cachezeile 16 int-Werte. Nur der jeweils erste Zugriff ist ein Fehlzugriff. Das ergibt 1.048.576 / 16 = 65.536 Fehlzugriffe, eine Trefferquote von 1 − 4/64 = 93,75 % und 65.536 × 64 = 4.194.304 übertragene Bytes. Die Matrix wird genau einmal vollständig geladen.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. Beim spaltenweisen Lesen umfasst eine Matrixzeile 4.096 Byte, also 64 Cachezeilen. Matrixzeile i beginnt daher in Cachezeile 64i mod 512. Eine Spalte nutzt nur 8 der 512 Cachezeilen. a[8][0] verdrängt den Block von a[0][0]. Lange bevor die Schleife zu a[0][1] zurückkehrt, ist dessen Block verschwunden. Jeder der 1.048.576 Lesezugriffe ist ein Fehlzugriff: 67.108.864 übertragene Bytes, also 16-mal so viel.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Mit 16 zusätzlichen int-Werten pro Matrixzeile wächst ihre Länge auf 4.160 Byte, also 65 Cachezeilen. 65 und 512 sind teilerfremd. Eine Spalte verteilt sich nun auf alle 512 Cachezeilen. Trotzdem gibt es keinen Treffer: Eine Spalte greift auf 1.024 Blöcke zu, der Cache fasst aber nur 512. Jeder Block wird verdrängt, bevor die nächste Spalte ihn wieder benötigt.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Antwort

4 MiB beim zeilenweisen Lesen, 64 MiB beim spaltenweisen Lesen. Das Auffüllen verteilt die Blöcke einer Spalte über den gesamten Cache, bringt aber weiterhin keinen Treffer. Es beseitigt die Konflikte. Die Daten jeder einzelnen Spalte dieser Matrix brauchen jedoch mehr Platz, als der gesamte Cache bietet.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Lernpfad

Wie ein Computer ein Programm ausführt

Quellen (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.