Zwei verschachtelte Schleifen, die dieselben Zellen einer Matrix besuchen, können sich allein dadurch um den Faktor sieben in den Cache-Fehlzugriffen unterscheiden, welche Schleife innen liegt. Diese Lektion vergleicht das Lesen Zeile für Zeile und Spalte für Spalte, zerlegt dann eine Transposition in Kacheln, damit ein Block im Cache bleibt, solange er genutzt wird, und misst beides an einer aus SPY-Schlusskursen gebauten Matrix.
Welche Schleife liegt innen?
Eine Matrix mit n Zeilen und n Spalten liegt in zeilenweiser Ordnung im Speicher. Eine Schleife, die an einer Zeile entlangläuft und j ändert, liest benachbarte Werte. Eine Schleife, die eine Spalte hinuntergeht und i ändert, springt bei jedem Schritt eine ganze Zeile. Die beiden Schleifen unten besuchen dieselben Zellen, eine mit j innen, eine mit i. Wir geben die ersten sechs Adressen einer 4-mal-4-Matrix aus float64-Werten aus.
def row_major_trace(n): return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n): return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])
row: [0, 8, 16, 24, 32, 40] col: [0, 32, 64, 96, 8, 40]
- 1Mit i innen liegt der nächste Lesezugriff eine ganze Zeile weiter (hier 4 Werte = 32 Byte).
Zeilenweise steigen die Adressen um 8 Byte, die Schrittweite des ersten Themas, und eine Cache-Zeile bedient acht Lesezugriffe. Spaltenweise springen sie hier um 32 Byte, in einer größeren Matrix um die Länge einer ganzen Zeile. Wir zählen jetzt die Fehlzugriffe der beiden Reihenfolgen in einem kleinen 4-KB-Cache für Matrizen von 16 mal 16 bis 73 mal 73.
for n in (16, 32, 48, 73): print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))
16 x 16 row: 32 col: 32 32 x 32 row: 128 col: 1024 48 x 48 row: 288 col: 2304 73 x 73 row: 667 col: 4573
Eine 16-mal-16-Matrix hat 2 KB und passt in den Cache, nach dem Laden kosten beide Reihenfolgen also 32 Fehlzugriffe, dasselbe. Ab 32 mal 32 passt die Matrix nicht mehr, und die spaltenweise Reihenfolge verfehlt bei jedem Zugriff: 1.024 Fehlzugriffe gegen 128, ein Faktor acht, die acht Werte einer Zeile. Bei 73 mal 73 beträgt der Faktor fast sieben. Die Form der Schleifen hat sich nicht geändert; die Größe der Daten schon.
Die Schleifen zu vertauschen ist kostenlos, wenn die Matrix größer als der Cache ist, und bewirkt nichts, wenn sie hineinpasst. Ein Test an einer kleinen Matrix kann das Problem völlig verbergen, und das Programm wird dann bei echten Daten langsam. Messen Sie in der echten Größe.
Wenn beide Schleifen sich widersprechen: die Transposition
Manchmal hilft keine Schleifenreihenfolge. Die Transposition B[j][i] = A[i][j] liest A und schreibt B, und wenn die Schleifen an den Zeilen von A entlanglaufen, gehen sie die Spalten von B hinunter. Welche Schleife auch innen liegt, eine der beiden Matrizen wird mit großer Schrittweite durchlaufen. Das Mittel ist Loop Tiling: Die Matrix wird in kleinen quadratischen Kacheln verarbeitet, sodass die wenigen Zeilen, die eine Kachel berührt, oft genutzt werden, bevor sie verdrängt werden.
- 1Eine Kachelgröße t wählenKlein genug, dass je eine Kachel von A und B in den Cache passt.
- 2Über die Kacheln laufenZwei äußere Schleifen mit Schritt t: ii und jj ergeben die Ecke einer Kachel.
- 3In der Kachel arbeitenDie beiden inneren Schleifen besuchen nur die t mal t Zellen dieser Kachel, wie zuvor.
- 4Zur nächsten KachelErst jetzt lässt das Programm die Zeilen der alten Kachel hinter sich.
Der Code unten listet nur die Reihenfolge auf, in der die Zellen besucht werden, für eine 4-mal-4-Matrix ohne und mit Kacheln von 2. Mit Kacheln beendet das Programm den 2-mal-2-Block oben links, bevor es eine andere Zelle berührt.
def visit_order(n, tile=None): step = n if tile is None else tile order = [] for ii in range(0, n, step):1 for jj in range(0, n, step): for i in range(ii, min(ii + step, n)): for j in range(jj, min(jj + step, n)): order.append((i, j)) return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])
plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)] tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]
- 1Die beiden äußeren Schleifen laufen über die Kacheln; die beiden inneren laufen innerhalb einer Kachel.
Nun die echte Transposition. Wir schreiben die Spur der Lesezugriffe auf A und der Schreibzugriffe auf B, wobei B direkt hinter A liegt, und zählen die Fehlzugriffe für eine 73-mal-73-Matrix ohne Kachel und mit Kacheln von 4, 8, 16 und 32.
def transpose_trace(n, tile=None): base_b = n * n * 8 step = n if tile is None else tile trace = [] for ii in range(0, n, step): for jj in range(0, n, step): for i in range(ii, min(ii + step, n)): for j in range(jj, min(jj + step, n)): trace.append((i * n + j) * 8) trace.append(base_b + (j * n + i) * 8) return tracefor tile in (None, 4, 8, 16, 32): print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))
tile None misses: 5996 tile 4 misses: 2603 tile 8 misses: 2036 tile 16 misses: 1960 tile 32 misses: 1714
Ohne Kacheln verfehlt die Transposition 5.996-mal. Mit Kacheln von 4 sind es schon nur 2.603, und mit Kacheln von 8 bis 32 bleibt sie zwischen 2.036 und 1.714, etwa dreimal weniger. Eine zu kleine Kachel verschwendet die Ränder der geladenen Zeilen, der Gewinn wächst also mit der Kachel, bis sie nicht mehr hineinpasst.
Eine für einen 4-KB-Cache abgestimmte Kachel passt nicht zu einem 32-KB-Cache. Hier liegt alles von 8 bis 32 innerhalb von 20 % des Besten, eine mittlere Kachel ist also eine sichere Wahl. Wechselt die Maschine, messen Sie neu, statt eine Zahl zu kopieren.
NumPy und BLAS multiplizieren und transponieren große Arrays bereits in Kacheln. Sie begegnen dem Tiling, wenn Sie eigene Schleifen schreiben, in Numba, C++ oder Rust, oder wenn ein eigener Kernel langsamer ist als der Bibliotheksaufruf, den er ersetzt hat.
Was Sie bauen werden
Das Labor folgt der Lektion: die zwei Leseordnungen, die Transpositionsspur mit optionaler Kachel, die Zählung der Fehlzugriffe nach Reihenfolge und Kachel, die Wahl der besten Kachel und die Studie an der SPY-Matrix.
- Funktion · FrageBaut auf
- row_major_trace(n)Welche Adressen berührt ein zeilenweises Lesen?Einfache Arithmetik
- col_major_trace(n)Und ein spaltenweises Lesen?Einfache Arithmetik
- transpose_trace(n, tile=None)Welche Adressen berührt eine Transposition, mit oder ohne Kacheln?Vier verschachtelte Schleifen
- compare_orders(n)Wie viel schlechter ist die spaltenweise Reihenfolge?row_major_tracecol_major_trace
- misses_by_tile(n, tiles)Wie verändern Kacheln die Fehlzugriffe der Transposition?transpose_trace
- best_tile(n, tiles)Welche Kachel ist die beste?misses_by_tile
- study(bars)Was bringt Tiling bei einer Matrix aus SPY-Schlusskursen?compare_ordersbest_tile
Nächstes Thema: Tiling verbirgt die Verzögerung eines Fehlzugriffs, indem es Zeilen wiederverwendet; Prefetching verbirgt sie, indem es eine Zeile anfordert, bevor sie gebraucht wird. In Prefetching fügen Sie dem Cache einen Schrittweiten-Detektor hinzu und sehen, welche Zugriffsmuster er vorhersagen kann und welche, wie ein Zufallsspaziergang durch eine Tabelle, nicht.
Lab: Was bewertet wird
7 Aufgaben · 100 Pkt.- Zeilenweises Lesen10 Pkt.
- Spaltenweises Lesen10 Pkt.
- Die Transposition, mit oder ohne Kacheln25 Pkt.
- Die Reihenfolgen vergleichen15 Pkt.
- Die Fehlzugriffe nach Kachel15 Pkt.
- Die beste Kachel10 Pkt.
- Die Studie mit der SPY-Matrix15 Pkt.