Prefetching

Ein Fehlzugriff kostet nur dann 80 ns, wenn das Programm darauf warten muss. Ein Prefetcher fordert eine Zeile an, bevor das Programm es tut, sodass das Warten vorbei ist, wenn der Lesezugriff eintrifft. Diese Lektion baut zwei Prefetcher, bewertet sie mit Abdeckung und Genauigkeit und zeigt, wo sie funktionieren, in Schleifen mit regelmäßiger Schrittweite, und wo nicht, bei Lesezugriffen in unvorhersehbarer Reihenfolge.

Bisher hat der Cache eine Zeile geladen, wenn ein Lesezugriff verfehlte. Ein Prefetch lädt sie früher. Stimmt die Vermutung, findet der spätere Lesezugriff die Zeile schon im Cache und trifft. Jeder moderne Prozessor hat Hardware-Prefetcher, die die Adressen der Lesezugriffe beobachten und erraten, was als Nächstes kommt. Die einfachste Vermutung: Wer Zeile L gelesen hat, will als Nächstes Zeile L + 1. Unser mitgelieferter Cache hat eine Methode fill, die eine Zeile lädt, ohne Treffer oder Fehlzugriff zu zählen, genau das ist ein Prefetch.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1Die nächste Zeile vorzuladen kostet hier nichts: fill zählt weder als Treffer noch als Fehlzugriff.

Liest man 800 Werte der Reihe nach, verfehlt ein einfacher Cache einmal pro Zeile, also 100-mal. Mit dem Next-Line-Prefetcher verfehlt er insgesamt nur einmal: Nach dem allerersten Lesezugriff ist die als Nächstes benötigte Zeile immer schon da. Der zweite Fall zeigt die Grenze. Springt das Programm jedes Mal 4096 Byte, ist die Zeile nach der aktuellen nutzlos und der Prefetcher spart nichts: weiterhin 50 Fehlzugriffe bei 50 Lesezugriffen.

Echte Prefetcher suchen ein Muster in den Zeilen, die ein Programm liest. Das häufigste ist eine konstante Schrittweite: Das Programm liest die Zeilen 0, 3, 6, 9 und springt jedes Mal drei Zeilen. Ein Schrittweiten-Detektor merkt sich die letzte Zeile und den letzten Schritt. Entspricht der neue Schritt dem letzten, ist es ein Muster, und die nächste Zeile ist die aktuelle plus der Schritt. Zwei gleiche Schritte sind nötig, um sicher zu sein, er rät also bei den ersten beiden Lesezugriffen nie.

1. 1
   Eine Wiederholung ignorierenDieselbe Zeile erneut zu lesen sagt nichts über eine Schrittweite.
2. 2
   Den Schritt berechnenDie neue Zeile minus die letzte Zeile.
3. 3
   Mit dem letzten Schritt vergleichenGleiche Schritte bedeuten ein Muster: die neue Zeile plus Schritt vorhersagen.
4. 4
   MerkenDen neuen Schritt und die neue Zeile für den nächsten Lesezugriff behalten.

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1Zwei gleiche Schritte hintereinander: Das ist eine Schrittweite, die nächste Zeile ist also die aktuelle plus der Schritt.

Die erste Folge hat eine Schrittweite von drei Zeilen. Der Detektor sagt bei den ersten beiden Lesezugriffen nichts und sagt dann 9, 12 und 15 voraus, immer einen Schritt voraus. In der zweiten Folge werden die wiederholten Lesezugriffe auf Zeile 5 ignoriert, und die Schrittweite 1 wird erst beim letzten Lesezugriff bestätigt. Ein guter Detektor ist vorsichtig: Eine falsche Vermutung hat einen Preis, wie wir gleich sehen.

Zwei Zahlen bewerten einen Prefetcher. Die Abdeckung sagt, wie viel vom Problem er gelöst hat. Die Genauigkeit sagt, wie viel seiner Arbeit nützlich war. Zum Messen schicken wir die Spur durch den Cache, machen einen Lesezugriff, fragen den Prefetcher, was als Nächstes zu laden ist, merken uns, welche Zeilen vorgeladen wurden, und zählen, wann ein Lesezugriff eine davon trifft.

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

Beim Lesen in Reihenfolge beseitigt der Prefetcher 98,8 % der Fehlzugriffe, und 99,6 % seiner Prefetches werden genutzt. Beim gemischten Lesen tut er nichts: Ohne wiederkehrenden Schritt gibt er fast nie einen Prefetch aus (nur einen) und richtet daher auch keinen Schaden an. Das ist das gewünschte Verhalten. Ein Prefetcher, der ständig rät, würde den Cache mit Zeilen füllen, die niemand liest.

Das Labor liest 2.000 Schlusskurse auf drei Arten: nacheinander gespeichert und der Reihe nach gelesen, in Zeilen aus fünf Werten gespeichert (Schrittweite 40 Byte) und nacheinander gespeichert, aber in der Reihenfolge steigenden Handelsvolumens gelesen. Die ersten beiden haben ein regelmäßiges Muster; die dritte besucht die Tage in einer scheinbar zufälligen Reihenfolge, weil das Volumen eines Tages nichts über das des nächsten aussagt.

Der Hinweis liegt in der Frage, die der Prefetcher beantwortet: Was kommt als Nächstes? Steckt die Antwort im Muster der Adressen, findet die Hardware sie umsonst. Hängt die Reihenfolge von den Daten ab, etwa beim Besuchen von nach Volumen sortierten Zeilen, kann nichts sie erraten. Die Software-Abhilfe ist, das Datenlayout so zu ändern, dass der Zugriff wieder regelmäßig wird, zum Beispiel indem man die Zeilen einmal sortiert und dann der Reihe nach liest.

Das Labor baut die zwei Prefetcher, die Simulation, die sie bewertet, und die Studie zu den drei Arten, die SPY-Schlusskurse zu lesen.

• Funktion · FrageBaut auf
• baseline_misses(trace)Wie viele Fehlzugriffe ohne Prefetching?Cache
• next_line_misses(trace)Wie viele mit einem Next-Line-Prefetcher?Cache.fill
• StridePrefetcher().observe(line)Welche Zeile kommt als Nächstes?Die letzte Zeile und der letzte Schritt
• run_with_prefetcher(trace, prefetcher)Was geschah: Fehlzugriffe, Prefetches, nützliche?Cache
• quality(trace)Welche Abdeckung und Genauigkeit erreicht er?baseline_missesrun_with_prefetcher
• study(bars)Wo hilft der Prefetcher bei den SPY-Schlusskursen?qualitynext_line_misses

Nächstes Thema: Bisher war eine Adresse eine Zeile und nur ein Cache-Treffer zählte. In TLB und große Seiten muss jede Adresse zuerst von einer virtuellen in eine physische Seite übersetzt werden, und ein kleiner Cache für Übersetzungen, der TLB, kann ebenfalls verfehlen, auf eine Weise, die von der Seitengröße abhängt.