PatentDe  


Dokumentenidentifikation DE19524925A1 01.02.1996
Titel Verfahren zum Umsetzen einer virtuellen Adresse in eine reale Adresse
Anmelder GMD - Forschungszentrum Informationstechnik GmbH, 53757 Sankt Augustin, DE
Vertreter Patentanwälte von Kreisler, Selting, Werner et col., 50667 Köln
DE-Anmeldedatum 08.07.1995
DE-Aktenzeichen 19524925
Offenlegungstag 01.02.1996
Veröffentlichungstag im Patentblatt 01.02.1996
IPC-Hauptklasse G06F 12/10
Zusammenfassung Mit dem Verfahren läßt sich eine einen Seitenadreßteil aufweisende virtuelle Adresse eines virtuellen Adreßraums in eine einen Seitenadreßteil aufweisende reale Adresse eines realen Adreßraums umsetzen. Beide Seiten sind Ein- oder Vielfache einer Basisseite und können unterschiedlich groß sein. Mittels der virtuellen Adresse wird ein Speicher mit mehreren Speichereinträgen adressiert. Jeder Speichereintrag weist ein Markierungsfeld für eine Markierung und ein Datenfeld für mindestens einen Seitenadreßteil einer realen Seitenadresse und ein Seitenkennungsfeld für die Größe der realen Seite mit der im Datenfeld gespeicherten realen Seitenadresse auf. Bei Übereinstimmung der Markierung des Markierungsfeldes eines Speichereintrags wird mit dem virtuellen Seitenadreßteil der virtuellen Adresse die reale Seitenadresse auf der Grundlage des Inhalts des Datenfeldes und des Seitenkennungsfeldes ermittelt.

Beschreibung[de]

Die Erfindung betrifft ein Verfahren zum Umsetzen einer virtuellen Adresse in eine reale Adresse (auch physische Adresse). Ein Anwendungsbeispiel der Erfindung ist die Speicherverwaltungseinheit (Hardware) auch MMU (Memory Management Unit) genannt, bei der unter anderem die Adresse im virtuellen Speicher in eine Adresse des physischen oder Realspeichers umgesetzt wird.

MMUs (Memory Management Units) sind die hardwaremäßige Basis für virtuelle Speicher, Adreßräume, Paging und Schutzmechanismen. Sie sind somit für alle Anwendungen bedeutsam, die mit großen Datenmengen operieren (insbesondere in verteilten Systemen oder Superrechnern) und/oder Sicherheitseigenschaften auf komplex aufgebauten Objekten benötigen.

Konventionelle MMUs teilen virtuelle Adreßräume typischerweise in 4 KB oder 8 KB große Seiten auf. Die Abbildung virtueller auf reale Adressen geschieht entweder mit mehrstufig aufgebauten Page Tables oder einer Inverted Page Table. Üblicherweise wird die Adreßumsetzung noch durch einen TLB (Translation Lookaside Buffer) oder virtuellen Cache beschleunigt.

Inverted Page Tables (und auch viele mehrstufige Page Table Verfahren) lassen konventionellerweise nur eine einheitliche Seitengröße zu.

Bei konventionellen Page Tables wird eine virtuelle Adresse in mehreren Stufen umgesetzt. Jede Stufe arbeitet dabei mit einer Page Table, deren Einträge entweder auf Page Tables der nächsten Stufe oder (bei der letzten Stufe) auf Datenseiten verweisen. Dabei haben Page Tables und Datenseiten in der Regel fest vorgegebene Größen 2i.

Im folgenden sei anhand von Fig. 3 eine Umsetzschrift einer virtuellen (Binär-)Adresse v anhand einer Page Table mit der Adresse p betrachtet. Dazu wird v in einen höherwertigen Teil u (bestehend aus einer bestimmten Anzahl der höherwertigen Bits) und einen niederwertigen Teil v&min; (bestehend aus den niederwertigen Bits) aufgespalten. Vermittels u wird dann ein Eintrag der Page Table ausgewählt, der unter anderem eine neue Adresse p&min; beinhaltet.

Inverted Page Tables bestehen aus einem Eintrag pro Kachel des Realspeichers, der jeweils die virtuelle Adresse der zugeordneten Seite des virtuellen Adreßraums enthält. Zugegriffen wird mit Hilfe einer Hashfunktion (siehe Fig. 4).

Bei der Umsetzung der virtuellen Adresse v in die Realadresse r wird der niederwertige Teil w direkt übernommen. Der höherwertige Teil u wird durch die Hashfunktion auf einen Wert p abgebildet, der sowohl die vermutliche Kachel im Realspeicher identifiziert als auch zur Indizierung der invertierten Page Table benutzt wird. Wenn der entsprechende Eintrag die richtige virtuelle Adresse u enthält, liegt ein Treffer vor. Andernfalls (in Fig. 4 nicht aufgeführt) müssen vermittels Rehash oder Weiterkettung weitere Kacheln untersucht werden, bis ein Treffer vorliegt oder auf Page Fault entschieden wird.

Hashed Page Tables (siehe Fig. 5) sind eine Variante des IPTs, wobei allerdings nicht mehr jeder Eintrag fest einer physischen Seite zugeordnet ist, sondern jeder Eintrag die physische Adresse der entsprechenden Seite enthält.

Aus Kostengründen kann nicht bei jedem Speicherzugriff eines Programms die MPT bzw. IPT oder HPT parsiert werden. Dieser Overhead wird mit Hilfe eines speziellen Caches für die Adreßumsetzung vermieden, eines Translation Lookaside Buffers (TLB) . Normalerweise werden mehr als 90% aller Adreßumsetzungen zu Nullkosten durch TLB-Treffer erledigt. Nur bei einem TLB-Miss werden die Page Tables parsiert.

Konventionelle TLBs weisen typischerweise 32 bis 256 Einträge auf, von denen jeder die Adreßumsetzung einer Seite beschreibt, d. h. eine Seitenadresse des Realspeichers aufweist. Sie sind teilweise voll assoziativ, häufig aber nur 2- oder 4-Wege-assoziativ aufgebaut.

Konventionelle n-Wege assoziative TLBs operieren üblicherweise nur mit einer einheitlichen Seitengröße.

Der Erfindung liegt die Aufgabe zugrunde, ein Adressenumsetzverfahren zu schaffen, das multiple Seitengrößen im virtuellen und realen Adreßraum unterstützt.

Insbesondere soll auf der Grundlage von Hashed Page Tables (HPTs) oder Inverted Page Tables (IPT) eine MMU konstruiert werden, die multiple Seitengrößen unterstützt. Varianten sollen möglichst auch bei anderen Page Tables eingesetzt werden können.

Zur Lösung dieser Aufgabe wird ein Verfahren mit den Merkmalen von Anspruch 1 bzw. Anspruch 4 vorgeschlagen. Vorteilhafte Ausgestaltungen dieser Verfahrensvarianten sind jeweils in den Unteransprüchen angegeben.

Das erfindungsgemäße Verfahren dient der Umsetzung einer einen Seitenadreßteil aufweisenden virtuellen Adresse eines virtuellen Adreßraums, der in mehrere virtuelle Seiten mit virtuellen Seitenadressen unterteilt ist, wobei die virtuellen Seiten Ein- oder Vielfache einer Basisseite vorgegebener Größe sind und unterschiedlich groß sein können, in eine einen Seitenadreßteil aufweisende reale Adresse eines realen Adreßraums, der in mehrere reale Seiten mit realen Seitenadressen unterteilt ist, wobei die realen Seiten Ein- oder Vielfache der Basisseite sind und unterschiedlich groß sein können. Hierbei gilt, daß die Größe einer virtuellen Seite gleich der Größe der zugehörigen realen Seite ist. Unterschiedliche virtuelle Seiten können unterschiedlich groß sein; selbiges gilt für die realen Seiten. Für sämtliche Seiten (reale und virtuelle) gilt, daß sie ein Ein- oder Vielfaches einer Basisseite sind.

Mittels der virtuellen Adresse wird ein Speicher mit mehreren Speichereinträgen adressiert. Dabei weist jeder Speichereintrag ein Markierungsfeld für eine Markierung und ein Datenfeld für mindestens einen Seitenadreßteil einer realen Seitenadresse und ein Seitenkennungsfeld für die Größe der realen Seite mit der im Datenfeld gespeicherten realen Seitenadresse auf.

Bei Übereinstimmung der Markierung des Markierungsfeldes eines adressierten Speichereintrags wird mit dem virtuellen Seitenadreßteil der virtuellen Adresse die reale Seitenadresse auf der Grundlage des Inhalts des Datenfeldes und des Seitenkennungsfeldes ermittelt.

Bei der Untersuchung der virtuellen Adresse auf Übereinstimmung mit der Markierung des Markierungsfeldes jedes adressierten Speichereintrages werden insbesondere die relevante Zahl der höchstwertigen Bits von Markierung und virtueller Adresse verglichen. Bei der "relevanten Zahl" handelt es sich um die Differenz der Bitlänge der virtuellen Adresse und dem 2er-Logarithmus der durch das Seitenkennungsfeld des jeweiligen Speichereintrages spezifizierten Seitengröße.

Vorzugsweise wird in dem Fall, daß keine der Markierungen der Markierungsfelder der adressierten Speichereinträge mit dem virtuellen Seitenadreßteil der virtuellen Adresse übereinstimmt, mittels des virtuellen Basisseitenadreßteils der virtuellen Adresse eine Page Table parsiert. Im Falle eines Treffers liefert die Page Table den realen Seitenadreßteil der realen Adresse und einen Wert für die Größe der realen Seite. Der virtuelle Seitenadreßteil der virtuellen Adresse, der reale Seitenadreßteil der realen Adresse sowie der Wert für die Größe der realen Seite werden in das Markierungsfeld, das Datenfeld bzw. das Seitenkennungsfeld eines Eintrages des Speichers (TLB) eingeschrieben.

Bei einer Variante des obigen Verfahrens weisen die realen und virtuellen Seiten maximal eine vorgegebene Größe auf (Maximalgröße). Die Seiten können gleich der oder kleiner als die Maximalgröße sein. Bei diesem Verfahren wird mittels der virtuellen Adresse eine mehrere Einträge aufweisende Inverted oder Hashed Page Table parsiert. Jeder Eintrag der Page Table weist eine Markierung für einen virtuellen Seitenadreßteil, ein Datenfeld für eine reale Seitenadresse der realen Adresse sowie ein Seitenkennungsfeld für eine die Größe der realen Seite mit dem realen Seitenadreßteil repräsentierenden Wert auf. Mittels des der Maximalseitengröße entsprechenden Maximalseitenadreßteils der virtuellen Adresse oder einer Abbildung desselben wird eine Gruppe von Einträgen der Page Table, insbesondere ein Cluster von Einträgen ausgewählt. Bei Übereinstimmung einer der Markierungen der Markierungsfelder der Einträge der indizierten Gruppe der Page Table mit dem durch die Seitengröße des Seitenkennungsfeldes des jeweiligen Eintrages bestimmten Seitenadreßteil der virtuellen Adresse wird anhand der in dem Datenfeld des betreffenden Eintrages der Page Table gespeicherten realen Seitenadreßteils, der Größe der Maximalseite und dem in dem Seitenkennungsfeld dieses Eintrages gespeicherten Wert die reale Adresse ermittelt.

Anstelle einer Inverted oder Hashed Page Table kann auch ein Translation Lookaside Buffer mit einer der Anzahl von Einträgen einer Gruppe gleichenden Assoziativität verwendet werden.

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

Fig. 1 eine bildliche Darstellung eines Zugriffs auf eine einfache Hashed Page Table mittels einer virtuellen Adresse nach einem ersten Ausführungsbeispiel,

Fig. 2 eine bildliche Darstellung eines Zugriffs auf eine k-assoziative Hashed Page Table mittels einer virtuellen Adresse nach einem ersten Ausführungsbeispiel,

Fig. 3 eine Darstellung des Zugriffs auf eine mehrstufige Page Table,

Fig. 4 eine Darstellung des Zugriffs auf eine Inverted Page Table und

Fig. 5 eine Darstellung des Zugriffs auf eine Hashed Page Table.

Bei einem mixed-page-size TLB für eine fixed-page-size Page Table sei ein Page Table Mechanismus mit fester Seitengröße 2s, beispielsweise IPT oder HPT, vorgegeben. Diese Seiten werden im folgenden Basisseiten genannt.

Desweiteren wird ein TLB vorausgesetzt, der unterschiedlich große Seiten erlaubt. Zulässige TLB-Seitengrößen seien dabei die Größe der Basisseite und Vielfache von 2s+x, wobei x = 0, 1, . . . X sein kann. Diese Seiten werden zusammengesetzte Seiten genannt.

Jeder Page Table Eintrag wird um ein (Daten-)Feld t erweitert, das die TLB-Seitenkennung definiert. Dabei gilt, daß die Basisseite Teil einer 2s+t großen zusammengesetzten Seite ist.

Angenommen, bei einem Zugriff über die virtuelle Adresse v tritt ein TLB-Miss auf. Dann wird die Page Table mit v-v mod 2s als virtueller Seitenadresse parsiert. Bei einem Treffer wird die physische Adresse p der Basisseite und die TLB-Seitenkennung t geliefert.

Bei einem konventionellen TLB würde jetzt einer der TLB-Einträge mit



geladen, d. h. genau die Basisseite beschrieben.

Statt dessen wird erfindungsgemäß einer der TLB-Einträge mit



geladen. (Dabei ist mit "mod" die mathematische Modulo-Funktion bezeichnet, die den ganzzahligen Rest c einer Division a/b beschreibt: a mod b = c.) Damit belegen (größere) zusammengesetzte Seiten im TLB auch nur einen Eintrag pro zusammengesetzter Seite und nicht mehr pro Basisseite, d. h. nicht mehr bis zu 2t Einträge. (Die aktuelle Seitengröße kann im TLB nicht nur durch Speicherung von t, sondern auch durch daraus abgeleitete Werte geschehen, z. B. durch eine Bitmaske 2s+t - 1.) Dagegen finden sich in der Page Table so viele Einträge für die zusammengesetzte Seite, wie diese Basisseiten aufweist.

Bei einer Variante des obigen Verfahrens bezeichnet p nicht die physische Adresse der Basisseite, sondern diejenige der zusammengesetzten Seite:



Damit brauchen zusammengesetzte Seiten im Realspeicher nicht mehr 2s+t ausgerichtet zu sein.

Bei einer zweiten Variante wird der Größenfaktor einer zusammengesetzten Seite nicht mehr als 2er-Logarithmus sondern direkt angegeben. Eine zusammengesetzte Seite hat dann die Größe 2st. Jeder Page Table Eintrag enthält außerdem ein Feld u, das die relative Distanz der Basisseite innerhalb der Seite angibt. u kann die Werte 0, 1, . . . t - 1 annehmen. Der TLB-Eintrag sieht dann folgendermaßen aus:



(Statt p - 2su kann, wie in bei der ersten Varianten vorgesehen, p die physische Adresse der Seite bezeichnen.)

Hiermit können physisch und virtuell zusammenhängende Basisseiten zusammengefaßt werden, ohne daß die entstehende zusammengesetzte Seite eine 2er-Potenz als Größenfaktor einer Basisseite aufweist und ohne daß sie ausgerichtet sein muß.

Jeder der oben beschriebenen mixed-page TLBs läßt sich auch bei Page Tables anwenden, die selbst schon unterschiedlich große Seiten zulassen (dritte Variante). Das kann beispielsweise sinnvoll sein, wenn die Bandbreite der möglichen Seitengrößen im TLB größer ist als bei den Page Tables.

Realisierungsmöglichkeiten
  • a) Beim Pariseren der Page Table wird jetzt auch die (variable) Größe s und damit die gerade aktuelle Basisseitengröße geliefert.
  • b) t definiert alleine die Seitengröße:



  • c) Zusammengesetzte Seiten lassen sich nur für eine bestimmte Basisseitengröße bilden, beispielsweise nur für die größte Seitengröße, die der Page Table Mechanismus zuläßt.


Nachfolgend soll eine k-assoziative mixed-page HPT erläutert werden, wobei des besseren Verständnisses wegen zuerst eine einfache HPT beschrieben wird. Die größtmögliche Seitengröße sei dabei 2S, wobei S die Bitlänge des Feldes w der S niederwertigsten Bits von v ist (s. Fig. 1). Dabei soll -2s einen Bitstring mit führenden EINSEN und den letzten s Bits jeweils als NULL, d. h. einen Bitstring beschreiben, dessen s niedrigstwertige Bits NULL und dessen übrige (höherwertige) Bits EINS sind. Umgekehrt soll (2s-1) einen Bitstring mit führenden NULLEN und den letzten s Bits jeweils als EINS, d. h. einen Bitstring beschreiben, dessen höherwertige Bits jeweils NULL und dessen s niedrigstwertige Bits jeweils EINS sind. AND beschreibt die bitweise logische UND-Verknüpfung.

Falls v&min; = v AND (-2s) gilt, so ergibt sich die reale Adresse r als p + (w AND (2s-1)).

Wichtig ist hierbei, daß mit u nur solche Bits der virtuellen Adresse v zur Adressierung der HPT verwandt werden, die bei keiner zulässigen Seitengröße zum Seitenoffset gehören.

Bei der k-assoziativen HPT hingegen wird durch die Hash-Funktion nicht nur ein Eintrag, sondern ein Cluster von k Einträgen ausgewählt (s. Fig. 2, in der für die k Einträge die Indizierung 0, 1, 2, . . . , k-1 gewählt ist).

Die k Einträge des Clusters werden, wie in Fig. 2 gezeigt, überprüft. Ergibt sich beim Clustereintrag i ein Treffer, d. h. liefert die Abfrage vi&min; = v AND (-2si) den Wert "wahr", werden pi und si dieses Eintrags zur Bildung der Realadresse verwandt. Ergibt sich kein Treffer, scheitert die Adreßumsetzung.

Mit diesem Verfahren sind z. B. die 2er-Potenzen von 2s bis hinunter nach 2s/k als Größen einer zusammengesetzten Seite möglich, wobei die Trefferraten nie schlechter sind als bei einfachen HPTs.

Kleinere Seitengrößen als 2s/k sind ebenfalls möglich, führen aber bei dichter Nutzung zu Clashes, da die k-assoziative HPT nur maximal k Seiten aus einem 2s-großen Bereich gleichzeitig aufnehmen kann.

Das Verfahren kann mit den bei Hashed Page Tables üblichen Rehash- und Link-Methoden kombiniert werden.

Die Assoziativität kann durch vollständig parallele Verarbeitung eines Clusters erfolgen. Sequentielle oder teilweise parallele Abarbeitung ist aber auch möglich.

Die Assoziativität kann über Rehash/Link auf weitere Cluster ausgedehnt werden.

Das oben anhand einer mixed-page HPT beschriebene Verfahren wird auf einen k-Wege assoziativen TLB angewandt .

Die Beschreibung geht aus dem obigen Sachverhalt hervor, wenn man die k-assoziative HPT durch den k-Wege assoziativen TLB ersetzt. Die Rolle des Clusters wird dann durch den ausgewählten aus k Einträgen bestehenden Set (Satz, Zeile) des TLB übernommen.


Anspruch[de]
  1. 1. Verfahren zum Umsetzen einer einen Seitenadreßteil aufweisenden virtuellen Adresse eines virtuellen Adreßraums, der in mehrere virtuelle Seiten mit virtuellen Seitenadressen unterteilt ist, wobei die virtuellen Seiten Ein- oder Vielfache einer Basisseite vorgegebener Größe sind und unterschiedlich groß sein können, in eine einen Seitenadreßteil aufweisende reale Adresse eines realen Adreßraums, der in mehrere reale Seiten mit realen Seitenadressen unterteilt ist, wobei die realen Seiten Ein- oder Vielfache der Basisseite sind und unterschiedlich groß sein können, bei dem
    1. - mittels der virtuellen Adresse ein Speicher mit mehreren Speichereinträgen adressiert wird, wobei jeder Speichereintrag ein Markierungsfeld für eine Markierung und ein Datenfeld für mindestens einen Seitenadreßteil einer realen Seitenadresse und ein Seitenkennungsfeld für die Größe der realen Seite mit der im Datenfeld gespeicherten realen Seitenadresse aufweist, und
    2. - bei Übereinstimmung der Markierung des Markierungsfeldes eines Speichereintrags mit dem virtuellen Seitenadreßteil der virtuellen Adresse die reale Seitenadresse auf der Grundlage des Inhalts des Datenfeldes und des Seitenkennungsfeldes ermittelt wird.
  2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß bei der Untersuchung der virtuellen Adresse auf Übereinstimmung mit der Markierung des Markierungsfeldes jedes adressierten Speichereintrages die relevante Zahl der höchstwertigen Bits von Markierung und virtueller Adresse verglichen werden, wobei die relevante Zahl sich aus der Differenz der Bitlänge der virtuellen Adresse und dem 2er-Logarithmus der durch das Seitenkennungsfeld des jeweiligen Speichereintrages spezifizierten Seitengröße ergibt.
  3. 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet,
    1. - daß in dem Fall, daß keine der Markierungen der Markierungsfelder der adressierten Speichereinträge mit dem virtuellen Seitenadreßteil der virtuellen Adresse übereinstimmt, mittels des virtuellen Basisseitenadreßteils der virtuellen Adresse eine Page Table parsiert wird,
    2. - daß die Page Table im Falle eines Treffers den realen Seitenadreßteil der realen Adresse und einen Wert für die Größe der realen Seite liefert und
    3. - daß der virtuelle Seitenadreßteil der virtuellen Adresse, der reale Seitenadreßteil der realen Adresse sowie der Wert für die Größe der realen Seite in das Markierungsfeld, das Datenfeld bzw. das Seitenkennungsfeld eines Eintrages des Speichers eingeschrieben werden.
  4. 4. Verfahren zum Umsetzen einer einen Seitenadreßteil aufweisenden virtuellen Adresse eines virtuellen Adreßraums, der in mehrere virtuelle Seiten mit virtuellen Seitenadressen unterteilt ist, wobei die virtuellen Seiten Ein- oder Vielfache einer Basisseite vorgegebener Größe sind, eine vorgegebene Maximalgröße nicht überschreiten und unterschiedlich groß sein können, in eine einen Seitenadreßteil aufweisende reale Adresse eines realen Adreßraums, der in mehrere reale Seiten mit realen Seitenadressen unterteilt ist, wobei die realen Seiten Ein- oder Vielfache der Basisseite sind, die Maximalgröße nicht überschreiten und unterschiedlich groß sein können, bei dem
    1. - mittels der virtuellen Adresse eine mehrere Einträge aufweisende Inverted oder Hashed Page Table parsiert wird,
    2. - wobei jeder Eintrag eine Markierung für einen virtuellen Seitenadreßteil, ein Datenfeld für eine reale Seitenadresse der realen Adresse sowie ein Seitenkennungsfeld für eine die Größe der realen Seite mit dem realen Seitenadreßteil repräsentierenden Wert aufweist und
    3. - wobei mittels des der Maximalseitengröße entsprechenden Maximalseitenadreßteils der virtuellen Adresse oder einer Abbildung derselben eine Gruppe von Einträgen der Page Table ausgewählt wird, und
    4. - bei Übereinstimmung einer der Markierungen der Markierungsfelder der indizierten Einträge der Page Table mit dem durch die Seitengröße des Seitenkennungsfeldes des jeweiligen Eintrages bestimmten Seitenadreßteil der virtuellen Adresse anhand der in dem Datenfeld des betreffenden Eintrages der Page Table gespeicherten realen Seitenadreßteils, der Größe der Maximalseite und dem in dem Seitenkennungsfeld dieses Eintrages gespeicherten Wert die reale Adresse ermittelt wird.
  5. 5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß anstelle einer Inverted oder Hashed Page Table ein Translation Lookaside Buffer mit einer der Anzahl von Einträgen einer Gruppe gleichenden Assoziativität verwendet wird.






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