DE69130086T2

DE69130086T2 - Mehrstufeneinschluss in mehrstufigen Cache-Speicherhierarchien

Info

Publication number: DE69130086T2
Application number: DE69130086T
Authority: DE
Inventors: Roger E. Houston Texas 77070 Tipley
Original assignee: Compaq Computer Corp
Current assignee: Compaq Computer Corp
Priority date: 1990-06-15
Filing date: 1991-06-14
Publication date: 1999-01-21
Anticipated expiration: 2011-06-15
Also published as: EP0461926B1; DE69130086D1; EP0461926A2; EP0461926A3; US5369753A; JPH04233048A; CA2044689A1; ATE170642T1

Description

Die vorliegende Erfindung betrifft Mikroprozessor-Cache-Teilsysteme in Computersystemen, und insbesondere ein Verfahren und eine Vorrichtung zum Erreichen von Mehrstufen-Inklusion bei Erststufen- und Zweitstufen-Caches in einem Computersystem in solcher Weise, daß die Zweitstufen-Cachesteuerung die grundsätzlichen Beobachtungs-Verantwortlichkeiten für beide Caches wahrnehmen kann.
Die Personalcomputer-Industrie ist ein lebhaftes und wachsendes Gebiet, das sich fortschreitend mit weiteren Innovationen entwickelt. Die Antriebskraft hinter diesen Innovationen war das wachsende Verlangen nach schnelleren und leistungsfähigeren Computern. Ein größeres Hindernis bei der Geschwindigkeitsentwicklung der Personalcomputer war historisch die Geschwindigkeit, mit der auf Daten aus dem Speicher zugegriffen werden kann, was man als die Speicherzugriffzeit bezeichnet. Der Mikroprozessor mit seinen relativ raschen Prozessorzykluszeiten wurde allgemein verlangsamt durch die Notwendigkeit von Wartezuständen während Speicherzugriffen, um die relativ langsamen Speicherzugriffzeiten aufzunehmen. Deshalb war eine Verbesserung der Speicherzugriffzeiten eines der größeren Forschungsgebiete bei der Verbesserung der Computerleistung.
Um den Abstand zwischen den schnellen Mikroprozessor-Zykluszeiten und den langsamen Speicherzugriffzeiten zu überbrücken wurde der Cache-Speicher entwickelt. Ein Cache ist eine kleine Ansammlung von sehr schnellen relativ teuren Speichern mit Null-Wartezustand, und wird benutzt, um eine Kopie von Kodes und Daten von dem Hauptspeicher zu speichern, auf die häufig zugegriffen wird. Der Mikroprozessor kann aus diesem sehr schnellen Speicher arbeiten und dadurch die Anzahl von Wartezuständen verringern, die während Speicherzugriffen eingeschoben werden müssen. Wenn der Prozessor Daten aus dem Speicher anfordert, und die Daten in dem Cache sitzen, findet ein Cache-Lese treffer statt, und die Daten von dem Speicherzugriff können von dem Cache ohne Auftreten von Wartezuständen zum Prozessor zurückgeführt werden. Falls die Daten sich nicht im Cache befinden, findet ein Cache-Lesefehlschlag statt, die Speicheranforderung wird zu dem System weitergegeben und die Daten werden vom Hauptspeicher abgeholt, wie es normalerweise bei nicht vorhandenem Cache der Fall ist. Bei einem Cache-Fehlschlag werden die vom Hauptspeicher abgeholten Daten zum Prozessor gebracht und werden auch in den Cache geschrieben, in Anbetracht der statistischen Wahrscheinlichkeit, daß diese Daten wieder durch den Prozessor angefordert werden.
Ein wirksamer Cache ergibt eine hohe "Trefferrate", was den Anteil von Cache-Treffern bedeutet, die während aller Speicherzugriffe auftreten. Wenn ein Cache eine hohe Trefferrate besitzt, wird die Mehrzahl von Speicherzugriffen mit Wartezustand Null bedient. Die Netto-Auswirkung einer hohen Cache- Trefferrate besteht darin, daß die bei relativ selten vorkommenden Fehlschlägen auftretenden Wartezustände über eine große Anzahl von Null-Wartezuständen bei Cache-Trefferzugriffen gemittelt werden, so daß sich ein durchschnittlicher Wartezustand von nahezu Null pro Zugriff ergibt. Da ein Cache üblicherweise an dem örtlichen Bus des Mikroprozessors gelegen ist, werden Cache-Treffer örtlich bedient, ohne den Systembus in Anspruch zu nehmen. Deshalb hat ein aus seinem örtlichen Cache arbeitender Prozessor eine viel geringere "Busverwendungshäufigkeit". Das setzt die durch den Prozessor benutzte Systembus-Bandbreite herab, so daß für andere Busmaster mehr Bandbreite verfügbar wird.
Eine andere wichtige Eigenschaft von Caches ist, daß der Prozessor aus seinem örtlichen Cache arbeiten kann, wenn er keine Kontrolle über den Systembus besitzt, wodurch der Wirkungsgrad des Computersystems erhöht wird. Bei Systemen ohne Mikroprozessor-Caches muß der Prozessor allgemein im Leerlauf sein, während er keine Kontrolle über den Systembus hat. Das setzt den Gesamtwirkungsgrad des Computersystems herab, weil der Prozessor in dieser Zeit keine nützliche Arbeit leisten kann. Wenn jedoch der Prozessor einen an seinem örtlichen Bus angeschlossenen Cache enthält, kann er die notwendigen Kodes und Daten aus seinem Cache holen, um eine nützliche Arbeit zu leisten, während andere Geräte den Systembus kontrollieren, und dadurch den Systemwirkungsgrad erhöhen.
Das Cache-Verhalten hängt von vielen Faktoren ab, einschließlich der Trefferrate und der Cache-Speicher-Zugriffzeit. Die Trefferrate ist ein Maß dafür, wie wirksam ein Cache beim Aufrechterhalten einer Kopie der am häufigsten benutzten Kodes und Daten ist, und in einem hohen Maß ist sie eine Funktion der Größe des Caches. Ein größerer Cache wird allgemein eine höhere Trefferrate besitzen als ein kleinerer Cache. Ein Erhöhen der Cache-Größe kann jedoch die Cache-Speicher-Zugriffzeit möglicherweise verschlechtern. Jedoch können Cache-Auslegungen für einen größeren Cache erzielt werden mit Benutzung von Cache- Speichern mit den schnellstmöglichen Zugriffzeiten, so daß der Begrenzungsfaktor bei der Auslegung die minimale CPU-Zugriffzeit ist. Auf diese Weise geht ein größerer Cache nicht zu Lasten der Speicherzugriffzeit gegenüber einem kleineren Cache, da der Begrenzungsfaktor in dieser Auslegung die minimale CPU- Zugriffzeit ist.
Andere wichtige Überlegungen bei dem Cache-Verhalten sind die Organisation des Caches und die bei dem Cache eingesetzten Cache-Verwaltungstaktiken. Ein Cache kann allgemein in entweder einer direktkopierenden oder einer satzassoziativen Gestaltung organisiert werden. Bei einer direktkopierenden Organisation wird der körperlich vorhandene Adreßraum des Computers vorstellungsmäßig in eine Anzahl von gleichen Seiten aufgeteilt, wobei die Seitengröße gleich der Größe des Caches ist. Der Cache wird in eine Anzahl von Sätzen unterteilt, wobei jeder Satz eine bestimmte Anzahl von Zeilen enthält. Jede Seite im Hauptspeicher besitzt eine der Anzahl von Zeilen im Cache äquivalente Anzahl von Zeilen, und jede Zeile einer jeweiligen Seite im Hauptspeicher entspricht einer gleichartig gelegenen Zeile im Cache. Eine wichtige Eigenschaft eines direktkopierenden Cache ist, daß jede Speicherzeile einer Seite im Hauptspeicher, die als ein Seitenversatz bezeichnet wird, nur in der äquivalent angeordneten Zeile oder mit dem gleichen Seitenversatz im Cache sitzen kann. Infolge dieser Begrenzung braucht der Cache nur auf eine gewisse Zahl von oberen Adreßbits einer Speicheradresse Bezug zu nehmen, die als eine Markierung bezeichnet werden, um zu bestimmen, ob eine Kopie der Daten von der jeweiligen Speicheradresse im Cache sitzt, da die Adreßbits niedrigerer Ordnung durch den Seitenversatz der Speicheradresse vorgegeben sind.
Während ein direktkopierender Cache als eine Speicherreihe organisiert ist, die in ihrer Größe einer konzeptionellen Seite im Hauptspeicher äquivalent ist, enthält ein satzassoziativer Cache eine Anzahl von Speicher-Reihen oder -Wegen, die jeweils in ihrer Größe einer konzeptionellen Seite im Hauptspeicher äquivalent sind. Dementsprechend kann ein Seitenversatz im Hauptspeicher in einer Anzahl von Plätzen im Cache abgezeichnet werden, die gleich der Anzahl von Wegen im Cache ist. Z. B. kann in einem vierwege-satzassoziativen Cache eine Zeile oder ein Seitenversatz vom Hauptspeicher in dem äquivalenten Seitenversatzplatz an einem der vier Wege des Cache sitzen.
Einsatzassoziativer Cache enthält allgemein einen Ersetzungs- Algorithmus, der bestimmt, welche Reihe oder welcher Weg mit welchen Daten aufgefüllt wird, wenn ein Lesefehlschlag auftritt. Viele satzassoziative Caches benutzen irgendeine Form einer LRU-(least recently used = am wenigsten zeitnah verwendet)-Algorithmus, der neue Daten in den Weg einsetzt, auf den am längsten nicht zugegriffen wurde. Das geschieht deswegen, weil statistisch der Weg, der zuletzt benutzt oder auf den zuletzt zugegriffen wurde, um Daten zum Prozessor zu schaffen, derjenige ist, der in der Zukunft am wahrscheinlichsten wieder benötigt wird. Deshalb stellt der LRU-Algorithmus sicher, daß der Block, der ersetzt wird, am wenigsten wahrscheinlich durch den Cache angeforderte Daten besitzt.
Cache-Verwaltung wird allgemein durch ein Gerät ausgeführt, das als Cachesteuerung bezeichnet wird. Die Cachesteuerung enthält ein Inhaltsverzeichnis, das für jeden Satz im Cache einen zugehörigen Eintrag enthält. Dieser Eintrag besitzt im allgemeinen drei Komponenten: eine Markierung, ein Markierungs- Gültigkeitsbit und eine Anzahl von Zeilen-Gültigkeitsbits, die gleich der Zahl von Zeilen in jedem Cache-Satz ist. Die Markierung wirkt als eine Hauptspeicher-Seitennummer, und hält die oberen Adreßbits der bestimmten Seite im Hauptspeicher, von der die Kopie der in dem jeweiligen Satz des Caches sitzenden Daten stammt. Der Zustand des Markierungs-Gültigkeitsbits bestimmt, ob die Daten in dem jeweiligen Cache-Satz als gültig oder ungültig betrachtet werden. Wenn das Markierungs-Gültigkeitsbit gelöscht ist, wird der ganze Satz als ungültig angesehen. Wenn das Markierungs-Gültigkeitsbit wahr ist, wird eine einzelne Zeile innerhalb des Satzes als gültig oder ungültig betrachtet, in Abhängigkeit von dem Status des jeweiligen Zeilen-Gültigkeitsbits.
Eine grundlegende Cache-Verwaltungstaktik ist die Aufrechterhaltung der Cache-"Kohärenz". Die Cache-Kohärenz bezieht sich auf die Erfordernis, daß irgendeine Datenkopie in einem Cache identisch mit dem Eigner der Daten an dieser Stelle sein muß (oder tatsächlich dieser Eigner ist). Der Eigner der Daten einer Stelle wird allgemein definiert als die entsprechende Stelle, die die jüngste Version der in dem jeweiligen Speicherplatz sitzenden Daten besitzt. Der Eigner von Daten kann entweder ein unmodifizierter Platz im Hauptspeicher oder ein modifizierter Platz in einem Rückschreibe-Cache sein. Bei Computersystemen, bei denen unabhängige Busmaster auf den Speicher zugreifen können, besteht eine Möglichkeit, daß ein Busmaster wie eine Direkt-Speicherzugriffsteuerung, ein Netz oder eine Festplatten-Schnittstellenkarte, oder eine Videographikkarte die Inhalte eines Hauptspeicherplatzes ändern können, der in dem Cache dupliziert ist. Wenn dies erfolgt, sagt man, daß der Cache "überständige" oder ungültige Daten enthält. Um Cache-Kohärenz aufrecht zu erhalten, ist es notwendig, daß die Cachesteuerung den Systembus überwacht, wenn der Prozessor den Systembus nicht inne hat, um zu sehen, ob ein anderer Busmaster auf den Hauptspeicher zugreift. Dieses Verfahren zum Überwachen des Buses wird als "beobachten" (snooping) bezeichnet.
Die Cachesteuerung muß den Systembus während Speicherlesevorgängen durch einen Busmaster in einer Rückschreibe-Cache- Auslegung überwachen wegen der Möglichkeit, daß ein vorhergehender Prozessor-Schreibvorgang eine Datenkopie in dem Cache geändert hat, die noch nicht im Hauptspeicher aktualisiert wurde. Das wird als Lesebeobachtung (read snooping) bezeichnet. Bei einem Lesebeobachtungstreffer, bei dem der Cache Daten enthält, die im Hauptspeicher noch nicht aktualisiert sind, gibt die Cachesteuerung allgemein die jeweiligen Daten an den Hauptspeicher, und der anfordernde Busmaster liest im allgemeinen diese Daten beim Durchlauf von der Cachesteuerung zum Hauptspeicher, und dieser Vorgang wird als "wegschnappen" (snarfing) bezeichnet. Die Cachesteuerung muß während Speichereinschreibungen auch den Systembus überwachen, da der Busmaster einen in dem Cache sitzenden Speicherplatz beschreiben oder ihn ändern kann. Das wird als Schreibbeobachtung (read snooping) bezeichnet. Bei einem Schreibbeobachtungstreffer wird der Cache-Eintrag entweder in dem Cache-Verzeichnis durch die Cachesteuerung als ungültig bezeichnet, was bedeutet, daß dieser Eintrag nicht länger korrekt ist, oder der Cache wird zusammen mit dem Hauptspeicher aktualisiert. Wenn deshalb ein Busmaster in einer Rückschreibe-Cache-Auslegung den Hauptspeicher liest oder in ihn einschreibt oder in einer Durchschreibe-Cache-Auslegung zum Hauptspeicher schreibt, muß die Cachesteuerung die Systemadresse zwischenspeichern und eine Cache-Nachschau in dem Markierungsverzeichnis ausführen, das dem Seitenversatzplatz entspricht, wo der Speicherzugriff vorgefallen ist, um zu sehen, ob der Inhalt des Hauptspeicherplatzes, auf den zugegriffen wurde, auch in dem Cache vorhanden ist. Falls eine Kopie der Daten von diesem Platz in dem Cache sitzt, unternimmt die Cachesteuerung die angemessene Aktion in Abhängigkeit davon, ob ein Lese- oder Schreibbeobachtungstreffer aufgetreten ist. Das verhindert, daß inkompaktible Daten im Hauptspeicher und dem Cache gespeichert sind, so daß dadurch die Cache-Kohärenz erhalten wird.
Eine andere Überlegung bei dem Erhalten von Cache-Kohärenz ist die Behandlung von Prozessor-Einschreibungen in den Speicher. Wenn der Prozessor in den Hauptspeicher schreibt, muß der Speicherplatz geprüft werden, um zu bestimmen, ob eine Kopie der Daten von diesem Platz ebenfalls im Cache sitzt. Wenn ein Prozessor-Schreibtreffer in einer Rückschreibe-Cache-Auslegung auftritt, wird der Cache-Platz mit den neuen Daten aktualisiert und der Hauptspeicher kann mit den neuen Daten zu einem späteren Zeitpunkt oder sobald es notwendig wird, aktualisiert werden. In einem Durchschreibe-Cache wird der Hauptspeicherplatz allgemein bei einem Prozessor-Schreibtreffer in Verbindung mit dem Cache-Platz aktualisiert. Falls ein Prozessor- Schreib-Fehlschlag auftritt, kann die Cachesteuerung den Schreib-Fehlschlag bei einer Durchschreibe-Cache-Auslegung ignorieren, da der Cache bei dieser Auslegung unbeeinflußt bleibt. Alternativ kann die Cachesteuerung eine "Schreib- Zuordnung" ausführen, wodurch die Cachesteuerung eine neue Zeile in dem Cache zusätzlich zum Durchleiten der Daten zum Hauptspeicher zuordnet. In einer Rückschreibe-Cache-Auslegung ordnet die Cachesteuerung allgemein eine neue Zeile im Cache zu, wenn ein Prozessor-Schreib-Fehlschlag auftritt. Dies enthält allgemein das Lesen der restlichen Einträge zum Auffüllen der Zeile in dem Hauptspeicher, vor oder gemeinsam mit dem Zuführen der Schreibdaten zum Cache. Der Hauptspeicher wird zu einem späteren Zeitpunkt aktualisiert, sobald es nötig wird.
Caches sind allgemein unabhängig vom Mikroprozessor ausgelegt. Der Cache ist an den örtlichen Bus (lokal bus) des Mikroprozessors angesetzt und während der Auslegung des Computersystems zwischen dem Prozessor und dem Systembus mit Schnittstellenbildung angeschlossen. Mit der Entwicklung von Computer-Chips mit höherer Transistordichte sind jedoch gegenwärtig viele Prozessoren mit einem Cache am Chip selbst ausgelegt, um die Verhaltensziele mit Bezug auf die Speicherzugriffzeiten zu erreichen. Der auf dem gemeinsamen Chip befindliche Cache, der bei diesen Prozessoren benutzt wird, ist allgemein klein, mit z. B. 8 kByte. Der kleinere am Chip befindliche Cache ist allgemein schneller als der große auf einem eigenen Chip befindliche Cache und verringert den Spalt zwischen schnellen Prozessorzykluszeiten und den relativ langsamen Zugriffzeiten für große Caches.
In Computersystemen, die Prozessoren mit am Chip befindlichen Caches benutzen, wird oftmals ein externer Zweitstufen-Cache zum System hinzugefügt, um die Speicherzugriffzeit weiter zu verbessern. Der Zweitstufen-Cache ist im allgemeinen viel größer als der am Chip befindliche Cache, und wenn er in Verbindung mit dem am Chip befindlichen Cache eingesetzt wird, ergibt er eine größere Gesamttrefferrate, als sie der am Chip befindliche Cache durch sich selbst schaffen könnte.
In Systemen, die mehrere Cache-Stufen verkörpern, wird der am Chip befindliche oder Erststufen-Cache zuerst geprüft, um zu sehen, ob eine Kopie der Daten dort sitzt. Falls das der Fall ist, tritt ein Erststufen-Cachetreffer auf, und der Erststufen- Cache schafft die entsprechenden Daten zum Prozessor. Wenn ein Erststufen-Cache-Fehlschlag auftritt, wird der Zweitstufen- Cache geprüft. Falls ein Zweitstufen-Cachetreffer auftritt, werden die Daten von dem Zweitstufen-Cache zum Prozessor geschafft. Falls ein Zweitstufen-Cache-Fehlschlag auftritt, werden die Daten vom Hauptspeicher abgeholt. Schreibvorgänge verlaufen gleichartig, wobei Mischen und Anpassen der vorher besprochenen Vorgänge möglich ist.
In Mehrstufen-Cache-Systemen war es im allgemeinen notwendig, daß jeder Cache den Systembus während Einschreibungen in den Speichern durch andere Busmaster beobachtet, um Cache-Kohärenz aufrecht zu erhalten. Wenn der Mikroprozessor nicht die Kontrolle über den Systembus inne hat, sind Cachesteuerungen sowohl für den Erststufen- wie den Zweitstufen-Cache erforderlich, um die Adresse jeder Speichereinschreibung zwischenzuspeichern und diese Adresse anhand der Markierung in dem eigenen Cache-Verzeichnis zu prüfen. Das behindert die Wirksamkeit des Prozessors beträchtlich, der während dieser Zeit aus seinem am Chip befindlichen Cache arbeitet, da er fortwährend durch die Beobachtungsaufwendungen des Cachesteuerers für den am Chip befindlichen Cache unterbrochen wird. Deswegen verschlechtert die Erfordernis, daß die Cachesteuerung des am Chip befindlichen Caches den Systembus bei jeder Speichereinschreibung beobachten muß, das Systemverhalten, da es den Prozessor davon abhält, wirksam aus seinem am Chip befindlichen Cache zu arbeiten, während er die Kontrolle über den Systembus nicht inne hat.
In vielen Fällen, wo Mehrstufen-Cache-Hierarchien bei mehreren Prozessoren vorhanden sind, ist eine als Mehrstufen-Inklusion bezeichnete Eigenschaft in der Hierarchie erwünscht. Mehrstufen-Inklusion sorgt dafür, daß der Zweitstufen-Cache garantierterweise eine Kopie des Inhalts des Erststufen- oder auf dem Chip befindlichen Caches besitzt. Wenn dies der Fall ist, sagt man, daß der Zweitstufen-Cache einen Supersatz des Erststufen-Caches hält. Mehrstufen-Inklusion wurde meistens in Mehrprozessor-Systemen benutzt, um Cache-Kohärenz-Probleme zu verhindern. Wenn Mehrstufen-Inklusion in Mehrprozessor-Systemen ausgeführt wird, können die höher gestuften Caches die niedriger gestuften Caches gegen Cache-Kohärenz-Probleme abschirmen und dadurch unnötige Blindprüfungen und Ungültigkeitsschreibungen verhindern, die sonst in den Niedrigerstufen-Caches auftreten würden, wenn keine Mehrstufen-Inklusion ausgeführt wäre.
Mehrstufen-Cache-Hierarchien mit Mehrstufen-Inklusion werden beispielsweise geoffenbart in Journal of Parallel and Distributed Computing, Band 6, Nr. 3, Juni 1989, DULUTH, MN, US, Seiten 451-476, BAER u. a.
Die vorliegende Erfindung enthält ein Verfahren und eine Vorrichtung zum Erreichen von Mehrstufen-Inklusion unter Erst- und Zweitstufen-Caches in einem Computersystem. Mehrstufen- Inklusion umgeht die Notwendigkeit, den Systembus durch die Cachesteuerung des Erststufen-Cache bei jeder auftretenden Speichereinschreibung zu überwachen, während der Prozessor keine Kontrolle über den Systembus innehat, weil die Cachesteuerung des Zweitstufen-Caches diese Pflichtaufgabe für beide Caches übernehmen kann. Das setzt die Erststufen-Cachesteuerung frei und erlaubt dadurch ein wirksameres Arbeiten des Mikroprozessors aus dem Erststufen-Cache, wenn er keine Steuerung des Systembus innehat.
Der Zweitstufen-Cache besitzt vorzugsweise eine Zahl von Wegen, die gleich oder größer als die Wegezahl im Erststufen-Cache ist. Der Erststufen- ist bei der bevorzugten Ausführung der vorliegenden Erfindung wie der Zweitstufen-Cache ein vierwegesatzassoziativer Cache. Bei dieser Ausführung besteht eine 1 : 1- Korrespondenz der Cachewege in dem Erststufen-Cache mit den Cachewegen in dem Zweitstufen-Cache. Während einer Erststufen- Cache-Zeilenfüllung vom Hauptspeicher kommuniziert die Erststufen-Cachesteuerung mit der Zweitstufen-Cachesteuerung den besonderen Erststufen-Cacheweg, in welchen die Daten einzusetzen sind, so daß die Zweitstufen-Cachesteuerung die Daten in den entsprechenden Cacheweg der zweiten Stufe einsetzen kann. Wenn die Zweitstufen-Cachesteuerung eine Datenkopie an die Erststufen-Cachesteuerung übermittelt, informiert die Zweitstufen-Cachesteuerung die Erststufen-Cachesteuerung darüber, von welchem Zweitstufen-Cacheweg die Daten kommen. Die Erststufen-Cachesteuerung mißachtet ihren normalen Ersetzungs- Algorithmus und füllt den entsprechenden Erststufen-Cacheweg. Auf diese Weise richten der Erststufen- und der Zweitstufen- Cache sich auf "Wegegrundlage" aus. Diese "Wege"-Ausrichtung verhindert, daß die Zweitstufen-Cachesteuerung Daten in einen anderen Weg als dem im Erststufen-Cache einsetzt, und bei diesem Vorgang möglicherweise Daten entfernt, die in dem Erststufen-Cache sitzen.
Die Cache-Organisation des Erststufen-Caches gemäß der vorliegenden Erfindung ist eine Durchschreibe-Architektur. Bei einer Prozessor-Einschreibung wird die Information vorzugsweise in den Erststufen-Cache geschrieben, ohne Rücksicht darauf, ob ein Schreibtreffer oder Schreibfehlschlag aufgetreten ist, und externe Schreibbuszyklen werden eingeleitet, welche die Information in den Zweitstufen-Cache schreiben. Der Erststufen-Cache sendet den bestimmten Erststufen-Cacheweg, wo die Daten eingesetzt wurden, an die Zweitstufen-Cachesteuerung, so daß die Zweitstufen-Cachesteuerung die Daten in den entsprechenden Zweitstufen-Cacheweg einsetzen kann, wodurch die "Wege"-Ausrichtung aufrecht erhalten bleibt. Der Zweitstufen-Cache ist vorzugsweise ein Rückschreibe-Cache gemäß der bevorzugten Ausführung, kann jedoch auch, falls gewünscht, ein Durchschreibe-Cache sein.
Die Zweitstufen-Cachesteuerung benutzt ein Inklusionsbit mit Bezug auf jede Datenzeile in dem Zweitstufen-Cache, um daran zu erinnern, ob eine Kopie dieser Daten auch in dem Erststufen- Cache sitzt. Wenn ein Platz in dem Erststufen-Cache ersetzt wird, ob nun gleichlaufend mit einer Zweitstufen-Cache-Ersetzung vom Speicher oder direkt von dem Zweitstufen-Cache, setzt die Zweitstufen-Cachesteuerung ein Inklusionsbit für diesen Platz in den Zweitstufen-Cache, um zu bezeichnen, daß eine Kopie dieser Daten im Erststufen-Cache dupliziert ist. Wenn dies auftritt, werden an allen anderen Plätzen in dem Zweitstufen-Cache, die dem gleichen Platz in dem Erststufen-Cache entsprechen, die jeweiligen Inklusionsbits durch die Zweitstufen-Cachesteuerung gelöscht, um zu bezeichnen, daß die in diesen Plätzen gehaltenen Daten nicht in dem Erststufen-Cache sitzen.
Die Zweitstufen-Cachesteuerung führt die grundlegenden Beobachtungspflichtaufgaben für beide Caches aus, wenn der Prozessor keine Kontrolle über den Systembus innehat. Wenn bei dem Zweitstufen-Cache ein Schreibbeobachtungstreffer auftritt, wird das Inklusionsbit durch die Zweitstufen-Cachesteuerung gelesen, um zu sehen, ob die Erststufen-Cachesteuerung auch den Speicherzugriff beobachten muß. Falls das Inklusionsbit nicht gesetzt ist, wird die Erststufen-Cachesteuerung alleingelassen. Falls das Inklusionsbit gesetzt ist, leitet die Zweitstufen- Cachesteuerung die Erststufen-Cachesteuerung an, den betreffenden Speicherzugriff zu beobachten. Auf diesen Weise kann die Erststufen-Cachesteuerung ihre Beobachtungspflichten außer acht lassen, bis die Zweitstufen-Cachesteuerung bestimmt, daß tatsächlich ein Schreibbeobachtungstreffer an dem Erststufen-Cache aufgetreten ist. Das erlaubt dem Prozessor einen wirksameren Betrieb aus seinem Erststufen-Cache, wenn er nicht die Kontrolle über den Systembus innehat.
Ein besseres Verständnis der Erfindung kann erhalten werden, wenn die folgende detaillierte Beschreibung der bevorzugten Ausführung in Verbindung mit den folgenden Zeichnungen in Betracht gezogen wird, in welchen:
Fig. 1 ein Blockschaltbild eines Computersystems ist, das Erst- und Zweitstufen-Caches enthält und eine Mehrstufen- Inklusion gemäß der vorliegenden Erfindung verwirklicht;
Fig. 2 die Organisation des 2Wege-Satzassoziativen C&sub1;- Caches der Fig. 1 abbildet;
Fig. 3 die Organisation des 2Wege-Satzassoziativen C2- Caches der Fig. 1 abbildet;
Fig. 4A und 4B ein Flußdiagramm abbilden, das den Betrieb von Cache-Lese-Treffern und -Fehlschlägen nach der vorliegenden Erfindung darstellt; und
Fig. 5 ein Flußdiagramm ist, das den Betrieb von Lese- und Schreibbeobachtung gemäß der vorliegenden Erfindung darstellt. In Fig. 1 ist allgemein ein Computersystem S dargestellt. Viele Einzelheiten eines Computersystems, die für die vorliegende Erfindung nicht relevant sind, wurden aus Klarheitsgründen weggelassen. Das Computersystem S enthält einen Mikroprozessor 20, der an einem Erststufen-Cache C1 angeschlossen ist, der sich vorzugsweise am gleichen Chip 22 wie der Prozessor 20 befindet. Der Chip 22 enthält eine C1-Cachesteuerung 30, die mit dem C1-Cache verbunden ist und den Betrieb des C&sub1;-Caches steuert. Der Prozessor 20, der Erststufen-Cache C1 und die Erststufen-Cachesteuerung 30 sind über einen örtlichen Prozessorbus mit einem Systembus 24 verbunden. Ein Zweitstufen-Cache C2 ist an dem örtlichen Prozessorbus 25 angeschlossen. Eine als C2-Cachesteuerung 32 bezeichnete Zweitstufen-Cachesteuerung ist mit dem C&sub2;-Cache und dem örtlichen Prozessorbus 25 verbunden. Ein RAM (random access memory - Speicher mit wahlfreiem Zugriff) 26, gemäß der vorliegenden Ausführung der Erfindung mit einer Größe von 4 Gigaßytes, und ein intelligenter Busmaster 28 sind mit dem Systembus 24 verbunden. Der RAM 26 enthält eine (nicht dargestellte) Systemspeichersteuerung, welche den Betrieb des RAM 26 steuert. Der RAM 26 und die (nicht gezeigte) Systemspeichersteuerung werden von hier ab als Hauptspeicher 26 bezeichnet. Der Systembus 24 enthält einen Datenbus und einen 32Bit-Adreßbus, wobei der Adreßbus Adreßbits A2 bis A31 enthält, die Zugriff auf eines der 230 32Bit-Doppelworte im Hauptspeicher 26 zulassen. Der Busmaster 28 kann von jeder Art sein, die den Systembus 24 steuert, wenn das Prozessorsystem im Halten ist, sowie eine System-Direktspeicherzugriff-Steuerung (DMA - direct memory access), eine Festplatten-Schnittstelle, eine Ortsbereichsnetz-(LAN)-Schnittstelle oder ein Videogra phik-Prozessorsystem.
Die C1- und C2-Caches sind auf "Wege"-Basis so miteinander ausgerichtet, daß eine Kopie von in einen bestimmten Weg in einem der Caches gesetzten Daten nur in einen vorgegebenen entsprechenden Weg im anderen Cache eingesetzt sein kann. Diese "Wege"-Ausrichtung erfordert, daß der C2-Cache mindestens so viel Cachewege wie der C1-Cache besitzt. Wenn die C1- und C2- Caches die gleiche Anzahl von Wegen besitzen, besteht eine 1 : 1- Korrespondenz zwischen den Cachewegen im C1-Cache und den Cachewegen in dem C2-Cache. Wenn der C2-Cache mehr Cachewege als der C1-Cache besitzt, entspricht jedem Cacheweg im C1-Cache ein Weg im C2-Cache, oder es entsprechen ihm mehrere Cachewege in dem C2-Cache. Jedoch können keine zwei C1-Cachewege dem gleichen C2-Cacheweg entsprechen. Diese Bedingung rührt von der Tatsache her, daß jede Speicheradresse nur einen möglichen Speicherplatz in jedem der C1- und C2-Caches besitzt. Wenn dementsprechend zwei C1-Cachewege einem einzigen C2-Cacheweg entsprechen würden, wären in dem C1-Cache sitzende Speicheradreßplätze möglich, die nicht in dem C2-Cache sitzen können. Der jeweilige C2-Cachewege-Platz wäre unfähig, die beiden Speicheradressen zu halten, die in jedem der jeweiligen C1- Cachewege sitzen könnten, der dem jeweiligen C2-Cachewege-Platz entspricht.
Die tatsächliche Größe jedes der Caches ist für die Zwecke der Erfindung nicht wichtig. Jedoch muß der C2-Cache mindestens so groß wie der C1-Cache sein, um Mehrstufen-Inklusion zu erreichen, und der C2-Cache ist vorzugsweise mindestens viermal so groß wie der C1-Cache, um für eine verbesserte Cache-Trefferrate zu sorgen. Bei der bevorzugten Ausführung der vorliegenden Erfindung hat der C1-Cache eine Größe von 8 kByte und der C2- Cache ist vorzugsweise 512 kByte groß. Bei dieser Ausführung ist der C1-Cache und der C2-Cache jeweils ein 4Wege-Satzassoziativer Cache. Bei einer alternativen Ausführung der vorliegenden Erfindung sind die C1- und C2-Caches jeweils 2Wege-Satzassoziative Caches.
In Fig. 2 und 3 sind konzeptionelle Schaubilder von C1- und C2- Caches mit ihren jeweiligen Cachesteuerungen 30 und 32 allgemein gezeigt, die in einer 2Wege-Satzassoziativen Organisation gestaltet sind. Die nachfolgende Diskussion ist dazu bestimmt, eine Einführung in die Struktur und den Betrieb eines Satzassoziativen Caches wie auch die Beziehung zwischen dem Cache-Speicher, den Cache-Verzeichnissen und dem Hauptspeicher 26 zu schaffen. Die C1- und C2-Caches werden mit Bezug auf eine 2Wege-Satzassoziative Cache-Organisation als einfacheres Beispiel der komplexeren 4Wege-Satzassoziativen Cache-Organisation der bevorzugten Ausführung diskutiert. Die spezielle Cachesteuerungs-Auslegungsbetrachtungen, die bei einer 4Wege-Satzassoziativen Cache-Organisation entstehen, und in einer 2Wege- Satzassoziativen Organisation nicht auftreten, sind in der nachfolgenden Diskussion angemerkt.
Der C1-Cache enthält zwei Reihen oder Wege von Speichern, die als A1 und B1 bezeichnet sind, und die jeweils eine Größe von 4 kByte haben. Jeder der Cachewege A1 und B1 ist in 128 Sätzen organisiert, wobei jeder Satz acht Zeilen 58 von Speicherplätzen enthält. Jede Zeile enthält ein 32Bit-Doppelwort oder 4 Byte Speicherraum. Der Hauptspeicher 26 ist konzeptionell organisiert als 220 Seiten mit einer Seitengröße von je vier kByte, was der Größe jedes C1-Cacheweges A1 bzw. B1 äqivalent ist. Jede konzeptionelle Seite im Hauptspeicher 26 enthält 1024 Zeilen, die gleiche Anzahl von Zeilen, die jeder der Cachewege A1 und B1 besitzt. Die Übertragungseinheit zwischen dem Hauptspeicher 26 und dem C1-Cache ist eine Zeile.
Ein bestimmter Zeilenplatz, oder Seitenversatz, von jeder der Seiten im Hauptspeicher 26 bildet sich auf der in gleicher Weise gelegenen Zeile in jedem der Cachewege A1 und B1 ab. Z. B. ist in Fig. 2 der Seitenversatz von jeder Seite im Hauptspeicher 26, die gestrichelt ist, auf den äquivalent gelegenen und gestrichelten Zeilenversatz in jedem der Cachewege A1 und B1 abgebildet. Auf diese Weise kann sich ein bestimmter Seitenversatz-Speicherplatz vom Hauptspeicher 26 nur auf einem von zwei Plätzen im C&sub1;-Cache abbilden, wobei diese Plätze in jedem der Cachewege A1 bzw. B1 liegen.
Jeder Cacheweg A1 und B1 enthält ein Cache-Verzeichnis, das als Verzeichnis DA1 bzw. Verzeichnis DB1 bezeichnet wird, und diese sind in der C&sub1;-Cachesteuerung 30 des C&sub1;-Cache gelegen. Die Verzeichnisse DA1 und DB1 enthalten jeweils einen Eintrag 60 bzw. 62 für jeden der 128 Sätze in dem jeweiligen Cacheweg A1 bzw. B1. Der Cache-Verzeichniseintrag für jeden Satz besitzt drei Komponenten: eine Markierung, ein Markierungsgültigkeits- Bit und 8 Zeilengültigkeits-Bits, wie dargestellt. Die Anzahl der Zeilengültigkeits-Bits ist gleich der Anzahl der Zeilen in jedem Satz. Die 20 Bits in dem Markierungsfeld halten die oberen Adreßbits, die Adreßbits A12 bis A31 des Hauptspeicher- Adreßplatzes der Datenkopie, die in dem jeweiligen Satz des Caches sitzt. Die oberen Adreßbits adressieren die zugehörigen 4 kByte Konzeptionellseite im Hauptspeicher 26, wo die Daten in dem jeweiligen Satz des Caches sitzen. Die restlichen Adreßbits von diesem Hauptspeicher-Adreßplatz, die Adreßbits A2 bis All, können aufgeteilt werden in ein Satzadressenfeld, welches 7 Bits A5 bis All enthält, die zum Auswählen eines der 128 Sätze in dem C&sub1;-Cache benutzt werden, und ein Zeilenadreßfeld mit 3 Bits A2 bis A4, die zum Auswählen einer einzelnen Zeile aus den 8 Zeilen in dem gewählten Satz benutzt werden. Deswegen dienen die unteren Adreßbits A2 bis A11 als die "Cache-Adresse", welche direkt einen der Zeilenplätze in jedem der Wege A1 und B1 des C1-Caches auswählt.
Wenn der Mikroprozessor einen Speicherlesezyklus einleitet, werden die Adreßbits A5 bis A11 benutzt, einen der 128 Sätze zu wählen, und die Adreßbits A2 bis A4 werden benutzt, um eines der jeweiligen Zeilengültigkeits-Bits innerhalb jedes Eintrages in den jeweiligen Verzeichnissen DA1 und DB1 aus dem gewählten Satz zu wählen. Die unteren Adreßbits A2 bis A11 werden auch benutzt, um die angemessene Zeile in dem C1-Cache zu wählen. Die Cachesteuerung vergleicht das obere Adreßbit das Markierungsfeld der angeforderten Speicheradresse mit jeder der Markierungen, die in den angewählten Verzeichniseinträgen des gewählten Satzes für jeden der Cachewege A1 und B1 gespeichert sind. Gleichzeitig werden sowohl die Markierungsgültigkeitswie auch die Zeilengültigkeits-Bits überprüft. Wenn die oberen Adreßbits zu einer der Markierungen passen und wenn sowohl das Markierungsgültigkeits-Bit als auch die zugehörigen Zeilengültigkeits-Bits für das jeweilige Cachewege-Verzeichnis gesetzt sind, wo die Markierungspassung hergestellt wurde, ist das Ergebnis ein Cache-Treffer, und der entsprechende Cacheweg wird angeleitet, die gewählte Datenzeile auf den Datenbus zu steuern.
Ein Fehlschlag kann auf eine von zwei Arten auftreten. Die erste ist bekannt als Zeilen-Fehlschlag und tritt auf, wenn die oberen Adreßbits der geforderten Speicheradresse einer der Markierungen in jedem der Verzeichnisse DA1 oder DB1 des gewählten Satzes entsprechen und das jeweilige Markierungsgültigkeits-Bit gesetzt ist, jedoch das/die jeweilige(n) Zeilengültigkeits-Bit(s), wo die angeforderten Daten sitzen, gelöscht ist/sind. Die zweite Art wird Markierungs-Fehlschlag genannt und tritt auf, wenn entweder die oberen Adreßbits der angeforderten Speicheradressen nicht zu einer der jeweiligen Markierungen in den Verzeichnissen DA1 oder DB1 des gewählten Satzes passen, wo die angeforderten Daten gelegen sind, oder das jeweilige Markierungsgültigkeits-Bit für jedes der Verzeichnisse DA1 oder DB1 nicht gelöscht sind.
Die C1-Cachesteuerung 30 enthält einen Ersetzungs-Algorithmus, der den Cacheweg A1 oder B1 bestimmt, in welchem neue Daten zu setzen sind. Der verwendete Ersetzungs-Algorithmus ist ein LRU- (least recently used - am längsten nicht verwendet)-Algorithmus, der neue Daten in den Cacheweg setzt, auf den die längste Zeit durch den Prozessor nicht wegen Daten zugegriffen worden war. Das hat den statistischen Grund, daß der in jüngster Zeit benutzte Weg der Weg ist, der am wahrscheinlichsten in der nahen Zukunft wieder benötigt wird. Die C&sub1;-Cachesteuerung 30 enthält ein Verzeichnis 70, das ein LRU-Bit bei jedem Satz im dem Cache enthält, und das LRU-Bit zeigt von dem Cacheweg weg, auf den als letzten durch den Prozessor zugegriffen wurde. Wenn so durch den Prozessor angeforderte Daten in dem Weg A1 sitzen, wird das LRU-Bit zu B1 zeigend gerichtet. Wenn die durch den Prozessor angeforderten Daten im Weg B1 sitzen, wird das LRU- Bit zu A1 zeigend gerichtet.
Bei der 4Wege-Satzassoziativen C&sub1;-Cache-Organisierung der bevorzugten Ausführung kann ein aufwendig gestalteter LRU- oder Pseudo-LRU-Ersetzungs-Algorithmus in der C&sub1;-Cachesteuerung 30 eingesetzt werden. Die Wahl eines Ersetzungs-Algorithmus ist allgemein für die vorliegende Erfindung irrelevant, und es wird vorgeschlagen, einen LRU- oder Pseudo-LRU-Algorithmus zu wählen, um die bestimmte bei der gewählten Ausführung benutzte Cache-Auslegung zu optimieren. Ein Ersetzungs-Algorithmus, der in der C1-Cachesteuerung 30 bei der 4Wege-Satzassoziativen C1- Cache-Organisierung der bevorzugten Ausführung eingesetzt werden kann, ist ein Pseudo-LRU-Algorithmus, der wie folgt arbeitet. Der 4Wege-Satzassoziative C1-Cache enthält vier Speicherwege, die als WO, W1, W2 und W3 bezeichnet werden. Drei als X0, X1 und X2 bezeichnete Bits sitzen in der C1-Cachesteuerung 30 und werden für einen jeweiligen Satz in jedem der Wege in dem 4Wege-C1-Cache definiert. Diese Bits werden LRU-Bits genannt und werden bei jedem Treffer oder jedem Ersetzungsvorgang in dem C1-Cache aktualisiert. Wenn der jüngste Zugriff in dem jeweiligen Sitz zum Weg W0 oder W1 ging, wird X0 auf 1 oder einem logisch hohen Wert gesetzt. Bit X0 wird auf 0 oder einen logisch tiefen Wert gesetzt, wenn der jüngste Zugriff auf den Weg W2 oder W3 gerichtet wurde. Wenn X0 auf 1 gesetzt ist und der jüngste Zugriff zwischen dem Weg W0 und dem Weg W1 auf Weg WO ging, wird X1 auf 1 gesetzt, sonst wird X1 auf 0 gesetzt. Wenn X0 auf 0 gesetzt ist und der jüngste Zugriff zwischen Weg W2 und Weg W3 zum Weg W2 ging, wird X2 auf 1 gesetzt, sonst wird X2 auf 0 gesetzt.
Der Pseudo-LRU-Ersetzungs-Mechanismus arbeitet in der folgenden Weise. Wenn eine Zeile in dem 4Wege-C&sub1;-Cache ersetzt werden muß, benutzt die C1-Cachesteuerung 30 das Bit X0, um zuerst die jeweiligen Wege WO und W1 oder W2 und W3 zu wählen, wo der bestimmte Zeilenersetzungs-Kandidat, der am längsten zurückliegend benutzt wurde, sitzt. Die C&sub1;-Cachesteuerung benutzt dann die X1- und X2-Bits zur Bestimmung, welcher der beiden gewählten Cachewege WO und W1 oder W2 und W3 den jeweiligen Zeilenplatz enthält, der am längsten zurückliegend benutzt wurde, und dieser Zeilenplatz wird zum Ersetzen markiert.
Die C1-Cachesteuerung 30 sendet ihre LRU-Information bei C1- und C2-Cache-Lesefehlschlägen und bei Prozessor-Schreibvorgängen erfindungsgemäß zu der C2-Cachesteuerung 32. Auf diese Weise ist die C2-Cachesteuerung 32 in der Lage, die Datenkopie, die sie entweder bei Lesefehlschlägen von dem Hauptspeicher 26 oder bei Prozessor-Schreibvorgängen von dem Prozessor 20 empfängt, in den C2-Cacheweg zu setzen, der dem C1-Cacheweg entspricht, wo die C1-Cachesteuerung die Datenkopie einsetzt und dadurch eine Mehrstufen-Inklusion erreicht. Zusätzlich ignoriert die C1-Cachesteuerung bei einem C1-Cache-Lesefehlschlag und einem C2-Cache-Lesetreffer ihren LRU-Ersetzungs- Algorithmus, so daß die C1-Cachesteuerung 30 die Kopie der Daten, die sie von der C2-Cachesteuerung 32 empfängt, in den C1-Cacheweg einsetzt, der dem C2-Cacheweg entspricht, wo der Lesetreffer aufgetreten ist.
Der 2Wege-Satzassoziative C2-Cache ist in einer gleichartigen Weise organisiert wie der 2Wege-Satzassoziative C1-Cache. Bei der bevorzugten Ausführung umfaßt der C2-Cache vorzugsweise 512 kByte Cache-Daten-RAM. Nach Fig. 3 ist jeder Cacheweg A2 und B2 in dem C2-Cache von einer Größe von 256 kByte und enthält 8192 Sätze von jeweils 8 Zeilen. Die Zeilengröße in dem C2-Cache ist ein 32Bit-Doppelwort, die gleiche wie bei dem C1-Cache. Der 4Gigaßyte-Hauptspeicher 26 ist in 214 konzeptionellen Seiten organisiert, wobei jede konzeptionelle Seite eine Größe von 256 kByte besitzt. Die Anzahl von konzeptionellen Seiten des Hauptspeichers 26 für den C2-Cache ist geringer als die des C1- Caches, da die konzeptionelle Seitengröße für den C2-Cache größer als die für den C1-Cache ist. Wie bei dem C1-Cache bildet jeder Zeilenplatz oder Seitenversatz in dem Hauptspeicher 26 eine gleichartig gelegene Zeile in jedem der Cachewege A2 und B2 ab.
Die C&sub2;-Cachesteuerung 32 enthält Cachewege-Verzeichnisse DA2 und DB2. Die Cachewege-Verzeichnisse DA2 und DB2 haben Satzeinträge, welche l4Bit-Markierungsfelder enthalten, im Gegensatz zu den 20Bit-Markierungsfeldern in den Einträgen der C&sub1;- Cache-Verzeichnisse DA1 und DB1. Die 14Bit-Markierungsfelder halten die oberen Adreßbits, die Adreßbits A18 bis A31, welche die zugehörige konzeptionelle Seite von 256 kByte in dem Hauptspeicher 26 adressieren, wo die Daten in dem jeweiligen Satz des Caches sitzen. Die restlichen Adreßbits A2 bis A17 können aufgeteilt werden in ein Satzadreßfeld aus 13 Bits A5 bis A17, die zum Wählen eines der 8192 Sätze in dem C2-Cache benutzt werden, und ein Zeilenadreßfeld mit 3 Bits A2 bis A4, die zum Auswählen einer Einzelnen aus den 8 Zeilen in dem ausgewählten Satz benutzt werden. Deshalb dienen bei dem C&sub2;-Cache die unteren Adreßbits A2 bis A17 als die "Cache-Adresse", die direkt einen der Zeilenplätze in jedem der Wege A2 und B2 des C2-Caches auswählt.
Die erfindungsgemäße C2-Cachesteuerung 32 erfordert nicht allgemein einen Ersetzungs-Algorithmus, da der C2-Cache neue Daten nur bei C1- und C2-Cache-Lesefehlschlägen und bei Prozessor-Einschreibungen empfängt, und in diesen Fällen die C2- Cachesteuerung den Wegeplatz von der C1-Cachesteuerung empfängt und den entsprechenden C2-Cacheweg füllen muß. Deshalb braucht die C2-Cachesteuerung 32 keinen Ersetzungs-Algorithmus, weil der jeweilige C2-Cacheweg, wo Daten eingesetzt werden, durch den Datenwegeplatz in dem C1-Cache bestimmt wird. Wenn jedoch der C2-Cache mehr Wege als der C1-Cache besitzt, erfordert die C2-Cachesteuerung 32 die Verwendung eines Ersetzungs-Algorithmus. In diesem Falle entspricht ein C1-Cacheweg zwei oder mehr C2-Cachewegen. Wenn dementsprechend die C1-Cachesteuerung 30 den C1-Cachewegeplatz an die C2-Cachesteuerung 32 sendet, braucht die C2-Cachesteuerung 32 einen Ersetzungs-Algorithmus, um zu entscheiden, in welchen von den mehreren C2-Cachewegen, welche dem C1-Cachewegeplatz entsprechen, die empfangenen Daten zu setzen sind.
Die 2Wege-Satzassoziativen Caches C1 und C2 sind auf "Wege"- Basis so ausgerichtet, daß die Wege A1 und B1 in dem C&sub1;-Cache eine 1 : 1-Korrespondenz mit den Wegen A2 bzw. B2 des C&sub2;-Caches besitzen. Auf diese Weise hat ein Seitenversatz vom Hauptspeicher 26, der in den jeweiligen Zeilenplatz in einem C&sub1;- Cacheweg A1 oder B1 gesetzt wird, nur einen möglichen Platz in dem entsprechenden C2-Cacheweg A2 bzw. B2. Umgekehrt besitzt ein jeweiliger Zeilenplatz in einem C2-Cacheweg A2 oder B2 nur einen möglichen Platz in dem entsprechenden C1-Cacheweg A1 bzw. B1. Da jedoch der C2-Cache 64 mal so groß wie der C1-Cache ist, hält jeder der C2-Cachewege A2 oder B2 64 Zeilen von Daten, die jeweils einer einzigen Zeile oder einem einzigen Seitenversatzplatz in dementsprechenden C1-Cacheweg A1 oder B1 entsprechen oder darin angeordnet sein können. Deshalb enthält die erfindungsgemäße C2-Cachesteuerung 32 Inklusions-Bits 80 für jede ihrer jeweiligen Zeilen. Das ermöglicht es der C2-Cachesteuerung 32, sich zu erinnern, ob eine Kopie von Daten von der jeweiligen C2-Cache-Zeile auch in dem entsprechenden C1-Cache- Zeilenplatz sitzt.
Die Verwendung von Inklusions-Bits 80 erlaubt es der C2-Cachesteuerung 32, sich zu erinnern, welche von den 64 Datenzeilen in dem jeweiligen C2-Cacheweg A2 oder B2, welche einem einzelnen C2-Cachewegeplatz entsprechen, eine Datenkopie enthält, die an diesem C1-Cacheplatz dupliziert ist. Wenn beispielsweise eine Zeile in dem C2-Cache eine Kopie von Daten vom Hauptspeicher 26 erhält, die ebenfalls in den C1-Cache gesetzt waren, oder wenn eine Zeile in dem C2-Cache eine Datenkopie ergibt, die in den C1-Cache gesetzt wird, dann ist ein Inklusions-Bit für die jeweilige C2-Cache-Zeile wahr oder auf einen logisch hohen Wert gesetzt, was bezeichnet, daß die jeweilige C2-Cache- Zeile eine Datenkopie hält, die in dem jeweiligen C1-Cachewegeplatz dupliziert ist. Die anderen 63 Zeilenplätze in dem C2- Cache, welche dem jeweiligen bei dem genannten Vorgang beteiligten C1-Cachewegeplatz entsprechen, haben gelöschte Inklusions-Bits als eine Erinnerungshilfe, daß die Datenkopie, die sie halten, nicht in dem C1-Cache-Platz dupliziert ist. Das ist wichtig, weil eine dieser anderen 63 Zeilenplätze Daten halten kann, die vorher in dem jeweiligen C1-Cache-Platz dupliziert waren, bevor einer der erwähnten Vorgänge neue Daten an den jeweiligen C1-Cache-Platz gesetzt hat, und deshalb kann einer dieser 63 Plätze sein Inklusions-Bit gesetzt haben. Der einzige Fall, bei dem einer dieser anderen 63 C2-Cache-Plätze sein Inklusions-Bit nicht gesetzt hätte, ist dann, wenn der jeweilige C2-Cache-Zeilenplatz, der bei dem genannten Vorgang beteiligt war und sein Inklusions-Bit gesetzt hatte, auch die Kopie von Daten hielt, die in dem jeweiligen C1-Cache-Platz dupli ziert waren, bevor der Vorgang stattfand, und deswegen bereits sein Inklusions-Bit gesetzt hatte.
In den Fig. 4A und 4B ist ein den Betrieb der C1- und C2-Caches gemäß der vorliegenden Erfindung beschreibendes Flußdiagramm gezeigt. Es ist zu verstehen, daß zahlreiche dieser Vorgänge gleichzeitig auftreten können, jedoch wurde ein Flußdiagrammformat gewählt, um die Erklärung der Vorgänge oder des Betriebes zu vereinfachen. Zur Klarstellung ist das Flußdiagramm in zwei Abschnitten gezeigt, wobei die Verbindungen zwischen Fig. 4A und 4B mit den eingekreisten Zahlen 1 und 2 bezeichnet sind. Schritt 100 stellt dar, daß das Computersystem arbeitet oder eingeschaltet ist. Bei manchen Computersystemen ist es erforderlich, daß der Prozessor Kontrolle über den Systembus 24 besitzt, bevor er Speicher-Lese- oder -Schreib-Vorgänge ausgibt. Bei dem System S nach der bevorzugten Ausführung ist es jedoch nicht erforderlich, daß der Prozessor 20 Kontrolle über den Systembus 24 hat, wenn er Speicher-Lese- oder -Schreib-Voränge ausgibt, sondern der Prozessor 20 kann aus seinem C1-Cache und dem C2-Cache arbeiten, ohne daß eine Verwendung des Systembus 24 erforderlich ist, bis ein C1- und C2-Cache-Lesefehlschlag oder ein Prozessor-Schreibvorgang jenseits jeder Ankündigungstiefe auftritt.
Wenn der Prozessor 20 im Schritt 102 einen Hauptspeicher- Lesevorgang versucht, prüft die C1-Cachesteuerung 30 zuerst im Schritt 104 den C1-Cache, um zu bestimmen, ob eine Kopie der angeforderten Hauptspeicher-Daten in dem C1-Cache sitzt. Falls keine Kopie der angeforderten Daten in dem C1-Cache sitzt, tritt ein C1-Cache-Lesefehlschlag im Schritt 106 auf, und der Lesebetrieb wird an den C2-Cache weitergegeben, wo die C2- Cachesteuerung 32 dann im Schritt 108 den C2-Cache prüft. Falls eine Kopie der angeforderten Daten auch nicht im C2-Cache sitzt, tritt im Schritt 110 ein C2-Cache Lesefehlschlag auf, und der Vorgang wird an die Systemspeichersteuerung weitergereicht, um die ntowendigen Daten vom Hauptspeicher 26 zu erhalten.
Der Hauptspeicher 26 sorgt im Schritt 112 für die angeforderten Daten für den C1-Cache, den C2-Cache und den Prozessor 20, und die C1-Cachesteuerung 30 setzt im Schritt 114 die Daten entsprechend ihrem bestimmten Ersetzungs-Algorithmus in einen ihrer Cachewege A1 oder B1. Die Daten werden in den C1-Cache gesetzt wegen der statistischen Wahrscheinlichkeit, daß diese Daten bald wieder vom Prozessor 20 angefordert werden. Die C1- Cachesteuerung 30 hat während dieses Zeitraums der C2-Cachesteuerung 32 den bestimmten C1-Cacheweg A1 oder B1 gesendet, in welchen sie die Daten einsetzt, wie im Schritt 118 dargestellt, so daß die C2-Cachesteuerung 32 im Schritt 120 die Daten in den entsprechenden C2-Cacheweg A2 oder B2 setzen kann. Die C2- Cachesteuerung 32 setzt im Schritt 122 das Inklusions-Bit an den jeweiligen C2-Cache-Speicherplatz, wo die Daten gespeichert sind, was bezeichnet, daß eine Kopie der an diesem Platz befindlichen Daten ebenfalls in dem C1-Cache sitzt. Die C2- Cachesteuerung 32 löscht im Schritt 124 auch die Inklusions- Bits an den anderen 32 C2-Cacheplätzen, die dem gleichen Seitenversetzplatz in dem C1-Cache entsprechen, um zu bezeichnen, daß keine Kopie der Daten in diesen Plätzen in dem C1- Cache sitzt. Nach Vollendung der Speicherauslesung kehrt das Computersystem zum Schritt 100 zurück.
Die genannte Ereignisfolge tritt bei einem C1- und C2-Cache-Lesefehlschlag auf, aber auch dann, wenn das Computersystem S zuerst eingeschaltet wird, da die C1- und C2-Caches beim Einschalten des Computersystems S beide leer und C1- und C2- Cache-Fehlschläge deswegen garantiert sind. Die Mehrzahl der Prozessor-Speicherlesevorgänge, die unmittelbar nach Einschalten des Computersystems S auftreten, werden C1- und C2-Cache- Fehlschläge sein, da die C1- und C2-Caches zu diesem Zeitpunkt relativ leer sind. Auf diesen Weise werden die C1- und C2- Caches mit Daten gefüllt und richten sich auf einer "Wege"- Grundlage aus, bei der Daten in einem bestimmten Weg A1 oder B1 in dem C&sub1;-Cache garantiert in dem entsprechenden Cacheweg A2 oder B2 im C2-Cache gefunden werden können. Wenn zusätzlich das Computersystem S eine gewisse Zeit gearbeitet hat und ein C1- und ein C2-Cache-Lesefehlschlag auftritt, werden die sich ergebenden Zeilenauffüllungen mit Daten wie vorstehend beschrieben in den C1- und C2-Caches ausgeführt, und deswegen wird die "Wege"-Ausrichtung aufrecht erhalten.
Wenn der Prozessor 20 im Schritt 102 einen Hauptspeicher- Lesevorgang einleitet und die C2-Cachesteuerung 32 im Schritt 180 den C2-Cache prüft, nachdem ein C1-Cache-Fehlschlag im Schritt 106 aufgetreten ist, und eine Kopie der angeforderten Daten in dem C2-Cache sitzt, tritt im Schritt 130 ein C2-Cache- Treffer auf. Die C2-Cachesteuerung 32 schafft die angeforderten Daten im Schritt 132 zum Prozessor 20 und versorgt auch den C1- Cache im Schritt 134 mit Daten infolge der statistischen Wahrscheinlichkeit, daß diese Daten bald wieder durch den Prozessor 20 angefordert werden. Die C2-Cachesteuerung 32 informiert die C1-Cachesteuerung 30 im Schritt 136 über den bestimmten C2-Cacheweg A2 oder B2, in denen die Daten in dem C2-Cache sitzen, so daß die C1-Cachesteuerung 30 die Daten in den entsprechenden C1-Cacheweg A1 oder B1 im Schritt 138 einsetzen kann. Das erfordert, daß die C&sub1;-Cachesteuerung 30 ihren normalen LRU-Ersetzungs-Algorithmus mißachtet, da der Ersetzungs-Algorithmus einen anderen C1-Cacheweg A1 oder B1 zum Einsetzen der Daten wählen könnte. Auf diese Weise halten die Caches C1 und C2 ihre "Wege"-Ausrichtung aufrecht, ohne daß es für die C2-Cachesteuerung 32 notwendig ist, Daten zwischen den Wegen im C2-Cache zu übertragen. Die C2-Cachesteuerung 32 setzt im Schritt 140 das Inklusions-Bit an den C2-Cacheplatz, wo sich die angeforderten Daten befinden, wodurch bezeichnet wird, daß eine Kopie dieser Daten auch in dem C1-Cache sitzt. Die C2- Cachesteuerung 32 löscht auch die anderen 63 Inklusions-Bits an den C2-Cache-Speicherplätzen, die dem gleichen Seitenversetzplatz entsprechen, um zu bezeichnen, daß keine Kopie der Daten in diesen Plätzen in dem C1-Cache sitzt. Das Computersystem S hat dann den Speicherlesevorgang beendet und kehrt zum Schritt 100 zurück.
Wenn der Prozessor 20 eine Speicherlesung im Schritt 102 einleitet und die Inhalte des C1-Caches im Schritt 104 prüft, um zu bestimmen, ob eine Kopie der angeforderten Daten dort sitzt, und eine Kopie der angeforderten Daten in dem C1-Cache sitzt, findet im Schritt 150 ein C1-Cache-Treffer statt. Die C1-Cachesteuerung 30 schafft im Schritt 152 die angeforderten Daten zu dem Prozessor 20, und der Betrieb des Computersystems 5 wird zum Schritt 100 zurückgeführt. Da Mehrstufen-Inklusion im dem Cache-Teilsystem vorhanden ist, ist garantiert, daß der C2-Cache eine Kopie der Daten besitzt, welche die C1-Cachesteuerung 30 zum Prozessor 20 geschafft hat, und keine Datenübertragung von der C1-Cachesteuerung 30 zu der C2-Cachesteuerung 32 notwendig ist, wenn ein C1-Cache-Lesetreffer stattfindet.
Die Cache-Architektur des C1-Caches in der bevorzugten Ausführung ist vorzugsweise eine Durchschreibe-Cache-Architektur, und die Cache-Architektur des C2-Caches ist vorzugsweise eine Rückschreibe-Cache-Architektur. Jedoch kann auch die Verwendung anderer Cache-Architekturen für den C1-Cache und für den C2- - Cache ins Auge gefaßt werden. Wenn der Prozessor 20 einen Speicherschreibebetrieb ausführt, werden die Daten in den C1- Cache eingeschrieben, ohne Rücksicht darauf, ob der Prozessor- Schreibvorgang ein C1-Cache-Schreibtreffer oder ein -Schreibfehlschlag ist. Zusätzlich leiten Prozessor-Schreibvorgänge externe Schreib-Buszyklen ein, um die jeweiligen Daten in den C2-Cache einzuschreiben. Wenn dies auftritt, sendet die C&sub1;- Cachesteuerung 30 den bestimmten C1-Cacheweg, wo die Daten eingesetzt wurden, so daß die C2-Cachesteuerung 32 die Daten in den entsprechenden C2-Cacheweg setzen kann. Deshalb ordnen die C1- und C2-Caches Schreibfehlschläge gemäß der vorliegenden Erfindung. Es wird bevorzugt, daß die C1- und die C2-Caches entweder miteinander Schreibfehlschläge ordnen oder miteinander Schreibfehlschläge nicht ordnen. Wenn der C1-Cache keine Schreibvorgänge ordnete und der C2-Cache verpflichtet wäre, diese zu ordnen, wäre die Auslegung komplizierter. Die C2- Cachesteuerung 32 würde einen LRU-Algorithmus erfordern und würde sicherstellen müssen daß, wenn der C2-Cachesteuerungs- LRU-Algorithmus einen bestimmten C2-Cacheweg ausgewählt hat, der eine in dem C1-Cache duplizierte Datenkopie enthält, der LRU-Algorithmus überfahren oder das Cache-Einspeichern abgebrochen werden müßte, damit die mehrstufige Inklusion garantiert bleibt.
Wenn nach Fig. 5 der intelligente Busmaster 28 im Schritt 200 Kontrolle über den Systembus 24 erhält, überwacht oder "beobachtet" die C2-Cachesteuerung 32 den Systembus 24 im Schritt 202, um zu sehen, ob der Busmaster 28 irgendwelche Schreibvorgänge ausführt, und in dem Fall eines Rückschreibe-Cache zum Hauptspeicher 26 liest, und wenn das der Fall ist, auf welchen Speicherplatz zugegriffen wurde. Die C2-Cachesteuerung 32 kann die Beobachtungs-Verantwortlichkeiten sowohl für den C1- wie auch für den C2-Cache ausführen, da der C2-Cache garantiert infolge der Mehrstufen-Inklusion eine Kopie aller in dem C1- Cache vorhandenen Daten besitzt.
Wenn der Busmaster 28 im Schritt 204 in den Hauptspeicher 26 schreibt und im Schritt 206 ein Schreib-Beobachtungstreffer in dem C2-Cache erfolgt, prüft die C2-Cachesteuerung 32 im Schritt 208 das Inklusions-Bit für den jeweiligen C2-Cacheplatz, um zu sehen, ob die C1-Cachesteuerung 30 ebenfalls den Speicherzugriff beobachten muß. Wenn das Inklusions-Bit im Schritt 208 als nicht gesetzt befunden wird, ist in dem C1-Cache keine Kopie der Daten von dem gerade beschriebenen Speicherplatz vorhanden, und die C1-Cachesteuerung 30 wird in Ruhe gelassen. In diesem Fall empfängt der C2-Cache im Schritt 210 die neue Kopie von Daten, und die C2-Cachesteuerung 32 nimmt im Schritt 202 ihre Beobachtungspflichten wieder auf. Falls das Inklusions-Bit im Schritt 208 nach einem Beobachtungstreffer im Schritt 206 an den C2-Cache-Speicherplätzen gesetzt ist, leitet die C2-Cachesteuerung die C1-Cachesteuerung 30 im Schritt 212 an, diesen bestimmten Speicherzugriff zu beobachten. Im Schritt 214 erhalten die C1- und C2-Caches jeweils eine Kopie der neuen Daten, und die C2-Cachesteuerung 32 nimmt im Schritt 202 ihre Beobachtungspflichten wieder auf. Wenn im Schritt 206 ein Beobachtungs-Fehlschlag auftritt, nachdem der Busmaster 28 im Schritt 204 in einen Speicherplatz geschrieben hat, nimmt die C2-Cachesteuerung 32 ihre Beobachtungspflichten im Schritt 202 wieder auf. Die C2-Cachesteuerung 32 setzt im Schritt 202 ihre Überwachung des Systembus 24 fort, bis der Busmaster 28 nicht mehr die Kontrolle über den Systembus 24 hat.
Wenn der Busmaster 28 im Schritt 204 einen Hauptspeicherplatz liest und im Schritt 220 ein Lese-Beobachtungstreffer im C2- Cache auftritt, prüft die C2-Cachesteuerung 32 im Schritt 222 den C2-Cacheplatz, um zu bestimmen, ob dieser der Eigner des jeweiligen Speicherplatzes ist. Falls nicht, fordern der Hauptspeicher 26 oder andere Quellendienste die Daten an, und die C2-Cachesteuerung 32 nimmt im Schritt 202 die Beobachtung wieder auf. Wenn die C2-Cachesteuerung 32 Eigner des Speicherplatzes ist, sorgt die C2-Cachesteuerung 32 dafür, daß die angeforderten Daten im Schritt 224 zum Hauptspeicher 26 gebracht werden. Der Busmaster 28 liest diese Daten im Schritt 226, wenn die Daten an dem Datenbus gesetzt sind, und dies wird als "Wegschnappen" (snarfing) bezeichnet. Die C2-Cachesteuerung 32 nimmt dann ihre Beobachtungspflichten im Schritt 202 wieder auf. Wenn im Schritt 220 ein Beobachtungs-Fehlschlag auftritt, nachdem der Busmaster 28 einen Speicherplatz im Schritt 204 gelesen hat, nimmt die C2-Cachesteuerung 32 ihre Beobachtungspflichten im Schritt 202 wieder auf.
Auf diese Weise kann die C1-Cachesteuerung 30 ihre Beobachtungspflichten unbeachtet lassen, bis die C2-Cachesteuerung 32 bestimmt, daß aktuell ein Beobachtungstreffer an in dem C1- Cache gehaltenen Daten aufgetreten ist. Das erlaubt dem Prozessor 20, wirksamer aus dem C1-Cache zu arbeiten, während er keine Kontrolle über den Systembus 24 besitzt, da die C1-Cache- Steuerung 30 den Systembus 24 nur zu beobachten hat, wenn ein C1-Cache-Beobachtungstreffer auftritt, und nicht bei jedem Speicherschreibvorgang, wie es normalerweise der Fall wäre.
Die vorangehende Offenbarung und Beschreibung der Erfindung sind für diese illustrativ und erklärend, und verschiedene Änderungen in der Größe, den Bestandteilen, dem Aufbau und der Betriebsweise können hergestellt werden, ohne den beanspruchten Bereich der Erfindung zu verlassen.

Claims

1. Verfahren zum Erreichen von Mehrstufen-Inklusion bei einem Computersystem mit einem Mikroprozessor (20), einem Systembus (24), einem satz-assoziativen Erststufen-Cache (C1), der eine erste Zahl von Wegen enthält, einer Erststufen- Cachesteuerung (30), einem satz-assoziativen Zweitstufen- Cache (C2), der eine zweite Zahl von Wegen enthält, einer Zweitstufen-Cachesteuerung (32), mit der Zweitstufen-Cachesteuerung gekoppeltem Mittel zum Einstellen und Löschen eines Inklusionsbits an Daten innerhalb des Zweitstufen- Cache, mit der Erst- und der Zweitstufen-Cachesteuerung gekoppelte Mittel zum Kommunizieren und Übertragen von Daten zwischen den Erststufen- und Zweitstufen-Caches, einem Busmastergerät (28), und einem RAM-Speicher (26), welches Verfahren dadurch gekennzeichnet ist, daß:

die zweite Wegezahl des Zweitstufen-Caches gleich oder größer als die erste Wegezahl des Erststufen-Caches ist, wobei jeder der Wege in dem Erststufen-Cache mindestens einem Weg in dem Zweitstufen-Cache entspricht;

die Erststufen-Cachesteuerung mit der Zweitstufen-Cachesteuerung über den besonderen Erststufen-Cacheweg kommuniziert, in welchen eine Kopie von von dem RAM-Speicher empfangenen Daten an einem Erststufen- und an einem Zweitstufencache-Lesefehlschlag gesetzt ist;

die Zweitstufen-Cachesteuerung die Kopie von von dem RAM- Speicher empfangenen Daten in den Zweitstufen-Cacheweg setzt, der dem Erststufen-Cacheweg entspricht, der durch die Erststufen-Cachesteuerung an dem Erststufen- und dem Zweitstufencache-Lesefehlschlag zum Kommunizieren gebracht wurde;

die Zweitstufen-Cachesteuerung mit der Erststufen-Cache steuerung über den bestimmten Zweitstufen-Cacheweg kommuniziert, wo eine Kopie von Daten an einem Erststufencache- Lesefehlschlag und einem Zweitstufencache-Lesetreffer gelegen ist;

die Erststufen-Cachesteuerung die Kopie von von der Zweitstufen-Cachesteuerung zu dem Prozessor übermittelten Daten in den entsprechenden Erststufen-Cacheweg setzt; und die Zweitstufen-Cachesteuerung ein Inklusionsbit an dem Zweitstufen-Cacheplatz der Kopie von Daten setzt und Inklusionsbits an allen anderen Zweitstufen-Cacheplätzen löscht, die dem Erststufen-Cacheplatz entsprechen, wo die Erststufen-Cachesteuerung die Datenkopie gesetzt hat.

2. Verfahren nach Anspruch 1, bei dem die Erststufen-Cachesteuerung einen Ersetzungs-Algorithmus benutzt, der den Erststufen-Cacheweg bestimmt, in welchen eine empfangene Kopie von Daten zu setzen ist, und der Schritt des Kopierens der Daten durch die Erststufen-Cachesteuerung in den dem Zweitstufen-Cacheweg entsprechenden Erststufen-Cacheweg enthält:

daß die Erststufen-Cachesteuerung ihren Ersetzungs-Algorithmus in Fällen des Erststufencache-Lesefehlschlages und des Zweitstufencache-Lesetreffers nicht beachtet.

3. Verfahren nach Anspruch 1, das weiter umfaßt:

Kommunizieren der Erststufen-Cachesteuerung mit der Zweitstufen-Cachesteuerung über den bestimmten Erststufen-Cacheweg, in welchen eine Kopie der empfangenen Daten in einer Prozessor-Schreibung gesetzt ist; und

Setzen der Kopie der empfangenen Daten durch die Zweitstufen-Cachesteuerung in den Zweitstufen-Cacheweg, der dem Erststufen-Cacheweg entspricht, über den die Erststufen- Cachesteuerung kommuniziert hat.

4. Verfahren nach Anspruch 1, bei dem mehr als ein Weg in dem Erststufen-Cache nicht einem Weg in dem Zweitstufen-Cache entsprechen kann und mehr als ein Weg in dem Zweitstufen- Cache einem Weg in dem Erststufen-Cache entsprechen kann.

5. Verfahren nach Anspruch 1, das weiter umfaßt:

Beobachten des Systembuses durch die Zweitstufen-Cachesteuerung, wenn der Prozessor keine Kontrolle über den Systembus innehat, um zu bestimmen, ob das Busmastergerät in einen cacheduplizierten Speicherplatz einschreibt;

Überprüfen des Inklusionsbits durch die Zweitstufen-Cachesteuerung an einem Zweitstufen-Cacheplatz, wo ein Zweitstufencache-Schreibbeobachtungs-Treffer auftritt, um zu bestimmen, ob eine Kopie von Daten in dem RAM-Speicherplatz, in den gerade geschrieben wurde, in dem Erststufen-Cache sitzt; und

Anleiten der Erststufen-Cachesteuerung durch die Zweitstufen-Cachesteuerung, den Systembus zu beobachten, falls das Inklusionsbit gesetzt ist.

6. Verfahren nach Anspruch 5, bei dem der Zweitstufen-Cache ein Rückschreibe-Cache ist, wobei das Verfahren weiter umfaßt:

Beobachten des Systembus durch die Zweitstufen-Cachesteuerung, wenn der Prozessor keine Kontrolle über den Systembus innehat, um zu bestimmen, ob das Busmastergerät einen cacheduplizierten Speicherplatz liest;

Bestimmen durch die Zweitstufen-Cachesteuerung bei einem Zweitstufencache-Lesebeobachtungstreffer, ob der Zweitstufen-Cache eine aktualisierte Version der in dem fraglichenen Speicherplatz befindlichen Daten besitzt;

Zuführen der angeforderten Daten zu dem Hauptspeicher durch die Zweitstufen-Cachesteuerung, falls der Zweitstufen-Cache eine aktualisierte Version der Daten besitzt; und

Lesen der angeforderten durch die Zweitstufen-Cachesteuerung zugeführten Daten durch die Bussteuerung.

7. Vorrichtung zum Erreichen von Mehrstufeninklusion in einem Computersystem mit:

einem Systembus (24);

einem mit dem Systembus gekoppelten RAM-Speicher (26);

einem mit dem Systembus gekoppelten Mikroprozessor (20);

einem satz-assoziativen Erststufen-Cache (C1), der mit dem Mikroprozessor gekoppelt ist und eine erste Anzahl von Wegen enthält;

eine Erststufen-Cachesteuerung (30), die mit dem Erststufen-Cache und dem Mikroprozessor und dem Systembus gekoppelt ist;

einem satz-assoziativen Zweitstufen-Cache (C2) mit einer Größe, die größer als die oder gleich der Größe des Erststufen-Caches ist, und eine zweite Anzahl von Wegen enthält und Inklusionsinformation enthält, die die Anwesenheit von Daten in dem Zweitstufen-Cache anzeigt, die in dem Erststufen-Cache dupliziert sind;

eine Zweitstufen-Cachesteuerung (31), die mit dem Systembus, dem Zweitstufen-Cache, dem Mikroprozessor und der Erststufen-Cachesteuerung gekoppelt ist, wobei die Vorrichtung dadurch gekennzeichnet ist, daß die zweite Anzahl von Wegen des Zweitstufen-Caches gleich groß wie oder größer als die erste Anzahl von Wegen des Erststufen-Caches ist, wobei jeder der Wege in dem Erststufen-Cache mindestens einem Weg in dem Zweitstufen-Cache entspricht;

daß die Erststufen-Cachesteuerung einen Ausgang zum Senden von Wege-Information und einen Eingang zum Empfangen von Wege-Information enthält;

die Zweitstufen-Cachesteuerung einen Eingang enthält, der mit dem Wege-Informations-Ausgang der Erststufen-Cachesteuerung zum Aufnehmen von Wege-Informätion gekoppelt ist, und einen Ausgang, der mit dem Wege-Tnformations-Eingang der Erststufen-Cachesteuerung verbunden ist zum Senden von Wege-Information; wobei bei einem Erst- und Zweitstufen- Cachelesefehlschlag die Erststufen-Cachesteuerung ausgelegt ist, Wege-Information zu der Zweitstufen-Cachesteuerung zu senden und die Zweitstufen-Cachesteuerung ausgelegt ist, empfangene Daten in einen Weg des Zweitstufen-Caches zu setzen, der der empfangenen Wege-Information entspricht, wobei bei einem Erststufen-Cachelesefehlschlag und einem Zweitstufen-Cachelesetreffer die Zweitstufen-Cachesteuerung ausgelegt ist, Wege-Information zu der Erststufen-Cachesteuerung zu senden und die Erststufen-Cachesteuerung ausgelegt ist, empfangene Daten in einen Weg des Erststufen- Caches zu setzen, der der empfangenen Wege-Information entspricht, und wobei die Zweitstufen-Cachesteuerung ausgelegt ist, das Inklusionsbit in den Zweitstufen-Cacheplatz zu setzen, der die in den Erststufen-Cache gesetzte Daten enthält und ausgelegt ist, die Inklusionsbits von jedem anderen Zweitstufen-Cacheplatz zu löschen, welche dem Erststufen-Cacheplatz entspricht, wo die Daten gesetzt waren.

8. Vorrichtung nach Anspruch 7, bei der die Erststufen-Cachesteuerung eine Ersetzungseinrichtung enthält, die den Erststufen-Cacheweg bestimmt, in welchen eine empfangene Datenkopie zu setzen ist, wobei die Erststufen-Cachesteuerung ausgelegt ist, die Ersetzungseinrichtung bei Fällen von Erststufencache-Lesefehlschlag und Zweitstufencache-Lesetreffer außer Acht zu lassen.

9. Vorrichtung nach Anspruch 7, bei der mehr als ein Weg in dem Erststufen-Cache nicht einem Weg in dem Zweitstufen- Cache entsprechen kann und mehr als ein Weg in dem Zweitstufen-Cache einem Weg in dem Erststufen-Cache entsprechen kann.

10. Vorrichtung nach Anspruch 7, bei der bei einer Prozessorschreibung die Erststufen-Cachesteuerung ausgelegt ist, Wege-Information der Zweitstufen-Cachesteuerung zu übermitteln und die Zweitstufen-Cachesteuerung ausgelegt ist, empfangene Daten in einem Weg des Zweitstufen-Caches zu setzen, der der empfangenen Wege-Information entspricht.

11. Vorrichtung nach Anspruch 7, die weiter umfaßt:

ein mit dem Systembus gekoppeltes Busmastergerät (28); und bei der die Erststufen-Cachesteuerung Einrichtungen zum Beobachten des Systembus enthält, wenn der Mikroprozessor keine Kontrolle über den Systembus besitzt, um zu bestimmen, ob das Busmastergerät in einen RAM-Speicherplatz schreibt, der in dem Erststufen-Cache dupliziert ist, und bei dem die Zweitstufen-Cachesteuerung weiter enthält:

Einrichtung zum Beobachten des Systembus, wenn der Mikroprozessor keine Kontrolle über den Systembus innehat, um zu bestimmen, ob das Busmastergerät in einen RAM-Speicher zu schreiben, der in dem Zweitstufen-Cache dupliziert ist;

Einrichtung zum Überprüfen des Inklusionsbits an einem Zweitstufen-Cacheplatz, wo ein Zweitstufencache-Beobachtungstreffer auftritt, um zu bestimmen, ob eine Datenkopie von dem Platz in dem RAM-Speicher, in den geschrieben wurde, auch in dem Erststufen-Cache vorhanden ist; und Einrichtung, die mit der Erststufen-Cachesteuerung gekoppelt ist, um die Erststufen-Cachesteuerung anzuleiten, den Systembus zu beobachten, ob das Inklusionsbit gesetzt ist.

12. Vorrichtung nach Anspruch 11, bei der weiter:

der Zweitstufen-Cache ein Zurückschreibe-Cache ist, wobei die Zweitstufen-Cachesteuerung weiter enthält:

Einrichtung zum Beobachten des Systembus, wenn der Mikroprozessor keine Kontrolle über den Systembus besitzt, um zu bestimmen, ob das Busmastergerät einen RAM-Speicherplatz liest, der in den Zweitstufen-Cache dupliziert ist;

Einrichtung zum Bestimmen, ob der Zweitstufen-Cache, wenn ein Zweitstufencache-Lesebeobachtungstreffer aufgetreten ist, eine aktualisierte Version der in dem fraglichen Speicherplatz vorhandenen Daten enthält; und

Einrichtung zum Zuleiten der angeforderten Daten zum Hauptspeicher, falls der Zweitstufen-Cache eine aktualisierte Version der Daten besitzt, wobei die Bussteuerung die angeforderten durch die Zweitstufen-Cachesteuerung zugeführten Daten liest.