Illinois-Protokoll

MESI (Modified Exclusive Shared Invalid) ist ein Protokoll zur Wahrung der Cache-Kohärenz in speichergekoppelten Multiprozessorsystemen. Das MESI-Protokoll wurde zuerst von Forschern der Universität von Illinois veröffentlicht. Es wird auch oft als Illinois-Protokoll bezeichnet.

Da in speichergekoppelten Multiprozessorsystem Systemen jeder Prozessor einen Cache besitzt, muss festgelegt werden, ob einer der Caches oder der Hauptspeicher den aktuellen Wert eines Datums enthält. Ein System, das zu jeder Zeit garantiert, den aktuellen Wert eines Datums zu beschaffen - auch wenn es sich in einem anderen Cache befindet -, heißt cache-kohärent.

Beim MESI-Protokoll werden jeder Cache-Line zwei Statusbits zugeordnet, durch die einer der folgenden vier Zustände beschrieben wird:

1. Modified oder Exclusive modified: Diese Cache-Line wurde lokal geändert. Die im Hauptspeicher befindliche (alte) Kopie ist daher ungültig. Will ein anderer Rechner diese Daten im Hauptspeicher lesen, so muss die Zeile zuerst vom Cache-Speicher in den Hauptspeicher zurückgeschrieben werden.
2. Exclusive oder Exclusive unmodified: Dieser Cache ist der einzige, der diesen Datenblock enthält. Der Wert im Hauptspeicher ist gültig. Liest ein anderer Rechner diese Daten im Hauptspeicher, so muss die Zeile als Shared gekennzeichnet werden. Werden die Daten im Hauptspeicher verändert, so müssen sie im Cache als ungültig erklärt werden, damit sie beim nächsten Zugriff neu aus dem Hauptspeicher geladen werden.
3. Shared unmodified: Mehrere Caches enthalten diesen Datenblock. Da alle aber bisher nur gelesen haben, ist der Wert im Hauptspeicher gültig. Schreibzugriffe auf eine Shared-Zeile müssen immer zu einem Zugriff auf den externen Bus führen um den Hauptspeicher nachzuführen damit die Zeilen in anderen Cache-Speichern als ungültig erklärt werden können.
4. Invalid: Der Inhalt dieser Cache-Line ist nicht aktuell oder es befindet sich noch gar kein Wert in dieser Cache-Line ("Compulsory Miss").

Übergänge zwischen den Zuständen

Die Übergänge zwischen diesen vier Zuständen können nun auf zwei verschiedene Arten ausgelöst werden: Entweder

• direkt durch das Schreiben oder Lesen der Daten vom Programm
• indirekt durch das Belauschen (Bus snooping) der Aktionen eines anderen Prozessors auf dem Bus durch den Cache. Dabei bedient sich ein Cache folgender Steuersignale:

1. Invalidate-Signal: Invalidieren der Zeile in den Caches anderer Prozessoren.
2. Shared-Signal: Signalisierung, ob ein zu ladender Speicherblock bereits als Kopie im Cache vorhanden ist.
3. Retry-Signal: Aufforderung an einen Prozessor, das Laden eines Blockes aus dem Hauptspeicher in den Cache abzubrechen, da der Hauptspeicher noch ein altes, ungültiges Datum besitzt und vorher aktualisiert werden muss. Das Laden kann danach wiederholt werden.

Ein Prozessor kann auf eine einzelne Adresse im Speichersystem schreibend oder lesend zugreifen. Entsprechend lösen Lese- und Schreiboperationen eines Prozessors Bustransaktionen aus. Beim MESI-Protokoll gibt es folgende Bustransaktionen:

1. Bus-Read (BusRd): Das Signal wird auf den Bus gelegt wenn ein Prozessor das Datum bzw. den Wert eines Speicherblocks lesen will.
2. Bus-Read-Exclusive (BusRdX): Signal wird auf den Bus gelegt wenn ein Prozessor das Datum eines Speicherblocks überschreiben will.
3. Flush: Dieses Signal wird erzeugt wenn ein Prozessor alleinig (evtl. noch der Hauptspeicher) das aktuelle Datum einer Speicherzelle in seinem Cache hat und ein weiterer Prozessor versucht auf die gleiche Adresse dieser Speicherzelle lesend oder schreibend zu zugreifen. Wenn das Signal Flush auf dem Bus erscheint, so wird ebenfalls das Datum der entsprechenden Speicherzelle auf den Bus gelegt.

Die Lese- und Schreiboperationen, sowie die dadurch direkt und indirekt erzeugten Bustransaktionen legen das Verhalten des Zustandsautomaten fest, welcher durch das MESI-Protokoll definiert ist (siehe Abbildung).

Beispiel

Angenommen sei ein Rechnersystem mit zwei Prozessoren, zwei Caches mit jeweils einer Cache-Line und gemeinsam genutztem Hauptspeicher, das das MESI Cache-Kohärenz-Protokoll anwendet.

Hauptspeicher     Cache A     Cache B
-------------------------------------
   Datum_1           -           -

Nun lädt Prozessor A das Datum 1, worauf dieses im Cache gespeichert wird. Dabei signalisiert Cache A an Cache B, dass Datum 1 geladen wird. Da Cache B keinen Eintrag für Datum 1 besitzt, signalisiert dieser nichts. Cache A kann also Datum 1 als Exclusive unmodified markieren.

Hauptspeicher     Cache A     Cache B
-------------------------------------
   Datum_1       E Datum_1       -

Daraufhin benötigt Prozessor B auch das Datum 1 und lädt dieses. Dabei signalisiert Cache B, dass Datum 1 geladen wird. Da Cache A schon einen Eintrag für Datum 1 besitzt, signalisiert er währenddessen Shared und beide Caches markieren ihren Eintrag als Shared unmodified.

Hauptspeicher     Cache A     Cache B
--------------------------------------
   Datum_1       S Datum_1   S Datum_1

Prozessor A hat seine Arbeiten mit Datum 1 abgeschlossen und ändert nun dessen Wert. Da Datum 1 mit Shared unmodified markiert ist, signalisiert Cache A beim Ändern des Eintrags Invalidate, woraufhin Cache B den Eintrag mit Invalid markiert. Cache A ändert den Wert von Datum 1 und markiert Datum 1 dann mit Exclusive modified, da nach dem Invalidate-Signal kein anderer Cache diesen Wert mehr vorrätig hat.

Hauptspeicher     Cache A     Cache B
---------------------------------------
   Datum_1       M Datum_1'   I Datum_1

Nun möchte Prozessor B mit Datum 1 arbeiten. Er fordert also von Cache B den Wert an. Jedoch hat Cache B diesen nicht vorrätig, da ein als Invalid markierter Eintrag wie ein nicht vorhandener Eintrag behandelt wird. Cache B versucht also Datum 1 aus dem Hauptspeicher zu laden. Dabei signalisiert er an Cache A, dass er dies tun möchte. Cache A erkennt aber, dass der Wert im Hauptspeicher nicht mehr aktuell ist, da er selbst einen Eintrag mit Datum 1 und der Markierung Exclusive modified besitzt. Also muss Cache A verhindern, dass der falsche Wert aus dem Hauptspeicher verwendet wird. Sofort sendet er das Retry-Signal. Cache B registriert dieses und bricht den Ladevorgang ab. Um Cache A genügend Zeit zu geben, wartet Cache B für eine kurze Zeitspanne. Derweil schreibt Cache A das aktuelle Datum 1 in den Hauptspeicher. Danach setzt er seinen eigenen Wert auf Exclusive unmodified, da der Wert nun aktuell ist und bisher kein anderer Cache den Wert zwischengespeichert hat.

Hauptspeicher     Cache A     Cache B
---------------------------------------
   Datum_1'       E Datum_1'  I Datum_1

Nach Ende der Wartezeit möchte nun Cache B endlich auch Datum 1 haben und liest dieses vom Hauptspeicher. Cache A registriert den Lesevorgang, signalisiert Shared und beide Caches haben das aktuelle Datum 1 mit der Markierung Shared unmodified eingetragen.

Hauptspeicher     Cache A     Cache B
---------------------------------------
   Datum_1'       S Datum_1'   S Datum_1'

Eine Weiterentwicklung des MESI-Protokolls ist das MOESI-Protokoll.

Literatur

• David E. Culler, Jaswinder Pal Singh: Parallel Computer Architecture - A Hardware/Software Approach Morgan Kaufmann, 1999, ISBN 1-55860-343-3

Weblinks

• Alternative Erklärung