Cache-Kohärenz – Enzyklopädie

 src=

Eine Abbildung, die mehrere Caches eines Speichers zeigt, der als gemeinsam genutzte Ressource fungiert.
 src=

Inkohärente Caches: Die Caches haben unterschiedliche Werte für einen einzelnen Adressort.

In der Computerarchitektur Cache-Kohärenz ist die Einheitlichkeit der gemeinsam genutzten Ressourcendaten, die 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 Multiprozessorsystem der Fall ist.

In der Abbildung rechts wird davon ausgegangen, dass beide Clients eine zwischengespeicherte Kopie eines bestimmten Speicherblocks aus einem früheren Lesevorgang haben. Angenommen, der Client im unteren Bereich aktualisiert / ändert diesen Speicherblock. Auf dem Client im oberen Bereich könnte ein ungültiger Speichercache verbleiben, ohne dass eine Benachrichtigung über die Änderung erfolgt. Die Cache-Kohärenz soll solche Konflikte bewältigen, indem eine kohärente Ansicht der Datenwerte in mehreren Caches beibehalten wird.

 src=

Kohärente Caches: Der Wert in allen Cachekopien ist derselbe.

Übersicht Bearbeiten

In einem Multiprozessorsystem mit gemeinsamem Speicher mit jeweils einem separaten Cache-Speicher 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 Kopien von Daten geändert wird, müssen die anderen Kopien diese Änderung widerspiegeln. Cache-Kohärenz ist die Disziplin, die sicherstellt, dass die Änderungen der Werte gemeinsam genutzter Operanden (Daten) rechtzeitig im System verbreitet werden. [1]

Die folgenden Anforderungen gelten für die Cache-Kohärenz: [2]

Schreibübertragung
Änderungen an den Daten in einem Cache müssen an andere Kopien (dieser Cache-Zeile) in den Peer-Caches übertragen werden.
Transaktionsserialisierung
Das Lesen / Schreiben an einen einzelnen Speicherort muss erfolgen gesehen von allen Prozessoren in derselben Reihenfolge.

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

Definition Bearbeiten

Kohärenz definiert das Verhalten von Lese- und Schreibvorgängen an einem einzelnen Adressort. ] [2]

Berücksichtigen Sie in einem Multiprozessorsystem, dass mehr als ein Prozessor eine Kopie des Speicherorts X zwischengespeichert hat. Die folgenden Bedingungen sind erforderlich, um eine Cache-Kohärenz zu erzielen: [4]

  1. Bei einem Lesevorgang von a Prozessor P an eine Stelle X, die auf ein Schreiben desselben Prozessors P an X folgt, wobei zwischen den von P ausgeführten Schreib- und Lesebefehlen kein Schreibvorgang eines anderen Prozessors auf X stattfindet. X muss immer den von P geschriebenen Wert zurückgeben. [19659020] Bei einem Lesevorgang eines Prozessors P1 an Position X, der auf einen Schreibvorgang eines anderen Prozessors P2 an X folgt, wobei zwischen den beiden Zugriffen keine weiteren Schreibvorgänge an X erfolgen und Lese- und Schreibvorgang ausreichend voneinander getrennt sind, muss X Liefert immer den von P2 geschriebenen Wert. Diese Bedingung definiert das Konzept der kohärenten Sicht auf das Gedächtnis. Durch die Weitergabe der Schreibvorgänge an den gemeinsam genutzten Speicherort wird sichergestellt, dass alle Caches eine kohärente Ansicht des Speichers haben. Wenn der Prozessor P1 den alten Wert von X auch nach dem Schreiben von P2 liest, können wir sagen, dass der Speicher inkohärent ist.

Die obigen Bedingungen erfüllen die für die Cache-Kohärenz erforderlichen Schreibausbreitungskriterien. Sie sind jedoch nicht ausreichend, da sie die Transaktionsserialisierungsbedingung nicht erfüllen. Betrachten Sie das folgende Beispiel, um dies besser zu veranschaulichen:

Ein Multiprozessorsystem besteht aus vier Prozessoren – P1, P2, P3 und P4, die alle zwischengespeicherte Kopien einer gemeinsam genutzten Variablen S enthalten, deren Anfangswert 0 ist. Prozessor P1 ändert den Wert von ] S (in seiner zwischengespeicherten Kopie) auf 10, woraufhin der Prozessor P2 den Wert von S in seiner eigenen zwischengespeicherten Kopie auf 20 ändert. Wenn wir nur die Schreibausbreitung sicherstellen, werden P3 und P4 mit Sicherheit sehen die von P1 und P2 an S vorgenommenen Änderungen. P3 kann jedoch die Änderung von P1 nach der Änderung von P2 sehen und daher 10 bei einem Lesevorgang an S zurückgeben. P4 hingegen kann Änderungen von P1 und P2 in der Reihenfolge sehen, in der sie vorgenommen wurden, und daher 20 bei einem Lesevorgang an S zurückgeben. Die Prozessoren P3 und P4 haben nun eine inkohärente Sicht auf den Speicher.

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

  • Schreibvorgänge an derselben Position müssen sequenziert werden. Mit anderen Worten, wenn der Ort X von zwei Prozessoren zwei unterschiedliche Werte A und B in dieser Reihenfolge erhalten hat, können die Prozessoren den Ort X niemals als B und dann als A lesen. Der Ort X muss mit den Werten A und gesehen werden B in dieser Reihenfolge. [5]

Die alternative Definition eines kohärenten Systems erfolgt über die Definition eines sequentiellen Konsistenzspeichermodells: "Das kohärente Cache-System muss so aussehen, dass es alle Ladevorgänge und Speicher in einem einzigen Speicher ausführt Position in einer Gesamtreihenfolge, die die Programmreihenfolge jedes Threads berücksichtigt. "[3] Der einzige Unterschied zwischen dem Cache-kohärenten System und dem sequenziell konsistenten System besteht in der Anzahl der Adresspositionen, von denen die Definition spricht (einzelne Speicherposition für einen 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 an derselben Speicherstelle in einer bestimmten Reihenfolge ausgeführt werden." [6]

Selten, aber insbesondere bei Algorithmen, kann Kohärenz auftreten Verweisen Sie stattdessen auf die Referenzstelle.
Es können mehrere Kopien derselben Daten gleichzeitig in verschiedenen Caches vorhanden sein. Wenn Prozessoren ihre eigenen Kopien frei aktualisieren können, kann dies zu einer inkonsistenten Speicheransicht führen.

Kohärenzmechanismen

Die beiden häufigsten Mechanismen zur Gewährleistung der Kohärenz sind Snooping und Directory-based mit jeweils eigenen eigene Vor- und Nachteile. Snooping-basierte Protokolle sind in der Regel 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 Anforderung muss an alle Knoten in einem System gesendet werden. Dies bedeutet, dass mit zunehmender Größe des Systems die Größe des (logischen oder physischen) Busses und die von ihm bereitgestellte Bandbreite zunehmen müssen. Auf der anderen Seite haben Verzeichnisse in der Regel längere Latenzen (mit einer 3-Sprung-Anforderung / Weiterleitung / Antwort), verbrauchen jedoch viel weniger Bandbreite, da Nachrichten Punkt-zu-Punkt sind und nicht gesendet werden. Aus diesem Grund verwenden viele der größeren Systeme (> 64 Prozessoren) diese Art der Cache-Kohärenz.

Snooping

Das 1983 erstmals eingeführte [7] Snooping ist ein Prozess, bei dem die einzelnen Caches Adresszeilen auf Zugriffe auf zwischengespeicherte Speicherstellen überwachen. [4] ] Die Protokolle zum Ungültigmachen des Schreibvorgangs und zum Aktualisieren des Schreibvorgangs verwenden diesen Mechanismus.
Beim Snooping-Mechanismus reduziert ein Snoop-Filter den Snooping-Verkehr, indem mehrere Einträge verwaltet werden wobei jede Zeile eine Cache-Zeile darstellt, die einem oder mehreren Knoten gehören kann. Wenn das Ersetzen eines der Einträge erforderlich ist, wählt der Snoop-Filter für das Ersetzen den Eintrag aus, der die Cache-Zeile oder -Zeilen darstellt, die den wenigsten Knoten gehören, wie aus einem Präsenzvektor in jedem der Einträge bestimmt. Ein zeitlicher oder ein anderer Algorithmus wird verwendet, um die Auswahl zu verfeinern, wenn mehr als eine Cache-Zeile den wenigsten Knoten gehört. [8]

Verzeichnisbasiert Bearbeiten

In einem Verzeichnis -basiertes System werden die gemeinsam genutzten Daten in einem gemeinsamen Verzeichnis abgelegt, das die Kohärenz zwischen den Caches aufrechterhält. Das Verzeichnis fungiert als Filter, über 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 oder ungültig macht das Verzeichnis die anderen Caches mit diesem Eintrag.

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

Kohärenzprotokolle [19659007] [ bearbeiten ]

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

Das Protokoll muss die grundlegenden Anforderungen für die Kohärenz 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 den Überblick über die gemeinsam genutzten Daten und die Sharer behalten würde. In Snoopy-Protokollen werden die Transaktionsanforderungen (zum Lesen, Schreiben oder Aktualisieren) an alle Prozessoren gesendet. Alle Prozessoren überwachen die Anforderung und antworten entsprechend.

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

Write-Invalidate
Wenn eine Schreiboperation an einem Speicherort beobachtet wird, von dem ein Cache eine Kopie hat, macht der Cache-Controller seine eigene Kopie des Snooping-Speicherorts ungültig, wodurch ein Lesen des neuen Werts aus dem Hauptspeicher erzwungen wird bei seinem nächsten Zugriff. [4]
Schreibaktualisierung
Wenn eine Schreiboperation an einer Stelle beobachtet wird, von der ein Cache eine Kopie hat, aktualisiert der Cache-Controller seine eigene Kopie des Snoops Speicherort mit den neuen Daten.

Wenn der Protokollentwurf besagt, dass alle anderen Kopien bei jeder Änderung einer Kopie der gemeinsam genutzten Daten "aktualisiert" werden müssen, um die Änderung widerzuspiegeln, handelt es sich um ein Schreibaktualisierungsprotokoll. Wenn der Entwurf besagt, dass ein Schreibvorgang in eine zwischengespeicherte Kopie von einem Prozessor erfordert, dass andere Prozessoren ihre zwischengespeicherten Kopien verwerfen oder ungültig machen, handelt es sich um ein Protokoll zum Ungültigmachen des Schreibvorgangs.

Die Skalierbarkeit ist jedoch ein Nachteil von Broadcast-Protokollen.

Verschiedene Modelle und Protokolle wurden entwickelt, um die Kohärenz aufrechtzuerhalten, z. B. das MSI-, MESI- (alias Illinois), MOSI-, MOESI-, MERSI-, MESIF-, Write-Once-, Synapse-, Berkeley-, Firefly- und Dragon-Protokoll. [1] 2011 , ARM Ltd schlug den AMBA 4 ACE [10] für den Umgang mit Kohärenz in SoCs vor.

Siehe auch Bearbeiten

Bearbeiten

  1. b E. Thomadakis, Michael (2011). Die Architektur des Nehalem-Prozessors und der Nehalem-EP-SMP-Plattformen (PDF) . Texas A & M Universität. p. 30. Aus dem Original (PDF) vom 11.08.2014.
  2. ^ a b Yan ,, Solihin ,. Grundlagen paralleler Multicore-Architektur . OCLC 884540034.
  3. ^ a b Sorin, Daniel J .; Hill, Mark D .; Wood, David Allen (01.01.2011). Eine Einführung in Speicherkonsistenz und Cache-Kohärenz . Morgan & Claypool Verlag. OCLC 726930429.
  4. ^ a b c Patterson und Hennessy. Computer Organisation und Design – 4. Auflage . ISBN 978-0-12-374493-7 .
  5. ^ Neupane, Mahesh (16. April 2004). "Cache-Kohärenz" (PDF). Archiviert aus dem Original (PDF) vom 20. Juni 2010.
  6. ^ Steinke, Robert C .; Nutt, Gary J. (2004-09-01). "Eine einheitliche Theorie der Shared Memory – Konsistenz". J. ACM . 51 (5): 800–849. arXiv: cs / 0208027 . doi: 10.1145 / 1017460.1017464. ISSN 0004-5411.
  7. ^ Ravishankar, Chinya; Goodman, James (28. Februar 1983). Cache-Implementierung für mehrere Mikroprozessoren (PDF) . Verfahren von IEEE COMPCON: 346–350 .
  8. ^ Rasmus Ulfsnes (Juni 2013). "Entwurf eines Snoop-Filters für Snoop-basierte Cache-Kohärenzprotokolle", archiviert am 01.02.2014 auf der Wayback-Maschine (PDF). diva-portal.org . Norwegische Universität für Wissenschaft und Technologie. Abgerufen am 20.01.2014.
  9. ^ https://people.eecs.berkeley.edu/~pattrsn/252F96/Lecture18.pdf
  10. ^ Kriouile. Formale Analyse der ACE-Spezifikation für Cache-kohärente On-Chip-Systeme. In formalen Methoden für industrielle kritische Systeme . Springer Berlin Heidelberg. ISBN 978-3-642-41010-9 .

Weiterführende Literatur [ Bearbeiten ]