DE3621321A1

DE3621321A1 - Cache-speicher- bzw. multiprozessor-system und betriebsverfahren

Info

Publication number: DE3621321A1
Application number: DE19863621321
Authority: DE
Inventors: Jr Andrew W Wilson; Steven J Frank
Original assignee: Encore Computer Corp
Current assignee: Encore Computer Corp
Priority date: 1985-06-27
Filing date: 1986-06-26
Publication date: 1987-03-12
Also published as: JPS6284350A; AU5914386A; FR2584212B1; JP2540517B2; GB2178205B; GB8615639D0; FR2584212A1; AU585361B2; GB2178205A; US4755930A

Description

Die Erfindung betrifft ein hierarchisch gegliedertes Cache-Speichersystem, ein Multiprozessor-Rechnersystem mit Cache-Speichereinrichtungen bzw. ein Verfahren zum Arbeiten mit einem Cache-Speichersystem in einem Multiprozessor- bzw. Mikroprozessor-System.

Im Verlauf der letzten Jahre wurden viele Verfahren entwickelt, um Prozessoren und Speichereinheiten eines Systems von eng gekoppelten Prozessoren miteinander zu verbinden. Eine derartige Lösung bestand darin, eine Gruppe von Prozessoren auf einer Seite des Systems und eine Gruppe von Speichern auf der anderen Seite des Systems zu organisieren und ein zentrales Schaltnetzwerk zum Verbinden der Prozessoren mit den Speichern vorzusehen. Geräte mit gemeinsam benutztem Adressenraum, bei denen die Speicher unter den Prozessoren unter Verwendung eines hierarchisch gegliederten Verbindungsnetzwerks verteilt werden, wurden ebenfalls gebaut bzw. vorgeschlagen. Da die Schaltnetzwerke zu einer zusätzlichen Verzögerung führen und der Hauptspeicher häufig nicht schnell genug ist, um mit den Prozessoren Schritt zu halten, wird es erforderlich, jeden der Prozessoren durch einen diesem Prozessor individuell zugeordneten, gewissermaßen privaten Cache-Speicher zu ergänzen, um ein Laufen der Prozessoren mit voller Geschwindigkeit zu ermöglichen. Der Zusatz eines solchen privaten Cache-Speichers steigert andererseits die Probleme der Cache-Speicher-Kohärenz, die bei einem allgemeinen Schaltnetzwerk sehr schwierig zu lösen sind. Tatsächlich führt in den bisher vorgeschlagenen Systemen das Aufrechterhalten der Kohärenz zwischen den im Hauptspeicher und den in den Cache-Speichern gespeicherten Daten häufig zu Engpässen.

Ein anderes Verfahren zum Verbinden einer Gruppe von Prozessoren eines Multiprozessorsystems besteht in der Verbindung über einen gemeinsam benutzten Bus. Da der gesamte Datenverkehr zwischen den Cache- Speichern und dem Hauptspeicher über den gemeinsam benutzten Bus läuft, kann jeder Cache-Speicher bei einem solchen System sicherstellen, daß er nur gültige bzw. auf dem neuesten Stand befindliche Kopien der Daten der betreffenden Hauptspeicherbereiche enthält, und zwar durch Überwachen des Busses auf sämtliche Übertragungen, welche dazu führen könnten, daß die gespeicherten Daten nicht mehr gültig bzw. überholt sind. Während man bei gemeinsam benutzten Bussen häufig eine nicht angemessene Bandbreite bemängelt hat, führt andererseits die Verwendung von großen, privaten Cache-Speichern zu einer drastischen Reduzierung der erforderlichen Bandbreite, während sich gleichzeitig für die Prozessoren eine kurze effektive Zugriffszeit ergibt. Außerdem ist der zusätzliche Busverkehr, der sich aufgrund der Kohärenz-Algorithmen ergibt, vernachlässigbar, so daß praktisch die volle Bandbreite des Busses für die Handhabung echter Daten verfügbar ist. Wie bei Einzelprozessoren können die privaten Cache-Speicher zum Write-Through-Typ oder zum Write-Deferred-Typ gehören, wobei die Kohärenz-Schemen bzw. -Kriterien dem Cache-Speichertyp angepasst sind. Da die Bandbreite des Busses bei der Erweiterung dieser Systeme den grundsätzlichen Grenzwert bestimmt, werden im allgemeinen Write-Deferred-Schemen bevorzugt. Andererseits sind die Write-Through-Schemen einfacher zu realisieren.

Kohärenz-Probleme zwischen verschiedenen privaten Cache-Speichern in einem Multiprozessor-System entstehen dann, wenn mehrere private Cache-Speicher Kopien der Inhalte eines bestimmten Speicherbereichs bzw. einer bestimmten Speicherstelle enthalten. Offensichlich ist es wesentlich, daß diese Kopien identisch sind. Wenn ein Prozessor eine Kopie der Daten eines Speicherplatzes in seinem Cache-Speicher modifiziert, muß diese Änderung entweder an den Hauptspeicher oder an allen anderen privaten Cache-Speicher weitergegeben werden, die eine Kopie dieses Speicherbereichs enthalten. Eine andere Möglichkeit besteht darin, den Inhalt aller anderen Cache-Speicher für ungültig zu erklären. In der Praxis ist es gewöhnlich erforderlich, das Verfahren des Ungültigmachens (invalidation) anzuwenden, da hierdurch eine Anzahl von Ablaufproblemen überwunden wird, die sich ergeben können, wenn das Aufdatieren der Kopien des Speicherbereichs in anderen Cache-Speichern versucht wird. Bei Umschaltverfahren ohne den Einsatz von gemeinsam benutzten Bussen kann der Datenverkehr aufgrund der Übermittlung von Ungültigkeitsbefehlen ähnlich groß werden. Bei gemeinsam benutzten Bussen werden die entsprechenden Botschaften bzw. Befehle automatisch erzeugt.

Cache-Speicheranwendungen vom Write-Deferred-Typ wurden bei der Entwicklung von Einzelprozessoren erfolgreich angewandt, nachdem man festgestellt hatte, daß der Datenverkehr zum Hauptspeicher beim Write-Deferred- Betrieb deutlich kleiner ist als beim Write-Through- Betrieb. In der Theorie wird der Datenverkehr mit dem Hauptspeicher zu Null, wenn die Cache-Speicherkapazität gegen Unendlich wächst. Die derzeit in der Praxis verwendeten Cache-Speichergrößen ermöglichen es, den Busverkehr in einem Multiprozessorsystem beim Arbeiten im Write-Deferred-Betrieb um bis zu einer Größenordnung gegenüber dem Write-Through-Betrieb zu verringern, so daß potentiell die Möglichkeit besteht, die Anzahl der Prozessoren in einem Multiprozessorsystem mit gemeinsam benutztem Bus um eine Größenordnung oder mehr zu erhöhen. Die Notwendigkeit, die Datenkohärenz aufrecht zu erhalten, lässt die Situation jedoch komplizierter werden, und gewöhnlich werden eine Reihe von Ergänzungen gegenüber dem Grundschema für den Write-Deferred-Betrieb benötigt. Dabei ergibt sich letztlich ein komplizierteres System, bei dem der Bus stärker benutzt wird als bei einem im reinen Write-Deferred-Betrieb arbeitenden System, jedoch immer noch wesentlich weniger (pro Prozessor) als beim Arbeiten im Write-Through-Betrieb.

Die Einzelheiten und Besonderheiten des Write-Through- Betriebes und des Write-Deferred-Betriebes werden weiterhin in der Detailbeschreibung noch näher erläutert, wobei insbesondere auf das sogenannte Goodman-System eingegangen wird.

Wie im Falle des Write-Through-Cache-Speicherbetriebes überwachen in dem Goodman-System alle Cache-Speicher den Bus auf Schreibbefehle, welche ihre eigenen Daten betreffen und markieren diese Daten als ungültig, wenn sie einen derartigen Schreibbefehl erkennen. Nach der ersten Übertragung im Write-Through-Betrieb wird einem Cache-Speicher garantiert, daß er die einzige (gültige) Kopie eines Speicherbereichs enthält und daß in diesem Bereich Schreiboperationen ausgeführt werden können, ohne daß weitere Schreibbefehle auf den gemeinsamen Bus gesendet würden. Der Cache- Speicher muß jedoch den gemeinsamen Bus auf alle Lesebefehle an Speicherplätze überwachen, deren Kopien er verändert hat, da er nach einem solchen Lesebefehl nicht länger über eine exklusive Kopie des Speicherbereichs verfügt. Solange lediglich der erste Schreibbefehl im Write-Through-Betrieb aufgetreten ist, besteht die einzige Aktion, die für den Cache- Speicher erforderlich ist, der die Schreiboperation durchgeführt hatte, darin, zu vergessen, daß er eine exklusive Kopie des Speicherbereichs enthielt. Wenn zwei oder mehr Schreiboperationen von dem dem Cache- Speicher zugeordneten Prozessor durchgeführt wurden, dann enthält der Cache-Speicher die einzig gültige Kopie und muß daher für ein Aufdatieren des Inhalts des Hauptspeichers sorgen, ehe dieses auf einen Lesebefehl eines anderen Cache-Speichers antwortet.

Es gibt mehrere bekannte Systeme für das Aufdatieren des Hauptspeichers vor dem Antworten desselben auf einen Lesebefehl (einen Datenabruf) durch die anderen Cache-Speicher, um sicherzustellen, daß auf den Lesebefehl, der das Aufdatieren ausgelöst hat, die neueste Kopie des betreffenden Speicherbereichs ausgegeben wird. Bei diesen Systemen ist es im allgemeinen erforderlich, daß derjenige Cache-Speicher, welcher die geänderte Kopie enthält, den Hauptspeicher daran hindert, auf einen Lesebefehl zu antworten, ehe die geänderte Kopie zum Hauptspeicher zurückgeliefert wurde. Eine andere Möglichkeit besteht darin, eine spezielle Busanforderung auszugeben, welche die Antwort vom Hauptspeicher überläuft. Das erwähnte Goodman-System kann ferner derart modifiziert werden, daß der anfängliche Write-Through-Vorgang vermieden wird, wenn beim ersten Zugriff auf die Daten bekannt ist, daß keine anderen Kopien vorhanden sind. Es gibt einige Ablaufbedingungen, die eine gleichzeitige Modifikation von einander nicht überlappenden Teilen eines Blockes durch unterschiedliche Prozessoren und die Realisierung von Lese/Modifizier/Schreib-Verriegelungen erforderlich machen. Die dabei auftretenden Probleme sind jedoch bei sorgfältiger Auslegung lösbar.

Ein anderes bekanntes System, welches das Problem vermeidet, daß ungültige Daten in den Hauptspeicher zurückgeliefert werden, fügt jedem Block im Hauptspeicher ein "checked-out"-Bit hinzu. Wenn nun ein privater Cache-Speicher feststellt, daß er einen exklusiven Zugriff zu einem Speicherbereich benötigt, dann liest er den entsprechenden Speicherbereich des Hauptspeichers mit einem Lesebefehl "exklusiver Zugriff" aus, wodurch das "checked-out"-Bit gesetzt und das "Eigentum" des Speicherbereichs an den privaten Cache-Speicher übertragen wird. Andere Cache-Speicher, welche Kopien der betreffenden Daten enthalten, markieren diese Kopien als "ungültig", sobald sie den Lesebefehl "exklusiver Zugriff" auf dem Bus erfassen. Bei dieser Betriebsart wird also der einleitende Write-Through- Vorgang des Goodman-Systems durch einen speziellen Lesebefehl ersetzt. Während auf diese Weise die Notwendigkeit für einen anfänglichen Write-Through-Vorgang vermieden wird, ist der gesamte Datenverkehr, der sich aufgrund dieser Arbeitsweise auf dem Bus ergibt, mit demjenigen beim Goodman-System vergleichbar. Andererseits bietet diese Betriebsweise geradlinige Lösungen für die oben erwähnten Lese/Modifizier- Schreib-Verriegelungsprobleme.

Trotz der erhöhten Komplexität ist jede der oben skizzierten Write-Deferred-Lösungen im allgemeinen gegenüber einem Write-Through-Betrieb der Cache-Speicher zu bevorzugen. Die Reduzierung des Busverkehrs, die sich bei Write-Deferred-Cache-Speichern ergibt, macht derartige Cache-Speicher für ein Multiprozessorsystem mit gemeinsam benutztem Bus sehr wünschenswert, selbst wenn die Auslastung des Busses immer noch die Größe dieser Rechner begrenzt.

Ausgehend vom Stande der Technik und den vorstehend erläuterten Problemen liegt der Erfindung die Aufgabe zugrunde, ein Cache-Speichersystem für ein Multiprozessorsystem mit gemeinsam benutzten Buseinrichtungen anzugeben. Diese Aufgabe wird durch das hierarchisch gegliederte Cache-Speichersystem gemäß Patentanspruch 1 gelöst.

Weiterhin liegt der Erfindung die Aufgabe zugrunde, ein Cache-Speichersystem anzugeben, welches es gestattet, eine Multiprozessor-Anlage in mehrer Multiprozessoren aufzuteilen, die jeweils mehrere hierarchisch organisierte, gemeinsam benutzte Busse umfassen. Diese Aufgabe wird gemäß dem Patentanspruch 12 gelöst.

Dabei wird insbesondere angestrebt, daß die hierarchisch organisierten, gemeinsam benutzten Busse insgesamt mit einem möglichst geringen Datenverkehr belastet werden. In diesem Zusammenhang wird zusätzlich angestrebt, daß sowohl mit Write-Through-Cache-Speichern als auch mit Write-Deferred-Cache-Speichern gearbeitet werden kann.

Gemäß einem bevorzugten Ausführungsbeispiel der Erfindung umfasst ein Cache-Speichersystem für einen Multiprozessor mit gemeinsam benutztem Bus mehrere Prozessoren, von denen jeder seinen eigenen privaten Cache-Speicher hat. Jeder private Cache-Speicher ist dabei mit einem ersten Bus verbunden, mit dem auch ein zweiter Cache-Speicher verbunden ist, der zu einer höheren Ebene gehört. Der zweite Cache-Speicher ist seinerseits entweder mit einem weiteren Bus und mit einem Cache-Speicher einer noch höheren Ebene verbunden oder über einen globalen bzw. übergeordneten Bus mit dem Hauptsystemspeicher. Dabei besitzt jeder Cache-Speicher einer höheren Ebene genügend Speicherplatz, um eine Kopie jedes Speicherbereichs der Cache- Speicher auf der unmittelbar darunter befindlichen Ebene zu enthalten. Weiterhin enthält der Hauptspeicher genügend Speicherplatz, um eine Kopie jedes Speicherbereichs der Cache-Speicher der höchsten Ebene speichern zu können. Das erfindungsgemäße Cache-Speicher- System kann zum Aufrechterhalten der Datenkohärenz im Write-Through-Betrieb oder im Write-Deferred-Betrieb arbeiten. Ferner besteht bei einem erfindungsgemäßen System die Möglichkeit, den Hauptspeicher durch Speicher mit mehreren Ports bzw. Eingängen zu ersetzen.

Weitere Einzelheiten und Vorteile der Erfindung werden nachstehend anhand von Zeichnungen noch näher erläutert und/oder sind Gegenstand weiterer Ansprüche.

Es zeigen:

Fig. 1 ein Status-Diagramm eines Cache-Speicherbereichs für einen Multiprozessor auf der Basis von Write-Through-Cache-Speichern;

Fig. 2 ein Status-Diagramm für einen Cache- Speicherbereich eines Multiprozessors, der auf der Basis von Write-Deferred- Cache-Speichern arbeitet;

Fig. 3 eine schematische Darstellung eines hierarchisch gegliederten Multiprozessors mit zwei Ebenen von Cache-Speichern und gemeinsam benutzten Bussen;

Fig. 4 ein Status-Diagramm für einen Cache-Speicherbereich einer zweiten Ebene beim Arbeiten nach einem Multicache-Speicher- Kohärenz-Algorithmus gemäß der Erfindung;

Fig. 5 eine schematische Darstellung eines erweiterten Ausführungsbeispiels des Multiprozessorsystems gemäß Fig. 1, bei dem im Write-Through-Cache-Speicherbetrieb gearbeitet wird;

Fig. 6 eine schematische Darstellung einer weiteren abgewandelten Ausführungsform des Multiprozessorsystems gemäß Fig. 1 mit einem hierarchisch gegliederten Cache-Speichersystem, bei dem im Write- Deferred-Cache-Speicherbetrieb gearbeitet wird;

Fig. 7 eine schematische Darstellung eines Multiprozessorsystems mit einem Speicher mit zwei Ports;

Fig. 8 ein Status-Diagramm für ein Zwei-Port- Speichersystem, welches im Multicache- Speicher-Kohärenz-Betrieb gemäß der Erfindung arbeitet;

Fig. 9 eine schematische Darstellung eines Multiprozessors mit Speichern mit mehreren Ports und einem hierarchisch gegliederten Cache-Speichersystem gemäß der Erfindung;

Fig. 10 eine schematische Darstellung eines weiteren abgewandelten Ausführungsbeispiels des Multiprozessorsystems gemäß Fig. 5, und

Fig. 11 ein Status-Diagramm eines Cluster- bzw. Gruppen-Adapters, welcher nach einem Multicache-Speicher-Kohärenz- Schema gemäß der Erfindung arbeitet.

Ehe nachstehend im einzelnen auf die Erfindung eingegangen wird, soll zunächst anhand der Fig. 1 der Zeichnung das eingangs bereits erwähnte Write-Through-Cache- Speicher-Schema näher erläutert werden.

Bei einem Write-Through-Cache-Speicher-Schema bzw. -System wird immer dann, wenn ein Prozessor neue Daten in einen Speicherbereich seines zugeordneten Cache- Speichers einschreibt, der Schreibbefehl über den gemeinsam benutzten Bus an den Hauptspeicher weitergeleitet. Wie aus dem in Fig. 1 gezeigten Zustandsdiagramm für einen Cache-Speicherbereich eines Multiprozessorsystems mit Write-Through-Cache-Speicherbetrieb hervorgeht, überwachen alle anderen Cache-Speicher des Systems den gemeinsam benutzten Bus auf Schreibbefehle. Wenn irgendeiner der anderen Cache-Speicher eine Kopie des Inhalts der durch den Schreibbefehl aufgerufenen Speicherstelle enthält, dann wird diese Kopie bei Feststellung des Schreibbefehls ungültig gemacht. Wenn keiner der anderen Cache-Speicher diesen Speicherplatz jemals wieder tatsächlich braucht, dann führt das Kohärenzschema, d. h. die Notwendigkeit, eine Übereinstimmung der Daten an der betreffenden Speicherstelle im Hauptspeicher und in den diversen Cache- Speichern aufrecht zu erhalten, nicht zu einem zusätzlichen Datenaustausch über den Bus bzw. nicht zu einem zusätzlichen Busverkehr. Wenn der betreffende Speicherplatz zu einem späteren Zeitpunkt von ein oder mehreren Prozessoren aufgerufen wird (und zwar in den Cache- Speichern) dann führt dies dazu, daß eigens ein Zugriff zum Hauptspeicher erfolgen muß, um dort die Daten auszulesen. Simulationsversuche haben gezeigt, daß diese besonderen Auslesevorgänge nicht sehr häufig sind und sehr wenig zum zusätzlichen Busverkehr beitragen. Da die Cache-Speicher im Write-Through-Betrieb arbeiten, wird das Ausmaß des Verkehrs, d. h. der Datenübermittlung auf den Bus, niemals kleiner sein als die Summe aller von den Prozessoren erzeugten Speicher- Schreibbefehle, welche typischerweise etwa 15 bis 20% aller Zugriffe zum Hauptspeicher ausmachen. Der Write- Through-Cache-Speicherbetrieb ist außerordentlich effektiv, wenn eine begrenzte Parallelität (in der Größenordnung von 20 Prozessoren mittlerer Geschwindigkeit) gefordert wird und leicht zu verwirklichen.

Nachstehend soll nunmehr anhand der Fig. 2 eine spezielle Form eines der eingangs erwähnten Write-Deferred- Cache-Speichersysteme erläutert werden, bei denen eine Kohärenz bzw. Übereinstimmung der in den Cache-Speichern gespeicherten Daten aufrecht erhalten wird. In dem Aufsatz "Verwendung eines Cache-Speichers zur Verringerung des Verkehrs zwischen Prozessor und Hauptspeicher" (Tenth International Symposium on Computer Architecture) von Dr. James R. Goodman wird ein Cache-Speichersystem (eingangs als "Goodman-System" bezeichnet) beschrieben, welches anfänglich in einem Write-Through-Betrieb für neu angenommene Daten arbeitet, um die anderen Cache-Speicher (bzw. deren entsprechende Speicherstellen) für den Fall einer lokalen Änderung der Daten in den Zustand "ungültig" zu bringen. Wie das Zustandsdiagramm gemäß Fig. 2 im einzelnen zeigt, wird beim Goodman-System beim ersten Zugriff auf einen Hauptspeicherplatz der Cache-Speicher entweder in den Zustand "gültig" gebracht, wenn es sich um einen Lesebefehl handelt, oder in den Zustand "reserviert", wenn es sich um einen Schreibbefehl handelt. Wenn durch einen Prozessor ein Zugriff mit einem Schreibbefehl erfolgt, dann wird ein Speicherplatz, der sich schon im Zustand "gültig" befindet, in den Zustand "reserviert" gebracht. Der Schreibbefehl, welcher den Übergang in den Zustand "reserviert" bewirkt hat, wird durch den Cache-Speicher hindurchgeleitet und auf den gemeinsam benutzten Bus gegeben. Spätere Zugriffe des Prozessors mit Schreibbefehlen zu dem betreffenden Speicherplatz bringen diesen in einen besonderen Zustand, der anzeigt, daß der Cache-Speicher, in dem dieser Zustand vorliegt, die einzige korrekte Kopie des betreffenden Speicherplatzes enthält. Dieser spezielle Zustand wird als "schmutzig" (dirty) bezeichnet.

Nachdem vorstehend noch einmal ausführlich auf den relevanten Stand der Technik eingegangen wurde, soll nachstehend nunmehr die vorliegende Erfindung näher erläutert werden.

Im einzelnen zeigt Fig. 3 ein vereinfachtes Ausführungsbeispiel eines Multiprozessors 10 mit gemeinsamen Buseinrichtungen, bei dem ein erfindungsgemäßes Cache- Speichersystem verwirklicht ist, welches mehrere Cache- Speicher umfasst, die gemäß einer hierarchischen Gliederung geordnet sind. Unter hierarchisch ist dabei zu verstehen, daß die einzelnen Cache-Speicher relativ zueinander auf unterschiedlichen Niveaus liegen, wobei die Cache-Speicher eines oder mehrerer Niveaus über einen gemeinsam benutzten Bus mit einem Cache- Speicher eines höheren Niveaus verbunden sind. Diese Cache-Speicher auf dem höheren Niveau können ebenfalls zusammen mit ein oder mehreren Cache-Speichern desselben Niveaus entweder mit dem Hauptspeicher oder mit einem Cache-Speicher eines noch höheren Niveaus verbunden sein.

Bei dem Ausführungsbeispiel gemäß Fig. 3 sind Cache- Speicher auf zwei Niveaus und zwei gemeinsam benutzte Busse vorgesehen, wobei jedem Prozessor 12 ein Cache- Speicher 14 zugeordnet ist und wobei jeder der Cache- Speicher 14 mit einem ersten gemeinsam benutzten Bus 16 verbunden ist. Der Bus 16 ist außerdem mit einem Cache-Speicher 18 eines zweiten, höheren Niveaus verbunden, welcher seinerseits mit einem zweiten Bus 20 des höheren Niveaus verbunden ist, wobei der Bus 20 gemeinsam von allen Cache-Speichern 18 des zweiten höheren Niveaus benutzt wird. Der Bus 20 verbindet die Hauptspeichermodule 22 mit den zum zweiten Niveau bzw. zu der zweiten Ebene gehörigen Cache-Speicher 18. Fig. 3 zeigt also ein hierarchisch gegliedertes Cache- Speichersystem, bei dem ein Bussystem für die den Prozessoren individuell zugeordneten Cache-Speicher mit mehreren zusätzlichen Ebenen für die Cache-Speicherung verwirklicht ist. In der sich dabei ergebenden baumartigen Struktur bilden die Cache-Speicher der jeweils höheren Ebene die Verbindungsglieder zu niedrigeren Zweigen des Baums. Die Cache-Speicher der höheren Ebene, wie z. B. der Cache-Speicher 18, wirken wie Filter und reduzieren damit den Umfang des Verkehrs bzw. Datenaustauschs zu den oberen Ebenen des Baums. Die Cache- Speicher einer höheren Ebene sorgen auch für die Kohärenzsteuerung zwischen den einzelnen Ebenen, so daß eine systemweite Adressierbarkeit möglich wird.

Da der größte Teil der Prozessorbeschleunigung durch die Cache-Speicher 14 der unteren Ebene erreicht wird, können die Cache-Speicher 18 der höheren Ebene langsamere, dynamische Speicher mit wahlfreiem Zugriff (DRAMs) und mit höherer Packungsdichte sein, die mit den Speichern identisch sein können, die als Hauptspeichermodule 22 verwendet werden. Die mittlere Zugriffszeit wird noch weiter verringert, da Schaltverzögerungen auf einer höheren Ebene bei Treffern vermieden werden (d. h. dann, wenn ein Zugriff zu einer Speicherstelle bzw. einem Speicherbereich des Hauptspeichers erfolgen soll, dessen Inhalt bereits im Cache- Speicher des betreffenden Prozessors gespeichert ist). Um aus den Cache-Speichern einer höheren Ebene einen optimalen Nutzen zu ziehen, müssen diese groß sein, und zwar um eine Größenordnung größer als sämtliche, damit verbundenen Cache-Speicher der nächst niedrigeren Ebene, welche diese Cache-Speicher speisen. Da die Cache-Speicher der höheren Ebene DRAMs sein können, stellt dies kein Problem dar. Die Cache-Speicher der zweiten und höherer Ebenen (Speicher 18 beim Ausführungsbeispiel gemäß Fig. 3) in dem hierarchisch gegliederten System benötigen einige Erweiterungen, um eine systemweite Multi-Cache-Speicher-Kohärenz aufrecht zu erhalten. Die wichtigste Erweiterung besteht darin, daß für jeden Speicherbereich, für den Kopien in den Cache- Speichern des niedrigeren Niveaus vorhanden sind, auch eine Kopie in dem Cache-Speicher höheren Niveaus vorhanden ist. Wie das Zustandsdiagramm gemäß Fig. 4 zeigt, wird dies bei dem betrachteten System dadurch erreicht, daß immer dann das Signal "ungültig machen" an die Cache-Speicher des niedrigeren Niveaus gegeben wird, wenn der Inhalt eines Speicherbereichs aus dem zugeordneten Cache-speicher der nächst höheren Ebene entfernt wird. Da alle Kopien von Speicherplätzen bzw. -bereichen der Cache-Speicher der unteren Ebene auch in dem Cache-Speicher (den Cache-Speichern) der höheren Ebene vorhanden sind, kann der Cache-Speicher der höheren Ebene als Multicachespeicher-Kohärenz-Monitor für alle Cache-Speicher der niedrigeren Ebene dienen, die mit ihm verbunden sind.

Das Write-Deferred-Cache-Speicherschema, welches in vorliegender Erfindung benutzt wird, ist dem Goodman- System insofern ähnlich, als in beiden Systemen für jeden Cache-Speicherbereich vier verschiedene Zustände möglich sind. Die Cache-Speicher der höheren Ebene senden jedoch gemäß der Erfindung dann, wenn es erforderlich ist, die Multi-Cache-Speicher-Kohärenz aufrecht zu erhalten, an die Cache-Speicher der niedrigeren Ebene den Befehl, die betreffenden Daten ungültig zu machen bzw. zu löschen (wegzuspülen/flush). Der Befehl, die Daten ungültig zu machen, wird von den Cache-Speichern der unteren Ebene ähnlich behandelt wie ein Schreibbefehl auf dem Bus, während der Befehl, die Daten zu löschen, ähnlich behandelt wird wie ein Lesebefehl auf dem Bus.

Die Multi-Cache-Speicher-Kohärenzkontrolle kann bei einem hierarchisch gegliederten Multiprozessor gemäß der Erfindung mit gemeinsam benutzten Buseinrichtungen erreicht werden, indem man entweder Write-Through-Cache- Speicher oder Write-Deferred-Cache-Speicher verwendet. Wenn bei den im Write-Through-Betrieb arbeitenden Multi- Cache-Speichersystem gemäß Fig. 5 ein Prozessor 12 einen Schreibbefehl an den Hauptspeicher abgibt, dann wird dieser Schreibbefehl nach oben durch die Hierarchie von Cache-Speichern hindurchgefiltert und erscheint auf jeder Ebene auf dem zugeordneten, gemeinsam benutzten Bus. Beispielsweise gelangt ein Schreibbefehl vom Prozessor 12 b von dem Cache-Speicher 14 b zum Bus 16 a und von dort zum Cache-Speicher 18 a und schließlich auf den Bus 20. Beim Ausführungsbeispiel stellt die horizontale Linie 15 in den verschiedenen Speichereinheiten eine gemeinsame Speicherstelle bzw. einen gemeinsamen Speicherbereich dar. Für die Teile des Systems, mit denen der Cache-Speicher 12 b direkt verbunden ist, erfolgt das Ungültigmachen ebenso wie dies oben für den Fall einer einzigen Ebene beschrieben wurde. Zusätzlich wird jeder Cache-Speicher, der eine Kopie des betroffenen Speicherbereichs 15 enthält (beispielsweise der Cache-Speicher 14 c), diesen Speicherbereich einfach ungültig machen. Für die Cache-Speicher auf höheren Ebenen der Hierarchie bedingt das Vorhandensein eines bestimmten Speicherbereichs, daß dort Kopien des Speicherbereichs vorhanden sein können, welche auf Ebenen direkt unterhalb des Cache-Speichers erhalten geblieben sein könnten. Wenn beispielsweise der Cache-Speicher 18 c auf der zweiten Ebene in Fig. 5 einen Schreibzugriff auf dem Bus 20 feststellt, muß er nicht nur seinen eigenen Speicher ungültig machen, sondern auch einen Befehl zum Ungültigmachen an die mit ihm verbundenen Cache-Speicher der unteren Ebene senden, die die Information des betreffenden Speicherplatzes enthalten. Bei dem Beispiel gemäß Fig. 5 werden die Signale zum Ungültigmachen der Daten an die Cache-Speicher 14 g, 14 i gesandt. Um das Ungültigmachen zu erreichen, wird ein Befehl "Ungültigmachen" auf den Bus 16 c gegeben, und dieser Befehl wird durch die Cache-Speicher 14 g, 14 h und 14 i als eine Schreib-Transaktion für den betreffenden Speicherplatz interpretiert. Die genannten Cache-Speicher machen daraufhin, falls vorhanden, ihre eigenen Kopien ungültig, ebenso als wenn der Befehl "Ungültig machen" ein Schreibbefehl von irgendeinem anderen Cache-Speicher auf dem gemeinsam benutzten Bus wäre. Bei einem solchen System wird davon ausgegangen, daß irgendwelche Kopien des Inhalts von Speicherstellen, die auf den unteren Ebenen vorhanden sind, auch in den zugeordneten Cache-Speichern auf den höheren Ebenen vorhanden sind. Um dies zu garantieren, ist es erforderlich, den Befehl "Ungültig machen" immer dann an die Cache-Speicher der unteren Ebene zu senden, wenn eine Speicherstelle auf einer höheren Ebene aufgrund eines Fehlers ausgewechselt wird. Folglich ist es wichtig, die Fehlerquote in den Cache-Speichern der oberen Ebene niedrig zu halten, und diese Cache-Speicher müssen groß sein, um dies zu erreichen.

Bei einem hierarchisch gegliederten Cache-Speichersystem gemäß vorliegender Erfindung, bei dem Write-Deferred- Cache-Speicher verwendet werden, ist die Operation zum Ungültigmachen sehr ähnlich wie diejenige, die bei Write-Through-Systemen verwendet wird. Bei einem hierarchisch aufgebauten Write-Deferred-Cache-Speichersystem dienen der Write-Through-Vorgang des Goodman-Systems oder der Lesebefehl mit exklusivem Zugriff, bei dem mit einem besonderen Bit im Hauptspeicher gearbeitet wird, wie dies bei den anderen, eingangs angesprochenen Systemen der Fall ist, dazu, das Ungültigmachen in derselben Weise einzuleiten wie die Schreibbefehle bei einem ständig im Write-Through-Betrieb arbeitenden Cache-Speichersystem. Speziell bei der Ausführungsform der vorliegenden Erfindung, bei der mit einem hierarchisch gegliederten Write-Deferred-Cache-Speichersystem ähnlich dem Goodman-System gearbeitet wird, wird der anfängliche Write-Through-Vorgang dazu benützt, die Speicherplätze in den anderen Cache-Speichern ungültig zu machen. Bei den Ausführungsbeispielen, bei denen mit exklusivem Zugriff durch den Lesebefehl und einem Extra-Bit gearbeitet wird, macht der Lesebefehl nicht nur die Daten in den anderen Cache-Speichern ungültig, sondern setzt außerdem ein Bit im Hauptspeicher, welches anzeigt, daß in einem der Cache-Speicher eine "private" Kopie des Speicherplatzes vorhanden ist.

Probleme ergeben sich jedoch nach dem anfänglichen Ungültigmachen, wenn andere Prozessoren erneut einen Zugriff zu den Daten fordern. Wie bei den Einebenen- Cache-Speichersystemen müssen alle Cache-Speicher die gemeinsam benutzten Busse auf Lesebefehle für Speicherplätze bzw. -bereiche überwachen, von denen sie exklusive Kopien gemacht haben. Bei einem nachfolgenden Lesevorgang von einem anderen "privaten" Cache-Speicher wird bei dem Ausführungsbeispiel mit einem Cache-Speichersystem vom Goodman-Typ derjenige Cache-Speicher mit der gültigen Kopie dem Hauptspeicher 24 signalisieren, daß dieser nicht antworten soll und daraufhin (die Daten im Hauptspeicher) durch die Daten seiner eigenen Kopie der betreffenden Speicherstelle ersetzen. Bei einem anschließenden Lesebefehl von einem anderen Prozessor in einem System mit exklusivem Lesezugriff wird das gesetzte Bit im Hauptspeicher 22 verhindern, daß der Hauptspeicher antwortet, und der Cache-Speicher mit der gültigen Kopie des betreffenden Hauptspeicherbereichs wird stattdessen antworten. Zusätzlich muß dann, wenn der Status eines Cache-Speichers anzeigt, daß es eine "schmutzige" Kopie in einem in der Hierarchie darunter befindlichen Cache-Speicher geben könnte, von diesem Speicher ein Löschbefehl für den betreffenden Speicherplatz nach unten zu dem fraglichen Cache-Speicher gesendet werden. Derartige Löschbefehle müssen nach unten zu niedrigeren Ebenen der Hierarchie weiterlaufen und bewirken, daß die Cache-Speicher der unteren Ebene ihren Zustand in den Status "gültig" ändern, gerade so, als ob ein tatsächlicher Lesebefehl für diese Speicherstelle auf den von ihnen gemeinsam benutzten Bussen gesehen worden wäre.

Fig. 6 zeigt einen typischen Fall, bei dem ein hierarchisch gegliedertes Write-Deferred-Cache-Speichersystem verwendet wird. Unter der Voraussetzung, daß die Cache- Speicher 14 b und 18 a exklusiv Zugriff zu einem Speicherbereich 15 haben, und zwar aufgrund der Schreibsequenz aufgrund eines früheren Schreibbefehls, und daß der Prozessor 12 h nunmehr die Daten aus dieser Speicherstelle lesen möchte, wandert die betreffende Anfrage bei der Anordnung gemäß Fig. 6 aufwärts durch die Hierarchie (d. h. es werden keine Kopien in irgendwelchen Cache-Speichern direkt oberhalb des Prozessors 12 h vorhanden sein), so daß die Anforderung auf jeder Ebene fehlschlagen wird. Wenn die Anforderung dann den Bus 20 erreicht, wird der Cache-Speicher 18 a die Notwendigkeit für das Aufheben des exklusiven Zugriffs erkennen sowie die Notwendigkeit, möglicherweise eine "schmutzige" Kopie des Speicherbereichs zu löschen. Der Cache-Speicher 18 a wird daraufhin einen Löschbefehl nach unten bis zu dem Bus 16 a senden, wo der Cache- Speicher 14 b den exklusiven Zugriff aufheben und die modifizierte Kopie des Speicherbereichs 15 aufwärts in der Hierarchie zurücksenden wird. In Abhängigkeit davon, welches Write-Deferred-Schema verwendet wird, werden die Daten dann entweder zuerst in den Hauptspeicher 22 zurückkehren oder direkt in den Cache- Speicher 18 c wandern und von dort zu dem Cache-Speicher 14 h und dem Prozessor 12 h. Die Kopien im Cache-Speicher 18 a und im Cache-Speicher 14 b bleiben erhalten, sind jedoch nicht länger als "exklusiv" markiert.

Bei dem Multiprozessor-System gemäß vorliegender Erfindung nehmen nur diejenigen unteren Zweige der Hierarchie an dem Kohärenz-Datenverkehr teil, welche tatsächlich Kopien des betroffenen Speicherbereichs enthalten. Bei dem oben diskutierten Beispiel sehen der Prozessor und die Cache-Speichereinheiten, die dem Cache-Speicher 18 b zugeordnet sind, keine Ungültigkeits- oder Löschbefehle, und folglich ergibt sich keine zusätzliche Verkehrsbelastung auf dem Bus 16 b. Die Cache-Speicher- Kohärenz wird folglich durch das ganze System hindurch ohne ein ins Gewicht fallendes Anwachsen des Busverkehrs aufrecht erhalten, und die auf der unteren Ebene befindlichen Teile des Multiprozessor-Systems sind gegeneinander soweit wie möglich isoliert. Der kombinierte Effekt der Verkehrsisolation auf den unteren Ebenen über mehrfache Busse, die Verringerung des Verkehrs auf den höheren Ebenen aufgrund der hierarchischen Anordnung der Cache-Speicher und die Begrenzung der Kohärenzkontrolle auf die Bereiche, in denen sie nötig ist, führt zu einer großen Multiplikation der Bandbreite bei in vollem Umfang gemeinsam genutzten Hauptspeicher und automatischer Kohärenzkontrolle. Während die Verwendung von Write-Through-Cache-Speichern zu einer Busauslastung auf den höheren Ebenen führen würde, würde die Verwendung von Write-Deferred-Cache-Speichern eine nahezu unbegrenzte Ausdehnung des Systems durch Hinzufügen zusätzlicher Ebenen zu der Hierarchie ermöglichen.

Der in Fig. 5 und 6 gezeigte Teil des Multiprozessorsystems, welcher den Cache-Speicher 18 a, den Bus 16 a, die privaten Cache-Speicher 14 a, 14 b und 14 c und die Prozessoren 12 a, 12 b, 12 c umfasst, wird nachstehend als ein "Cluster" bzw. als Gruppe bezeichnet. Derartige Gruppen sind in Wirklichkeit unabhängige Multiprozessor- Computersysteme, in denen der Cash-Speicher 18 in Wirklichkeit den Hauptsystemspeicher bildet. Das hierarchisch gegliederte Cash-Speichersystem gemäß vorliegender Erfindung ermöglicht das Verbinden mehrerer derartiger Cluster bzw. Gruppen zu einem größeren Multiprozessor- Computersystem, welches einen Haupt-Zentralspeicher 22 umfasst, der eine Kopie aller Daten in den Cache-Speichern 18 enthält. Da die Cache-Speicher-Kohärenz zwischen den Cache-Speichern 18 aufrecht erhalten wird, können die Daten zwischen den verschiedenen Gruppen übertragen werden.

Das hierarchisch gegliederte Cache-Speichersystem gemäß vorliegender Erfindung kann auch in Verbindung mit Speichern mit mehreren Ports verwendet werden, welche ihrerseits über mehrere gemeinsam benutzte Busse gespeist werden können. Wie Fig. 7 zeigt, können Speicher mit mehreren Ports verwendet werden, indem man jedem Block in den Speichern ein Bit-Paar hinzufügt, um die Spur für die Zugriffsmuster zu halten und um die Notwendigkeit für das Aussenden von Ungültigkeits- oder Löschbefehlen an die zugeordneten, gemeinsam genutzten Busse 16 zu bestimmen.

Der Multiport-Speicher 24 kann auf eine Reihe von unterschiedlichen Arten betrieben werden, je nachdem, ob Write-Through-Cache-Speicher oder Write-Deferred-Cache- Speicher verwendet werden. Beide Arten der Cache-Speicherung nutzen die Tatsache, daß die Menge der aktiv genutzten Daten in den meisten Multiprozessor-Systemen sehr klein ist und daß somit eine gewisse verringerte Effektivität für den Fall einer gemeinsamen Nutzung von Daten toleriert werden kann. Das Arbeiten nach dem einfachsten Schema bringt es mit sich, daß das System hinsichtlich der Frage auf dem laufenden gehalten werden muß, welcher der Ports 25, 26 (falls überhaupt einer) exklusiv Zugriff zu einem Speicherplatz hat, damit gewährleistet ist, daß die richtigen Ungültigkeits- oder Löschbefehle bei jeder Änderung des Port-Status ausgesendet werden. Wie das Zustandsdiagramm gemäß Fig. 8 zeigt, kann dies dadurch erreicht werden, daß für jeden Port für einen Zustand gesorgt wird, der anzeigt, daß dies der letzte Port für das Empfangen eines Schreibzugriffs war und daß seither keine Lese-Zugriffe von anderen Ports erfolgt sind. Ein weiterer Zustand wird angegeben, wenn seit dem letzten Schreibvorgang Lesebefehle von mehreren Ports eingetroffen sind. Dieser Zustand zeigt an, daß Kopien des Speicherinhalts bzw. des Speicherbereichs in mehreren Gruppen vorhanden sind. Diese Zustandssignale gestatten das Ausdehnen von Write-Through- und Write-Deferred-Multi-Cache- Speicher-Kohärenzschemen bei Speichern mit mehreren Ports.

Die Arbeitsweise der Zwei-Port-Speicher ist für die Write-Through- und die Write-Deferred-Schemen ähnlich. Wenn ein Schreibzugriff an einem Port erfolgt, der bereits in den Zustand "reserviert" gebracht wurde, dann werden Ungültigkeitssignale an alle anderen Ports gesendet, da diese eine Kopie des Speicherbereichs enthalten könnten. Der Speicherbereich wird dann für den betreffenden Port reserviert, indem man diesem Port einen exklusiven Zugriff gewährt. Weitere Lese- oder Schreibbefehle von dem reservierten Port führen nicht zu zusätzlichen Ungültigkeitsbefehlen (und damit nicht zu einem zusätzlichen Busverkehr); der Zugriff von anderen Ports wird jedoch die Gewährung des exklusiven Zugriffs für den ursprünglichen Port aufheben. Da Ungültigkeitsbefehle nur dann ausgesendet werden, wenn Schreibvorgänge an nicht reservierten Ports auftreten, wird der Normalfall, bei dem Speicherbereiche nicht gemeinsam über Gruppengrenzen hinweg benutzt werden oder nur im Lesebetrieb, nicht zur Erzeugung zusätzlicher Ungültigkeitsbefehle führen. Ungültigkeitsbefehle werden nur für diejenigen Speicherbereiche auftreten, die zwischen beiden Bussen gemeinsam benutzt und modifiziert werden, so daß insgesamt nur eine sehr geringe Erhöhung des Busverkehrs eintritt. Beim Arbeiten nach den Write-Deferred-Schemen müssen Löschbefehle an diejenigen Gruppen gesendet werden, die den Status ihrer exklusiven Zugriffsmöglichkeit aufgrund eines Lesezugriffs von einem anderen Port verlieren. Dies gewährleistet, daß beim Lesezugriff die neueste Kopie des betreffenden Speicherbereichs erhalten wird. Für den Fall, daß ein Löschbefehl erforderlich ist, ist der Lesezyklus, welcher diesen Befehl ausgelöst hat, nicht abgeschlossen, ehe nicht die Forderung nach der Auslösung eines Löschbefehls erfüllt ist.

Das hierarchisch gegliederte Cache-Speichersystem gemäß vorliegender Erfindung kann auf der untersten Ebene mit Zwei-Port-Speichern verbunden werden, um eine Struktur mit hierarchischen Verbindungen und einem körperlich verteilten Hauptspeicher zu bilden, wie dies in Fig. 9 gezeigt ist. Fernabfragen eines lokalen Speichers können über die lokalen, gemeinsam benutzten Buseinrichtungen geleitet werden, wenn eine spezielle Adapterschaltung verwendet wird, um eine Multiport-Kohärenzkontrolle aufrecht zu erhalten, während Ein-Port- Standardspeicher verwendet werden. In einem derartigen, in Gruppen unterteilten System bildet jeder Bus auf der untersten Ebene eine komplette Multiprozessor- Gruppe mit direktem Zugriff zu einer Bank von lokalen Gruppenspeichern.

Gemäß Fig. 10 erfolgt der Zugriff zu Daten, die in entfernten Gruppen gespeichert sind, in ähnlicher Weise wie bei einem geradlinig gegliederten, hierarchischen Cache-Speichersystem. Die Gruppen-Cache-Speicher bilden die zweite Ebene von Cache-Speichern und sorgen für dieselbe Filterung und Kohärenzkontrolle für Fernanfragen wie die zweite Ebene von Cache-Speichern bei dem hierarchischen System gemäß Fig. 3, 5 und 6. Nach dem Erreichen der Spitze bzw. der globalen Ebene der Hierarchie wird die Anfrage abwärts zu der Gruppe gelenkt, die die gewünschte Speicherstelle enthält, und läuft über den gemeinsamen Bus dieser Gruppe. Da private Cache-Speicher an dem Gruppenbaus diesen Zugriff ebenfalls feststellen, sind keine speziellen Multiport- Kohärenzaktionen erforderlich, wie sie erforderlich wären, wenn der lokale Speicher als echter Multiport- Speicher realisiert worden wäre. Für diejenigen Zugriffe, die direkt zu dem Speicher in derselben Gruppe gehen, zu der auch der den Zugriffsbefehl aussendende Prozessor gehört, wird eine zusätzliche Kohärenzkontrolle gemäß demselben Schema wie bei den Zwei-Port- Speichern erforderlich. Diese Kohärenzkontrolle wird ausgeführt, indem man eine spezialle Adapterkarte verwendet, um die Spur möglicher entfernter Kopien zu halten und um für Write-Deferred-Cache-Speicher festzustellen, ob für diese entfernt abgelegte Kopie ein exklusiver Zugriff besteht oder nicht. Wenn in einem solchen Fall ein lokales Schreibsignal erhalten wird und die Adapterkarte (vgl. die Adapterkartenzustände gemäß Fig. 11) feststellt, daß eine entfernt abgespeicherte Kopie vorhanden sein könnte, dann wird ein Ungültigkeitsbefehl aufwärts durch die Hierarchie geschickt, um die Funktion zu erfüllen, die der Einschreibbefehl in einer reinen Hierarchie ausüben würde. Wenn ein lokales Lesesignal für einen Speicherbereich festgestellt wird, für den das Vorhandensein einer entfernt abgelegten Kopie mit exklusivem Zugriff aufgezeichnet ist, dann muß ein Löschbefehl nach oben durch die Hierarchie geleitet werden. Mit diesen Erweiterungen kann das Cache-Speicher-Kohärenzschema, welches für hierarchisch geordnete Strukturen entwickelt wurde, auch dazu verwendet werden, zwischen den einzelnen Gruppen eines Systems die Kohärenz aufrecht zu erhalten.

Die Gruppenarchitektur bietet mehrere Vorteile. Beispielsweise gestattet sie es, Code und Stapel lokal für eine gegebene Gruppe beizubehalten und somit die höheren Ebenen des Systems für den globalben Datenverkehr übrig zu lassen. Infolgedessen ermöglichst die Gruppenarchitektur selbst bei mäßig großen Multiprozessoren die Verwendung des einfacheren Write-Through- Cache-Speicherschemas. Man kann jeden Prozess auf jedem der lokalen Gruppenprozessoren mit gleicher Leichtigkeit laufen lassen und gewinn damit die meisten Vorteile, die sich bei dem automatischen Belastungsausgleich eines Multiprozessors mit enger Koppelung ergeben. Diese Prozesse können jedoch auch, wenn es erforderlich ist, in einer entfernten Gruppe durchgeführt werden. Wegen der lokalen Cache-Speicher wird selbst ein Prozess, der von einer entfernten Gruppe läuft, nahezu die optimale Leistung erreichen. Ohne die Lokalisierung wird jedoch der Busverkehr zwischen den Gruppen erhöht, insbesondere, wenn Write-Through- Cache-Speicher verwendet werden.

Die Gruppenarchitektur kann auch bei der Handhabung von global-gemeinsamen Zugriffen hilfreich sein. Der iterative Charakter mancher wissenschaftlicher Algorithmen hat zur Folge, daß die globalen Zugriffe ein schwaches Cache-Speicher-Verhalten zeigen. Da jedoch diese Zugriffsmuster mit hoher Genauigkeit vorhersagbar sind, ist es häufig der Fall, daß die globalen Zugriffe unterteilt werden können, um sie in die Gruppen zu bringen, wo die größte Benutzungshäufigkeit stattfinden wird. In anderen Fällen kann sich die Notwendigkeit ergeben, daß sich die globalen Daten zwischen mehreren Gruppen bewegen. Es kann eine Blockübertragungs- Hardware verwendet werden, um diese Bewegung zu erreichen, ehe die Daten in der entfernten Gruppe benötigt werden. Somit kann die Gruppenarchitektur die Vorteile einer grobkörnigen Lokalität nutzen, un das schlechte Cache-Speicherverhalten der globalen Daten zu überwinden, was zu kürzeren Zugriffszeiten und zu einem geringeren globalen Busverkehr führt als bei einem geradlinig gegliederten hierarchischen Cache- Speicherschema.

Während die Erfindung vorstehend unter Bezugnahme auf bevorzugte Ausführungsbeispiele beschrieben wurde, stehen dem Fachmann zahlreiche Möglichkeiten für Änderungen und/oder Ergänzungen zu Gebote. Während beispielsweise die Erfindung so beschrieben wurde, daß zwei Ebenen von Cache-Speichern vorhanden sind (die privaten Cache-Speicher und die Cache-Speicher zwischen den privaten Cache-Speichern und dem Hauptspeicher), kann zwischen den privaten Cache-Speichern und dem Hauptspeicher jede Zahl von Cache-Speicherebenen liegen, solange jeder Cache-Speicher einer höheren Ebene genügend Speicherkapazität hat, um eine Kopie des Speicherinhalts jedes der Cache-Speicher in der unmittelbar darunter befindlichen Ebene aufzunehmen, mit denen er verbunden ist. Weiterhin können andere Write- Deffered-Schemen verwendet werden, um die Cache-Speicher- Kohärenz aufrecht zu erhalten.

Anlage zu Zeichnungen

Legende (Key) zu Fig. 1 und 2:

Purge - Löschen von Cache-Speicher-Kopie wegen Cache-Speicher-Ersatz
Processor Read - Lesebefehl von mit diesem Cache- Speicher verbundenen Prozessor
Processor Write - Schreibbefehl von mit diesem Cache- Speicher verbundenen Prozessor
Bus Read - Lesebefehl auf Bus
Bus Write - Schreibbefehl auf Bus
Flush Write - Spezieller Schreibbefehl an Hauptspeicher, dessen Daten ebenfalls auf den Befehl "Bus Read" ausgegeben werden.

Legende zu Fig. 4:

L2BR - Lesebefehl auf Gruppenbus
L1BW - Schreibbefehl auf Gruppenbus
L1B1 - Befehl "ungültig machen" auf Gruppenbus
L1B1 - Befehl "Flush Write" auf Gruppenbus
L2 - Lesebefehl auf übergeordnetem Bus
L2 - Schreibbefehl auf übergeordnetem Bus
Purge - Ersatz von Cache-Speicher-Bereich durch anderen Speicherbereich

Legende zu Fig. 8:

P0 - Port 0
P1 - Port 1
BR - Buslesebefehl empfangen
BW - Busschreibbefehl empfangen
GENBI - Signal "ungültig machen" auf Bus erzeugt
GENBF - Signal "Flush (Löschen)" auf Bus erzeugt
RESERVED - reserviert
NO RESERVATION - keine Reservierung

Legende zu Fig. 11:

LOCAL READ - Lokaler Lesebefehl; LOCAL WRITE - lokaler Schreibbefehl; LOCAL RESERVED - lokale Reservierung; REMOTE READ - Fern-Lesebefehl; REMOTE WRITE - Fern- Schreibbefehl; LOCAL VALID - lokal gültig; NO LOCAL COPY - keine lokale Kopie; REMOTE INVALIDATE - Fernbefehl "ungültig machen"; REMOTE FLUSH - Fernbefehl "Flush (Löschen)"

Anlage zu den Zeichnungen

Legende zu Fig. 1 und 2:

Löschen - Löschen von Cache-Speicher-Kopie wegen Cache-Speicher-Ersatz
Prozessor lesen - Lesebefehl von mit diesem Cache-Speicher verbundenem Prozessor
Prozessor schreiben - Schreibbefehl von mit diesem Cache-Speicher verbundenem Prozessor
Bus lesen - Lesebefehl auf Bus
Bus schreiben - Schreibbefehl auf Bus
ungültig machen - Spezieller Schreibbefehl ("flush read") an Hauptspeicher, dessen Daten ebenfalls auf den Befehl "Bus lesen" ausgegeben werden

Legende zu Fig. 4:

L2BR - Lesebefehl auf Gruppenbus
L1BW - Schreibbefehl auf Gruppenbus
L1B1 - Befehl "ungültig machen" (invalidate) auf Gruppenbus
L1BF - Befehl "ungültig machen" (flush write) auf Gruppenbus
L2 - Lesebefehl auf übergeordnetem Bus
L2 - Schreibbefehl auf übergeordnetem Bus
Löschen - Ersatz von Cache-Speicher-Bereich durch anderen Speicherbereich

Legende zu Fig. 8:

P0 - Port 0
P1 - Port 1
BR - Buslesebefehl empfangen
BW - Busschreibbefehl empfangen
GENBI - Signal "ungültig machen" auf Bus erzeugt
GENBF - Signal "Flush (Löschen" auf Bus erzeugt

Claims

1. Hierarchisch gegliedertes Cache-Speichersystem für ein Multiprozessor-Rechnersystem mit mehreren Prozessoren und einem Systemspeicher, gekennzeichnet durch folgende Merkmale:
es sind private Cache-Speichereinrichtungen (14) einer ersten unteren Ebene vorgesehen, die jeweils einem der Prozessoren (12) zugeordnet sind;
es sind erste Buseinrichtungen (16) vorgesehen, welche mindestens zwei der privaten Cache-Speichereinrichtungen (14) miteinander verbinden;
es sind Cache-Speichereinrichtungen (18) einer zweiten höheren Ebene vorgesehen, welche mit den ersten Buseinrichtungen (16) verbunden sind und welche eine Kopie des Inhalts jedes Speicherbereichs der mit den ersten Buseinrichtungen (16) verbundenen privaten Cache-Speichereinrichtungen (14) enthalten und die ebenfalls mit den ersten Buseinrichtungen (16) verbunden sind; und
es sind zweite Buseinrichtungen (20) vorgesehen, die mit mindestens einer der Cache-Speichereinrichtungen (18) der höheren Ebene und mit dem Systemspeicher (22) verbunden sind, welcher eine Kopie des Inhalts jedes Speicherbereichs der mit den zweiten Buseinrichtungen (20) verbundenen Cache-Speichereinrichtungen (18) der höheren Ebene enthält.

2. Cache-Speichersystem nach Anspruch 1, dadurch gekennzeichnet, daß es Einrichtungen umfasst, die es ermöglichen, daß die Inhalte eines Speicherbereichs einer der privaten Cache-Speichereinrichtungen (14), zu welcher von ihrem zugeordneten Prozessor (12) ein Schreibbefehl übertragen wurde, in den entsprechenden Speicherbereich der zu der höheren Ebene gehörenden Cache-Speichereinrichtung (18), die direkt zwischen der betreffenden privaten Cache-Memoryeinrichtung (14) und dem Systemspeicher (22) angeordnet ist, sowie in den entsprechenden Speicherbereich des Systemspeichers (22) eingeschrieben werden.

3. Cache-Speichersystem nach Anspruch 2, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, um die Inhalte eines Speicherbereichs einer privaten Cache-Speichereinrichtung (14) und/oder einer zu der höheren Ebene gehörenden Cache-Speichereinrichtung (18) ungültig zu machen, welche einen Speicherbereich umfasst, der einem Speicherbereich einer anderen privaten Speichereinrichtung (14) entspricht, für den eine Schreiboperation durchgeführt wurde.

4. Cache-Speichersystem nach Anspruch 1, gekennzeichnet durch folgende Merkmale:
es sind Einrichtungen vorgesehen, um einen Speicherbereich einer privaten Cache-Speichereinrichtung in einen Zustand "reserviert" zu bringen, wenn der dieser privaten Cache-Speichereinrichtung (14) zugeordnete Prozessor (12) eine Schreiboperation für den betreffenden Speicherbereich ausführt, wobei der Zustand "reserviert" anzeigt, daß diejenige private Cache-Speichereinrichtung (14), welche den reservierten Speicherbereich enthält, die einzige private Cache-Speichereinrichtung (14) mit einer gültigen Kopie dieses Speicherbereichs ist; und
es sind Einrichtungen vorgesehen, um die Inhalte des reservierten Speicherbereichs in die mit der betreffenden Cache-Speichereinrichtung (14) verbundene Cache-Speichereinrichtung (18) der höheren Ebene und in den Systemspeicher (22) zu kopieren.

5. Cache-Speichersystem nach Anspruch 4, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, um die Inhalte eines Speicherbereichs einer privaten Cache-Speichereinrichtung (14) und/oder einer Cache-Speichereinrichtung (18) der höheren Ebene ungültig zu machen, wenn der betreffende Speicherbereich einem Speicherbereich einer anderen privaten Cache-Speichereinrichtung (14) entspricht, für den eine Schreiboperation ausgeführt wurde.

6. Cache-Speichersystem nach Anspruch 5, dadurch gekennzeichnet, daß Freigabeeinrichtungen vorgesehen sind, die den Prozessor (12), welcher eine zugehörige private Cache-Speichereinrichtung (14) mit einem in einem Zustand "reserviert" befindlichen Speicherbereich aufweist, zur Durchführung zusätzlicher Schreiboperationen ausschließlich für folgende Speichereinrichtungen freigeben: die zugehörige private Cache-Speichereinrichtung (14); die zu der höheren Ebene gehörige Cache-Speichereinrichtung (18), die mit der ersten Buseinrichtung (16) verbunden ist, mit der auch die private Cache-Speichereinrichtung (14) verbunden ist, die den reservierten Speicherbereich enthält; und der Systemspeicher (22), welcher die Inhalte des reservierten Speicherbereichs in der Form beibehält, in der sie vor den zusätzlichen Schreiboperationen vorhanden waren.

7. Cache-Speichersystem nach Anspruch 4, dadurch gekennzeichnet, daß Freigabeeinrichtungen vorgesehen sind, durch die eine zu der höheren Ebene gehörige Cache-Speichereinrichtung (18) zum Erkennen eines in einem Zustand "reserviert" befindlichen Speicherbereichs in einer Cache-Speichereinrichtung (14) der niedrigeren Ebene freigebbar ist, die mit der betreffenden Cache-Speichereinrichtung (18) der höheren Ebene über einen Bus (16) verbunden ist, mit dem die Cache-Speichereinrichtung (18) der höheren Ebene und die Cache-Speichereinrichtung (14) der niedrigeren Ebene verbunden sind.

8. Cache-Speichersystem nach Anspruch 7, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, die es der zu der höheren Ebene gehörigen Cache- Speichereinrichtung (18) ermöglichen, den in dem Zustand "reserviert" befindlichen Speicherbereich zu erkennen und dessen Inhalte zu übernehmen.

9. Cache-Speichersystem nach Anspruch 1, dadurch gekennzeichnet, daß die zweiten Buseinrichtungen (20) mit den zu der höheren Ebene gehörigen Cache- Speichereinrichtungen (18) verbunden sind.

10. Cache-Speichersystem nach Anspruch 1, dadurch gekennzeichnet, daß der Systemspeicher (22) Speichereinrichtungen mit mehreren Ports aufweist, von denen ein Port mit einem übergeordneten Bus (20) verbunden ist und von denen ein zweiter Port mit einem Bus (16) verbunden ist, mit dem auch die Cache-Speichereinrichtungen (18) der höheren Ebene verbunden sind.

11. Cache-Speichersystem nach Anspruch 1, dadurch gekennzeichnet, daß mindestens ein Satz von zu zumindest einer höheren Ebene gehörigen Cache- Speichereinrichtungen (18) vorgesehen ist, daß zugeordnete Buseinrichtungen vorgesehen sind, welche zwischen die Cache-Speichereinrichtungen der zweiten höheren Ebene und die zweiten Buseinrichtungen geschaltet sind, wobei eine der zugeordneten Buseinrichtungen mit den Cache-Speichereinrichtungen der zweiten höheren Ebene und einer einer noch höheren Ebene zugehörigen Cache-Speichereinrichtungen eines der Sätze dieser Cache-Speichereinrichtungen verbunden ist, die mit den zweiten Buseinrichtungen verbunden sind.

12. Mikroprozessorsystem gekennzeichnet durch folgende Merkmale:
es ist ein erstes Mikroprozessorsystem vorgesehen, welches mindestens einen Prozessor umfasst, wobei der bzw. jeder einzelne Prozessor mit einem zugeordneten privaten Cache-Speicher zum Speichern von häufig benötigten Speicherbereichen verbunden ist und wobei der bzw. jeder einzelne Cache-Speicher mit den übrigen Cache-Speichern über einen ersten, gemeinsamen Bus verbunden ist;
es sind erste, gemeinsam benutzte Cache-Speichereinrichtungen vorgesehen, die mit dem ersten, gemeinsamen Bus verbunden sind und eine Kopie der Inhalte jedes Speicherbereichs des bzw. der privaten Cache-Speicher enthalten, die mit dem ersten gemeinsamen Bus verbunden sind;
es ist ein zweites Multiprozessorsystem vorgesehen, welches mindestens einen Prozessor umfasst, wobei der bzw. jeder einzelne Prozessor mit einem zugeordneten privaten Cache-Speicher zum Speichern von häufig benötigten Speicherbereichen verbunden ist und wobei der bzw. jeder einzelne Cache-Speicher mit dem bzw. jedem anderen dieser privaten Cache- Speicher über einen zweiten gemeinsamen Bus verbunden ist;
es sind zweite, gemeinsam benutzte Cache-Speichereinrichtungen vorgesehen, die mit dem zweiten gemeinsamen Bus verbunden sind und eine Kopie der Inhalte jedes Speicherbereichs des bzw. der privaten Cache-Speicher enthalten, die mit dem zweiten gemeinsamen Bus verbunden sind;
es sind Systemspeichereinrichtungen vorgesehen, die mit einem übergeordneten Bus verbunden sind, mit dem die ersten und die zweiten Cache-Speichereinrichtungen ebenfalls verbunden sind, und die Systemspeichereinrichtungen enthalten eine Kopie der Inhalte jedes Speicherbereichs der ersten und der zweiten Cache-Speichereinrichtungen.

13. Multiprozessorsystem nach Anspruch 12, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, die es ermöglichen, daß die Inhalte eines Speicherbereichs einer der privaten Cache-Speichereinrichtungen, zu welcher von ihrem zugeordneten Prozessor ein Schreibbefehl übertragen wurde, in den entsprechenden Speicherbereich der ersten oder der zweiten, gemeinsam benutzten Cache-Speichereinrichtungen sowie in den entsprechenden Speicherbereich des Systemspeichers eingeschrieben werden.

14. Multiprozessorsystem nach Anspruch 13, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, um die Inhalte eines Speicherbereichs einer privaten Cache-Speichereinrichtung und/oder der ersten und der zweiten, gemeinsam benutzten Cache- Speichereinrichtungen ungültig zu machen, welche einen Speicherbereich umfassen, der einem Speicherbereich einer anderen privaten Cache-Speichereinrichtung entspricht, für den eine Schreiboperation durchgeführt wurde.

15. Multiprozessorsystem nach Anspruch 13, gekennzeichnet durch folgende Merkmale:
es sind Einrichtungen vorgesehen, um einen Speicherbereich einer privaten Cache-Speichereinrichtung in einen Zustand "reserviert" zu bringen, wenn der dieser privaten Cache-Speichereinrichtung zugeordneten Prozessor eine Schreiboperation für den betreffenden Speicherbereich ausführt, wobei der Zustand "reserviert" anzeigt, daß diejenige private Cache-Speichereinrichtung, welche den reservierten Speicherbereich enthält, die einzige private Cache- Speichereinrichtung mit einer gültigen Kopie dieses Speicherbereichs ist; und
es sind Einrichtungen vorgesehen, um die Inhalte des reservierten Speicherbereichs in die ersten oder die zweiten, gemeinsam benutzten Cache-Speichereinrichtungen zu kopieren, die mit der Cache-Speichereinrichtung verbunden sind, welche den reservierten Speicherbereich enthält, und um die Inhalte des reservierten Speicherbereichs in die Systemspeichereinrichtungen zu kopieren.

16. Multiprozessorsystem nach Anspruch 15, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, um die Inhalte eines Speicherbereich einer privaten Cache-Speichereinrichtung und/oder der ersten und der zweiten, gemeinsam benutzten Cache-Speichereinrichtungen ungültig zu machen, wenn der betreffende Speicherbereich einem Speicherbereich einer anderen privaten Cache-Speichereinrichtung entspricht, für den eine Schreiboperation ausgeführt wurde.

17. Multiprozessorsystem nach Anspruch 15, dadurch gekennzeichnet, daß Freigabeeinrichtungen vorgesehen sind, um eine gemeinsam benutzte Cache-Speichereinrichtung dafür freizugeben, daß sie einen in dem reservierten Zustand befindlichen Speicherbereich in einer privaten Cache-Speichereinrichtung erkennt, die mit der erkennenden, gemeinsam benutzten Cache-Speichereinrichtung über einen Bus verbunden ist, mit dem sowohl die gemeinsam benutzte Cache- Speichereinrichtung als auch die private Cache- Speichereinrichtung verbunden sind.

18. Multiprozessorsystem nach Anspruch 16, dadurch gekennzeichnet, daß Freigabeeinrichtungen vorgesehen sind, die denjenigen Prozessor, welcher eine zugehörige private Cache-Speichereinrichtung mit einem in einem Zustand "reserviert" befindlichen Speicherbereich aufweist, zur Durchführung zusätzlicher Schreiboperationen, ausschließlich für folgende Speichereinrichtungen freigeben:
die zugehörigen privaten Cache-Speichereinrichtungen, die ersten oder die zweiten Cache-Speichereinrichtungen und die Systemspeichereinrichtungen, welche die Inhalte des reservierten Speicherbereichs in der Form enthalten, in der sie vor den zusätzlichen Schreiboperationen vorhanden waren.

19. Multiprozessorsystem nach Anspruch 17, dadurch gekennzeichnet, daß Einrichtungen vorgesehen sind, die es der den reservierten Speicherbereich erkennenden, gemeinsam benutzten Cache-Speichereinrichtung ermöglichen, die Inhalte des Speicherbereichs zu übernehmen, der sich in dem reservierten Zustand befindet.

20. Verfahren zum Aufrechterhalten der Cache-Speicher- Kohärenz in einem hierarchisch gegliederten Cache- Speichersystem für ein Multiprozessor-Rechnersystem mit mehreren Prozessoren, von denen jedem jeweils ein privater Cache-Speicher individuell zugeordnet ist, und mit einem Hauptsystemspeicher, gekennzeichnet durch folgende Verfahrensschritte:
es wird ein zweiter, einer höheren Ebene zugeordneter Cache-Speicher vorgesehen, der mit dem privaten Cache-Speicher über einen ersten, von mindestens zweien der Prozessoren gemeinsam benutzten Bus und mit dem Hauptsystemspeicher über einen zweiten, übergeordneten (globalen) Bus verbunden ist; wenn ein Prozessor eine Schreiboperation bezüglich eines Speicherbereichs seines zugeordneten privaten Cache-Speichers ausführt, werden die Inhalte dieses Speicherbereichs in den zweiten, einer höheren Ebene zugeordneten Cache-Speicher, der mit dem ersten Bus verbunden ist, und in den mit dem übergeordneten zweiten Bus verbundenen Hauptspeicher kopiert;
diejenigen Cache-Speicherbereiche der Cache-Speicher, welche eine Kopie des angeschriebenen Speicherbereichs enthalten, werden außer in dem privaten Cache- Speicher, in den die neuen Daten eingeschrieben wurden, und außer in dem dazugehörigen, übergeordneten Cache-Speicher, in den die neuen Daten kopiert werden, ungültig gemacht.

21. Verfahren nach Anspruch 20, gekennzeichnet durch folgende Merkmale:
derjenige Speicherbereich des privaten Cache-Speichers, in dem die Schreiboperation ausgeführt wird, wird in einen Zustand "reserviert" gebracht, der anzeigt, daß der private Cache-Speicher, welcher den reservierten Speicherbereich enthält, der einzige private Cache-Speicher mit einer gültigen Kopie des betreffenden Speicherbereichs ist;
die Inhalte des reservierten Speicherbereichs werden in diejenigen, zu der zweiten höheren Ebene gehörigen Cache-Speichereinrichtungen kopiert, die mit dem genannten privaten Cache-Speicher verbunden sind und zwischen diesem privaten Cache-Speicher und dem Systemspeicher liegen und den reservierten Speicherbereich enthalten, sowie in den Systemspeicher;
derjenige Prozessor, dessen zugeordnete private Cache-Speichereinrichtungen einen im reservierten Zustand befindlichen Speicherbereich aufweisen, wird für weitere Schreiboperationen nur bezüglich der zugeordneten privaten Cache-Speichereinrichtungen, der zu der höheren Ebene gehörigen Cache- Speichereinrichtungen und des Systemspeichers freigegeben, welche die Inhalte des reservierten Speicherbereichs in der Form enthalten, in der diese vor den zusätzlichen Schreiboperationen vorhanden waren.

22. Verfahren nach Anspruch 21, dadurch gekennzeichnet, daß eine zu der höheren Ebene gehörige Cache- Speichereinrichtung zum Erkennen eines im reservierten Zustand befindlichen Speicherbereichs in einer zu einer niedrigeren Ebene gehörigen Cache-Speichereinrichtung freigegeben wird, die mit der erkennenden Cache-Speichereinrichtung über einen Bus verbunden ist, mit dem die Cache-Speichereinrichtungen der höheren Ebene und der niedrigeren Ebene verbunden sind, und daß den zu der höheren Ebene gehörigen Cache-Speichereinrichtungen, die den im reservierten Zustand befindlichen Speicherbereich erkennen, die Übernahme der Inhalte dieses im reservierten Zustand befindlichen Speicherbereichs gestattet wird.