DE19516949A1

DE19516949A1 - Speichervorrichtung zum Speichern von Daten

Info

Publication number: DE19516949A1
Application number: DE19516949A
Authority: DE
Inventors: Jochen Liedtke
Original assignee: GMD GmbH
Current assignee: GMD GmbH
Priority date: 1994-05-11
Filing date: 1995-05-11
Publication date: 1996-02-15
Also published as: EP0760134A1; JPH10500235A; WO1995031783A1; US6260130B1

Description

Die Erfindung betrifft eine Speichervorrichtung zum Speichern von Daten. Insbesondere betrifft die Erfin dung einen Cache oder einen Translation Lookaside Buffer (TLB) wobei die Neuerung in einem insbesondere parallel arbeitenden Flush-Buffer besteht, der Flushing größerer und kleinerer Bereiche erlaubt, ohne daß so fort der ganze Cache bzw. TLB geflusht werden muß.

Moderne Prozessoren benutzen TLBs für die schnelle Um setzung virtueller in reale Adressen. Typischerweise befinden sich TLB und Cache auf dem Prozessorchip. Bei real indizierten Caches sind sie serial angeordnet (Fig. 4), bei virtuell indizierten, real markierten Caches parallel (Fig. 5).

Der TLB ist dabei ein spezieller Cache für die Adreßum setzung. Zwar werden auch voll-assoziative TLBs einge setzt, in der Regel sind TLBs jedoch n-Wege assoziativ. Fig. 6 zeigt einen direct-mapped TLB, also einen 1-Wege assoziativen TLB. Der höherwertige Teil v′ der virtuel len Adresse v wird benutzt, um eine Zeile (Speicher- Eintrag) des TLBs anzuwählen. Dort finden sich die zu diesem Eintrag gehörige virtuelle Seitenadresse v′_i, die reale Seitenadresse r′_i sowie in Fig. 6 nicht auf geführte Statusbits, die unter anderem angeben, ob der Eintrag überhaupt gültig ist. Wenn er gültig ist und v′_i mit der aktuellen Seitenadresse v′ übereinstimmt, liegt ein TLB-Treffer vor und die Realadresse wird aus dem niederwertigen Teil v′′ der virtuellen Adresse und der vom TLB gelieferten realen Seitenadresse r′_i zusam mengesetzt.

Ein n-Wege assoziativer TLB unterscheidet sich vom direct-mapped TLB dadurch, daß sich in einer Zeile meh rere Einträge befinden, die gleichzeitig angewählt und parallel gegen v′ geprüft werden. Ein Treffer liegt dann vor, wenn einer dieser Einträge zutrifft; dessen r′_i und Statusbits werden dann zur Bildung der Real adresse r und Validierung des Zugriffs benutzt.

TLBs kürzen den Vorgang der Adreßumsetzung ab. Wird die definierende Adreßabbildung, d. h. eine oder mehrere Page Table Einträge, verändert, müssen aus Konsistenz gründen diejenigen TLB-Einträge ungültig gemacht "(ge flusht") oder entsprechend verändert werden, die von der Änderung tangiert sind.

Bezieht sich die Änderung in der Adreßabbildung nur auf eine Seite, reicht es aus, den entsprechenden Eintrag zu flushen oder abzuändern, sofern er im TLB ist. Da es sich dabei um höchstens einen TLB-Eintrag handelt, ist der Aufwand mit einem normalen Umsetzschritt des TLBs vergleichbar: der TLB wird mit der virtuellen Seiten adresse angesprochen, und bei einem Treffer wird der Eintrag ungültig gemacht oder verändert.

Bei Änderungen, die größere Bereiche umfassen, wird dieses Verfahren schnell zu aufwendig. Für einen vir tuellen Bereich mit m Seiten würde man nämlich m Schritte benötigen. Bei voll-assoziativen TLBs läßt sich das Problem effizient lösen, indem man bedingtes Flushing parallel auf allen TLB-Einträgen ausführt. Leider ist der Hardware-Aufwand dafür in der Regel zu groß.

Bei n-Wege assoziativen TLBs ist die Durchmusterung des gesamten TLBs teuer und nicht skalierbar, k/n Schritte bei einem TLB mit k Einträgen. Deshalb wird in solchen Fällen üblicherweise der gesamte TLB geflusht, was sich in einem Schritt realisieren läßt. Mit zunehmender TLB- Größe wird das wegen der dadurch induzierten TLB-Misses immer uninteressanter.

Der Erfindung liegt die Aufgage zugrunde, eine Speichervorrichtung, insbesondere n-Wege assoziativer Cache bzw. TLB anzugeben, die Flushing größerer Adreß raum-Bereiche (virtueller Regionen) effizient ermög licht.

Zur Lösung dieser Aufgabe wird mit der Erfindung eine Speichervorrichtung mit den Merkmalen des Anspruchs 1 vorgeschlagen. Die Merkmale vorteilhafter Weiterbildun gen der Erfindung sind jeweils in den Unteransprüchen angegeben.

Die erfindungsgemäße Speichervorrichtung ist mit einem Nutzspeicher versehen, der mehrere mittels Adressen adressierbare Speicher-Einträge aufweist. Bei diesem Nutzspeicher kann es sich beispielsweise um einen Cache-Speicher oder um einen Translation-Lookaside- Buffer handeln, der als spezieller Cache-Speicher für die Adreßumsetzung aufgefaßt werden kann. Der Nutz speicher der erfindungsgemäßen Vorrichtung weist insbe sondere wesentlich weniger Speicher-Einträge auf als der Adreßraum Adressen zur Adressierung des Nutz speichers umfaßt. Jeder Speicher-Eintrag ist mit einem Datenfeld versehen, in dem ein oder mehrere Datenwörter abspeicherbar sind. Zusätzlich zu dem Datenfeld weist jeder Speicher-Eintrag ein Statusfeld auf, das in min destens einen Einschränk-Zustand zum Einschränken eines Schreib/Lese-Zugriffs auf das Datenfeld und in min destens einen Nichteinschränk-Zustand zum Nichtein schränken eines Schreib/Lese-Zugriffs auf das Datenfeld überführbar ist. Jeder Speicher-Eintrag weist darüber hinaus weitere Felder auf, insbesondere ein Markie rungsfeld und ein Gültigkeits-/Ungültigkeits-Feld. Beim Ansprechen des Nutzspeichers wird die Adresse oder Teile davon mit dem Inhalt der Markierungsfelder sämt licher adressierter Nutzspeicher-Einträge verglichen. Im Falle einer Übereinstimmung mit einem Markierungs feld kann dann ein Schreib/Lese-Zugriff auf das Daten feld erfolgen, wenn dieses einerseits durch das Gültig keits-/Ungültigkeits-Feld als gültig markiert ist und entweder sich das Statusfeld in einem Nichteinschränk- Zustand befindet oder sich das Statusfeld in einem Ein schränk-Zustand befindet sowie die beim Ansprechen des Nutzspeichers verwendete Adresse nicht Teil mindestens eines im Hilfsspeicher abgespeicherten Adreßraum-Be reichs ist.

Ferner ist die erfindungsgemäße Speichervorrichtung mit einem Hilfsspeicher versehen, der ein oder mehrere Speicher-Einträge aufweist, in die Daten abspeicherbar sind, welche einen Bereich des Adreßraums spezifizie ren. Mittels dieses Hilfsspeichers (nachfolgend auch als Flush-Lookaside-Buffer, abgekürzt FLB, bezeichnet) läßt sich der Nutzspeicher effizient bereichsselektiv flushen, nämlich durch einen einzigen Operations schritt.

Die Verfahrensweise zum bereichsselektiven Flushen des Nutzspeichers ist wie folgt: Sobald in den Hilfs speicher ein Adreßraum-Bereich abgespeichert wird, wer den die Statusfelder sämtlicher Nutzspeicher-Einträge in einen Einschränk-Zustand überführt. Bei einer danach erfolgenden Adressierung eines Nutzspeicher-Eintrages kann dann nicht auf das Datenfeld dieses Nutzspeicher- Eintrages ein Schreib/Lese-Zugriff erfolgen, wenn die Adresse innerhalb mindestens eines im Hilfsspeicher gespeicherten Adreßraum-Bereichs liegt und sich das Statusfeld in einem Einschränk-Zustand befindet. Um dies zu Ermitteln, wird die zur Adressierung des Nutz speicher-Eintrages verwendete Adresse daraufhin über prüft, ob sie von mindestens einem im Hilfsspeicher gespeicherten Adreßraum-Bereich umfaßt ist. Ist dies der Fall, so gibt der Hilfsspeicher ein diesen Zustand anzeigendes Signal (nachfolgend auch Fhit genannt) aus. Anders herum ausgedrückt kann nach einem Flushing des Nutzspeichers weiterhin auf die Datenfelder sämtlicher derjenigen Nutzspeicher-Einträge zugegriffen werden, die mittels einer Adresse adressierbar sind, welche nicht von mindestens einem im Hilfsspeicher gespeicher ten Adreßraum-Bereich umfaßt ist. Bei der Realisierung des Nutzspeichers als TLB oder Cache können also zeit aufwendige Table Walk bzw. Hauptspeicherzugriffe für die nicht von dem selektiven Flushing betroffenen Nutz speicher-Einträge vermieden werden, und zwar bei ver hältnismäßig geringem Hard- und Software-Aufwand, da lediglich ein Hilfsspeicher neben dem Nutzspeicher vor gesehen werden muß und die Speicher-Einträge des Nutz speichers um das Statusfeld ergänzt werden müssen, wobei diese Statusfelder im Bedarfsfall auf einen zen tralen Befehl hin simultan in einen Einschränk-Zustand und selektiv in einen Nichteinschränk-Zustand überführ bar sind.

Vorteilhafterweise wird beim Laden eines Nutzspeicher- Eintrages, bei dem dieser initialisiert wird (im Regel fall werden dabei Daten in den Nutzspeicher-Eintrag ge schrieben und dieser dann als gültig markiert), das Statusfeld des betreffenden Nutzspeicher-Eintrages genau dann in einen Einschränk-Zustand überführt, wenn die Adresse, mit der der Nutzspeicher-Eintrag adres siert worden ist, nicht Teil mindestens eines im Hilfs speicher gespeicherten Adreßraum-Bereichs ist. Ist hin gegen die Adresse Teil mindestens eines in dem Hilfs speicher gespeicherten Adreßraum-Bereichs, so wird das Statusfeld des adressierten Nutzspeicher-Eintrages in einen Nichteinschränk-Zustand überführt.

Alternativ dazu kann vorgesehen sein, das Statusfeld eines adressierten Nutzspeicher-Eintrags bei einem Lade-Zugriff stets in einen Nichteinschränk-Zustand zu überführen, und zwar unabhängig davon, ob die zur Adressierung verwendete Adresse Teil mindestens eines in dem Hilfsspeicher gespeicherten Adreßraum-Bereichs ist oder nicht. Befindet sich das Statusfeld eines adressierten Nutzspeicher-Eintrages vor einer Adressie rung in einem Einschränk-Zustand (was insbesondere bei der Initialisierung des Nutzspeichers oder nach jedem Flushing der Fall ist) und ist die zur Adressierung verwendete Adresse nicht Teil mindestens eines im Hilfsspeicher gespeicherten Adreßraum-Bereichs, so wird das Statusfeld bei der Adressierung in einen Nichtein schränk-Zustand überführt, so daß von da ab bis zum Überführen des Statusfeldes in den Einschränk-Zustand eine Abfrage des Hilfsspeichers bei Ansprache des Nutz speicher-Eintrages nicht mehr notwendig ist.

Zweckmäßigerweise werden beim Einschreiben von einen Bereich des Adreßraums spezifizierenden Daten in einen Hilfsspeicher-Eintrag die Statusfelder sämtlicher Nutz speicher-Einträge in einen Einschränk-Zustand über führt. Vorzugsweise ist der Hilfsspeicher mit mehreren Speicher-Einträgen versehen. Beim Überlaufen des Hilfs speichers wird vorteilhafterweise derart verfahren, daß sämtliche Nutzspeicher-Einträge und sämtliche Hilfs speicher-Einträge als nicht gültig markiert werden. An dieser Stelle sei angemerkt, daß in der schaltungstech nischen Realisierung jeder Hilfsspeicher-Eintrag ein Valid-Bit aufweist, das anzeigt, ob die im Hilfs speicher-Eintrag gespeicherten Daten gültig sind oder nicht. Ein derartiges Valid-Bit ist auch bei jedem Nutzspeicher-Eintrag vorgesehen (oben als Gültig keits-/Ungültigkeits-Feld bezeichnet).

Vorteilhafterweise wird vor jedem Abspeichern eines Adreßraum-Bereichs in einen Hilfsspeicher-Eintrag der neu abzuspeichernde Adreßraum-Bereich auf Überschnei dungen mit bereits im Hilfsspeicher abgespeicherten Adreßraum-Bereichen untersucht. Ist die Schnittmenge der Vereinigung aller im Hilfsspeicher gespeicherter Adreßraum-Bereiche mit dem neu abzuspeichernden Adreß raum-Bereich gleich diesem, so braucht der neue Adreß raum-Bereich nicht erneut im Hilfsspeicher abge speichert zu werden; es reicht vielmehr aus, die Statusfelder sämtlicher Nutzspeicher-Einträge in einen Einschränk-Zustand zu überführen. Der Hilfsspeicher kann dann unverändert weiterbenutzt werden. Ist hin gegen beispielsweise im Hilfsspeicher ein Adreßraum- Bereich abgespeichert, der vollständig innerhalb des zusätzlich abzuspeichernden Adreßraum-Bereichs liegt, wobei dieser größer ist als der bereits abgespeicherte Adreßraum-Bereich, oder der sich mit dem neu abzu speichernden Adreßraum-Bereich überlappt oder sich an diesen (mit oder ohne Abstand) anschließt, so kann der jenige Hilfsspeicher-Eintrag, in dem der bereits abge speicherte Adreßraum-Bereich abgelegt ist, mit den den neu abzuspeichernden Adreßraum-Bereich spezifizierenden Daten überschrieben werden. In gewohnter Weise wird der Nutzspeicher wiederum selektiv geflusht, indem die Statusfelder sämtlicher Nutzspeicher-Eintrage in einen Einschränk-Zustand überführt werden. Die obigen Über legungen gelten entsprechend in Bezug auf einen Ver gleich des neu abzuspeichernden Adreßraum-Bereichs mit der Vereinigungsmenge sämtlicher bereits im Hilfs speicher gespeicherter Adreßraum-Bereiche.

Die vorstehend beschriebenen Operationen auf dem Hilfs speicher verfolgen den Zweck, den Hilfsspeicher optimal auszunutzen, um ein zu schnelles Überlaufen des Hilfs speichers zu verhindern. Mit anderen Worten werden bei dieser Weiterbildung der Erfindung der oder die be stehenden Hilfsspeicher-Einträge und/oder der neue Hilfsspeicher-Eintrag stets derart aktualisiert bzw. gewählt, daß im Hilfsspeicher stets mindestens sämt liche durch die bisherigen und die neuen Daten spezi fizierte Adreßraum-Bereiche abgespeichert sind.

Vorzugsweise lassen sich die Statusfelder sämtlicher Nutzspeicher-Einträge gleichzeitig in einen Einschränk- Zustand überführen, und zwar unabhängig von einer Ope ration auf dem Hilfsspeicher und unabhängig von dessen Zustand.

Bei der einfachsten Form der Realisierung des Status feldes ist dieses als ein 1-Bit-Feld ausgeführt, welches zur Spezifizierung des Einschränk- bzw. Nicht einschränk-Zustandes setzbar bzw. rücksetzbar ist.

Eine zur zuvor genannten Weiterbildung alternative Realisierung des Statusfeldes besteht darin, daß das Statusfeld mehrere Bits umfaßt und daß sich in das Statusfeld "Generationsnummern" abspeichern lassen. Hierbei weist die erfindungsgemäße Speichervorrichtung einen Generationsnummern-Zähler auf, der bei jeder Ab speicherung eines Adreßraum-Bereichs in einen Hilfs speicher-Eintrag inkrementiert wird. Jeder Hilfs speicher-Eintrag ist um ein Generationsnummernfeld er gänzt. Das Generationsnummernfeld eines Hilfsspeicher- Eintrages wird in dem Augenblick, in dem in diesen Hilfsspeicher-Eintrag ein Adreßraum-Bereich abge speichert wird, auf den vor der Inkrementierung vorlie genden Wert des Generationsnummern-Zählers gesetzt. Das Statusfeld eines Nutzspeicher-Eintrages, auf den ein Lade-Zugriff erfolgt, wird auf den aktuellen Wert des Generationsnummern-Zählers gesetzt. Ob sich das Status feld eines adressierten Nutzspeicher-Eintrages im Ein schränk- oder Nichteinschränk-Zustand befindet, wird dann durch Vergleich des Wertes des Statusfeldes mit dem Wert des Generationsnummernfeldes desjenigen Hilfs speicher-Eintrages entschieden, in dem der die zur Adressierung des Nutzspeicher-Eintrages verwendete Adresse umfassende Adreßraum-Bereich gespeichert ist. Der Nichteinschränk-Zustand liegt genau dann vor, wenn der Wert des Statusfeldes größer ist als der Wert des Generationsnummernfeldes des betreffenden Hilfs speicher-Eintrages. Die Statusfeld-Werte der Nutz speicher-Einträge und die Generationsnummernfeld-Werte der Hilfsspeicher-Einträge geben also stets an, welche der beiden Einträge aktueller ist (Hilfspeicher-Eintrag oder der Nutzspeicher-Eintrag mit derjenigen Adresse, die innerhalb des durch den Hilfsspeicher-Eintrag spezifizierten Adreßraum-Bereichs liegt). In Abhängig keit davon befindet sich das Statusfeld in einem Nicht einschränk- oder in einem Einschränk-Zustand.

Nach der Erfindung ist es grundsätzlich möglich, daß die Adresse, mit der ein Nutspeicher-Eintrag adressiert wird, innerhalb mehrerer im Hilfsspeicher abgespeicher ter Adreßraum-Bereiche liegt. Bei der Realisierung der Nichteinschränk- bzw. Einschränk-Zustände der Status felder durch Vergleich von Generationsnummern des Nutz speichers und des Hilfsspeichers befindet sich in dem Fall, in dem die Adresse eines adressierten Nutz speicher-Eintrages innerhalb der durch die Daten mehre rer Hilfsspeicher-Einträge spezifizierten Adreßraum- Bereiche liegt, das Statusfeld des adressierten Nutz speicher-Eintrages in einem Nichteinschränk-Zustand, wenn der Wert des Statusfeldes größer ist als der größ te in den Generationsnummernfeldern derjenigen Hilfs speicher-Einträge gespeicherten Generationsnummern, in denen die zur Adressierung des Nutzspeicher-Eintrags verwendete Adresse umfassende Adreßraum-Bereiche abge speichert sind. Andernfalls befindet sich das Status feld des adressierten Nutzspeicher-Eintrages in einem Einschränk-Zustand.

Vorzugsweise wird der Generationsnummern-Zähler bei einer Abspeicherung eines Adreßraum-Bereichs in einen Hilfsspeicher-Eintrag nur dann inkrementiert, wenn der Adreßraum-Bereich Überschneidungen mit einem oder meh reren bereits im Hilfsspeicher abgespeicherten Adreß raum-Bereichen aufweist. Hierdurch kann die Anzahl an insgesamt zu vergebenden Generationsnummern reduziert werden, was wiederum den Vorteil hat, daß die ent sprechenden Generationsnummernfelder des Hilfsspeichers und Statusfelder des Nutzspeichers verkleinert werden können.

Sämtliche Nutz- und Hilfsspeicher-Einträge werden als nicht gültig markiert und zusätzlich wird der Genera tionsnummern-Zähler rückgesetzt, wenn der Hilfsspeicher überläuft, d. h. weitere Adreßraum-Bereiche in den Hilfsspeicher nicht mehr abspeicherbar sind. Ein Rück setzen des Generationsnummern-Zählers und die Markie rung sämtlicher Nutz- und Hilfsspeicher-Einträge als nicht gültig erfolgt auch dann, wenn der Generations nummern-Zähler einen vorgebbaren Maximalwert über steigt.

Nachfolgend werden anhand der Figuren Ausführungsbei spiele der Erfindung näher erläutert. Im einzelnen zei gen:

Fig. 1 schematisch den Aufbau eines "Flush-Lookaside- Buffer", als Ergänzung für ein bestehendes TLB/ Cache-System,

Fig. 2 den Aufbau eines TLB mit als Collision-Sensi tive-Bit ausgeführtem Statusfeld,

Fig. 3 ein Blockschaltbild von FLB und TLB mit Logik- Beschaltung,

Fig. 4 schematisch den Aufbau eines FLB mit Genera tionsnummern zur Kennzeichnung eines Ein schränk- und Nichteinschränk-Zustandes,

Fig. 5 den Aufbau eines FLB mit Generationsnummern und ohne Valid-Bit und Fhit-Signal,

Fig. 6 einen TLB mit Generationsnummern,

Fig. 7 ein Blockschaltbild von FLB und TLB jeweils mit Generationsnummern und mit Logik-Beschaltung der Ausgänge,

Fig. 8 den Aufbau eines TLB ohne Valid-Bit und Thit- Signal,

Fig. 9 den Aufbau (als Blockschaltbild) von FLB und TLB ohne Valid- und Thit-Signal,

Fig. 10 einen TLB mit maskiertem FLB (als Blockschalt bild),

Fig. 11 den grundsätzlichen Aufbau eines einfachen FLB mit Aktivitätsvermerk,

Fig. 12 den Aufbau eines Schatten-TLB,

Fig. 13 als Blockschaltbild ein System aus TLB und FLB mit "Write-Protect",

Fig. 14 den grundsätzlichen Aufbau eines aus TLB und Cache bestehenden seriell arbeitenden Cache- Speichersystems,

Fig. 15 den Aufbau eines aus TLB und Cache bestehenden, parallel arbeitenden Cache-Speichersystems und

Fig. 16 einen direct-mapped TLB (grundsätzlicher Auf bau).

1. Flush Lookaside Buffer 1.1 Ein einfacher FLB

Nachfolgend wird anhand der Fig. 1 bis 3 ein erstes Ausführungsbeispiel einer erfindungsgemäßen Speicher vorrichtung näher erläutert, und zwar anhand eines TLB- Speichersystems. Sämtliche nachfolgend aufgeführten Überlegungen (dies gilt für sämtliche Ausführungsbei spiele) lassen sich in analoger Weise auch auf ein Cache-Speichersystem übertragen. Dabei ist zu beachten, daß es sich bei einem TLB physikalisch um einen Cache speicher handelt.

Um bei einem TLB-System die Erfindung verwirklichen zu können, wird dieses TLB-System um einen kleinen, voll assoziativen Flush-Lookaside-Buffer (nachfolgend FLB genannt) erweitert. Jeder Eintrag des FLB umfaßt ein Valid-Bit und kann die Spezifikation einer Region ρ_j aufnehmen (Fig. 1).

Dabei kann eine Region beispielsweise durch Anfangs- und Endadresse bzw. Länge spezifiziert sein, aber auch durch Adresse und eine Maske, die angibt, welche Adreß bits zur Trefferprüfung benutzt und welche ignoriert werden sollen.

Der FLB signalisiert einen Treffer Fhit, wenn es min destens einen Eintrag j gibt, der gültig ist (valid_j) und dessen Bereich ρ_j die virtuelle Adresse v enthält.

Der TLB wird um ein Collision-Sensitive-Bit cs_i er weitert, das pro Eintrag angibt, ob Kollision mit einem FLB-Treffer hierbei beachtet (cs) werden soll, d. h. ein Einschränk-Zustand vorliegt, oder ignoriert () werden soll, d. h. ein Nichteinschränk-Zustand vorliegt. Bei einem Treffer signalisiert der TLB Thit und liefert die Realadresse r′ sowie das Collision-Sensitive-Bit cs aus dem Treffereintrag.

Liegen bei einer Umsetzung TLB- und FLB-Treffer vor (Thit ∧ Fhit), wird von einer Kollision gesprochen. Die Kollision ist echt, wenn zusätzlich cs gesetzt ist; andernfalls ist sie unecht. Das Gesamtsystem ignoriert TLB-Treffer bei echten Kollisionen, d. h. genau dann, wenn auch ein FLB-Treffer gemeldet wird und das Colli sion-Sensitive-Bit gesetzt ist, d. h.

hit = Thit ∧ ¬ (Fhit ≁ cs).

Zur Verdeutlichung dieses Treffer-Aspekts siehe Fig. 3.

Immer dann, wenn ein TLB-Eintrag neu geladen wird, wird das Collision-Sensitive-Bit cs_i dabei genau dann ge setzt, wenn die entsprechende virtuelle Adresse keinen FLB-Treffer auslöst. Andernfalls wird cs_i dabei zurück gesetzt. Da TLB-Einträge normalerweise aufgrund eines TLB-Miss geladen werden (Lade-Zugriff) und in diesem Fall die entsprechende virtuelle Adresse v′ parallel zum TLB-Schritt vom FLB verarbeitet wurde, wird als cs_i des neuen TLB-Eintrags auf = ¬Fhit gesetzt, ge nauer auf den Wert von , der beim TLB-Miss auftrat. Man beachte, daß das unabhängig davon ist, ob ein ech ter TLB-Miss () oder eine echte Kollision vorliegt.

Bei einem TLB-Hit mit echter Kollision wird

1. der entsprechende TLB-Eintrag geflusht (valid_i:= false),
2. ein TLB-Miss signalisiert und ein MMU-Table-Walk durchgeführt,
3. da Fhit beim TLB-Miss gesetzt war, wird das Colli sion-Sensitive-Bit cs_i des verwandten Eintrags beim erneuten Laden zurückgesetzt.

Ein erneutes Ansprechen derselben virtuellen Adresse führt dann nur zu einer unechten Kollision.

Bei der Darstellung des Zusammenspiels der Hit-Signale sind im folgenden jeweils links von die Voraussetzun gen für die rechts davon beschriebenen Operationen auf geführt. Zur Anwahl einer Alternative müssen alle dafür aufgeführten Voraussetzungen erfüllt sein (UND-Ver knüpfung). Alle durch Komma getrennte Operationen er folgen parallel. Überstreichung (wie ) bezeichnet die Negation eines Signals bzw. eines Bits, "!" das Setzen und "⁻!" das Zurücksetzen eines Signals bzw. eines Bits.

Methode der FLB-Nutzung:

- Wenn eine Region ρ sich mit keiner schon im FLB vermerkten Region ρ_j überschneidet und noch min destens ein FLB-Eintrag frei ist, kann die Region geflusht werden, indem ρ in einen freien Eintrag geladen und dieser gültig gesetzt wird.
- Beim Überlaufen des FLB oder bei Überschneidung
- (a) können FLB und TLB vollständig geflusht wer den, in der Regel durch gleichzeitiges Rück setzen aller Valid-Bits,
- (b) oder der TLB wird lediglich wieder kollisions sensitiviert, indem alle Collision-Sensitive- Bits cs_i gleichzeitig gesetzt werden, der TLB sonst aber intakt bleibt. Der FLB kann dann unverändert bleiben oder so verändert werden, daß die Vereinigungsmenge der Regionen aller gültigen FLB-Einträge nach der Änderung die entsprechende Menge vor der Veränderung um faßt.

1.2 FLB mit Generationsnummern

Nachfolgend wird anhand der Fig. 1 bis 6 ein zweites Ausführungsbeispiel der Erfindung beschrieben, bei dem die Statusinformation bzw. der Inhalt des Statusfeldes, die bzw. der angibt, ob auf das Datenfeld eines adres sierten TLB-Speichereintrages, der mittels einer Adres se, welche Teil eines im FLB abgespeicherten Adreßraum- Bereichs ist, adressiert ist, zugegriffen werden darf oder nicht.

Der einfache FLB wird pro Eintrag um ein Generations nummernfeld G_j erweitert. Sind keine Überschneidungen von Regionen im FLB zulässig, wird bei einem FLB-Hit die Generationsnummer G_j des zutreffenden Eintrags in G geliefert. Bei überschneidenden Regionen wird beim FLB- Hit die größte Generationsnummer G_j aller zutreffender (v′ ∈ ρ_j) gültiger Einträge in G geliefert.

Eine in Fig. 5 gezeigte Alternative verzichtet auf das Valid-Bit und Fhit-Signal. Hierbei wird Ungültigkeit durch eine reservierte minimale Generationsnummer -∞ angezeigt. FLB-Einträge werden durch G_j = -∞ als ungül tig gekennzeichnet. Außerdem liefert der FLB G = -∞, wenn kein Treffer vorliegt. Um die Darstellung in den Figuren und die Beschreibung einfacher zu halten, wird im folgenden immer diese zweite Realisierung angenom men. Eine Realisierung mit Valid-Bit und Fhit-Signal, die schaltungstechnisch unter Umständen einfacher oder schneller ist, kann auf einfache Weise aus diesen Be schreibungen abgeleitet werden.

Der TLB erhält anstelle eines Collision-Sensitive-Bits pro Eintrag eine Generationsnummer g_i (Fig. 6). Bei einem TLB-Treffer wird dann die entsprechende Genera tionsnummer in g geliefert. Es gibt ein Register γ, das die jeweils aktuelle Generation angibt. Initial bzw. nach jedem FLB-Flush erhält es beispielsweise den Wert 1. Bei jeder Änderung des FLB-Inhalts wird die Genera tion um eins erhöht. Bei jedem Laden eines TLB-Eintrags wird seine Generationsnummer auf die aktuelle Genera tion gesetzt, g_i:= γ.

Eine Kollision liegt bei Thit ∧ G < -∞ vor. Sie ist genau dann echt, wenn G g gilt, siehe Fig. 7. Bei geeigneter Verwendung von γ und der FLB-Felder G_j führt erneutes Ansprechen derselben virtuellen Adresse dann nur zu einer unechten Kollision, es gilt also:

Verwendet man 0 als Repräsentation von -∞ und hat k Bits für jedes Generationsnummerfeld g_i im TLB zur Ver fügung, können als gültige Generationswerte 1 bis 2^k-1 benutzt werden.

Methoden der FLB-Verwaltung

Die konkrete Flush-Semantik wird wesentlich durch die Verwaltung des FLB definiert. Als Beispiel werden hier zwei Methoden skizziert.

(a) Wenn die Generationsnummernfelder ausreichend breit sind, kann man bei jedem neuen FLB-Eintrag den Wert von γ in G_j übernehmen und danach das Register γ um 1 inkrementieren. Überlappung mit anderen FLB-Einträgen spielt dann keine Rolle mehr. Läuft der FLB über, wird er und der TLB ge flusht sowie γ zurückgesetzt.
(b) In vielen Fällen kann man aber mit Hilfe einer Erweiterung der unter 1.1 beschriebenen Methode auch mit schmaleren Generationsnummernfeldern aus kommen. Dabei wird G_j eines neuen FLB-Eintrags stets auf γ gesetzt, danach wird das Register γ aber nur dann um 1 inkrementiert, wenn eine Über lappung der neu einzutragenden Region ρ mit min destens einer der gültigen ρ_j auftritt. Andern falls bleibt γ unverändert. Falls der FLB über läuft oder die aktuelle Generationsnummer γ zu groß wird, werden FLB und TLB geflusht sowie γ zurückgesetzt.

Bei Methode (b) kann anstelle eines totalen TLB Flushs auch der TLB nur wieder kollisions-sensitiviert werden, indem alle Generationsnummern g_i gleichzeitig zurückge setzt werden, z. B. auf 1. Der FLB kann dann unverändert bleiben oder so verändert werden, daß die Gesamtheit aller gültigen FLB-Einträge nach der Änderung min destens die entsprechenden vor der Veränderung gültigen Regionen überdeckt.

Ohne Valid-Bits und Thit-Signal

Auch beim TLB kann man mit Hilfe der reservierten mini malen Generationsnummer -∞ auf Valid-Bit und Thit-Sig nal verzichten, indem man g_i = -∞ bei ungültigen TLB- Einträgen setzt, im Falle von mehr-Wege assoziativen TLBs nur Einträge mit g_i < -∞ berücksichtigt und in jedem Fall -∞ in g liefert, wenn kein Treffer vorliegt. Dieses Modell ist in den Fig. 8 und 9 gezeigt.

Es gilt:

Interessant bei diesem Modell ist insbesondere, daß im TLB ein Bit pro Eintrag gespart wird. Wenn beispiels weise anstatt der beiden Bits cs_i und valid_i ein 2-Bit Feld g_i verwandt und der Wert 0 als -∞ benutzt wird, sind mit demselben Speicheraufwand schon 3 echte Gene rationen möglich.

Allerdings ist Kollisions-Sensitivierung durch Rück setzen aller gültigen (g_i < 0) Generationsnummern jetzt schaltungstechnisch nicht mehr einfach.

1.3 FLB und TLB mit Generationsmasken

Anstelle der Generationsnummern können auch Bit-Masken verwandt werden; statt des arithmetischen Vergleichs < wird dann "bitweises UNDen" nötig.

1.4 TLB mit maskiertem FLB

Ist die Generationsnummer bzw. Maske genügend breit, kann man auf die Generationsinformation G_j beim FLB verzichten und g_i als Adressen von FLB-Einträgen auf fassen. Wie in Fig. 10 dargestellt, liefert der FLB dann für jeden Eintrag j ein Signal Fhit_j. Alle diese Signale werden maskiert geODERt, bei k FLB-Einträgen:

Xhit = (Fhit₀ ∧ m₀) ∨ (Fhit₁ ∧ m₁) ∨ . . . ∨ (Fhit_k-1 ∧ m_k-1)

Dabei wird die Maske (m₀, m₁, . . . m_k-1) entweder direkt im TLB-Eintrag gespeichert und als g geliefert, oder aus dem gelieferten g erzeugt, beispielsweise als -2^g. Bei ¬Xhit ∧ Thit liegt ein Treffer (hit), bei Xhit ∧ Thit eine echte Kollision vor. Es gilt:

1.5 FLB mit Aktivitätsvermerk

Einige FLB-Betriebsarten flushen den TLB oder machen ihn wieder vollständig kollisions-sensitiv, wenn eine neu in den FLB einzutragende Region sich mit schon darin befindlichen überlappt. Um die Häufigkeit solcher Ereignisse zu reduzieren, kann man aktive und inaktive Eintrage im FLB unterscheiden: jeder Eintrag wird erst aktiv, wenn er zum ersten Mal eine echte Kollision be wirkt. Inaktive Einträge können dann erweitert oder für ein erneutes Flushing verwandt werden, ohne daß ein echter FLB- und TLB-Flush erforderlich ist.

Jeder FLB-Eintrag wird um ein Aktivitätsbit actv_j er weitert. Fig. 11 zeigt das für den einfachen FLB, mit Valid-Bits und ohne Generationsnummern. Die anderen FLB-Typen werden genauso durch Hinzufügen der Aktivi tätsbits erweitert. Beim Neuladen eines FLB-Eintrags wird der Aktivitätsvermerk stets zurückgesetzt. Erst bei einer echten Kollision werden die Aktivitätsbits aller matchenden (v′∈ρ_j : actv_j!) FLB-Einträge ge setzt, wobei allerdings ungültige Einträge ignoriert werden können. Man beachte, daß nur dann mehrere Akti vitätsbits gesetzt werden müssen, wenn Überlappungen von Regionen im FLB auftreten können. Andernfalls gibt es bei einer echten Kollision nur genau einen zutref fenden FLB-Eintrag.

Bei einfachem FLB und TLB mit Collision-Sensitive- und Valid-Bits gilt:

Bei FLB mit Generationsnummern G_j und TLB mit Genera tionsnummern g_i sowie Valid-Bits gilt:

Bei FLB mit Generationsnummern G_j und TLB mit Genera tionsnummern g_i ohne Valid-Bits gilt:

Bei TLB mit maskiertem FLB gilt:

Wenn eine Region ρ sich mit keiner schon im FLB ver merkten Region ρ_j überschneidet, die auch aktiv ist (actv_j) und noch mindestens ein FLB-Eintrag frei ist, kann die Region geflusht werden, indem ρ in einen frei en Eintrag geladen und dieser gültig gesetzt wird.

Außerdem können nichtaktive (actv_j) FLB-Einträge modifiziert oder freigegeben werden. Voraussetzung für die Einhaltung der Flush-Semantik ist nur, daß die Ge samtheit aller gültigen FLB-Einträge nach der Änderung mindestens die entsprechenden vor der Veränderung gül tigen Regionen überdeckt.

2. Weitere FLB-Möglichkeiten 2.1 Selektives TLB-Flushing

Der TLB kann selektiv geflusht werden, indem sequen tiell die Felder v′_i aller gültigen TLB-Einträge gegen den FLB getestet werden. Falls der FLB bei v_i einen Treffer meldet, wird dieser TLB-Eintrag invalidiert. Ist der gesamte TLB in dieser Art durchgemustert, kön nen alle FLB-Einträge freigegeben werden, die seit Be ginn dieser Durchmusterung nicht verändert wurden. Ins besondere kann der gesamte FLB geflusht werden, wenn keine FLB-Änderungen während der Durchmusterung auftra gen.

Die TLB-Durchmusterung kann für n-Wege TLBs um den Fak tor n beschleunigt werden, indem parallel die jeweils n zusammengehörigen TLB-Einträge getestet werden. Je nach Geschwindigkeit des FLB muß dieser dazu vervielfacht werden.

Um parallel zur Durchmusterung normale Adreßumsetzung durch den TLB zu ermöglichen, kann man das System um einen "Schatten"-TLB ergänzen, siehe Fig. 12. Im Gegen satz zu TLB ist der Schatten TLB kein assoziativer son dern ein direkt adressierter Speicher. Bei Updates auf grund von TLB-Änderungen können die TLB-Adressen über nommen werden. Der Schatten-TLB dupliziert virtuelle Adresse, Gültigkeits- und Kollisionsinformation jedes TLB-Eintrages. Bei TLBs mit Collision-Sensitive-Bit gilt für die Einträge des Schatten-TLB (siehe Fig. 12):

w_i = v_i, x_i = valid_i ∧ cs_i

bei TLBs mit Generationsnummer und Valid-Bit gilt

w_i = v_i, x_i = (valid_i, g_i),

und bei TLBs mit Generationsnummer ohne Valid-Bit

w_i = v_i, x_i = g_i.

Änderungen in den entsprechenden TLB-Feldern werden sofort zum Schatten-TLB propagiert. Selektives Flushing geschieht vermittels Durchmusterung des Schatten-TLBs. Wenn dabei ein zu flushender Eintrag gefunden wird, wird die Flush-Operation auf Schatten- und eigentlichem TLB ausgeführt.

2.2 FLB als temporärer TLB

Man kann FLB-Einträge um Felder erweitern, die auch im TLB gehalten werden, beispielsweise Zugriffsattribute. Wenn diese dann für eine Region verändert (einge schränkt) werden, reicht es bei einem Fhit aus, die entsprechende Information vom FLB zu übernehmen. Ein Table-Walk wird unnötig.

Fig. 13 zeigt als Beispiel einen FLB, der auch ein Write-Protect-Signal pro Region mitführt, das bei einem FLB-Treffer in Fwp geliefert wird. Das endgültige Write-Protect-Signal wp wird als Twp ∨ (Fhit ∧ Fwp) ge bildet, wobei Twp das vom TLB gelieferte Write-Protect- Signal ist. Damit kann eine Region temporär schreibge schützt werden, ohne daß zusätzliche TLB-Misses und damit Table-Walks erforderlich werden.

Diese Methode kann auch für virtuelles Aliasing und Call-on-Reference genutzt werden. Das in 2.1 beschrie bene Verfahren kann so erweitert werden, daß TLB-Ein träge falls möglich nicht geflusht werden, sondern an hand der vom FLB gelieferten Information verändert wer den.

2.3 Überlappungen im FLB

Bei größeren FLBs kann es aufwendig werden, fest zustellen, ob eine neue Region ρ = [ ] sich mit schon gültig eingetragenen Regionen ρ_j = [ _j, _j] überschnei det. Als voll-assoziatives Element kann der FLB diese Entscheidung unabhängig von seiner Größe in 2 Schritten treffen; allerdings steigen Komplexität und damit auch Kosten des FLB hierdurch.

Jeder FLB-Eintrag wird um das Bit low_j erweitert. Zu Beginn einer Untersuchung auf Überschneidung werden alle low_j-Bits sowie das Fhit-Signal zurückgesetzt. Dem FLB wird die Untergrenze des neuen Bereichs angeboten und jedes Element führt Schritt 1 gemäß folgender Vor schrift durch:

Dann wird dem FLB die Obergrenze angeboten und jedes Element führt Schritt 2 gemäß folgender Vorschrift durch:

Ist nach Schritt 2 das Signal Fhit gesetzt, liegt eine Überlappung vor.

2.4 Caches

Alle aufgeführten Methoden lassen sich genau so mit Caches anstelle der TLBs einsetzen. Anstelle eines Table-Walks mit neuem Laden eines TLB-Eintrags tritt dann ein Hauptspeicher-Zugriff.

Claims

1. Speichervorrichtung zum Speichern von Daten, ins besondere Cache-Speichervorrichtung oder Trans lation-Lookaside-Buffer, mit

- einem Nutzspeicher, der mehrere mittels Adres sen eines Adreßraums adressierbare Speicher- Einträge aufweist, von denen jeder ein als gültig oder nicht gültig markiertes Datenfeld und ein veränderbares Statusfeld aufweist, das in mindestens einen Einschränk-Zustand zum Einschränken eines Schreib/Lese-Zugriffs auf das gültige Datenfeld und in mindestens einen Nichteinschränk-Zustand zum Nichteinschränken eines Schreib/Lese-Zugriffs auf das gültige Datenfeld überführbar ist, und
- einem Hilfsspeicher mit mindestens einem Speicher-Eintrag zum Speichern von einen Be reich des Adreßraums spezifizierenden Daten,
- wobei der Schreib/Lese-Zugriff auf das Daten feld eines adressierten Nutzspeicher-Eintrages dann nicht erlaubt ist, wenn die Adresse innerhalb mindestens eines im Hilfsspeicher gespeicherten Adreßraum-Bereichs liegt und das Statusfeld des Nutzspeicher-Eintrags den Schreib/Lese-Zugriff einschränkt.

2. Speichervorrichtung nach Anspruch 1, dadurch ge kennzeichnet, daß bei einem Lade-Zugriff, mit dem der Nutzspeicher-Eintrag initialisiert wird, das Statusfeld eines adressierten Nutzspeicher-Ein trags

- in einen Einschränk-Zustand überführt wird, wenn die Adresse nicht Teil mindestens eines in dem Hilfsspeicher gespeicherten Adreßraum- Bereichs ist, und
- andernfalls in einen Nichteinschränk-Zustand überführt wird, wenn die Adresse Teil min destens eines in dem Hilfsspeicher gespeicher ten Adreßraum-Bereichs ist.

3. Speichervorrichtung nach Anspruch 1, dadurch ge kennzeichnet, daß das Statusfeld eines adressier ten Nutzspeicher-Eintrags bei einem Lade-Zugriff, mit dem der Nutzspeicher-Eintrag initialisiert wird, in einen Nichteinschränk-Zustand überführt wird.

4. Speichervorrichtung nach Anspruch 3, dadurch ge kennzeichnet, daß das Statusfeld eines adressier ten Nutzspeicher-Eintrags bei dessen Adressierung in einen Nichtschränk-Zustand überführt wird, wenn es zuvor in einem Einschränk-Zustand war und die zur Adressierung verwendete Adresse nicht Teil mindestens eines im Hilfsspeicher gespeicherten Adreßraum-Bereichs ist.

5. Speichervorrichtung nach einem der Ansprüche 2 bis 4, dadurch gekennzeichnet, daß beim Einschreiben von einen Bereich des Adreßraums spezifizierenden Daten in einen Hilfsspeicher-Eintrag die Status felder sämtlicher Nutzspeicher-Einträge in einen Einschränk- Zustand überführt werden.

6. Speichervorrichtung nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß der Hilfsspeicher mehrere Speicher-Einträge aufweist.

7. Speichervorrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß in dem Fall, daß sich in sämtlichen Hilfsspeicher-Eintragen jeweils einen Bereich des Adreßraums spezifizierende Daten befinden und weitere einen Bereich des Adreßraums spezifizierende Daten in den Hilfsspeicher abge speichert werden sollen, sämtliche Nutzspeicher- Einträge und Hilfsspeicher-Einträge als nicht gül tig markiert werden.

8. Speichervorrichtung nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, daß vor dem Abspeichern von einen Bereich des Adreßraums spezifizierenden Daten in einen Hilfsspeicher-Eintrag dieser Adreß raum-Bereich auf Überschneidungen mit bereits im Hilfsspeicher abgespeicherten Adreßraum-Bereichen untersucht wird und der oder die gegebenenfalls bestehenden Hilfsspeicher-Einträge und/oder der neue Hilfsspeicher-Eintrag derart aktualisiert bzw. gewählt wird/werden, daß im Hilfsspeicher sämtliche durch die bisherigen und die neuen Daten spezifizierte Adreßraum-Bereiche abgespeichert sind und die Statusfelder sämtlicher Nutzspeicher- Einträge in einen Einschränk-Zustand überführt werden.

9. Speichervorrichtung nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, daß die Statusfelder sämtlicher Nutzspeicher-Einträge gleichzeitig in einen Einschränk-Zustand überführbar sind, und zwar unabhängig von einer Operation auf dem Hilfs speicher oder dessen Zustand.

10. Speichervorrichtung nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, daß das Statusfeld eines Nutzspeicher-Eintrages ein einziges Bit umfaßt, welches zur Spezifizierung des Einschränk- und des Nichteinschränk-Zustandes setzbar und rücksetzbar ist.

11. Speichervorrichtung nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet,

- daß jeder Hilfsspeicher-Eintrag ein Genera tionsnummernfeld aufweist,
- daß ein Generationsnummern-Zähler vorgesehen ist, der bei jeder Abspeicherung von einen Adreßraum-Bereich spezifizierenden Daten in einen Hilfsspeicher-Eintrag inkrementierbar ist, wobei das Generationsnummernfeld eines Hilfsspeicher-Eintrags auf den vor der Inkre mentierung vorliegenden Wert des Generations nummern-Zählers setzbar ist, wenn in diesen Hilfsspeicher-Eintrag einen Adreßraum-Bereich spezifizierende Daten abgespeichert werden, und wobei das Statusfeld eines Nutzspeicher- Eintrags auf den aktuellen Wert des Genera tionsnummern-Zählers setzbar ist, wenn auf den Nutzspeicher-Eintrag ein diesen initialisie render Lade-Zugriff erfolgt, und
- daß sich das Statusfeld eines adressierten Nutzspeicher-Eintrags
- in einem Nichteinschränk-Zustand befindet, wenn der Wert des Statusfeldes größer ist als der Wert des Generationsnummernfeldes desjenigen Hilfsspeicher-Eintrages, der die Adresse des adressierten Nutzspeicher-Ein trages umfaßt, und
- andernfalls in einem Einschränk-Zustand be findet.

12. Speichervorrichtung nach Anspruch 11, dadurch ge kennzeichnet, daß in dem Fall, daß die Adresse eines adressierten Nutzspeicher-Eintrages inner halb der durch die Daten mehrerer Hilfsspeicher- Einträge spezifizierten Adreßraum-Bereiche liegt, sich das Statusfeld des adressierten Nutzspeicher- Eintrages

- in einem Nichteinschränk-Zustand befindet, wenn der Wert des Statusfeldes größer ist als der größte in den Generationsnummernfeldern der betreffenden Hilfsspeicher-Einträge gespeicher ten Generationsnummern, und
- andernfalls in einem Einschränk-Zustand befin det.

13. Speichervorrichtung nach Anspruch 11 oder 12, da durch gekennzeichnet, daß der Generationsnummern- Zähler bei einer Abspeicherung von einen Adreß raum-Bereich spezifizierenden Daten in einen Hilfsspeicher-Eintrag nur dann inkrementiert wird, wenn der durch diese Daten spezifizierte Adreß raum-Bereich Überschneidungen mit einem oder mehreren bereits im Hilfsspeicher abgespeicherten Adreßraum-Bereichen aufweist.

14. Speichervorrichtung nach einem der Ansprüche 11 bis 13, dadurch gekennzeichnet, daß sämtliche Nutz- und Hilfsspeicher-Einträge als nicht gültig markiert werden und der Generationsnummern-Zähler rückgesetzt wird, wenn weitere einen Adreßraum- Bereich spezifizierende Daten in dem Hilfsspeicher nicht mehr abspeicherbar sind.

15. Speichervorrichtung nach einem der Ansprüche 11 bis 14, dadurch gekennzeichnet, daß sämtliche Nutz- und Hilfsspeicher-Einträge als nicht gültig markiert werden und der Generationsnummern-Zähler rückgesetzt wird, wenn der Generationsnummern-Zäh ler einen vorgebbaren Maximalwert übersteigt.