DE69616226T2

DE69616226T2 - Ungültigkeitserklärungsbusoptimierung für Multiprozessoren mit verzeichnisbasierten Kohärenzprotokollen

Info

Publication number: DE69616226T2
Application number: DE69616226T
Authority: DE
Inventors: Sandra Johnson Baylor; Yarsun Hsu
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1995-09-25
Filing date: 1996-08-23
Publication date: 2002-06-27
Anticipated expiration: 2016-08-24
Also published as: EP0764905A1; US5778437A; EP0764905B1; KR970016951A; DE69616226D1; JP3320312B2; KR100234503B1; JPH0991255A

Description

Hintergrund der Erfindung

Technisches Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich im Allgemeinen auf Mehrprozessorsysteme, bei denen eine Vielzahl von Prozessoren mit jeweils einem privaten Cachespeicher unter Verwendung eines Mehrstufen-Kommunikationsnetzwerks mit einem gemeinsam genutzten Speicher verbunden sind, und im Besonderen auf die Verbesserung der Systemleistung anhand einer Ungültigkeitserklärungsbusoptimierung für Mehrprozessorsysteme unter Verwendung von verzeichnisbasierten Cachespeicher- Kohärenzprotokollen.

Beschreibung des Stands der Technik

Die Einführung von Parallelverarbeitungssystemen eröffnete die Möglichkeit einer höheren Leistung gegenüber herkömmlichen Einprozessorsystemen. Die Bandbreite des Hauptspeichers konnte jedoch bei derartigen Systemen nicht mit den Anforderungen durch die immer schnelleren Prozessoren Schritt halten. Ein Verfahren für die Schließung der Zugriffslücke, die sich aus diesem Problem ergibt, besteht darin, dem Prozessor einen kleinen Hochgeschwindigkeitspufferspeicher beizufügen, der als Cachespeicher bezeichnet wird. Dieser Cachespeicher ist in der Regel um eine ganze Größenordnung schneller als der Hauptspeicher und kommt im Allgemeinen der Geschwindigkeit des Prozessors gleich.
Mehrprozessorsysteme mit gemeinsam genutztem Speicher bestehen üblicherweise aus einer Anzahl von Prozessoren mit zugehörigen privaten Cachespeichern, einem globalen Speicher und einem Verbindungsnetzwerk zwischen den Prozessoren und einem Teil oder auch dem gesamten globalen Speicher. Der globale Speicher bildet den Hauptspeicher, der von den Prozessoren gemeinsam genutzt wird und häufig als eine Vielzahl von Speichermodulen ausgeführt ist. Die Einführung von mehreren Cachespeichern mit möglicherweise mehreren Kopien von Speicherzeilen in Systemen mit gemeinsam genutztem Speicher kann zu Dateninkonsistenzen führen. Generell gibt es zum gegenwärtigen Zeitpunkt zwei Verfahren für die Lösung dieses Problems: die hardwaregestützte und die softwaregestützte Cachespeicherkohärenz. Die vorliegende Erfindung bezieht sich auf ein in Hardware ausgeführtes Cachespeicher-Kohärenzprotokoll.
Hardwareprotokolle können in zwei Typen untergliedert werden: Busbasierte (bzw. "mithörende") sowie verzeichnisbasierte Protokolle. Busbasierte Protokolle kommen in der Regel bei Systemen mit einer verhältnismäßig geringen Anzahl von Prozessoren zum Einsatz, während verzeichnisbasierte Protokolle bei größeren Systemen mit einer höheren Skalierbarkeit verwendet werden. Bei verzeichnisbasierten Protokollen wird dem Hauptspeicher zumeist ein globales Verzeichnis zugewiesen, das im Wesentlichen Daten enthält, die den globalen Zustand einer Cachespeicherzeile sowie die Anzahl und/oder die Speicherstelle der Cachespeicher angeben, die über eine Kopie der Zeile verfügen.
Bei herkömmlichen verzeichnisbasierten Cachespeicher- Kohärenzprotokollen gibt es keinen globalen Mechanismus, der allen Prozessoren gleichzeitig die Übersicht über die Cachespeicher-Kohärenzaktivität ermöglicht. Aus diesem Grund wird ein globales Verzeichnis verwendet, um den globalen Zustand der Zeilen und die Identität bzw. die Anzahl der Prozessoren mit einer Kopie der Zeile zu erfassen. Wenn ein Prozessor versucht, eine Zeile zu modifizieren und nicht über die exklusive Lese/Schreib-Zugriffsberechtigung für die Zeile verfügt, sendet er eine Modifizierungsanforderung an den Eintrag in dem globalen Verzeichnis, der über ein Mehrstufen- Kommunikationsnetzwerk (MIN) der Zeile zugewiesen ist. Das Verzeichnis sendet dann Ungültigkeitserklärungen an die Prozessoren mit einer Kopie der Zeile bzw. überträgt Ungültigkeitserklärungen an alle Prozessoren, wenn die Identitäten der Prozessoren mit einer Kopie der Zeile nicht bekannt sind (ebenfalls über das MIN). Danach werden über das MIN Ungültigkeitsbestätigungen entweder zurück an das Verzeichnis oder aber an den Cachespeicher gesendet, der die Modifizierung der Zeile angefordert hat. Der Mehraufwand für die über das MIN übertragenen Ungültigkeitserklärungen und Ungültigkeitsbestätigungen verursacht eine erhebliche Konkurrenzsituation innerhalb des MIN und damit eine Verringerung der Leistung.
Zu Cachespeicher-Kohärenzprotokollen auf der Basis globaler Verzeichnisse wurden eine Reihe von Untersuchungen durchgeführt. Dazu zählen z. B. die folgenden Veröffentlichungen:
A. Agarwal, R. Simoni, J. Hennessy und M. Horowitz: "An Evaluation of Directory Schemes for Cache Coherence", Proceedings of the lSth Annual International Symposium on Computer Architecture, S. 280-289, Honolulu, Hawaii, IEEE Computer Society Press, 1988.
L. M. Censier und P. Feautrier: "A New Solution to Coherence Problems in Multicache Systems", IEEE Transactions an Computers, Bd. C-27, Nr. 12, S. 1112-1118, Dez. 1978.
M. Dubois und F. A. Briggs: "Effects of Cache Coherency in Multiprocessors", IEEE Transactions an Computers, Bd. C-31, Nr. 11, Nov. 1982.
Daniel Lenoski, James Landon, Kourosh Gharachorloo, Anoop Gupta und John Hennessy: "The Directory-Based Cache Coherency Protocol for the DASH Multiprocessor", Proc. of the l7th Annual International Symposium of Computer Architecture, Mai 1990, S. 148-159.
C. K. Tang: "Cache Systems Design in the Tightly Coupled Multiprocessor System", Proceedings of the 1976 National Computer Conference, S. 749-753, 1976.
W. C. Yen, D. W. L. Yen und K. 5. Fu: "Data Coherence Problem in a Multicache System", IEEE Transactions an Computers, S. 56- 65, Jan. 1985.
Keine dieser Untersuchungen berücksichtigt jedoch die Folgen, die sich aus einer Verringerung der Auswirkung von Netzwerklatenzzeiten, die durch Ungültigkeitserklärungen und die darauffolgenden Genehmigungssignalen verursacht werden, auf die Leistungsfähigkeit dieser Protokolle ergeben. Mehrprozessorsysteme mit Mehrstufen-Kommunikationsnetzwerken (MNI) und privaten Cachespeichern verwenden in der Regel ein verzeichnisbasiertes Cachespeicher-Kohärenzprotokoll zur Gewährleistung der Datenkonsistenz, wobei jedoch die Netzwerkverzögerung die Leistung derartiger Systeme begrenzen kann, da Prozessorschreiboperationen, die zu Ungültigkeitserklärungen führen, zwei Netzwerkumläufe benötigen.
L. N. Bhuyan und I. Ahmed stellten in "Analysis of MIN Based Multiprocessors With Private Cache Memories", Proceedings of the International Conference on Parallel Processing, Bd. I, S. 51-58, 1989, einen Mehrprozessor mit einem den Cachespeichern zugehörigen Snooping-Bus (der Prozessor "hört" bei Speicherzugriffen am Bus mit) sowie einem Verbindungsnetzwerk vor, das die Prozessoren mit den Speichermodulen verbindet. In ihrem System erfolgt sämtliche kohärenzbezogene Aktivität über diesen Bus. Da der Bus als globale Datenübertragungsquelle für das Mehrprozessorsystem dient, benötigt das Cachespeicherkohärenzprotokoll keine Ungültigkeitsbestätigungen. Das MIN wird ausschließlich für Datenübertragungen zwischen den Cachespeichern und dem Speicher verwendet. Bhuyan und Ahmed gehen davon aus, dass diese Architektur auf bis zu 64 Prozessor skaliert werden kann. Dabei besteht jedoch die Möglichkeit, dass mit steigender Anzahl der Prozessoren der Snooping-Bus gesättigt wird, so dass die Skalierbarkeit des Systems begrenzt ist.
M. 5. Algudady et. al. stellten in "A write-invalidate cache coherence protocol for MIN-Based Multiprocessors", International Journal of Mini and Microcomputers, Bd. 14, Nr. 1, S. 39-44, 1982, ein hardwaregestütztes Cachespeicher- Kohärenzprotokoll für MIN-basierte Mehrprozessorsysteme mit privaten Cachespeichern vor. Das Protokoll verwendet einen Kohärenzsteuerungsbus, der mit allen Cachespeicher- Steuereinheiten verbunden ist, sowie eine zentrale Tabelle mit gemeinsam genutzten Blockstatusdaten. Zeitsteuerungsprobleme aufgrund der unterschiedlich langen Durchlaufverzögerungen durch das MIN werden durch die Einführung von Übergangszuständen in diese Tabelle gelöst. Das Protokoll verursacht eine minimale Datenverkehrslast auf dem Kohärenzbus. Die Maßnahmen für die Systemleistung werden mit einer umfassenden Analysemethodik bewertet und durch Simulation überprüft. Dabei zeigt sich, dass dieses einfache Protokoll für mittelgroße MIN-basierte Systeme mit akzeptabler Busauslastung eingesetzt werden kann.

Zusammenfassung der Erfindung

Gemäß einem ersten Aspekt stellt die vorliegende Erfindung ein Mehrprozessorsystem mit gemeinsam genutztem Speicher nach Anspruch 1 bereit.
Gemäß einem zweiten Aspekt stellt die vorliegende Erfindung nach Anspruch 2 ein Ungültigkeitserklärungsprotokoll für die Gewährleistung der Cachespeicherkohärenz in einem Mehrprozessorsystem mit gemeinsam genutzten Speicher bereit.
Die vorliegende Erfindung stellt eine Optimierungsmethode für die Verwendung in Mehrstufen-Kommunikationsnetzwerken (MIN) zur Verfügung, die in skalierbaren Mehrprozessorsystemen zum Einsatz kommen, die eine Cachespeicherkohärenz ohne die üblicherweise bei derartigen Systemen auftretende Netzwerkverzögerung bereitstellen und dabei die Skalierbarkeit des Systems gewährleisten.
Genauer gesagt, die vorliegende Erfindung stellt darüber hinaus ein Cachespeicher-Kohärenzprotokoll auf der Basis eines globalen Verzeichnisses für skalierbare Mehrprozessorsysteme bereit, das den Nachteil der Netzwerklatenzzeit verringert und die Systemleistung verbessert.
Gemäß der vorliegenden Erfindung wird ein Ungültigkeitserklärungsbus ausschließlich für Ungültigkeitserklärungen oder für Ungültigkeitserklärungen und - bestätigungen verwendet. Die praktische Verwertung der bevorzugten Ausführungsform der Erfindung geht von einem Mehrprozessorsystem mit gemeinsam genutztem Speicher und privaten Cachespeichern, einem Mehrstufen- Kommunikationsnetzwerk (MIN) und verschachtelten Speichermodulen aus. Das Cachespeicher-Kohärenzprotokoll soll als ein verzeichnisbasiertes Protokoll ausgeführt werden. Der Gegenstand der Erfindung wurde insbesondere mit Blick auf die Verringerung des MIN-Mehraufwands für Ungültigkeitserklärungen und -bestätigungen bei verzeichnisbasierten Kohärenzprotokollen entworfen.
Die Optimierungsmethode gemäß der Erfindung beinhaltet einen Ungültigkeitserklärungsbus auf der Prozessorseite des Mehrstufen-Kommunikationsnetzwerks (MIN), um alle Daten in entfernten Cachespeichern ungültig zu setzen, wenn ein Prozessor die Modifizierung gemeinsam genutzter Daten versucht. Der Ungültigkeitserklärungsbus stellt den globalen Mechanismus bereit, der den Prozessoren die gleichzeitige Übersicht über die Ungültigkeitsaktivität des Kohärenzprotokolls ermöglicht. Da von einem verzeichnisbasierten Protokoll ausgegangen wird, muss das Verzeichnis trotzdem Zustandsinformationen über eine Cachespeicherzeile zur Verfügung halten. Der Gegenstand der Erfindung unterscheidet sich jedoch von herkömmlichen verzeichnisbasierten Protokollen insofern, als er die Identitäten der Cachespeicher mit einer Kopie der Zeile nicht kennen muss. Lediglich die tatsächliche Anzahl der Cachespeicher mit einer Kopie der Zeile muss bekannt sein. Aus diesem Grund sind, wenn eine Ungültigkeitserklärung auf den Bus gegeben wird, auch Ungültigkeitsbestätigungen erforderlich, damit das Verzeichnis weiß, dass alle Cachespeicher mit einer Kopie der Zeile ungültig gesetzt wurden.
Der Unterschied zwischen der Erfindung und der Architektur von Bhuyan und Ahmed besteht in der Tatsache, dass diese ein busbasiertes Cachespeicher-Kohärenzprotokoll verwenden. Die Cachespeicherkohärenz wird vollständig auf dem Bus realisiert. Im Gegensatz dazu verwendet der Gegenstand der Erfindung ein verzeichnisbasiertes Cachespeicher-Kohärenzprotokoll. Der größte Teil des Kohärenzprotokolls wird anhand des Verzeichnisses realisiert. Dies macht die Verwendung von Ungültigkeitserklärungen erforderlich, die für den Snooping- Bus-Ansatz von Bhuyan und Ahmed nicht benötigt werden. Gleichzeitig unterscheidet sich die Erfindung von herkömmlichen verzeichnisbasierten Protokollen dadurch, dass die Prozessoren nicht daraufhin überwacht werden müssen, ob sie eine Kopie der Zeile nicht verfolgt haben und dass ein Ungültigkeitserklärungsbus hinzugefügt wird, der für Ungültigkeitserklärungen verwendet wird. Nur die tatsächliche Anzahl der Prozessoren mit einer Kopie der Zeile ist erforderlich. Aus diesem Grund ist der Größenbedarf des globalen Verzeichnisses geringer und der Ungültigkeitserklärungsbus führt zu einer weniger ausgeprägten MIN-Konkurrenzsituation und damit zu einer verbesserten Leistung.
Das globale Verzeichnis wird in einer bevorzugten Ausführungsform als eine Vielzahl von globalen Verzeichnismodulen ausgeführt, die den Speichermodulen zugehörig sind und ein verteiltes globales Verzeichnis bilden. Der Ungültigkeitserklärungsbus dient zur Optimierung der Protokollaktion, die erforderlich ist, wenn ein Prozessor versucht, Daten auf eine gemeinsam genutzte Cachespeicherzeile zu schreiben. Ein Prozessor, der die Modifizierung von Daten in seinem Cachespeicher versucht, gibt die Adresse der Daten auf den Ungültigkeitserklärungsbus und sendet gleichzeitig eine Speicheranforderung an das globale Verzeichnis. Da alle Cachespeicher mit dem Ungültigkeitserklärungsbus verbunden sind, erkennen die Cachespeicher mit einer Kopie der Daten, dass die Daten modifiziert werden sollen und machen ihre Kopien daraufhin ungültig. Die Cachespeicher, die ihre Kopien ungültig setzen, senden außerdem Ungültigkeitsbestätigungssignale an das globale Verzeichnis. Gleichzeitig sendet der Prozessor die Speicheranforderung an das globale Verzeichnis. Das globale Verzeichnis wartet auf die Ungültigkeitserklärungen und sendet dann ein Genehmigungssignal an den Prozessor.
Ohne diesen Ungültigkeitserklärungsbus sind bei dem herkömmlichen verzeichnisbasierten Cachespeicher- Kohärenzprotokoll zwei Netzwerkumläufe erforderlich. Der Ungültigkeitserklärungsbus der Erfindung verbessert die Leistung von skalierbaren Systemen, indem sich Speicheranforderungen und Ungültigkeitserklärungen überlappen und so die Anzahl der Netzwerkumläufe verringert werden. Bhuyan und Ahmed gehen davon aus, dass ihr Ansatz auf bis zu 64 Prozessoren skaliert werden kann. Der Gegenstand der Erfindung verfügt über eine noch bessere Skalierbarkeit. Als Beispiel soll ein Mehrprozessorsystem mit P Prozessoren dienen, wobei die Hälfte der Prozessoren eine Nur-Lese-Kopie einer Cachespeicherzeile enthalten. Ein anderer Prozessor möchte die Zeile modifizieren, und danach versuchen alle P/2 Prozessoren eine Modifizierung der Zeile. Bei der Architektur nach Bhuyan und Ahmed gibt der Cachespeicher des ersten Prozessors ein Ungültigkeitserklärungssignal auf den Bus. Alle P/2 Prozessoren setzen danach ihre jeweiligen Kopien der Zeile ungültig, und die Zeile wird dann an den anfordernden Cachespeicher übertragen. Daraufhin versuchen alle P/2 Prozessoren, die Zeile zu modifizieren, indem sie Zugriff auf den Bus zu erlangen versuchen, um eine Ungültigkeitserklärung zu senden und eine Kopie der Zeile bereitzustellen. Üblicherweise ist ein Buszyklus erforderlich, um eine Ungültigkeitserklärung zu senden, sowie 1s/4 Buszyklen (wobei 1s die Zeilenlänge in Byte ist), um die Zeile über den Bus zu übertragen. Somit lautet die Anzahl der Buszyklen für die vollständige Durchführung der Transaktion wie folgt:
(P/2 + 1) (1 + 1s/4)
Die Skalierbarkeit des Mehrprozessorsystems wird durch die an den Bus gestellten Anforderungen begrenzt. In dem System nach Bhuyan und Ahmed stellt die obige Beziehung eine Näherung erster Ordnung der an den Bus gestellten Anforderungen dar.
Gemäß einer ersten Ausführungsform des Gegenstands der Erfindung werden ausschließlich Ungültigkeitserklärungen auf den Bus gegeben. Aus diesem Grund stellt sich die Gesamtzahl der Buszyklen, die für die vollständige Durchführung der Transaktion erforderlich sind, wie folgt dar:
P/2 + 1
In einer zweiten Ausführungsform der Erfindung beinhaltet die Gesamtzahl der erforderlichen Buszyklen die folgenden Ungültigkeitserklärungen und -bestätigungen, wobei die Ungültigkeitsbestätigungen einen Buszyklus in Anspruch nehmen sollen:
P + P/2 + 1
Bei einem System mit 64 Prozessoren und einer Zeilenlänge von 128 Byte erfordert die Architektur von Bhuyan und Ahmed 1089 Buszyklen. Im Gegensatz dazu benötigt die erste Ausführungsform des Gegenstands der Erfindung für die gleiche Anzahl an Prozessoren lediglich 33 Buszyklen, und die zweite Ausführungsform der Erfindung benötigt 97 Buszyklen. Als Ergebnis hat die erste Ausführungsform des Gegenstands der Erfindung somit eine um 1089/33 = 33-mal höhere Skalierbarkeit, während die zweite Ausführungsform eine um 1089/96 = 11-mal höhere Skalierbarkeit aufweist. Daher lässt sich die Erfindung bei der gleichen Leistung wie ein 64-Prozessor-System nach Bhuyan und Ahmed bei der ersten und zweiten Ausführungsform auf mindestens 64 · 33 = 2112 bzw. 64 · 11 = 704 Prozessoren skalieren.

Kurze Beschreibung der Zeichnungen

Die oben genannten und weitere Aufgaben, Aspekte und Vorteile werden aus der folgenden detaillierten Beschreibung einer bevorzugten Ausführungsform der Erfindung und mit Blick auf die Zeichnungen besser verständlich, wobei:
die Fig. 1A, 1B, 1C und 1D Funktionsblock-Darstellungen sind, die ein herkömmliches Ungültigkeitserklärungsprotokoll in einem Mehrprozessorsystem mit verzeichnisbasierter Cachespeicherkohärenz zeigen;
die Fig. 2A, 2B und 2C Funktionsblock-Darstellungen sind, die ein verbessertes herkömmliches Ungültigkeitserklärungsprotokoll zeigen;
Fig. 3 ein Funktionsschaltbild eines Systems mit einem Verzeichnis und einem Ungültigkeitserklärungsbus gemäß einer bevorzugten Ausführungsform der Erfindung ist;
die Fig. 4A, 4B und 4C Funktionsblock-Darstellungen sind, die das Ungültigkeitserklärungsprotokoll gemäß einer ersten Ausführungsform der Erfindung zeigen, bei der der Ungültigkeitserklärungsbus ausschließlich für Ungültigkeitserklärungen verwendet wird;
die Fig. 5 A und 5B Funktionsblock-Darstellungen sind, die das Ungültigkeitserklärungsprotokoll gemäß einer zweiten Ausführungsform der Erfindung zeigen, bei der der Ungültigkeitserklärungsbus sowohl für Ungültigkeitserklärungen als auch für Ungültigkeitsbestätigungen verwendet wird;
die Fig. 6A, 6B, 6C und 6D jeweils Zeitablaufdiagramme sind, welche die erforderliche Zeitdauer für die Verarbeitung einer Anforderung für das herkömmliche Ungültigkeitserklärungsprotokoll, das verbesserte herkömmliche Ungültigkeitserklärungsprotokoll und die ersten und zweiten Ausführungsformen der Erfindung zeigen; und
die Fig. 7A und 7B Hauptspeicherabbilder sind, die jeweils ein verteiltes Verzeichnis mit N Einträgen für die herkömmlichen Ungültigkeitserklärungsansätze und die ersten und zweiten Ausführungsformen gemäß der Erfindung zeigen.

Ausführliche Beschreibung der bevorzugten Ausführungsformen der Erfindung

Die Zeichnungen und hier insbesondere die Fig. 1B bis 1D zeigen das herkömmliche verzeichnisbasierte Ungültigkeitserklärungsprotokoll in einem Mehrprozessorsystem. Dabei wird von einem Mehrprozessorsystem mit einem Mehrstufen- Kommunikationsnetzwerk (MIN) ausgegangen. Sämtliche Datenübertragungen zwischen den Prozessoren und dem Verzeichnis laufen über das MIN (nicht abgebildet). In Fig. 1A gibt ein Prozessor P1 eine Modifizierungsanforderung an das Verzeichnis aus. Jeder der übrigen Prozessoren P2 bis PP soll einen Nur- Lese-Zugriff auf die Zeile(n) haben, für die die Modifizierungsanforderung gestellt wird, und diese Daten sind in dem Verzeichnis gespeichert. In Fig. 1B gibt das Verzeichnis Ungültigkeitserklärungen an jeden der übrigen Prozessoren P2 bis PP aus. Danach setzen die Prozessoren P2 bis PP in Fig. 1C ihre jeweiligen Kopien der Zeilen ungültig und senden Ungültigkeitsbestätigungen an das Verzeichnis. Erst nachdem das Verzeichnis alle Ungültigkeitsbestätigungen von jedem Prozessor mit einer Kopie der zu modifizierenden Zeile(n) empfangen hat, erteilt das Verzeichnis in Fig. 1D eine Genehmigung für die Modifizierungsanforderung durch den Prozessor.
Das herkömmliche Ungültigkeitserklärungsprotokoll wurde in den Fig. 2A bis 2C verbessert. Wie zuvor sendet der Prozessor in Fig. 2A eine Modifizierungsanforderung an das Verzeichnis, aber zusätzlich zur Sendung von Ungültigkeitserklärungen an jeden Prozessor P2 bis PP sendet das Verzeichnis auch eine vorläufige Genehmigung der Modifizierungsanforderung an den Prozessor P1. Die Genehmigung der Modifizierungsanforderung hat zur Bedingung, dass der Prozessor P1 eine vorgegebene Anzahl von Ungültigkeitsbestätigungen von den anderen Prozessoren empfängt, wobei diese vorgegebene Anzahl dem Prozessor P1 von dem Verzeichnis zusammen mit der vorläufigen Genehmigung der Modifizierungsanforderung übergeben wird. In Fig. 2C empfängt der Prozessor P1 die Ungültigkeitsbestätigungen direkt von jedem Prozessor P2 bis PP, woraufhin dem Prozessor P1 die Modifizierung der Zeile(n) gestattet wird.
Fig. 3 zeigt ein Funktionsblockschaltbild eines MIN-basierten Mehrprozessorsystems, in dem der Gegenstand der Erfindung ausgeführt ist. Das System beinhaltet ein Mehrstufen- Kommunikationsnetzwerk (MIN) 10, zu dem eine Vielzahl von Speichermodulen (mm) 121 bis 12 m gehört. Mehrstufen- Kommunikationsnetzwerke (MIN) sind in der Technik hinlänglich bekannt. In diesem Zusammenhang wird auf Chuan-Lin Wu und Tse- Yun Feng, "On a Class of Multistage Interconnection Networks", IEEE Transactions on Computers, Bd. C-29, Nr. 8. August 1980, 5. 694-702, verwiesen. Die Speichermodule 121 bis 12 m bilden den gemeinsam genutzten Hauptspeicher des Systems. Zum Hauptspeicher gehört ein globales Verzeichnis mit den Daten, die für die Angabe des globalen Zustands einer Cachespeicherzeile sowie der Anzahl und/oder der Speicherstelle der Cachespeicher mit einer Kopie der Zeile verwendet werden.
Das globale Verzeichnis des Systems aus Fig. 3 besteht aus einer Vielzahl von globalen Verzeichnismodulen 141 bis 14 m, die so verteilt sind, dass die Speichermodule ein verteiltes globales Verzeichnis (DGD) bilden. Das DGD 14 enthält Daten, mit denen der globale Zustand einer Cachespeicherzeile sowie die Anzahl und/oder Speicherstelle der Cachespeicher, die über eine Kopie der Zeile verfügen, angegeben werden. Außerdem sind eine Vielzahl von Cachespeichern (C) 18&sub1; bis 16p mit dem MIN 10 verbunden, bei denen es sich um die lokalen Cachespeicher für die zugehörigen Prozessoren (P) 18&sub1; bis 18p handelt. Jeder dieser Cachespeicher ist direkt mit einem Ungültigkeitserklärungsbus 20 verbunden, der, wie weiter unten ausführlicher beschrieben wird, die Verarbeitung eines Ungültigkeitserklärungsanforderung verbessert, die von einem der Prozessoren ausgegeben wird, und das Senden von Ungültigkeitserklärungen über das Netzwerk überflüssig macht.
Das verteilte globale Verzeichnis 14 weiß möglicherweise nicht, welche Cachespeicher über eine Kopie der Zeile verfügen. Für die Identifizierung der Cachespeicher bietet der Entwurf verschiedene Optionen. Bei einer Entwurfsalternative verfügt das Verzeichnis über Daten, die alle Cachespeicher mit einer Kopie der Zeile angeben. Bei einer anderen Entwurfsalternative gibt es pro Verzeichniseintrag eine kleine Anzahl von Bezeichnern für die Cachespeicher. Wenn die Anzahl der Cachespeicher, welche die Zeile gemeinsam nutzen, kleiner oder gleich der Anzahl der Bezeichner für die Cachespeicher ist, weiß das Verzeichnis, welcher Cachespeicher über die Zeile verfügt. Andernfalls kennt das Verzeichnis nur die Anzahl der Cachespeicher mit der Zeile.
Die Fig. 4A bis 4C zeigen das Ungültigkeitserklärungsprotokoll gemäß einer ersten Ausführungsform der Erfindung. In Fig. 4A gibt der Prozessor P1 eine Modifizierungsanforderung an das Verzeichnis aus und gibt gleichzeitig eine Ungültigkeitserklärungsanforderung auf den Ungültigkeitserklärungsbus. Die Prozessoren mit Kopien der zu modifizierenden Zeile(n), angegeben durch die Adresse(n) auf dem Ungültigkeitserklärungsbus, setzen die betreffenden Zeile(n) ungültig und senden eine Ungültigkeitsbestätigung an das Verzeichnis, wie aus Fig. 4B hervorgeht. Wenn das Verzeichnis alle Ungültigkeitsbestätigungen empfangen hat, erteilt es dem Prozessor P1 in Fig. 4C eine Genehmigung.
Die Fig. 5A und 5B zeigen das Ungültigkeitserklärungsprotokoll gemäß einer zweiten Ausführungsform der Erfindung. In Fig. 5 A gibt der Prozessor P1 eine Modifizierungsanforderung an das Verzeichnis aus und gibt gleichzeitig eine Ungültigkeitserklärungsanforderung auf den Ungültigkeitserklärungsbus. In Fig. 5B reagiert das Verzeichnis auf den Prozessor P1 mit einer vorläufigen Modifizierungsgenehmigung nach dem Empfang einer Anzahl von Ungültigkeitsbestätigungen, die der Anzahl der Prozessoren mit Kopien der zu modifizierenden Zeile(n) entspricht. Dieses Mal werden die Ungültigkeitsbestätigungen dem Prozessor P1 über den Ungültigkeitserklärungsbus direkt von den anderen Prozessoren bereitgestellt.
Die Fig. 6A bis 6C sind Zeitablaufdiagramme, welche die Leistungen mehrerer Protokolle einander gegenüberstellen. Die Funktionsweise des herkömmlichen Systems aus den Fig. 1A bis 1D ist in Fig. 6A abgebildet. Dabei soll die Netzwerkverzögerung vier Zeiteinheiten und ein Buszyklus eine Zeiteinheit umfassen. Da die Modifizierungsanforderung über das Netzwerk an das Verzeichnis gestellt werden muss, nimmt die Modifizierungsanforderung in Fig. 6A vier Zeiteinheiten in Anspruch. Entsprechend müssen die Ungültigkeitserklärungen über das Netzwerk von dem Verzeichnis an die übrigen Prozessoren übertragen werden, die eine Kopie der zu modifizierenden Zeile(n) halten, was weitere vier Zeiteinheiten in Anspruch nimmt. Die Ungültigkeitsbestätigungen müssen wiederum über das Netzwerk an das Verzeichnis übertragen werden, wofür weitere vier Zeiteinheiten erforderlich sind. Schließlich überträgt das Verzeichnis über das Netzwerk die Genehmigung der Modifizierungsanforderung an den anfordernden Prozessor, wofür weitere vier Zeiteinheiten benötigt werden. Insgesamt benötigt der Prozess somit 16 Zeiteinheiten.
Das verbesserte herkömmliche Protokoll aus den Fig. 2A bis 2C ist in Fig. 6B dargestellt. Die ersten beiden Zyklen entsprechen hier denjenigen des herkömmlichen Protokolls. Da die Genehmigung der Modifizierungsanforderung jedoch davon abhängt, dass der anfordernde Prozessor alle Ungültigkeitsbestätigungen direkt von den übrigen Prozessoren empfängt, überlappt sich der Genehmigungszyklus entweder mit dem Ungültigkeitserklärungszyklus oder dem Ungültigkeitsbestätigungszyklus, so dass sich eine Ersparnis von vier Zeiteinheiten ergibt.
Im Gegensatz zu den herkömmlichen und den verbesserten herkömmlichen Protokollen bringen die Ausführungsformen der Erfindung eine beträchtliche Zeitersparnis mit sich, welche die Leistung größerer Mehrprozessorsystem erheblich steigert. Das in den Fig. 4A bis 4C dargestellte Protokoll der ersten Ausführungsform ist in Fig. 6C abgebildet. Da die Modifizierungsanforderung gleichzeitig auf den Ungültigkeitserklärungsbus gegeben und über das Netzwerk an das Verzeichnis übertragen wird, tritt nur eine Busverzögerung von einem Zyklus auf, bevor die übrigen Prozessoren mit der Übertragung der Ungültigkeitsbestätigungen an das Verzeichnis beginnen. Somit überträgt das Verzeichnis mit einer Verzögerung von einem Buszyklus nach Empfang der Modifizierungsanforderung die Genehmigung über das Netzwerk an den anfordernden Prozessor. Dieser Zyklus ist in nur neun Zeiteinheiten abgeschlossen.
Das Protokoll gemäß der zweiten Ausführungsform führt zu noch größeren Zeitersparnissen und damit zu einer noch besseren Leistung. Dieses in den Fig. 5A und 5B dargestellte Protokoll ist in Fig. 6D abgebildet. In diesem Fall befinden sich auf dem Ungültigkeitserklärungsbus sowohl die Modifizierungsanforderung als auch die als Folge davon ausgegebenen Ungültigkeitsbestätigungen. Somit gibt das Verzeichnis sofort nach dem Empfang der Modifizierungsanforderung die vorläufige Genehmigung aus, so dass der Zyklus in nur acht Zeiteinheiten abgeschlossen ist.
Die Hauptspeicherabbilder für ein verteiltes globales Verzeichnis mit N Einträgen für ein herkömmliches verteiltes globales Verzeichnis mit N Einträgen sowie für das globale Verzeichnis mit N Einträgen für die erste und zweite Ausführungsform der Erfindung sind in den Fig. 7A bzw. 7B abgebildet. Bei dem herkömmlichen Verzeichnis aus Fig. 7A besteht ein Eintrag aus einem Verzeichniskennzeichen (dtag), einem globalen Zustand (gstate), einer Prozessorkennung (PID) für jeden der N Prozessoren, einer Ereignismarkierung (WTEVNT), die das Warten auf Rückschreib- oder Ungültigkeitsbestätigungen angibt, sowie einer Ereignismarkierung (RQEVNT) für das angeforderte Ereignis, das die Rückschreib-/ Ungültigkeitsbestätigungen verursacht hat. Für eine höhere Kompaktheit des Eintrags können die PIDs durch einen P-Vektor ersetzt werden, wobei jedes Bit für einen Prozessor steht. Im Gegensatz dazu ist das verteilte globale Verzeichnis mit N Einträgen der Erfindung sehr viel einfacher aufgebaut und benötigt weder PIDs noch P-Vektor. Wie aus Fig. 7B hervorgeht, sind für einen Eintrag in dem globalen Verzeichnis gemäß der praktischen Verwertung der vorliegenden Erfindung lediglich dtag, gstate sowie die Markierungen WTEVNT und RQEVNT erforderlich.

Claims

1. Mehrprozessorsystem mit gemeinsam genutztem Speicher, das Folgendes umfasst:

eine Vielzahl von Prozessoren (18&sub1; bis 18p) mit jeweils einem zugehörigen Cachespeicher (16&sub1; bis 16p);

ein Mehrstufen-Kommunikationsnetzwerk (10), das mit dem Cachespeicher eines jeden Prozessors verbunden ist;

eine Vielzahl von verschachtelten Speichermodulen (121 bis 12m), die mit dem Mehrstufen-Kommunikationsnetzwerk (10) verbunden sind;

ein globales Verzeichnis mit Daten für die Ermittlung eines globalen Zustands einer Cachespeicherleitung, wobei sich das globale Verzeichnis aus einer Vielzahl von globalen Verzeichnismodulen (14&sub1; bis 14 m) zusammensetzt, die ein verteiltes globales Verzeichnis (14) bilden, und wobei jedes Speichermodul ein zugehöriges globales Verzeichnismodul hat; und

einen Ungültigkeitserklärungsbus (20), der mit jedem Cachespeicher (161 bis 16p) direkt verbunden ist, einen Prozessor, der versucht, Daten zu modifizieren, indem er eine Adresse der zu modifizierenden Daten auf den Ungültigkeitserklärungsbus (20) gibt und gleichzeitig eine Speicheranforderung für die Datenmodifizierung an das globale Verzeichnis sendet, wobei die Speicheranforderung in das Mehrstufen-Kommunikationsnetzwerk gestellt wird, wobei alle Cachespeicher (16&sub1; bis 16p) eine Kopie einer Cachespeicherleitung haben, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, die ihre Kopien für ungültig erklärt, wobei das globale Verzeichnis ein Genehmigungssignal an den Prozessor überträgt, das die Modifizierung der Daten gestattet, wobei das Genehmigungssignal in das Mehrstufen- Kommunikationsnetzwerk gestellt wird;

dadurch gekennzeichnet, dass das globale Verzeichnis die Identitäten der Cachespeicher mit einer Kopie der Cachespeicherleitung nicht kennt, sondern vielmehr außerdem die tatsächliche Anzahl der Cachespeicher mit einer Kopie der Leitung enthält;

wobei ein Cachespeicher bei der Ungültigkeitserklärung einer Kopie einer Cachespeicherleitung, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, ein Ungültigkeitsbestätigungssignal an das globale Verzeichnis sendet, und wobei bei Empfang der Ungültigkeitsbestätigungssignale das globale Verzeichnis das Genehmigungssignal an den Prozessor sendet, der versucht, die Daten zu modifizieren,

oder wobei ein Cachespeicher bei der Ungültigkeitserklärung einer Kopie einer Cachespeicherleitung, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, ein Ungültigkeitsbestätigungssignal direkt an den Prozessor sendet, der versucht, Daten zu modifizieren, und wobei das globale Verzeichnis zusätzlich zu dem Genehmigungssignal einen Zählwert mit der Anzahl der Ungültigkeitsbestätigungen sendet, die er empfangen sollte.

2. Ungültigkeitserklärungsprotokoll für die Aufrechterhaltung der Cachespeicherkohärenz in einem Mehrprozessorsystem mit gemeinsam genutztem Speicher, in dem eine Vielzahl von verschachtelten Speichermodulen (12&sub1; bis 12 m) über ein Mehrstufen-Kommunikationsnetzwerk (10) mit einer Vielzahl von Prozessoren (16&sub1; bis 16p) verbunden sind, wobei jeder Prozessor einen zugehörigen Cachespeicher hat, wobei das Mehrprozessorsystem mit gemeinsam genutztem Speicher ein globales Verzeichnis mit Daten enthält, anhand derer ein globaler Zustand einer Cachespeicherleitung ermittelt wird, wobei sich das globale Verzeichnis aus einer Vielzahl von globalen Verzeichnismodulen (14&sub1; bis 14 m) zusammensetzt, die ein verteiltes globales Verzeichnis (14) bilden, wobei jedes Speichermodul ein zugehöriges globales Verzeichnismodul und einen Ungültigkeitserklärungsbus (20) hat, der direkt mit jedem Cachespeicher verbunden ist, wobei das Ungültigkeitserklärungsprotokoll die folgenden Schritte umfasst:

Aufgeben einer Adresse der zu modifizierenden Daten durch einen Prozessor, der versucht, Daten zu modifizieren, auf den Ungültigkeitserklärungsbus (20) gleichzeitig mit dem Senden einer Speicheranforderung für die Datenmodifizierung an das globale Verzeichnis, wobei die Speicheranforderung in das Mehrstufen- Kommunikationsnetzwerk gestellt wird, wobei alle Kopien aller Cachespeicher (16&sub1; bis 16P) mit einer Kopie einer Cachespeicherleitung, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, ungültig gemacht werden; und Senden eines Genehmigungssignals durch das globale Verzeichnis an den Prozessor, das die Modifizierung der Daten zulässt, wobei das in das Mehrstufen-Kommunikationsnetzwerk gestellte Genehmigungssignal dadurch gekennzeichnet ist, dass das globale Verzeichnis die Identitäten der Cachespeicher mit einer Kopie der Cachespeicherleitung nicht kennt, sondern vielmehr außerdem die tatsächliche Anzahl der Cachespeicher mit einer Kopie der Leitung enthält;

wobei ein Cachespeicher bei der Ungültigkeitserklärung einer Kopie einer Cachespeicherleitung, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, ein Ungültigkeitsbestätigungssignal an das globale Verzeichnis sendet; und wobei das globale Verzeichnis bei Empfang der Ungültigkeitsbestätigungssignale das Genehmigungssignal an den Prozessor sendet, der versucht, Daten zu modifizieren,

oder wobei ein Cachespeicher bei der Ungültigkeitserklärung einer Kopie einer Cachespeicherleitung, die durch die Adresse auf dem Ungültigkeitserklärungsbus (20) angegeben wird, ein Ungültigkeitsbestätigungssignal direkt an den Prozessor sendet, der versucht, Daten zu modifizieren; und wobei das globale Verzeichnis zusätzlich zu dem Genehmigungssignal einen Zählwert mit der Anzahl der Ungültigkeitsbestätigungen sendet, die der Prozessor empfangen sollte.