Cache-Kohärenz und Synchronisation

In diesem Kapitel werden wir die Cache-Kohärenzprotokolle besprechen, um die Multicache-Inkonsistenzprobleme zu bewältigen.

Das Cache-Kohärenzproblem

In einem Multiprozessorsystem können Dateninkonsistenzen zwischen benachbarten Ebenen oder innerhalb der gleichen Ebene der Speicherhierarchie auftreten. Beispielsweise können der Cache und der Hauptspeicher inkonsistente Kopien desselben Objekts enthalten.

Da mehrere Prozessoren parallel arbeiten und unabhängig voneinander mehrere Caches unterschiedliche Kopien desselben Speicherblocks besitzen können, entsteht das Cache-Kohärenzproblem. Cache-Kohärenzschemata helfen, dieses Problem zu vermeiden, indem ein einheitlicher Zustand für jeden gecachten Datenblock aufrechterhalten wird.

Angenommen, X sei ein Element gemeinsam genutzter Daten, das von zwei Prozessoren, P1 und P2, referenziert wurde. Zu Beginn sind drei Kopien von X konsistent. Wenn der Prozessor P1 neue Daten X1 in den Cache schreibt, wird dieselbe Kopie sofort in den gemeinsamen Speicher geschrieben, indem die Write-Through-Policy angewendet wird. In diesem Fall entsteht eine Inkonsistenz zwischen Cache-Speicher und Hauptspeicher. Wenn eine Rückschreibrichtlinie verwendet wird, wird der Hauptspeicher aktualisiert, wenn die geänderten Daten im Cache ersetzt oder ungültig gemacht werden.

Im Allgemeinen gibt es drei Quellen für Inkonsistenzprobleme –

• Gemeinsame Nutzung von beschreibbaren Daten
• Prozessmigration
• I/O-Aktivität

Snoopy-Bus-Protokolle

Snoopy-Protokolle erreichen Datenkonsistenz zwischen dem Cache-Speicher und dem gemeinsamen Speicher durch ein busbasiertes Speichersystem. Zur Aufrechterhaltung der Cache-Konsistenz werden Write-Invalidate- und Write-Update-Verfahren verwendet.

In diesem Fall haben wir drei Prozessoren P1, P2 und P3, die eine konsistente Kopie des Datenelements „X“ in ihrem lokalen Cache-Speicher und im gemeinsamen Speicher haben (Abbildung-a). Prozessor P1 schreibt X1 in seinen Cache-Speicher unter Verwendung des Protokolls für die Ungültigkeitserklärung von Schreibvorgängen. Alle anderen Kopien werden also über den Bus ungültig gemacht. Er wird mit „I“ bezeichnet (Abbildung-b). Ungültig gemachte Blöcke werden auch als „dirty“ bezeichnet, d. h. sie sollten nicht verwendet werden. Das Write-Update-Protokoll aktualisiert alle Cache-Kopien über den Bus. Bei Verwendung des Write-Back-Cache wird auch die Speicherkopie aktualisiert (Abbildung-c).

Cache-Ereignisse und -Aktionen

Bei der Ausführung von Speicherzugriffs- und Invalidierungsbefehlen treten folgende Ereignisse und Aktionen auf –

• Read-miss – Wenn ein Prozessor einen Block lesen will und dieser nicht im Cache vorhanden ist, tritt ein Read-miss auf. Dadurch wird ein Bus-Lesevorgang ausgelöst. Wenn keine Dirty Copy vorhanden ist, liefert der Hauptspeicher, der eine konsistente Kopie hat, eine Kopie an den anfordernden Cache-Speicher. Wenn eine Dirty Copy in einem entfernten Cache-Speicher vorhanden ist, hält dieser Cache den Hauptspeicher zurück und sendet eine Kopie an den anfordernden Cache-Speicher. In beiden Fällen geht die Cache-Kopie nach einem Lesefehler in den gültigen Zustand über.

• Write-hit – Wenn sich die Kopie in einem schmutzigen oder reservierten Zustand befindet, wird der Schreibvorgang lokal durchgeführt und der neue Zustand ist schmutzig. Wenn der neue Zustand gültig ist, wird der Befehl write-invalidate an alle Caches gesendet, wodurch deren Kopien ungültig werden. Wenn der gemeinsame Speicher durchgeschrieben wird, ist der resultierende Zustand nach diesem ersten Schreibvorgang reserviert.

• Write-miss – Wenn ein Prozessor nicht in den lokalen Cache-Speicher schreiben kann, muss die Kopie entweder aus dem Hauptspeicher oder aus einem entfernten Cache-Speicher mit einem schmutzigen Block stammen. Dies geschieht durch Senden eines read-invalidate-Befehls, der alle Cache-Kopien ungültig macht. Dann wird die lokale Kopie mit dem schmutzigen Zustand aktualisiert.

• Lesetreffer – Ein Lesetreffer wird immer im lokalen Cache-Speicher durchgeführt, ohne einen Zustandsübergang zu verursachen oder den Snoopy-Bus für die Invalidierung zu verwenden.

• Blockersetzung – Wenn eine Kopie schmutzig ist, muss sie mit der Blockersetzungsmethode in den Hauptspeicher zurückgeschrieben werden. Befindet sich die Kopie jedoch in einem gültigen, reservierten oder ungültigen Zustand, findet keine Ersetzung statt.

Verzeichnisbasierte Protokolle

Bei Verwendung eines mehrstufigen Netzwerks zum Aufbau eines großen Multiprozessors mit Hunderten von Prozessoren müssen die Snoopy-Cache-Protokolle entsprechend den Netzwerkfähigkeiten geändert werden. Da das Broadcasting in einem mehrstufigen Netzwerk sehr teuer ist, werden die Konsistenzbefehle nur an diejenigen Caches gesendet, die eine Kopie des Blocks besitzen. Dies ist der Grund für die Entwicklung von verzeichnisbasierten Protokollen für netzverbundene Multiprozessoren.

In einem verzeichnisbasierten Protokollsystem werden die gemeinsam zu nutzenden Daten in einem gemeinsamen Verzeichnis abgelegt, das die Kohärenz zwischen den Caches aufrechterhält. Hier fungiert das Verzeichnis als Filter, bei dem die Prozessoren um Erlaubnis bitten, einen Eintrag aus dem Primärspeicher in ihren Cache-Speicher zu laden. Wird ein Eintrag geändert, aktualisiert das Verzeichnis ihn entweder oder macht die anderen Caches mit diesem Eintrag ungültig.

Hardware-Synchronisationsmechanismen

Synchronisation ist eine besondere Form der Kommunikation, bei der anstelle der Datenkontrolle Informationen zwischen kommunizierenden Prozessen ausgetauscht werden, die sich im selben oder in verschiedenen Prozessoren befinden.

Multiprozessorsysteme verwenden Hardwaremechanismen, um Synchronisationsoperationen auf niedriger Ebene zu implementieren. Die meisten Multiprozessoren verfügen über Hardware-Mechanismen, um atomare Operationen wie Speicher-Lese-, Schreib- oder Lese-Änderungs-Schreib-Operationen zu erzwingen, um einige Synchronisationsprimitive zu implementieren. Neben atomaren Speicheroperationen werden auch einige Interprozessor-Interrupts für Synchronisierungszwecke verwendet.

Cache-Kohärenz in Maschinen mit gemeinsamem Speicher

Die Aufrechterhaltung der Cache-Kohärenz ist ein Problem in Multiprozessorsystemen, wenn die Prozessoren lokalen Cache-Speicher enthalten. In diesem System kommt es leicht zu Dateninkonsistenzen zwischen verschiedenen Caches.

Die wichtigsten Problembereiche sind –

• Teilung von beschreibbaren Daten
• Prozessmigration
• I/O-Aktivität

Teilung von beschreibbaren Daten

Wenn zwei Prozessoren (P1 und P2) dasselbe Datenelement (X) in ihren lokalen Caches haben und ein Prozess (P1) auf das Datenelement (X) schreibt, da die Caches durch den lokalen Cache von P1 geschrieben werden, wird auch der Hauptspeicher aktualisiert. Wenn nun P2 versucht, das Datenelement (X) zu lesen, findet er X nicht, weil das Datenelement im Cache von P2 veraltet ist.

Prozessmigration

In der ersten Phase hat der Cache von P1 das Datenelement X, während P2 nichts hat. Ein Prozeß auf P2 schreibt zunächst auf X und migriert dann zu P1. Nun beginnt der Prozess, das Datenelement X zu lesen, aber da der Prozessor P1 veraltete Daten hat, kann der Prozess sie nicht lesen. Also schreibt ein Prozess auf P1 in das Datenelement X und migriert dann zu P2. Nach der Migration beginnt ein Prozess auf P2 mit dem Lesen des Datenelements X, findet aber eine veraltete Version von X im Hauptspeicher vor.

I/O-Aktivität

Wie in der Abbildung dargestellt, wird in einer Zwei-Prozessor-Multiprozessor-Architektur ein I/O-Gerät zum Bus hinzugefügt. Zu Beginn enthalten beide Caches das Datenelement X. Wenn das E/A-Gerät ein neues Element X erhält, speichert es das neue Element direkt im Hauptspeicher. Wenn nun entweder P1 oder P2 (angenommen P1) versucht, Element X zu lesen, erhält es eine veraltete Kopie. Wenn nun P1 versucht, X zu übertragen, erhält es eine veraltete Kopie.

Uniform Memory Access (UMA)

Uniform Memory Access (UMA) Architektur bedeutet, dass der gemeinsame Speicher für alle Prozessoren im System gleich ist. Beliebte Klassen von UMA-Maschinen, die häufig für (Datei-)Server verwendet werden, sind die sogenannten symmetrischen Multiprozessoren (SMP). In einem SMP sind alle Systemressourcen wie Speicher, Festplatten, andere E/A-Geräte usw. für die Prozessoren auf einheitliche Weise zugänglich.

Non-Uniform Memory Access (NUMA)

In der NUMA-Architektur gibt es mehrere SMP-Cluster, die über ein internes indirektes/gemeinsames Netzwerk verfügen und über ein skalierbares Message-Passing-Netzwerk verbunden sind. Bei der NUMA-Architektur handelt es sich also um eine logisch gemeinsam genutzte, physisch verteilte Speicherarchitektur.

In einer NUMA-Maschine bestimmt der Cache-Controller eines Prozessors, ob ein Speicherverweis lokal zum SMP-Speicher gehört oder entfernt ist. Um die Anzahl der entfernten Speicherzugriffe zu reduzieren, werden in NUMA-Architekturen in der Regel Caching-Prozessoren eingesetzt, die die entfernten Daten zwischenspeichern können. Wenn jedoch Caches beteiligt sind, muss die Cache-Kohärenz aufrechterhalten werden. Daher werden diese Systeme auch als CC-NUMA (Cache Coherent NUMA) bezeichnet.

Cache Only Memory Architecture (COMA)

COMA-Maschinen ähneln den NUMA-Maschinen, mit dem einzigen Unterschied, dass die Hauptspeicher von COMA-Maschinen als Direct-Mapped- oder Set-Associative-Caches fungieren. Die Datenblöcke werden entsprechend ihrer Adressen an eine Stelle im DRAM-Cache gehasht. Daten, die aus der Ferne geholt werden, werden tatsächlich im lokalen Hauptspeicher gespeichert. Außerdem haben Datenblöcke keinen festen Heimatort, sondern können sich frei im System bewegen.

COMA-Architekturen haben meist ein hierarchisches Message-Passing-Netzwerk. Ein Schalter in einem solchen Baum enthält ein Verzeichnis mit Datenelementen als Unterbaum. Da die Daten keinen Heimatort haben, müssen sie explizit gesucht werden. Das bedeutet, dass ein Fernzugriff eine Traversierung entlang der Schalter im Baum erfordert, um deren Verzeichnisse nach den gewünschten Daten zu durchsuchen. Wenn also ein Switch im Netz mehrere Anfragen von seinem Teilbaum nach denselben Daten erhält, fasst er sie zu einer einzigen Anfrage zusammen, die an den übergeordneten Switch gesendet wird. Wenn die angeforderten Daten zurückkommen, sendet der Switch mehrere Kopien davon in seinen Teilbaum.

COMA versus CC-NUMA

Nachfolgend sind die Unterschiede zwischen COMA und CC-NUMA aufgeführt.

• COMA ist tendenziell flexibler als CC-NUMA, da COMA die Migration und Replikation von Daten transparent unterstützt, ohne dass das Betriebssystem benötigt wird.

• COMA-Maschinen sind teuer und komplex zu bauen, weil sie nicht standardisierte Speicherverwaltungshardware benötigen und das Kohärenzprotokoll schwieriger zu implementieren ist.

• Fernzugriffe in COMA sind oft langsamer als in CC-NUMA, da das Baumnetz durchquert werden muss, um die Daten zu finden.