Ein Cache holt nie ein einzelnes Byte. Er holt eine ganze Zeile von 64 Byte, der Wert neben dem gerade gelesenen ist also schon da. Diese Lektion baut einen Cache, zeigt, dass Lesen in Reihenfolge achtmal billiger ist als jedes Mal eine Zeile zu überspringen, und wendet das auf eine Preistabelle an.
Speicher kommt in Zeilen
Ein Holen aus dem Speicher kostet gleich viel, egal wie viele Byte Sie anfordern, also fordert die Hardware viele auf einmal an. Der Speicher ist in Blöcke von 64 Byte geschnitten, und der Cache lädt und verdrängt immer ganze Blöcke. Stellen Sie sich einen Aufzug vor, der 64 Byte zum Cache hinauffährt: Wenn er sowieso fährt, kostet es nichts, die Nachbarn mitzunehmen, und wenn Sie einen von ihnen später brauchen, ist er schon oben.
Ein Block aufeinanderfolgender Byte, bei den meisten Prozessoren 64, den der Cache als eine Einheit lädt und verdrängt. Zeile n enthält die Byte von 64n bis 64n + 63.
Jedes Byte hat eine Adresse, eine Zahl, die sagt, wo es liegt. Um die Zeile einer Adresse zu finden, teilen Sie durch die Zeilengröße und verwerfen den Rest. Der Code unten gibt die Zeile von vier Adressen aus.
line_bytes = 64for address in (0, 63, 64, 130): print(address, "is in line", address // line_bytes)
0 is in line 0 63 is in line 0 64 is in line 1 130 is in line 2
Die Adressen 0 und 63 teilen sich Zeile 0, ist also eine geladen, ist die andere gratis. Adresse 64 beginnt Zeile 1, und 130 liegt in Zeile 2. Alles in diesem Thema folgt aus dieser ganzzahligen Division.
Ein Cache ist eine Tabelle aus Plätzen
Der einfachste Cache ist eine Tabelle mit einem Platz für jede Zeile, die er halten kann. Ein 32-KB-Cache mit 64-Byte-Zeilen hat 512 Plätze. Jede Speicherzeile darf in genau einen Platz, gefunden über einen Rest: Zeilennummer modulo Anzahl der Plätze. Das ist ein direkt abgebildeter Cache. Weil viele Zeilen sich einen Platz teilen, merkt sich der Platz auch ein Tag, das sagt, welche Zeile er gerade hält.
- 1Zeile bestimmenTeilen Sie die Adresse durch die Zeilengröße.
- 2Platz bestimmenNehmen Sie die Zeilennummer modulo die Anzahl der Plätze.
- 3Tag vergleichenHält der Platz diese Zeile, ist es ein Treffer.
- 4Bei Fehlzugriff ersetzenLaden Sie die Zeile in den Platz und vergessen Sie die vorherige.
Das ist der ganze Cache. Die Klasse unten ist eine vollständige, funktionierende Version in fünfzehn Zeilen. Wir lesen vier benachbarte Werte, dann die nächste Zeile und gehen dann zurück zu Adresse 0.
def line_of(address, line_bytes): return address // line_bytesclass Cache: def __init__(self, size_bytes, line_bytes): self.line_bytes = line_bytes self.n_lines = size_bytes // line_bytes self.tags = [None] * self.n_lines self.hits = 0 self.misses = 0 def access(self, address): line = line_of(address, self.line_bytes)1 slot = line % self.n_lines if self.tags[slot] == line:2 self.hits += 1 return True self.misses += 1 self.tags[slot] = line return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")
[False, True, True, True, False, True, True, False, False] 5 hits and 4 misses
- 1Der Platz ist die Zeilennummer modulo die Anzahl der Plätze.
- 2Ein Treffer heißt, dass das Tag im Platz genau diese Zeile ist.
Lesen Sie die Liste der Flags: Der erste Lesezugriff verfehlt und lädt Zeile 0, die nächsten drei treffen, weil sie in Zeile 0 liegen, 64 verfehlt und lädt Zeile 1, 72 trifft, und die Rückkehr zu 0 trifft wieder, weil Zeile 0 nicht verdrängt wurde. Dann ist Adresse 512 Zeile 8, die ebenfalls auf Platz 0 abgebildet wird (8 modulo 8), also Zeile 0 verdrängt, und der letzte Zugriff auf Adresse 0 verfehlt wieder: Ein Konflikt hat uns einen Fehlzugriff gekostet.
Ein 512-Byte-Cache mit 64-Byte-Zeilen hat nur 8 Plätze, nicht 512. Die Größe nicht durch die Zeilengröße zu teilen ist der übliche Weg zu einem Cache, der riesig aussieht und sich falsch verhält.
In Reihenfolge lesen gegen springen
Nutzen Sie nun den Cache. Ein float64-Wert belegt 8 Byte, eine Zeile fasst also acht. Lesen Sie ein Array der Reihe nach: Der erste Zugriff auf jede Zeile verfehlt und die nächsten sieben treffen, ein Fehlzugriff auf acht. Lesen Sie es mit einer Schrittweite, also mit einer festen Anzahl übersprungener Werte zwischen den Lesezugriffen, und die Zugriffe landen in verschiedenen Zeilen. Der nächste Code misst die Fehlzugriffsrate für Schrittweiten von 1, 2, 4, 8 und 16 Werten.
def sequential_trace(n, elem_bytes): return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride): return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64): cache = Cache(size_bytes, line_bytes) for address in trace: cache.access(address) return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16): print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))
stride 1 values: 0.125 stride 2 values: 0.25 stride 4 values: 0.5 stride 8 values: 1.0 stride 16 values: 1.0
Die Fehlzugriffsrate verdoppelt sich mit jeder Verdopplung der Schrittweite, bis sie 1,0 erreicht: Bei 8 Werten ist der Sprung 64 Byte, eine ganze Zeile, jeder Zugriff öffnet also eine neue Zeile und der Cache spart nichts. Eine größere Schrittweite kann nicht schlimmer sein, nur gleich. Das Muster ist die Formel unten.
Auf fast allen x86- und Server-ARM-Chips ja. Manche Chips nutzen 128 Byte in einem äußeren Cache, messen Sie also die Zeilengröße der Zielmaschine. Unser Cache nimmt sie als Parameter, damit Sie beides ausprobieren können.
Das Layout einer Tabelle bestimmt die Schrittweite
Eine Tabelle von Tagesbalken hat fünf Zahlen pro Tag: Eröffnung, Hoch, Tief, Schluss und Volumen. Speichern Sie sie Zeile für Zeile, wie es die meisten Programme tun, liegen die fünf Zahlen eines Tages nebeneinander. Um nur die Schlusskurse zu lesen, überspringen Sie dann vier Werte zwischen den Lesezugriffen: eine Schrittweite von 5, also 40 Byte. Speichern Sie jede Spalte für sich, folgen die Schlusskurse aufeinander: Schrittweite 1. Gleiche Zahlen, gleiche Lesezugriffe, anderes Layout.
closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout: ", as_rows)
column layout: 0.125 row layout: 0.625
Fünfmal so viele Lesezugriffe verfehlen, wenn die Schlusskurse mit Abstand liegen. Das ändert nicht die Antwort Ihres Programms, nur seine Geschwindigkeit, und keine Rechenzeile im Profiler zeigt es: Die zusätzliche Zeit geht beim Warten auf den Speicher drauf.
Was Sie bauen werden
Das Labor verlangt die Teile, die Sie gerade gelesen haben, in derselben Reihenfolge, und endet mit der Studie an der echten SPY-Tabelle.
- Funktion · FrageBaut auf
- line_of(address, line_bytes)Welche Zeile enthält diese Adresse?Die ganzzahlige Division
- Cache(size_bytes, line_bytes).access(address)Ist dieser Lesezugriff ein Treffer?line_of
- sequential_trace(n, elem_bytes)Welche Adressen berührt ein Lesen in Reihenfolge?Einfache Arithmetik
- strided_trace(n, elem_bytes, stride)Welche Adressen berührt ein springendes Lesen?Einfache Arithmetik
- miss_rate(trace, size_bytes, line_bytes)Welcher Anteil einer Spur verfehlt?Cache
- study(bars)Was kostet das Zeilenlayout für die SPY-Schlusskurse?miss_ratestrided_trace
Nächstes Thema: Ein direkt abgebildeter Cache hat eine Schwäche, die diese Lektion berührt hat, den Konflikt zwischen Zeilen, die sich einen Platz teilen. In Assoziativität und Konfliktfehler geben Sie jedem Platz mehrere Stellen und sehen, warum eine Tabelle, deren Zeilen 4096 Byte auseinanderliegen, einen Cache ruinieren kann.
Lab: Was bewertet wird
6 Aufgaben · 100 Pkt.- Die Zeile einer Adresse10 Pkt.
- Ein direkt abgebildeter Cache25 Pkt.
- Ein Lesen in Reihenfolge10 Pkt.
- Ein Lesen mit Schrittweite10 Pkt.
- Die Fehlzugriffsrate einer Spur20 Pkt.
- Die Studie mit der SPY-Tabelle25 Pkt.