Cache-Kohärenz-Protokolle

Cache-Kohärenz-Protokolle halten die Konsistenz der mehreren privaten Caches in einem Multiprozessor mit gemeinsamem Speicher aufrecht und stellen sicher, dass, wenn ein Kern einen Speicherort beschreibt, andere Kerne keine veralteten zwischengespeicherten Kopien weiterlesen.

Definition

Ein Cache-Kohärenz-Protokoll ist ein Mechanismus, der eine konsistente Sicht des gemeinsamen Speichers über die privaten Caches mehrerer Prozessoren hinweg aufrechterhält, indem er den Zustand jedes zwischengespeicherten Blocks verfolgt und Lese- und Schreibvorgänge koordiniert, sodass ein Schreibvorgang sichtbar wird und alte Kopien nicht verwendet werden.

Scope

Dieses Thema behandelt das Kohärenzproblem und seine Lösungen: Invalidierungs- versus Update-Protokolle, Snooping-Protokolle auf einem gemeinsamen Bus, verzeichnisbasierte Protokolle für skalierbare Systeme und die kanonischen Zustandsmaschinen wie MSI und MESI. Es behandelt, wie Hardware eine kohärente Sicht des Speichers über Caches hinweg bewahrt. Ausgeschlossen sind die Reihenfolge von Operationen über Adressen hinweg (Speicherkonsistenz, unter Shared-Memory-and-Coherence) und Einzel-Cache-Richtlinien (Cache-Organisation und -Richtlinien).

Core questions

• Was bedeutet es, dass Caches kohärent sind, und warum ist Kohärenz notwendig?
• Wie unterscheiden sich Invalidierungs- und Update-Protokolle?
• Wie verwenden Snooping-Protokolle eine gemeinsame Verbindung, um Kohärenz aufrechtzuerhalten?
• Wie skalieren Verzeichnisprotokolle die Kohärenz über einen gemeinsamen Bus hinaus?

Key concepts

• Kohärenzproblem
• Invalidierungs- vs. Update-Protokolle
• Snooping-Protokolle
• verzeichnisbasierte Protokolle
• MSI- und MESI-Zustände
• gemeinsamer Bus und Interconnect
• False Sharing
• Schreibserialisierung

Key theories

Zustandsbasierte Kohärenz (MSI/MESI)

Jeder zwischengespeicherte Block wird in einer kleinen Menge von Zuständen verfolgt (wie Modified, Exclusive, Shared, Invalid); Lese- und Schreibvorgänge lösen Zustandsübergänge und Kohärenz-Nachrichten aus, die sicherstellen, dass höchstens ein Schreiber vorhanden ist und dass Leser niemals veraltete Daten sehen.

Mechanisms

Jeder Cache-Block trägt einen Kohärenzzustand. Bei Snooping-Protokollen beobachtet (snoopt) jeder Cache Bustransaktionen und aktualisiert oder invalidiert seine Kopien entsprechend; bei Verzeichnisprotokollen zeichnet ein Verzeichnis auf, welche Caches jeden Block halten, und sendet gezielte Kohärenz-Nachrichten. Ein Schreibvorgang auf einen gemeinsam genutzten Block invalidiert zuerst andere Kopien (in einem Invalidierungsprotokoll) und gewährt dem Schreiber exklusiven Besitz, bevor er die Daten modifiziert.

Clinical relevance

Kohärenz macht Shared-Memory-Multiprozessoren programmierbar: Software kann den Speicher als einen einzigen gemeinsamen Speicher behandeln, während die Hardware die Existenz mehrerer Caches verbirgt. Kohärenz-Traffic und Effekte wie False Sharing können jedoch die Leistung in parallelen Programmen dominieren, daher ist das Bewusstsein für Kohärenz für skalierbare Multithread-Software wichtig.

History

Kohärenzprotokolle entstanden in den 1980er Jahren mit busbasierten Multiprozessoren, wo Snooping-Schemata wie Write-Invalidate und die MESI-Familie zum Standard wurden. Als Systeme über einen einzelnen Bus hinaus skalierten, wurden verzeichnisbasierte Protokolle für verteilten gemeinsamen Speicher entwickelt, und Kohärenz bleibt ein zentrales Designproblem in Multicore-Prozessoren.

Debates

Snooping versus Verzeichnis-Kohärenz

Snooping ist einfach und schnell auf kleinen Shared-Bus-Systemen, skaliert aber nicht, während Verzeichnisse auf viele Kerne skalieren, jedoch auf Kosten von Komplexität und Speicher; große Designs kombinieren oft hierarchische oder hybride Ansätze.

Key figures

• David E. Culler
• Mark D. Hill
• James R. Goodman
• John L. Hennessy

Seminal works

• hennessy2019
• culler1999

Frequently asked questions

Was ist der Unterschied zwischen Kohärenz und Konsistenz?

Kohärenz betrifft einen einzelnen Speicherort: Alle Caches müssen sich schließlich auf seinen Wert einigen und Schreibvorgänge darauf in der richtigen Reihenfolge sehen. Konsistenz (das Speicherkonsistenzmodell) betrifft die Reihenfolge von Operationen über verschiedene Speicherorte hinweg, wie sie von verschiedenen Prozessoren beobachtet werden. Kohärenz ist notwendig, aber nicht ausreichend für ein wohldefiniertes Konsistenzmodell.

Was ist False Sharing?

False Sharing tritt auf, wenn unabhängige Variablen, die von verschiedenen Kernen verwendet werden, zufällig im selben Cache-Block liegen. Da Kohärenz auf Blockgranularität arbeitet, invalidieren Schreibvorgänge eines Kerns den Block in anderen, obwohl sie verschiedene Variablen betreffen, was zu unnötigem Kohärenz-Traffic und Verlangsamung führt.