PatentDe  


Dokumentenidentifikation DE19532418A1 14.03.1996
Titel Cache-System zum Speichern von Daten
Anmelder GMD - Forschungszentrum Informationstechnik GmbH, 53757 Sankt Augustin, DE
Vertreter Patentanwälte von Kreisler, Selting, Werner et col., 50667 Köln
DE-Anmeldedatum 01.09.1995
DE-Aktenzeichen 19532418
Offenlegungstag 14.03.1996
Veröffentlichungstag im Patentblatt 14.03.1996
IPC-Hauptklasse G06F 12/08
Zusammenfassung Das Cache-System zum Speichern von Daten ist mit einem Cache-Hauptspeicher mit mehreren Einträgen versehen, von denen jeder mindestens ein Markierungsfeld für Adreßdaten und mindestens ein diesem zugeordnetes Datenfeld für Nutzdaten aufweist. Ferner ist mindestens ein Cache-Nebenspeicher mit mehreren Einträgen vorgesehen, von denen jeder pro Markierungsfeld eines Eintrages des Cache-Hauptspeichers ein Markierungsfeld aufweist. Der Cache-Hauptspeicher und jeder Cache-Nebenspeicher sind zwecks Ausführung von Operationsaufträgen auf dem Cache-Hauptspeicher mit identischen oder unterschiedlichen Adressen indizierbar. Zum Übertragen der Inhalte von Markierungsfeldern des Cache-Hauptspeichers zu jedem Cache-Nebenspeicher und umgekehrt eine Verbindung zwischen dem Cache-Hauptspeicher und jedem Cache-Nebenspeicher vorgesehen.

Beschreibung[de]

Die Erfindung betrifft ein Cache-System mit vielfachparallelem Zugriff, das zusammen mit parallelen Bussen, Netzwerken oder Kreuzschaltwerken in multiskalaren, parallelen oder massiv-parallelen Rechnern eingesetzt werden kann.

1. Caches in Mehrprozessorsystemen

Moderne Prozessoren benötigen Cache-Speicher, um die Lücke zwischen schnellen Prozessoren und langsamen Hauptspeichern auszugleichen. In Mehrprozessorsystemen findet man Strukturen wie in Fig. 22. Dabei benutzen l bis k aktive Prozessorelemente Pi,j einen Cache Ci gemeinsam. Pi,1 . . . Pi,k können spezielle Werke eines einzelnen Prozessors sein (Instruction-Fetch- und eine oder mehrere Integer- und Floating-Point-Units) oder aber auch komplette Prozessoren sein. Neben einer oder mehreren Verbindungen zu Speicherelementen hat jeder Cache Ci auch n-1 Verbindungen zu den anderen Caches. Die Inter-Cache-Verbindungen dienen zur Realisierung von Cache-Kohärenz-Protokollen (siehe unter 1.3). In vielen Fällen werden die Inter-Cache-Verbindungen nicht durch einen n×n Crossbar, sondern durch ein kostengünstigeres Verbindungsnetzwerk realisiert, im Extremfall durch einen einfachen oder Mehrfach-Bus. Der Typ des Verbindungsnetzwerks ist für das Folgende aber irrelevant, solange ein Cache mehrere Aufträge pro Cache-Zyklus erhalten kann.

Allgemein wird die in Fig. 23 gezeigte Situation betrachtet, wo n sogenannte Accessoren in einem Cache- Zyklus n Aufträge (aj, oj) an den Cache senden. Jeder Auftrag besteht dabei aus der angesprochenen Adresse aj und der durchzuführenden Operation oj.

1.1 Direct-mapped- und n-Wege-assoziative Caches

Bekannt sind reine real- und virtuell-adressierte Caches sowie die Mischform des real indizierten und virtuell markierten Cache. Die Unterschiede der einzelnen Cache-Typen sind für die Erfindung ohne Relevanz, da sich die Strukturen und Verfahren für alle diese Cache-Typen einsetzen lassen.

Bei direct-mapped Caches wird (s. Fig. 24) mit Hilfe einer map-Funktion aus der realen oder virtuellen Adresse a ein Cache-Index berechnet und damit eine Zeile des Caches angewählt. Dann wird a mit der Adresse des augenblicklich mit dieser Cache-Zeile assoziierten Speicherbereichs (der Markierung des Cache-Eintrags) verglichen. Bei Gleichheit liegt ein Treffer vor (und die Cache-Zeile wird anstelle des Hauptspeichers benutzt) andernfalls liegt ein Miss vor.

Meistens wird als map-Funktion die Vorschrift

(a mod Cache-Größe)/Zeilengröße

benutzt. Dann braucht im Cache nicht die vollständige virtuelle Adresse gespeichert zu werden, sondern es reicht a/Cache-Größe.

Direct-mapped Caches sind einfach aufgebaute und organisierte Caches, führen aber zu höheren Miss-Raten als n-Wege Caches. Diese bestehen prinzipiell aus n entsprechend kleineren direct-mapped Cache-Blöcken. Fig. 25 zeigt einen 2-Wege-assoziativen Cache. Dabei wird sichergestellt, daß sich jedes Hauptspeicherelement in höchstens einem Block befindet. Die map-Funktion adressiert immer eine ganze Zeile, d. h. n Cache-Einträge gleichzeitig. Alle n Markierungen werden parallel ausgelesen und mit der Adresse a verglichen. Scheitern alle Vergleiche, liegt ein Cache-Miss vor. Wird genau einmal Gleichheit festgestellt, liegt ein Treffer vor und der dem betreffenden Weg zugeordnete Cache-Eintrag wird benutzt.

Da jeweils n Cache-Einträge gleichzeitig adressiert werden, können jeweils bis zu n Elemente mit map-äquivalenten Adressen im Cache enthalten sein. Diese n- fache Assoziativität verringert die Wahrscheinlichkeit von Clashes und vergrößert entsprechend die Trefferrate.

1.2 Multiported Caches

Durch Verwendung von k-ported Speichern und k-facher Replikation der Steuerlogik kann man Caches bauen, die k Zugriffe parallel abarbeiten können. 2- und 3-ported Caches existieren; Caches mit wesentlich höheren Werten für k sind allerdings wegen des hohen Schaltungsaufwands unrealistisch.

1.3 Kohärenzprotokolle

Cache-Kohärenz wird durch Versenden von Invalidate- oder Update-Botschaften an die anderen Caches sichergestellt. Empfängt ein Cache eine Invalidate-Botschaft für eine Adresse, die er aktuell hält, invalidiert er den entsprechenden Cache-Eintrag, so daß ein erneuter Zugriff zu einem Cache-Miss führt. Bei einem Update- Auftrag wird zusätzlich zur Adresse auch der neue Wert mitgeschickt, so daß der Cache diesen übernehmen kann und der Cache-Eintrag gültig bleibt. Die im Rahmen dieser Erfindung beschriebenen Systeme erlauben beide Methoden.

Cache-Kohärenz-Protokolle basieren auf Broadcast- oder gezielten Multicast-Mechanismen. Im ersten Fall wird die Invalidate- oder Update-Botschaft immer an alle Caches geschickt. Jeder Cache prüft dann, ob er betroffen ist oder nicht. Das bekannteste Verfahren dieser Art ist Bus-Snooping. Verzeichnis-basierte Verfahren führen darüber Buch, in welchen Caches sich aktuell Kopien jedes Speicherbereichs befinden. Bei Invalidate oder Update brauchen dann nur die Caches per Multicast benachrichtigt zu werden, die für diese Adresse als aktiv markiert sind.

Der Typ des Kohärenz-Protokolls ist für die Erfindung von untergeordneter Bedeutung.

2. Aufgabe/Lösung

Es soll ein Cache-System entwickelt werden, das vielfach parallelen Cache-Zugriff effizient unterstützt.

Zur Lösung dieser Aufgabe wird mit der Erfindung ein Cache-System mit den Merkmalen des Anspruchs 1 oder des Anspruchs 12 vorgeschlagen. Vorteilhafte Ausgestaltungen der Erfindung sind jeweils in den Unteransprüchen angegeben.

Gemäß einer ersten Variante der Erfindung ist das Cache-System zum Speichern von Daten versehen mit

  • - einem Cache-Hauptspeicher mit mehreren Einträgen, von denen jeder mindestens ein Markierungsfeld für Adreßdaten und mindestens ein diesem zugeordnetes Datenfeld für Nutzdaten aufweist,
  • - mindestens einen Cache-Nebenspeicher mit mehreren Einträgen, von denen jeder pro Markierungsfeld eines Eintrages des Cache-Hauptspeichers ein Markierungsfeld aufweist,
  • - wobei der Cache-Hauptspeicher und jeder Cache- Nebenspeicher zwecks Ausführung von Operationsaufträgen auf dem Cache-Hauptspeicher mit identischen oder unterschiedlichen Adressen indizierbar sind, und
  • - einer Verbindung zwischen dem Cache-Hauptspeicher und jedem Cache-Nebenspeicher zum Übertragen der Inhalte von Markierungsfeldern des Cache-Hauptspeichers zu jedem Cache-Nebenspeicher und umgekehrt (s. Fig. 1).


Bei dem erfindungsgemäßen Cache-System sind also die Inhalte der Markierungsfelder des Cache-Hauptspeichers auch in den Cache-Nebenspeichern abgelegt. Aktualisierungen der Markierungsfelder werden über die Verbindung vom Cache-Hauptspeicher zu jedem Cache-Nebenspeicher propagiert. Ein zur Invalidierung eines Markierungsfeldes angesprochener Cache-Nebenspeicher gibt diese Information an den Cache-Hauptspeicher weiter.

Zweckmäßigerweise sind also die Inhalte der Markierungsfelder der Cache-Nebenspeicher gleich den Inhalten der Markierungsfelder des Cache-Hauptspeichers.

In vorteilhafter Weiterbildung der Erfindung ist vorgesehen,

  • - daß jeder Eintrag des Cache-Hauptspeichers mehrere Markierungsfelder aufweist,
  • - daß sämtliche Markierungsfelder des Cache-Hauptspeichers zu unterschiedlichen Gruppen zusammengefaßt sind, wobei jeder Gruppe pro Eintrag des Cache-Hauptspeichers genau ein Markierungsfeld zugeordnet ist,
  • - daß die Anzahl der Cache-Nebenspeicher gleich der Anzahl der Gruppen von Markierungsfeldern ist und
  • - daß jeder Cache-Nebenspeicher pro Eintrag eine der Anzahl von Gruppen von Markierungsfeldern des Cache-Hauptspeichers gleichende Anzahl von Markierungsfeldern aufweist, wobei pro Eintrag für jede Gruppe von Markierungsfeldern genau ein Markierungsfeld vorgesehen ist (s. Fig. 2).


Der Cache-Hauptspeicher ist also ein Mehr-Weg-assoziativer Cache, dessen Markierungsfelder in jedem der Cache-Nebenspeicher oder dessen Gesamtheit von Markierungsfeldern auf mehrere Cache-Nebenspeicher verteilt abgelegt sind (s. Fig. 1, 2, 5 und).

Sofern im vorgenannten sowie im nachfolgenden nicht ausdrücklich erwähnt ist, daß ein Eintrag bzw. ein Markierungsfeld ungültig ist, wird stets davon ausgegangen, daß der Eintrag bzw. das Markierungsfeld gültig ist.

Vorteilhafterweise wird das Cache-System derart betrieben, daß beim Eintreffen eines an den Cache-Hauptspeicher weiterzuleitenden Operationsauftrages bei einem Cache-Nebenspeicher zunächst der Cache-Nebenspeicher mit der Adresse indiziert wird und daß der Operationsauftrag dann an den Cache-Hauptspeicher weitergeleitet wird, wenn der Inhalt eines Markierungsfeldes des Cache-Nebenspeichers mit der Adresse übereinstimmt.

Zweckmäßigerweise weist das Cache-System mindestens zwei Cache-Nebenspeicher auf, wobei zwischen die Cache- Nebenspeicher und den Cache-Hauptspeicher eine Selektionsvorrichtung geschaltet ist, die im Falle von gleichzeitig von den Cache-Nebenspeichern an den Cache- Hauptspeicher weitergeleiteten Aufträgen auswählt, welcher Auftrag und/oder in welcher Reihenfolge die Aufträge jeweils an den Cache-Hauptspeicher weitergeleitet wird bzw. werden (s. Fig. 3).

In vorteilhafter Weiterbildung der Erfindung ist vorgesehen, daß jeder Eintrag eines Cache-Nebenspeichers um ein Pending-Order-Feld zur Zwischenspeicherung von Operationsaufträgen für den Cache-Hauptspeicher ergänzt ist, wobei der Auftrag nur dann zwischengespeichert wird, wenn die zur Indizierung eines Cache-Nebenspeichers verwendete Adresse mit dem Inhalt genau eines Markierungsfeldes dieses Cache-Nebenspeichers übereinstimmt und der Auftrag nicht unmittelbar an den Cache- Hauptspeicher weitergeleitet werden kann (s. Fig. 4).

Vorzugsweise ist die Summe der Anzahl der Markierungsfelder sämtlicher Cache-Nebenspeicher gleich der Anzahl der Markierungsfelder des Cache-Hauptspeichers, wobei die Inhalte der Menge der Markierungsfelder der Cache- Nebenspeicher eine mathematische Zerlegung der Inhalte der Menge der Markierungsfelder des Cache-Hauptspeichers sind und aufgrund einer von außen angelegten Adresse entschieden wird, in welchem Cache-Nebenspeicher sich der Inhalt des zu dieser Adresse gehörenden Markierungsfeldes befindet, sofern sich diese Adresse in einem Cache-Nebenspeicher befindet (s. Fig. 5 und 6).

Ferner kann nach der Erfindung vorgesehen sein,

  • - daß jeder Eintrag des Cache-Hauptspeichers mehrere Markierungsfelder aufweist,
  • - daß sämtliche Markierungsfelder des Cache-Hauptspeichers zu unterschiedlichen Gruppen zusammengefaßt sind, wobei zu jeder Gruppe pro Eintrag des Cache-Hauptspeichers genau ein Markierungsfeld zugeordnet ist,
  • - daß die Anzahl der Cache-Nebenspeicher gleich der Anzahl der Gruppen von Markierungsfeldern ist und
  • - daß jeder Cache-Nebenspeicher pro Eintrag ein Markierungsfeld und so viele Einträge aufweist, wie eine Markierungsfeld-Gruppe Markierungsfelder umfaßt (s. Fig. 5 und 6).


Vorzugsweise ist die Verbindung zwischen den Cache- Nebenspeichern und dem Cache-Hauptspeicher derart ausgebildet, daß Inhalte von Markierungsfeldern lediglich jeweils zwischen einer Gruppe von Markierungsfeldern des Cache-Hauptspeichers und den Markierungsfeldern des betreffenden Cache-Nebenspeichers austauschbar sind (Fig. 6).

In vorteilhafter Weiterbildung der Erfindung ist ferner vorgesehen,

  • - daß jedem Eintrag des Cache-Hauptspeichers eine Gruppeninformation zugeordnet ist,
  • - daß jedem Gruppeninformation ein Blockierungssignal zugeordnet ist, das sich im Setz-Zustand oder Rücksetz-Zustand befindet, und
  • - daß eine Operation mit einer Adresse auf dem Cache-Hauptspeicher nur dann durchführbar ist, wenn sich das Blockierungssignal, das der Gruppeninformation des mittels der Adresse adressierten Eintrages des Cache-Hauptspeichers zugeordnet ist, in dem Rücksetz-Zustand befindet (s. Fig. 7 bis 12).


Vorteilhafterweise setzt jeder Cache-Nebenspeicher, der einen nicht unmittelbar weiterleitbaren Auftrag zur Durchführung einer Operation mit einer Adresse auf dem Cache-Hauptspeicher zwischenspeichert, das der Gruppeninformation des Cache-Hauptspeichers zugeordnete Blockierungssignal, wobei dieses Blockierungssignal dann rückgesetzt wird, wenn in dem Cache-Nebenspeicher keine an den Cache-Hauptspeicher weiterzuleitende Aufträge mehr gespeichert sind (s. Fig. 10 bis 12).

Eine Variante des Cache-Systems zum Speichern von Daten ist versehen mit

  • - mehreren Cache-Speichern, die jeweils mehrere Einträge aufweisen, von denen jeder zumindest ein Markierungsfeld für Adreßdaten aufweist, und
  • - mindestens einer Verteilervorrichtung, die mit jedem Cache-Speicher gekoppelt ist, wobei die Verteilervorrichtung einen Operationsauftrag zur Durchführung einer Operation mit einer Adresse auf einem der Cache-Speicher empfängt und diesen Auftrag selektiv an ein oder mehrere Cache-Speicher weitergibt (s. Fig. 13 bis 18).


Die Cache-Speicher können als Cache-Hauptspeicher und/ oder als Cache-Nebenspeicher ausgebildet sein.

Vorzugsweise ist jedem Cache-Speicher eine Selektionsvorrichtung vorgeschaltet, wobei mehrere Verteilervorrichtungen vorgesehen sind, von denen jede mit jeder der den Cache-Speichern zugeordneten Selektionsvorrichtungen verbunden ist, wobei jede Selektionsvorrichtung im Falle des gleichzeitigen Empfangs mehrerer Aufträge von den Verteilervorrichtungen auswählt, welcher der Aufträge und/oder in welcher Reihenfolge die Aufträge an den zugeordneten Cache-Speicher weitergeleitet wird bzw. werden (s. Fig. 14 bis 17).

Insbesondere ist zwischen jede Selektionsvorrichtung und dem zugeordneten Cache-Speicher eine Puffervorrichtung zum Zwischenspeichern von Aufträgen geschaltet (s. Fig. 15 bis 17).

Sind den Aufträgen unterschiedliche Prioritäten zugeordnet, so wird zweckmäßigerweise gleichzeitigen Empfang mehrerer Aufträge durch die Verteilervorrichtungen denjenigen mit der höchsten Priorität Vorrang vor denjenigen mit niedrigerer Priorität gegeben (s. Fig. 16 bis 18).

Vorzugsweise werden die Aufträge mit höchster Priorität an den Verteilervorrichtungen vorbei sämtlichen Cache- Speichern zugeleitet (s. Fig. 17 und 18).

Insbesondere erfolgt die Verteilung der Aufträge an die Cache-Speicher anhand der Adresse.

Nachfolgend werden anhand der Figuren Ausführungsbeispiele der Erfindung näher erläutert. Im einzelnen zeigen:

Fig. 1 ein Cache-System mit einem direct-mapped Cache als Cache-Hauptspeicher und Schatten-Caches als Cache -Nebenspeicher,

Fig. 2 ein Cache-System mit einem 2-Wege-assoziativen Cache-Hauptspeicher und Schatten-Caches als Nebenspeicher,

Fig. 3 ein Cache-System mit einer Selektionsvorrichtung zwischen dem Cache-Hauptspeicher, der mit einem Prozessor kommuniziert, und den Cache- Nebenspeichern,

Fig. 4 einen Cache-Nebenspeicher mit um ein Pending- Order-Feld ergänzten Einträgen,

Fig. 5 ein Cache-System mit einem Cache-Hauptspeicher und Adreß-selektiven Cache-Nebenspeichern,

Fig. 6 ein Cache-System mit einem 2-Wege-assoziativen Cache-Hauptspeicher und mit Weg-selektiven Cache-Nebenspeichern,

Fig. 7 ein Cache-System mit einer Blockierungssteuerung, die aus der Schattierung einer Adresse abgeleitet ist,

Fig. 8 ein Cache-System mit einer Blockierungssteuerung, wobei die Schattierung vom Cache-Hauptspeicher geliefert wird,

Fig. 9 ein Cache-System mit einer Blockierungssteuerung, wobei die Schattierung von einem TLB geliefert wird,

Fig. 10 ein Cache-System mit einem Cache-Hauptspeicher und mehreren Cache-Nebenspeichern, die über einen Block-Bus mit dem Prozessor verbunden sind,

Fig. 11 ein Cache-System mit Blockierungssteuerung durch Bit-Masken,

Fig. 12 ein Cache-System mit einem Block-Bus und selektiven Cache-Nebenspeichern,

Fig. 13 ein vierfach-paralleles Cache-System mit vier Cache-Moduln, wobei im linken Teil ein selektiver Zugriff und im rechten Teil ein assoziativer Zugriff auf die Cache-Moduln dargestellt ist,

Fig. 14 ein vierfach-paralleles Cache-System mit vier aktiven Accessoren, wobei im linken Teil eine Situation ohne Zugriffskonflikt und im rechten Teil eine Situation mit zwei Zugriffskonflikten gezeigt ist,

Fig. 15 ein vierfach-paralleles Cache-System mit den Cache-Moduln vorgeschalteten 3-fach-Puffern,

Fig. 16 ein vierfach-paralleles Cache-System mit den Cache-Moduln vorgeschalteten 3-fach-Puffern, wobei die einem der Verteilervorrichtung zugeführten Aufträge den den anderen Verteilern zugeführten Aufträgen vorgezogen werden,

Fig. 17 ein vierfach-paralleles Cache-System mit assoziativem Parallelzugriff, wobei latenzkritische Accessoren latenzunkritischen Accessoren vorgezogen werden.

Fig. 18 ein vierfach-paralleles Cache-System ohne Verteilervorrichtungen und mit assoziativem Parallelzugriff,

Fig. 19 eine mehrere Schatten-Caches aufweisende Verteilervorrichtung,

Fig. 20 eine alternative Verteilervorrichtung, die einen Schatten-Cache aufweist,

Fig. 21 eine Verteilervorrichtung mit einem über die Schattierung verteilenden Schatten-Cache,

Fig. 22 ein Mehrprozessorsystem mit Cache-Speichern,

Fig. 23 einen Cache-Speicher mit mehreren Accessoren,

Fig. 24 einen direct-mapped Cache-Speicher und

Fig. 25 einen 2-Wege-assoziativen Cache-Speicher.

3. Schattencache 3.1 Einfacher Schattencache

Ein normaler Cache besteht aus Markierungs- und Datenfeldern. Ein einfacher Schattencache ist die Replikation des Caches ohne die Datenfelder. Fig. 1 zeigt einen direct-maapped, Fig. 2 einen 2-Wege assoziativen Cache mit Schattencaches. Sowohl der Cache-Hauptspeicher C als auch die Schatten-Cache-Nebenspeicher Si erhalten Aufträge von außen, die jeweils aus einer durchzuführenden Operation o und der angesprochenen Adresse a bestehen. Änderungen in den Markierungsfeldern werden über den sogenannten Schattenbus (Verbindung zwischen dem Cache C und den Schattencaches Si) vom Cache C an die Schattencaches Si geschickt.

Ist C ein normaler Cache und S ein Schattencache davon, muß für alle Adressen a immer die Invarianzaussage

hit (a,C) ⇐ hit(a, S)

gelten. Hierbei ist hit eine boolesche Funktion, die genau dann den Wert true annimmt, wenn der spezifizierte Cache bei der angegebenen Adresse einen Treffer liefert.

Ein Schattencache kann mehr als nur die Treffer-Information (hit/miss) liefern, beispielsweise auch den Weg und die Zeilenadresse des angesprochenen Eintrags. Wird das ausgenutzt, müssen die Informationen des Schattencaches im Trefferfall immer mit den entsprechenden Informationen des Caches konsistent sein.

Um treffer-respektive weitergehende Konsistenz zu erhalten, propagiert der Cache Änderungen in den Markierungsfeldern an alle seine Schattencaches. Aufgrund der oben angegebenen Invarianzbedingung können Invalidierungen durchaus verzögert werden, nicht aber Neueintragungen im Cache. Diese werden vor dem Gültigwerden des Cache-Eintrags an die Schattencaches propagiert, so daß sie dort spätestens zum selben Zeitpunkt gültig werden. Bezeichnet man die Cache,-Adresse (Weg und Zeilennummer) des zu ändernden Cache-Eintrags mit x, ergibt sich für eine Invalidierung folgende Abfolge:



Bei einem Neueintrag respektive dem Ersetzen eines Cache-Eintrags durch einen neuen müssen die neue Adresse aneu in das Markierungsfeld und die Daten dneu im Datenfeld eingetragen werden:



Für Totalinvalidierung eines Caches gibt es häufig einen Hardwaremechanismus, der alle Markierungen gleichzeitig in einem Schritt invalidiert. Dieser Mechanismus kann genau so in Schattencaches eingesetzt werden. Dann ergibt sich folgender Ablauf, wobei Vx "für alle x" bedeutet:



Man sieht, daß Schattencaches sowohl von außen als auch vom Schattenbus aus angesprochen werden können. Konkurrierende Zugriffe müssen hardwaremäßig erlaubt sein (multiported) oder serialisiert werden (Arbiter).

In geringer Zahl lassen sich Schattencaches auch durch Multiporting des Markierungsspeichers des eigentlichen Caches realisieren. Die Propagation von Änderungen geschieht dann automatisch.

Natürlich können auch Schattencaches multi-ported konstruiert werden. So lassen sich n logische Schattencaches durch n/2 dualported Schattencaches realisieren.

Anstelle der Nummer x des Cache-Eintrags kann auch die dem Eintrag aktuell zugeordnete (Speicher-Adresse) bei Propagation über den Schattenbus verwandt werden.

Schattencaches können zur Effizienzsteigerung beitragen, wenn häufig Cache-Aufträge zu behandeln sind, die auf Cache-Miss führen und trotzdem keine Veränderung im Cache auslösen, d. h. ignoriert werden können. Das ist beispielsweise bei Bus Snooping oder ähnlichen Broadcast-basierten Kohärenzprotokollen der Fall: Cache Invalidierungen oder Updates werden nur im Trefferfall notwendig, Misses können ignoriert werden.

Fig. 3 zeigt ein Prozessorelement mit einem Cache C und 4 Schattencaches Si die bis zu 4 Aufträge (ai, oi) parallel behandeln können. (Der Schattenbus ist aus Gründen der Übersichtlichkeit nicht eingezeichnet.) Erhält Si den Auftrag, die Operation oi mit der Adresse ai durchzuführen, prüft er, ob ai einen Treffer (im Schattencache Si) auslöst. Im Trefferfall leitet er den Auftrag an den Cache C weiter, andernfalls ignoriert er ihn. Wollen mehrere Schattencaches gleichzeitig Aufträge an den Cache C weiterleiten, wählt ein Arbiter (Selektionsvorrichtung) einen daraus aus und blockiert die anderen.

Solche Blockaden können durch Einsatz von Puffern zwischen Schattencaches und eigentlichem Cache etwas entschärft werden.

Anstelle der Adresse ai kann auch die Nummer x des angesprochenen Schattencache-Eintrags für die Weiterleitung an den Cache C verwandt werden. Das ermöglicht dem Cache C einen direkten Zugriff statt eines assoziativen Zugriffs, setzt aber Konsistenz zwischen der Belegung von Si und C voraus.

Wenn im folgenden die Weiterleitung von Aufträgen (a, o) erwähnt wird, kann statt dessen auch immer die hier erwähnte Variante (x, o) verwandt werden.

3.2 Schattencache mit Auftragsspeicher

Damit ein Schattencache jederzeit Aufträge von außen bearbeiten kann, auch wenn die Weiterleitung an den eigentlichen Cache durch den Arbiter blockiert wird, kann man Schattencaches um ein Pending-Order-Feld erweitern (siehe Fig. 4). Hier handelt es sich im einfachsten Fall um ein 1-Bit-Feld pro Schattencache-Eintrag. Zu Beginn sind alle diese Bits zurückgesetzt.

Erhält der Schattencache dann einen Auftrag (a, o), der zu einem Treffer führt und der nicht sofort weitergeleitet werden kann und der auch durch eine Invalidierung des entsprechenden Cache-Eintrags erledigt werden kann - das sind nicht nur Aufträge o = invalidate; auch Aufträge mit o = update mit Wert (v) lassen sich in der Regel durch eine einfache Invalidierung abhandeln, ohne daß semantische Fehler entstehen -, dann wird das entsprechende Order-Pending-Bit gesetzt (pi := 1). Wenn wieder ein Auftrag an den eigentlichen Cache weitergeleitet werden kann, wird ein Eintrag mit pi = ausgewählt, ein Invalidate-Auftrag (mi, inv) - falls die Markierung m mehr als nur die Adresse der im Cache-Eintrag gespeicherten Daten enthält, wird die Adresse aus mi extrahiert oder falls mi nicht die vollständige Adresse ist, wird sie aus mit Hilfe des Cache-Index ergänzt - weitergeleitet und das Order-Pending-Bit zurückgesetzt (pi := 0) . Der Schattencache-Eintrag i kann dann auch invalidiert werden.

Um nicht nur Invalidierungsaufträge speichern zu können, kann man das Order-Pending-Feld erweitern, so daß auch weitere Auftragstypen inklusive Parametern gespeichert werden können. Zu Beginn sind dann alle Felder pi auf nil gesetzt. Erhält der Schattencache einen Auftrag (a, o), der zu einem Treffer führt und der nicht sofort weitergeleitet werden kann und der entweder vollständig in pi abgespeichert oder durch einen semantisch gleichwertigen in pi speicherbaren Auftrag ersetzt werden kann, dann wird bei pi = nil der entsprechende Auftrag im Order-Pending-Feld gespeichert (pi := o) oder bei pi ≠ nil ein Auftrag gespeichert, der den schon gespeicherten und den neuen Auftrag semantisch erfaßt (pi := max(pi, o) (Bei Aufträgen inv und upd(v) gilt beispielsweise max(inv, x) = inv und max(upd(v&sub1;), upd(v&sub2;)) = upd(v&sub2;).) Sobald wieder ein Auftrag an den eigentlichen Cache weitergeleitet werden kann, wird ein Eintrag mit pi ≠ nil ausgewählt, als (mi, pi) an den eigentlichen Cache weitergeleitet und das Order-Pending-Feld zurückgesetzt (pi := nil).

Eine weitere Variante besteht darin, das Pending-Order- Feld so zu erweitern, daß eine Pending-Orders-Warteschlange im Schattencache als einfach oder doppelt gekettete Liste realisiert werden kann.

Man beachte, daß ein Schattencache mit Pending-Order- Feld nach außen nie blockiert, da es nie zu viele Pending-Orders geben kann. Im Extremfall repräsentieren alle Einträge des Schattencaches Pending-Orders. Jeder von außen kommende Auftrag (a, o) kann dann entweder ignoriert oder durch Modifikation einer schon vorhandenen Pending-Order realisiert werden.

3.3 Selektive Schattencaches

Statt zu fordern, daß jeder Schattencache den kompletten Cache widerspiegelt, kann man sich auch damit begnügen, daß alle Schattencaches zusammen den kompletten Cache widerspiegeln. Die Invarianzbedingung ist dann nur

hit (a, C) ⇐ 3i : hit (a, Si).

Für den Einsatz solcher selektiven Schattencaches muß allerdings in der Regel sichergestellt sein, daß Aufträge (a, o) entweder den richtigen oder allen Schattencaches präsentiert werden.

Eine Unterklasse der selektiven Schattencaches sind die Adreß-selektiven Schattencaches, die Aufträge anhand der Adresse a auf die Schattencaches verteilen.

Mit H = {a|hit(a,C)} sei die Menge der Adressen aller aktuell im Cache C gültigen Einträge bezeichnet. Wenn nun in einem Schattencache-System jedem Schattencache Si nur Aufträge (a, o) erteilt werden, deren Adresse a aus einer definierten Teilmenge Ai aller möglichen Adressen A kommt, d. h. a ∈ Ai ⊂ A gilt, reicht die Invarianzaussage

a ∈ Ai ∩ H ⇐ hit (a, Si)

aus, um die Schattencaches Si konsistent zum eigentlichen Cache C zu halten. Änderungen in den Markierungsfeldern von C brauchen dann nur an die möglicherweise betroffenen Schattencaches Si propagiert zu werden, genauer: Änderungen betreffend Adresse a nur an Si mit a ∈ Ai ∩ H.

Bilden die Ai ∩ H eine Zerlegung (im mathematischen Sinn) von H, dann brauchen Änderungen nicht mehr per Broadcast oder Multicast an alle oder mehrere Schattencaches propagiert zu werden. Anstelle des Schattenbusses kann ein Verbindungsnetzwerk treten, wie z. B. Fig. 5.

Bei Weg-selektiven Schattencaches wird jedem Weg eines n-Wege assoziativen Caches C ein Schattencache Si zugeordnet. Bezeichnet man die Menge der Adressen aller gültigen Einträge im Weg i des Caches mit

Hi ={a|hit (a, C) ∧ weg (a, C) = i},

mit ∧ für die logische UND-Verknüpfung, dann ist

a ∈ Hi ⇐ hit (a, Si)

die Invarianzbedingung für Weg-selektive Schattencaches. Fig. 6 zeigt einen 2-Wege assoziativen Cache mit Weg-selektiven Schattencaches. Alternativ kann man auch mehreren Wegen einen Schattencache oder einer Menge von Wegen eine Menge von Schattencaches zuordnen.

Meistens setze der Einsatz Weg-selektiver Schattencaches voraus, daß jeder Auftrag (a, o) allen Schattencaches Si präsentiert wird oder daß beim Cache-Miss, d. h. beim Laden von Daten in den Cache C, der Weg des neuen Eintrags vorherbestimmbar gewählt wird. Das kann man beispielsweise dadurch erreichen, daß man den Weg aus der Adresse a oder aus der Schattierung (siehe unter 4.) ableitet.

Adreß- oder Weg-selektive Schattencaches können insbesondere in Kombination mit n-parallelen Caches vorteilhaft sein (siehe unter 5.4).

4. Schattierung

Jedem Cache-Eintrag wird statisch oder dynamisch eine Schattierung zugeordnet. Im Fall von n möglichen Schattierungen gilt s = 0,1 . . . n-1. Bei jedem Zugriff des Prozessors P auf den Cache C wird im Trefferfall die Schattierung s benutzt, um das zugeordnete Signal blocks zu prüfen. Ist es nicht gesetzt, wird wie bei einem normalen Cache-Treffer verfahren. Ist es jedoch gesetzt, wird die Cache-Operation nicht durchgeführt und die verursachende Prozessor-Operation suspendiert (ähnlich wie bei einem Cache-Miss). Somit werden durch Anlegen eines Signals blocki alle Cache-Einträge mit der Schattierung i gesperrt. Die Blockade wird durch Rücksetzen von blocki wieder aufgehoben.

In Fig. 7 wird die Schattierung s bei jedem Zugriff aus der angesprochenen virtuellen oder realen Adresse abgeleitet, beispielsweise durch Auswahl einiger Adreßbits. In Fig. 8 wird die Schattierung s bei jedem Zugriff vom Cache geliefert. Sie wird dafür entweder von der Nummer des Cache-Eintrags (repektive des Wegs) abgeleitet oder ist pro Eintrag in einem Schattierungsfeld im Cache gespeichert. Im letzten Fall muß bei einem Cache-Miss zusätzlich zu den Daten auch die Schattierung geladen werden. In Fig. 9 liefert der TLB (Translation Lookaside Buffer) bei jedem Treffer neben der Realadresse auch die Schattierung s. Hierbei ist die Schattierung auf Seitenebene definiert. In der Regel wird die Schattierungsinformation deshalb als zusätzliche Information in den Page-Table-Einträgen enthalten sein, um aus den Page-Table-Einträgen bei einem TLB-Miss in den TLB geladen zu werden.

Die Block-Steuerung kann von Schattencaches mit Pending-Order-Behandlung (siehe unter 3.2) benutzt werden, um den Zugriff auf Cache-Einträge zu verhindern, für die von außen ein Invalidate- oder Update-Auftrag gekommen ist, der aber (wegen eines Staus) noch nicht an den eigentlichen Cache weitergeleitet werden konnte. Fig. 10 zeigt einen solchen Block-Bus, wobei die Schattierung hier vom Cache geliefert wird. Jeder Schattencache Si setzt, sobald er einen Auftrag (ai, oi) erhält und ihn nicht sofort an den Cache weiterleiten kann, das Signal blockschattierung(ai). Entsprechend den oben bei Prozessor und Cache aufgeführten Möglichkeiten kann der Schattencache die Schattierung aus der Adresse ai oder dem Schattencache-Index bzw. -Weg ableiten oder sie pro Eintrag im Schattencache in einem Schattierungsfeld führen. Im letzten Fall muß der Cache bei Änderungen, insbesondere bei neuem Laden, nicht nur die Markierung, sondern auch die Schattierung über den Schattenbus respektive das Netzwerk an die betroffenen Schattencaches propagieren.

Auch wenn die Schattierung auf Seitenebene mit Hilfe der MMU und des TLB erfolgt, kann die oben aufgeführte Methode der Schattierungsfelder und -propagation verwandt werden. Wenn Synonyme, d. h. Daten mit unterschiedlichen virtuellen, aber identischen realen Adressen, unter allen virtuellen Adressen immer dieselbe Schattierung haben, kann die Schattierung als Zahl im Schattencache gespeichert werden. Andernfalls kann eine n-bit breite Bitmaske zur Speicherung einer Schattierungsmenge verwandt werden, in der jedes Bit genau eine Schattierung repräsentiert. Gesetzte Bits bedeuten dann zugeordnete Schattierungen. Der Schattencache odert dann für eine Blockierung diese Maske bitweise auf den Block-Bus, so daß auch alle Synonyme blockiert werden.

Es ist auch möglich, allen Objekten grundsätzlich eine Menge von Schattierungen zuzuordnen, d. h. als s in Cache, TLB, Page Tables usw. immer eine Bitmaske zu führen. Zur Prüfung der Blockierung wird dann nicht mehr eines der n Signale blocki ausgewählt, sondern die Bitmaske aller Signale b = (block&sub0;, block&sub1;, . . . ) wird bitweise mit der Schattierungsmaske geundet. Der Prozessor wird genau dann blockiert, wenn b ∧ s ≠ 0 gilt, siehe Fig. 11. Entsprechendes gilt für TLB-basierte Steuerungen.

Besonders einfach wird die Situation bei selektiven Schattencaches, bei denen die Schattierung immer die Nummer des betreffenden Schattencaches ist, d. h. für a ∈ Ai ∩ H die Schattierung immer gleich i ist. Die Schattierung braucht dann nicht im Schattencache gespeichert zu werden und der Block-Bus wird etwas einfacher, siehe Fig. 12. Das Signal blocki wird gesetzt, wenn Si einen an C weiterzuleitenden Auftrag nicht weiterleiten kann (pending order) und zurückgesetzt, wenn die letzte Pending Order von Si und C weitergeleitet wird.

5. n-paralleler Cache

Das Cache-System wird in n unabhängig operierende Cache-Moduln CM&sub0; . . . CMn-1 aufgeteilt. Die einzelnen Moduln können dabei direct-mapped, k-Wege assoziativ oder auch voll-assoziativ sein.

Beim selektiven Zugriff mit der Operation o auf die Adresse a wird das Paar (a, o) von einem Verteiler X an ein Cache-Modul zur Durchführung der Operation geleitet. In Fig. 13 wird links ein selektiver Zugriff gezeigt, der CM&sub2; anspricht (aktive Phase respektive Cache-Moduln sind jeweils durch dicke Linien gekennzeichnet). Das rechte Teilbild von Fig. 13 zeigt einen assoziativen Zugriff (a, o), der gleichzeitig an alle Cache-Moduln zur Durchführung geleitet wird. Teilassoziative Zugriffe (Ansprache einer Teilmenge der Cache- Moduln) sind ebenfalls möglich.

Sind die einzelnen Moduln direct-mapped, d. h. 1-Wegassoziativ, kann der n-parallele Cache mittels assoziativen Zugriffen wie ein n-Wege-assoziativer Cache betrieben werden.

Da jeder selektive Zugriff nur ein Cache-Modul aktiviert, können bis zu n selektive Zugriffe parallel ausgeführt werden, und zwar unter der Voraussetzung, daß jeder Zugriff einem anderen Modul zugeteilt werden kann, wie in Fig. 14. Dafür wird jede Zugriffsquelle mit einem eigenen Verteiler Xi versehen und jeder Verteiler mit jedem Cache-Modul verbunden. Konflikte werden pro Modul durch einen 1-aus-n Arbiter gelöst: wird ein Modul gleichzeitig von mehreren Verteilern angewählt, wählt der Arbiter einen Auftrag aus und blockiert die anderen. Der rechte Teil der Fig. 14 zeigt eine Konfliktsituation, in der die von X&sub2; und X&sub3; auf CM&sub0; geschalteten Aufträge blockiert werden.

5.1 m-fach Pufferung

Zur besseren Behandlung von Konflikten können die Arbiter durch Auftragspuffer ergänzt werden, die vor jedem Cache-Modul eine Warteschlange realisieren (s. Fig. 15). Hat man pro Modul m Puffer, wird als Arbiter ein m-aus-n Arbiter verwandt. Bei leerer Warteschlange wählt er bis zu m Aufträge aus den anliegenden aus und übernimmt sie in die Warteschlange. Falls in der Warteschlange noch k Aufträge an das Cache-Modul warten, übernimmt der Arbiter entsprechend nur m-k der anliegenden Aufträge.

Solange keine Warteschlange überläuft, kann das System n Aufträge pro Cache-Zyklus behandeln. Die Latenz eines einzelnen Auftrags kann dabei allerdings zwischen 1 und m Zyklen schwanken.

5.2 Unterschiedliche Access-Prioritäten

Falls ein oder mehrere Accessoren latenzkritischer sind als der Rest, d. h. hierüber erfolgende Zugriffe immer möglichst ohne Verzögerung abgewickelt werden sollen, kann man diesen eine priorisierte Zugriffsmöglichkeit an der Warteschlange der übrigen vorbei geben. In Fig. 16 kann der X&sub0; zugeordnete Accessor die anderen überholen.

Sind die Cache-Moduln dual-ported aufgebaut, kann jeweils ein latenzkritischer Zugriff parallel zu einem latenzunkritischen erfolgen. Fig. 17 zeigt eine solche Situation, wobei der latenzkritische Accessoir assoziativ zugreift.

Die anderen hier beschriebenen Verfahren können entsprechend für den oder die latenzkritischen Accessoren eingesetzt werden.

5.3 Einfache Verteiler

Im einfachsten Fall werden die Aufträge bereits mit der richtigen Zuordnung empfangen, d. h. (ai, oi) wird immer an Si geleitet. Verteiler und Arbiter sind dann nicht notwendig, siehe Fig. 18.

Die Verteiler Xi können die Aufträge (a, o) anhand der Adresse a an die Cache-Moduln verteilen. In der Regel werden dazu geeignete Bits von a ausgewählt und als Index i verwandt.

Entsprechend kann die Schattierung s zur Auswahl herangezogen werden, die dann allerdings den Verteilern als Ergänzung von (a, o) geliefert werden muß.

5.4 Schattencaches als Verteiler

Schattencaches können zur Verteilung der Aufträge an die einzelnen Moduln herangezogen werden. Beispielsweise können bei n Cache-Moduln CMi jedem Verteiler Xi n Schattencaches SiO . . . Si,n-1 zugeordnet werden, wobei jeder Si,j jeweils Schattencache von CMj ist. Ein Auftrag (ai, oi) wird genau dann auf CMj verteilt, wenn Si,j für ai einen Treffer liefert. Fig. 19 zeigt solch einen Verteiler für einen 4-parallelen Cache.

Ähnlich funktioniert die Kombination der Si,j zu einem n-Wege assoziativen Schattencache Si, wobei jeder Weg j dann Schattencache des Moduls CMj und damit jeder Si Schattencache von C = (CM&sub0;, . . . CMn-1) ist. Ein Auftrag (ai, oi) wird genau dann auf CMj verteilt, wenn Si einen Treffer im Weg j meldet. Fig. 20 zeigt solch einen Verteiler für einen 4-parallelen Cache. Sind die einzelnen CMi selbst m-Wege assoziativ, nimmt man entsprechend n·m-Wege assoziative Si und entscheidet für CMj1 wenn Si einen Treffer bei Weg k mit k·m ≤ k 3< (k+1)·m meldet.

Bei Verwendung von Schattierungen kann auch anhand der Schattierung verteilt werden. Man verwendet im Verteiler einen Schattencache, der bei einem Treffer bei einem Auftrag (ai, oi) auch die Schattierung s liefert. Der Auftrag wird dann unter Verwendung von s verteilt, beispielsweise an CMs oder an CMsmodn, falls es mehr Schattierungen als Cache-Moduln gibt. Fig. 21 zeigt einen Verteiler für einen 4-parallelen Cache, der anhand der Schattierung verteilt.

5.5 Schattencaches als Filter

Alle in 3. beschriebenen Arten von Schattencaches können bei n-parallelen Caches eingesetzt werden, nicht nur zur oben beschriebenen Verteilung der Aufträge sondern auch unabhängig davon, um wie unter 3. beschrieben, Effizienzsteigerungen durch Ignorieren irrelevanter Aufträge und Pufferung zu realisieren. Auftragsspeicherung und Blockieren kann entsprechend verwandt werden. Hierbei kann die Blockierung prozessorspezifisch (wie unter 4. beschrieben), aber auch Cache-Modul-spezifisch erfolgen.

6. Kombinierbarkeit und Unabhängigkeit

Das erfindungsgemäße System kann die Merkmale der oben beschriebenen Schattencaches und/oder die Merkmale der oben beschriebenen Schattierung und/oder die Merkmale des n-parallelen Caches aufweisen.


Anspruch[de]
  1. 1. Cache-System zum Speichern von Daten, mit
    1. - einem Cache-Hauptspeicher mit mehreren Einträgen, von denen jeder mindestens ein Markierungsfeld für Adreßdaten und mindestens ein diesem zugeordnetes Datenfeld für Nutzdaten aufweist,
    2. - mindestens einen Cache-Nebenspeicher mit mehreren Einträgen, von denen jeder pro Markierungsfeld eines Eintrages des Cache-Hauptspeichers ein Markierungsfeld aufweist,
    3. - wobei der Cache-Hauptspeicher und jeder Cache- Nebenspeicher zwecks Ausführung von Operationsaufträgen auf dem Cache-Hauptspeicher mit identischen oder unterschiedlichen Adressen indizierbar sind, und
    4. - einer Verbindung zwischen dem Cache-Hauptspeicher und jedem Cache-Nebenspeicher zum Übertragen der Inhalte von Markierungsfeldern des Cache-Hauptspeichers zu jedem Cache-Nebenspeicher und umgekehrt.
  2. 2. Cache-System nach Anspruch 1, dadurch gekennzeichnet, daß die Inhalte der Markierungsfelder der Cache-Nebenspeicher gleich den Inhalten der Markierungsfelder des Cache-Hauptspeichers sind.
  3. 3. Cache-System nach Anspruch 1 oder 2, dadurch gekennzeichnet, - daß jeder Eintrag des Cache-Hauptspeichers mehrere Markierungsfelder aufweist,
    1. - daß sämtliche Markierungsfelder des Cache- Hauptspeichers zu unterschiedlichen Gruppen zusammengefaßt sind, wobei jeder Gruppe pro Eintrag des Cache-Hauptspeichers genau ein Markierungsfeld zugeordnet ist,
    2. - daß die Anzahl der Cache-Nebenspeicher gleich der Anzahl der Gruppen von Markierungsfeldern ist und
    3. - daß jeder Cache-Nebenspeicher pro Eintrag eine der Anzahl von Gruppen von Markierungsfeldern des Cache-Hauptspeichers gleichende Anzahl von Markierungsfeldern aufweist, wobei pro Eintrag für jede Gruppe von Markierungsfeldern genau ein Markierungsfeld vorgesehen ist.
  4. 4. Cache-System nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß beim Eintreffen eines an den Cache-Hauptspeicher weiterzuleitenden Operationsauftrages bei einem Cache-Nebenspeicher zunächst der Cache-Nebenspeicher mit der Adresse indiziert wird und daß der Operationsauftrag dann an den Cache-Hauptspeicher weitergeleitet wird, wenn der Inhalt eines Markierungsfeldes des Cache- Nebenspeichers mit der Adresse übereinstimmt.
  5. 5. Cache-System nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß mindestens zwei Cache- Nebenspeicher vorgesehen sind und daß zwischen die Cache-Nebenspeicher und den Cache-Hauptspeicher eine Selektionsvorrichtung geschaltet ist, die im Falle von gleichzeitig von den Cache-Nebenspeichern an den Cache-Hauptspeicher weitergeleiteten Aufträgen auswählt, welcher Auftrag und/oder in welcher Reihenfolge die Aufträge jeweils an den Cache-Hauptspeicher weitergeleitet wird bzw. werden.
  6. 6. Cache-System nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß jeder Eintrag eines Cache-Nebenspeichers um ein Pending-Order-Feld zur Zwischenspeicherung von Operationsaufträgen für den Cache-Hauptspeicher ergänzt ist, wobei der Auftrag nur dann zwischengespeichert wird, wenn die zur Indizierung eines Cache-Nebenspeichers verwendete Adresse mit dem Inhalt genau eines Markierungsfeldes dieses Cache-Nebenspeichers übereinstimmt und der Auftrag nicht unmittelbar an den Cache-Hauptspeicher weitergeleitet werden kann.
  7. 7. Cache-System nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß die Summe der Anzahl der Markierungsfelder sämtlicher Cache-Nebenspeicher gleich der Anzahl der Markierungsfelder des Cache- Hauptspeichers ist, wobei die Inhalte der Menge der Markierungsfelder der Cache-Nebenspeicher eine mathematische Zerlegung der Inhalte der Menge der Markierungsfelder des Cache-Hauptspeichers sind und aufgrund einer von außen angelegten Adresse entschieden wird, in welchem Cache-Nebenspeicher sich der Inhalt des zu dieser Adresse gehörenden Markierungsfeldes befindet, sofern sich diese Adresse in einem Cache-Nebenspeicher befindet.
  8. 8. Cache-System nach Anspruch 7, dadurch gekennzeichnet,
    1. - daß jeder Eintrag des Cache-Hauptspeichers mehrere Markierungsfelder aufweist,
    2. - daß sämtliche Markierungsfelder des Cache- Hauptspeichers zu unterschiedlichen Gruppen zusammengefaßt sind, wobei zu jeder Gruppe pro Eintrag des Cache-Hauptspeichers genau ein Markierungsfeld zugeordnet ist,
    3. - daß die Anzahl der Cache-Nebenspeicher gleich der Anzahl der Gruppen von Markierungsfeldern ist und
    4. - daß jeder Cache-Nebenspeicher pro Eintrag ein Markierungsfeld und so viele Einträge aufweist, wie eine Markierungsfeld-Gruppe Markierungsfelder umfaßt.
  9. 9. Cache-System nach Anspruch 8, dadurch gekennzeichnet, daß die Verbindung zwischen den Cache-Nebenspeichern und dem Cache-Hauptspeicher derart ausgebildet ist, daß Inhalte von Markierungsfeldern lediglich jeweils zwischen einer Gruppe von Markierungsfeldern des Cache-Hauptspeichers und den Markierungsfeldern des betreffenden Cache-Nebenspeichers austauschbar sind.
  10. 10. Cache-System nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet,
    1. - daß jedem Eintrag des Cache-Hauptspeichers eine Gruppeninformation zugeordnet ist,
    2. - daß jeder Gruppeninformation ein Blockierungssignal zugeordnet ist, das sich im Setz-Zustand oder Rücksetz-Zustand befindet, und
    3. - daß eine Operation mit einer Adresse auf dem Cache-Hauptspeicher nur dann durchführbar ist, wenn sich das Blockierungssignal, das der Gruppeninformation des mittels der Adresse adressierten Eintrages des Cache-Hauptspeichers zugeordnet ist, in dem Rücksetz-Zustand befindet.
  11. 11. Cache-System nach Anspruch 10 und 6, dadurch gekennzeichnet, daß jeder Cache-Nebenspeicher, der einen nicht unmittelbar weiterleitbaren Auftrag zur Durchführung einer Operation mit einer Adresse auf dem Cache-Hauptspeicher zwischenspeichert, das der Gruppeninformation des Cache-Hauptspeichers zugeordnete Blockierungssignal setzt, wobei dieses Blockierungssignal dann rückgesetzt wird, wenn in dem Cache-Nebenspeicher keine an den Cache-Hauptspeicher weiterzuleitende Aufträge mehr gespeichert sind.
  12. 12. Cache-System zum Speichern von Daten mit
    1. - mehreren Cache-Speichern, die jeweils mehrere Einträge aufweisen, von denen jeder zumindest ein Markierungsfeld für Adreßdaten aufweist, und
    2. - mindestens einer Verteilervorrichtung, die mit jedem Cache-Speicher gekoppelt ist, wobei die Verteilervorrichtung einen Operationsauftrag zur Durchführung einer Operation mit einer Adresse auf einem der Cache-Speicher empfängt und diesen Auftrag selektiv an ein oder mehrere Cache-Speicher weitergibt.
  13. 13. Cache-System nach Anspruch 12, dadurch gekennzeichnet, daß die Cache-Speicher als Cache-Hauptspeicher und/oder als Cache-Nebenspeicher des Cache-Systems nach einem der Ansprüche 1 bis 11 ausgebildet sind.
  14. 14. Cache-System nach Anspruch 12 oder 13, dadurch gekennzeichnet, daß jedem Cache-Speicher eine Selektionsvorrichtung vorgeschaltet ist, daß mehrere Verteilervorrichtungen vorgesehen sind, von denen jede mit jeder der den Cache-Speichern zugeordneten Selektionsvorrichtungen verbunden ist, wobei jede Selektionsvorrichtung im Falle des gleichzeitigen Empfangs mehrerer Aufträge von den Verteilervorrichtungen auswählt, welcher der Aufträge und/oder in welcher Reihenfolge die Aufträge an den zugeordneten Cache-Speicher weitergeleitet wird bzw. werden.
  15. 15. Cache-System nach Anspruch 14, dadurch gekennzeichnet, daß zwischen jede Selektionsvorrichtung und dem zugeordneten Cache-Speicher eine Puffervorrichtung zum Zwischenspeichern von Aufträgen geschaltet ist.
  16. 16. Cache-System nach einem der Ansprüche 12 bis 15, dadurch gekennzeichnet, daß den Aufträgen unterschiedliche Prioritäten zugeordnet sind und daß beim gleichzeitigen Empfang mehrerer Aufträge durch die Verteilervorrichtungen diejenigen mit der höchsten Priorität Vorrang vor denjenigen mit niedrigerer Priorität haben.
  17. 17. Cache-System nach einem der Ansprüche 12 bis 16, dadurch gekennzeichnet, daß den Aufträgen unterschiedliche Prioritäten zugeordnet sind und daß die Aufträge mit höchster Priorität an den Verteilervorrichtungen vorbei sämtlichen Cache-Speichern zugeleitet werden.
  18. 18. Cache-System nach einem der Ansprüche 12 bis 17, dadurch gekennzeichnet, daß die Verteilung der Aufträge an die Cache-Speicher anhand der Adresse erfolgt.
  19. 19. Cache-System mit den Merkmalen gemäß mindestens einem der Ansprüche 1 bis 11 und mindestens einem der Ansprüche 12 bis 18.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com