False Sharing und Padding

Vier Threads aktualisieren je ihren eigenen Zähler, nichts wird geteilt, und doch läuft die Schleife 40-mal langsamer als sie sollte. Der Grund: Die vier Zähler liegen in einer Cache-Zeile, und die Kerne streiten darum. Diese Lektion baut ein kleines Modell der Cache-Kohärenz, zeigt, was False Sharing in einer von den Daten der SPY-Tabelle gesteuerten Schleife kostet, und behebt es mit ein paar Byte Padding.

Bisher lief ein Programm auf einem Kern. Eine echte Maschine hat mehrere Kerne, und jeder hat seinen eigenen kleinen, schnellen Cache. Das schafft ein Problem: Halten Kern 0 und Kern 1 eine Kopie einer Zeile und ändert Kern 0 sie, darf Kern 1 nicht weiter den alten Wert lesen. Die Hardware-Regel dagegen ist die Cache-Kohärenz. Die einfachste Art, sie durchzusetzen: Bevor ein Kern in eine Zeile schreiben darf, wird die Kopie dieser Zeile in allen anderen Kernen verworfen. Das ist eine Invalidierung.

1. 1
   Im eigenen Cache nachsehenIst die Zeile nicht da, ist dieser Zugriff ein Fehlzugriff.
2. 2
   Beim Schreiben die anderen verdrängenJeder andere Kern, der die Zeile hält, verliert seine Kopie: eine Invalidierung je Kern.
3. 3
   Die Zeile behaltenDanach liegt die Zeile im Cache dieses Kerns, bereit für den nächsten Zugriff.

Die Klasse unten merkt sich für jeden Kern die Menge der Zeilen, die er hält. Wir spielen drei Schritte nach: Kern 0 schreibt Byte 0, Kern 1 schreibt Byte 8 (dieselbe Zeile), dann schreibt Kern 0 wieder Byte 0.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1Ein Schreibzugriff entfernt die Zeile aus jedem anderen Kern, der sie hält, und zählt eine Invalidierung pro Kopie.

Alle drei Zugriffe verfehlen. Der Schreibzugriff von Kern 1 invalidiert die Kopie von Kern 0, und der nächste Schreibzugriff von Kern 0 invalidiert seinerseits die Kopie von Kern 1. Kern 0 und Kern 1 haben nie dasselbe Byte geschrieben, nur benachbarte, und nehmen sich die Zeile bei jedem Schreibzugriff trotzdem gegenseitig weg.

Eine übliche Art, Ereignisse parallel zu zählen, ist, jedem Kern einen eigenen Zähler zu geben, damit kein Kern auf einen anderen wartet. Die Zähler sind je 8 Byte groß. Legt man sie hintereinander in ein Array, passen vier in eine 64-Byte-Zeile. Wir bauen die Schreibzugriffe von 50 Aktualisierungsrunden, einen pro Kern und Runde, und spielen sie ab, mit den Zählern 8 Byte auseinander (gepackt) und 64 Byte auseinander (mit Padding). Die Zeit beträgt 1 ns für einen Zugriff im eigenen Cache des Kerns und 60 ns für einen Fehlzugriff, der die Zeile von einem anderen Kern holt.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

Gepackt verfehlen alle 200 Schreibzugriffe und 199 davon invalidieren den vorherigen Schreiber: 12.000 ns. Mit Padding hält jeder Kern seinen Zähler in einer eigenen Zeile: vier Kaltstart-Fehlzugriffe am Anfang, danach trifft jeder Schreibzugriff, und es gibt keine Invalidierung: 436 ns. Das ist 27-mal schneller bei exakt derselben Arithmetik, weil die vier Kerne sich die Zeile nicht mehr wegnehmen.

Damit jeder Zähler eine eigene Zeile bekommt, muss der Abstand zweier Zähler ein Vielfaches der Zeilengröße sein, die Elementgröße wird also auf das nächste Vielfache von 64 aufgerundet. Ein 8-Byte-Zähler belegt 64 Byte, 56 davon sind verschwendet. Ein Element von 65 Byte belegt 128. Die Funktion unten rundet auf.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

Im Labor zählen vier Kerne je die Handelstage, die sie bearbeiten, und der Tag Nummer i der SPY-Tabelle geht an Kern Wochentag % 4. Die ersten 1.000 Tage steuern die Schreibzugriffe in Datumsreihenfolge. Weil die Tage dem Kalender folgen, schreibt derselbe Kern selten zweimal hintereinander, und die Zeile wird immer wieder weggenommen. Mit gepackten Zählern verfehlen 818 der 1.000 Schreibzugriffe und 817 invalidieren einen anderen Kern; mit Padding verfehlen nur die ersten vier.

Das Labor baut das Kohärenzmodell, die Spuren von Zählern pro Kern mit gegebener Schrittweite, die Wiedergabe, die Padding-Regel, das Zeitmodell und die Studie an den SPY-Daten.

• Funktion · FrageBaut auf
• CoherentCaches(n_cores).access(core, address, write)Treffer oder Fehlzugriff, und wer verliert eine Kopie?Einfache Arithmetik
• counter_address(core, stride_bytes)Wo liegt der Zähler eines Kerns?Einfache Arithmetik
• update_trace(n_cores, n_updates, stride_bytes)Welche Schreibzugriffe machen die Kerne?counter_address
• run_trace(trace, n_cores)Wie viele Fehlzugriffe und Invalidierungen?CoherentCaches
• padding_needed(item_bytes)Wie weit müssen die Elemente auseinanderliegen?Einfache Arithmetik
• time_ns(stats)Wie lange dauert der Lauf?Die Kosten für Treffer und Fehlzugriff
• study(bars)Was kostet False Sharing bei den SPY-Daten?run_tracepadding_neededtime_ns

Nächstes Thema: False Sharing betrifft Kerne, die sich einen Sockel teilen. Auf einer Maschine mit zwei Sockeln ist der Speicher selbst geteilt: ein Teil liegt nahe an einem Kern, ein anderer weit weg. In NUMA-Effekte platzieren Sie Seiten auf Knoten, zählen lokale und entfernte Zugriffe und beziffern den Unterschied.