Cache-Kohärenz - Cache coherence

Eine Abbildung, die mehrere Caches eines Speichers zeigt, der als gemeinsam genutzte Ressource fungiert
Inkohärente Caches: Die Caches haben unterschiedliche Werte einer einzelnen Adressposition.

In der Computerarchitektur ist Cache-Kohärenz die Einheitlichkeit von gemeinsam genutzten Ressourcendaten, die schließlich in mehreren lokalen Caches gespeichert werden . Wenn Clients in einem System Caches einer gemeinsamen Speicherressource verwalten, können Probleme mit inkohärenten Daten auftreten, was insbesondere bei CPUs in einem Mehrprozessorsystem der Fall ist.

Stellen Sie sich in der Abbildung rechts vor, dass beide Clients über eine zwischengespeicherte Kopie eines bestimmten Speicherblocks aus einem vorherigen Lesevorgang verfügen. Angenommen, der Client im unteren Bereich aktualisiert/ändert diesen Speicherblock, der Client im oberen Bereich könnte mit einem ungültigen Speichercache zurückbleiben, ohne dass eine Benachrichtigung über die Änderung erfolgt. Cache-Kohärenz soll solche Konflikte verwalten, indem eine kohärente Ansicht der Datenwerte in mehreren Caches beibehalten wird.

Kohärente Caches: Der Wert in allen Kopien der Caches ist gleich.

Überblick

In einem Mehrprozessorsystem mit gemeinsam genutztem Speicher mit einem separaten Cache-Speicher für jeden Prozessor ist es möglich, viele Kopien gemeinsam genutzter Daten zu haben: eine Kopie im Hauptspeicher und eine im lokalen Cache jedes Prozessors, der sie angefordert hat. Wenn eine der Datenkopien geändert wird, müssen die anderen Kopien diese Änderung widerspiegeln. Cache-Kohärenz ist die Disziplin, die sicherstellt, dass die Änderungen in den Werten gemeinsam genutzter Operanden (Daten) rechtzeitig durch das System weitergegeben werden.

Im Folgenden sind die Anforderungen für die Cache-Kohärenz aufgeführt:

Vermehrung schreiben
Änderungen an den Daten in einem Cache müssen an andere Kopien (dieser Cachezeile) in den Peer-Caches weitergegeben werden.
Transaktionsserialisierung
Lese-/Schreibvorgänge an einem einzelnen Speicherort müssen von allen Prozessoren in der gleichen Reihenfolge gesehen werden.

Theoretisch kann Kohärenz mit der Lade-/Speicher- Granularität durchgeführt werden . In der Praxis wird es jedoch im Allgemeinen mit der Granularität von Cache-Blöcken durchgeführt.

Definition

Kohärenz definiert das Verhalten von Lese- und Schreibvorgängen an einer einzelnen Adressposition.

Eine Art von Daten, die gleichzeitig in verschiedenen Cache-Speichern auftreten, wird Cache-Kohärenz oder in einigen Systemen globaler Speicher genannt.

Bedenken Sie, dass in einem Mehrprozessorsystem mehr als ein Prozessor eine Kopie des Speicherplatzes X zwischengespeichert hat. Die folgenden Bedingungen sind erforderlich, um Cache-Kohärenz zu erreichen:

  1. Bei einem Lesevorgang eines Prozessors P an einer Stelle X, der einem Schreibvorgang desselben Prozessors P nach X folgt, wobei zwischen den Schreib- und den Lesebefehlen von P keine Schreibvorgänge an X durch einen anderen Prozessor erfolgen, muss X immer den Wert . zurückgeben geschrieben von P.
  2. Bei einem von einem Prozessor P1 ausgeführten Lesevorgang an die Speicherstelle X, der einem Schreibvorgang durch einen anderen Prozessor P2 an X folgt, ohne dass zwischen den beiden Zugriffen weitere Schreibvorgänge an X von irgendeinem Prozessor vorgenommen werden und wobei das Lesen und das Schreiben ausreichend getrennt sind, muss X immer gibt den von P2 geschriebenen Wert zurück. Diese Bedingung definiert das Konzept der kohärenten Sicht auf das Gedächtnis. Die Weitergabe der Schreibvorgänge an den gemeinsam genutzten Speicherort stellt sicher, dass alle Caches eine kohärente Ansicht des Speichers haben. Wenn der Prozessor P1 den alten Wert von X liest, auch nach dem Schreiben von P2, können wir sagen, dass der Speicher inkohärent ist.

Die obigen Bedingungen erfüllen die Schreibfortpflanzungskriterien, die für die Cache-Kohärenz erforderlich sind. Sie reichen jedoch nicht aus, da sie die Transaktionsserialisierungsbedingung nicht erfüllen. Um dies besser zu veranschaulichen, betrachten Sie das folgende Beispiel:

Ein Multiprozessorsystem besteht aus vier Prozessoren - P1, P2, P3 und P4, die alle zwischengespeicherte Kopien einer gemeinsamen Variablen S enthalten, deren Anfangswert 0 ist. Prozessor P1 ändert den Wert von S (in seiner zwischengespeicherten Kopie) auf 10, woraufhin Prozessor P2 ändert den Wert von S in seiner eigenen zwischengespeicherten Kopie auf 20. Wenn wir nur die Schreibausbreitung sicherstellen, dann werden P3 und P4 sicherlich die von P1 und P2 an S vorgenommenen Änderungen sehen . P3 kann jedoch die von P1 vorgenommene Änderung sehen, nachdem er die von P2 vorgenommene Änderung gesehen hat, und daher 10 bei einem Lesen zu S zurückgeben . P4 kann andererseits von P1 und P2 vorgenommene Änderungen in der Reihenfolge sehen, in der sie vorgenommen werden, und daher 20 bei einem Lesen zu S zurückgeben . Die Prozessoren P3 und P4 haben nun eine inkohärente Sicht auf den Speicher.

Um die Transaktionsserialisierung zu erfüllen und damit Cache-Kohärenz zu erreichen, muss daher die folgende Bedingung zusammen mit den beiden vorherigen in diesem Abschnitt genannten erfüllt sein:

  • Schreibvorgänge an denselben Speicherort müssen sequenziert werden. Mit anderen Worten, wenn der Standort X zwei verschiedene Werte A und B in dieser Reihenfolge von zwei beliebigen Prozessoren empfangen hat, können die Prozessoren den Standort X niemals als B lesen und ihn dann als A lesen. Der Standort X muss mit den Werten A und gesehen werden B in dieser Reihenfolge.

Die alternative Definition eines kohärenten Systems erfolgt über die Definition des sequenziellen Konsistenz Speichermodell: „the kohärentes System cache erscheinen alle Threads' Lade- und Speichervorgänge in eine zur Ausführung einzelnen Speicherstelle in einer Gesamt damit Hinsicht die Programmreihenfolge von jedem Thread“ . Somit besteht der einzige Unterschied zwischen dem Cache-kohärenten System und dem sequentiell konsistenten System in der Anzahl der Adressorte, über die die Definition spricht (ein einzelner Speicherort für ein Cache-kohärentes System und alle Speicherorte für ein sequentiell konsistentes System).

Eine andere Definition lautet: "ein Multiprozessor ist Cache-konsistent, wenn alle Schreibvorgänge in dieselbe Speicherstelle in einer gewissen sequentiellen Reihenfolge ausgeführt werden".

Selten, aber besonders bei Algorithmen, kann sich Kohärenz stattdessen auf den Ort der Referenz beziehen . Mehrere Kopien derselben Daten können gleichzeitig in verschiedenen Caches vorhanden sein, und wenn es den Prozessoren erlaubt ist, ihre eigenen Kopien frei zu aktualisieren, kann dies zu einer inkonsistenten Ansicht des Speichers führen.

Kohärenzmechanismen

Die beiden häufigsten Mechanismen der Kohärenz sichergestellt werden Snooping und verzeichnisbasierte , die jeweils ihre eigenen Vor- und Nachteile haben. Snooping-basierte Protokolle sind tendenziell schneller, wenn genügend Bandbreite verfügbar ist, da alle Transaktionen eine Anfrage/Antwort sind, die von allen Prozessoren gesehen wird. Der Nachteil ist, dass Snooping nicht skalierbar ist. Jede Anfrage muss an alle Knoten in einem System gesendet werden, was bedeutet, dass mit zunehmender Größe des Systems die Größe des (logischen oder physischen) Busses und die von ihm bereitgestellte Bandbreite wachsen müssen. Andererseits neigen Verzeichnisse zu längeren Latenzen (mit einer 3-Hop-Anfrage/Weiterleitung/Antwort), verbrauchen jedoch viel weniger Bandbreite, da Nachrichten Punkt-zu-Punkt und nicht gesendet werden. Aus diesem Grund verwenden viele der größeren Systeme (>64 Prozessoren) diese Art von Cache-Kohärenz.

Schnüffeln

Snooping, das erstmals 1983 eingeführt wurde, ist ein Prozess, bei dem die einzelnen Caches Adressenleitungen auf Zugriffe auf Speicherorte überwachen, die sie zwischengespeichert haben. Die Write-Invalidate-Protokolle und Write-Update-Protokolle verwenden diesen Mechanismus.
Für den Snooping-Mechanismus reduziert ein Snoop-Filter den Snooping-Verkehr, indem eine Vielzahl von Einträgen verwaltet wird, von denen jeder eine Cache-Zeile repräsentiert, die einem oder mehreren Knoten gehören kann. Wenn ein Ersetzen eines der Einträge erforderlich ist, wählt das Snoop-Filter das Ersetzen des Eintrags aus, der die Cache-Zeile oder -Zeilen darstellt, die den wenigsten Knoten gehören, wie aus einem Anwesenheitsvektor in jedem der Einträge bestimmt. Ein zeitlicher oder anderer Algorithmus wird verwendet, um die Auswahl zu verfeinern, wenn die wenigsten Knoten mehr als eine Cache-Zeile besitzen.

Verzeichnisbasiert

In einem verzeichnisbasierten System werden die gemeinsam genutzten Daten in einem gemeinsamen Verzeichnis abgelegt, das die Kohärenz zwischen Caches aufrechterhält. Das Verzeichnis fungiert als Filter, durch den der Prozessor um Erlaubnis bitten muss, einen Eintrag aus dem Primärspeicher in seinen Cache zu laden. Wenn ein Eintrag geändert wird, aktualisiert das Verzeichnis die anderen Caches mit diesem Eintrag entweder oder macht sie ungültig.

Verteilte gemeinsam genutzte Speichersysteme ahmen diese Mechanismen nach, um die Konsistenz zwischen Speicherblöcken in lose gekoppelten Systemen aufrechtzuerhalten.

Kohärenzprotokolle

Kohärenzprotokolle wenden Cache-Kohärenz in Mehrprozessorsystemen an. Die Absicht ist, dass zwei Clients niemals unterschiedliche Werte für dieselben gemeinsam genutzten Daten sehen dürfen.

Das Protokoll muss die grundlegenden Kohärenzanforderungen implementieren. Es kann auf das Zielsystem oder die Anwendung zugeschnitten werden.

Protokolle können auch als snoopy oder verzeichnisbasiert klassifiziert werden. Typischerweise verwendeten frühe Systeme verzeichnisbasierte Protokolle, bei denen ein Verzeichnis die gemeinsam genutzten Daten und die Mitbenutzer verfolgte. Bei Snoopy-Protokollen werden die Transaktionsanforderungen (zum Lesen, Schreiben oder Upgraden) an alle Prozessoren gesendet. Alle Prozessoren schnüffeln die Anfrage und reagieren entsprechend.

Die Schreibweiterleitung in Snoopy-Protokollen kann mit einer der folgenden Methoden implementiert werden:

Schreiben-ungültig
Wenn eine Schreiboperation an einer Stelle beobachtet wird, von der ein Cache eine Kopie hat, macht die Cache-Steuerung ihre eigene Kopie der abgetasteten Speicherstelle ungültig, was ein Lesen des neuen Werts aus dem Hauptspeicher bei seinem nächsten Zugriff erzwingt.
Schreiben-Update
Wenn eine Schreiboperation an einer Stelle beobachtet wird, von der ein Cache eine Kopie hat, aktualisiert der Cache-Controller seine eigene Kopie der abgesuchten Speicherstelle mit den neuen Daten.

Wenn der Protokollentwurf festlegt, dass jedes Mal, wenn eine Kopie der gemeinsam genutzten Daten geändert wird, alle anderen Kopien "aktualisiert" werden müssen, um die Änderung widerzuspiegeln, dann handelt es sich um ein Schreib-Aktualisierungs-Protokoll. Wenn der Entwurf festlegt, dass ein Schreiben in eine zwischengespeicherte Kopie durch einen beliebigen Prozessor erfordert, dass andere Prozessoren ihre zwischengespeicherten Kopien verwerfen oder ungültig machen, dann handelt es sich um ein Schreib-Ungültig-Protokoll.

Skalierbarkeit ist jedoch ein Manko von Broadcast-Protokollen.

Zur Aufrechterhaltung der Kohärenz wurden verschiedene Modelle und Protokolle entwickelt, wie MSI , MESI (alias Illinois), MOSI , MOESI , MERSI , MESIF , Write-Once , Synapse, Berkeley, Firefly und Dragon-Protokoll . Im Jahr 2011 schlug ARM Ltd den AMBA 4 ACE für den Umgang mit Kohärenz in SoCs vor . Die Spezifikation AMBA CHI (Coherent Hub Interface) von ARM Ltd , die zur AMBA5-Spezifikationsgruppe gehört, definiert die Schnittstellen für die Anbindung von vollständig kohärenten Prozessoren.

Siehe auch

Verweise

Weiterlesen