Registerumbenennung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Registerumbenennung (englisch register renaming) bezeichnet eine Phase in der Befehlsdekodierung, die meist von superskalaren Mikroprozessoren angewandt wird. Sie hilft, unnötige Sequentialisierung zu vermeiden bzw. verbessert die Out-of-Order-Execution, d. h. die Möglichkeit, Anweisungen nebenläufig auszuführen.

In der x86-Familie kam Registerumbenennung erstmals im Pentium Pro zum Einsatz, in dem acht für den Programmierer sichtbare Register des Befehlscodes (EAX, EBX, …, ESP) auf 96 unsichtbare (aber physisch vorhandene) Register umgelegt wurden.

Motivation[Bearbeiten]

Heutige Hochleistungs-CPUs sind massiv superskalare Prozessoren. Aus ihrer Historie heraus enthalten diese (meist) viel zu wenige Register. Das führt zu Abhängigkeiten ausgeführter Befehle, die in den Daten aber nicht bestehen:

 1. R0  = [R3]
 2. R1  = 42
 3. R0 *= R1
 4. R2 += R0
 5. R0  = [R4]    # <-- Der Inhalt von R0 ist unabhängig vom Wert R0 bis 4.
 6. R1  = 13      # <-- Der Inhalt von R1 ist unabhängig vom Wert R1 bis 5.
 7. R0 *= R1
 8. R2 += R0
 9. R0  = [R5]    # <-- Der Inhalt von R0 ist unabhängig vom Wert R0 bis 8.
10. R1  = 91      # <-- Der Inhalt von R1 ist unabhängig vom Wert R1 bis 9.
11. R0 *= R1
12. R2 += R0

Diesen Code will man eigentlich parallel abarbeiten:

 1. R0  = [R3]
 2. R1  = 42     R0  = [R4]
 3. R0 *= R1     R1  = 13    R0  = [R5]
 4. R2 += R0     R0 *= R1    R1  = 91
 5.              R2 += R0    R0 *= R1
 6.                          R2 += R0

Bei Prozessoren mit vielen Registern kann man diese Abhängigkeiten zur Compilezeit auflösen, i Allerdings steht man vor zwei Dilemmas:

  • Man benötigt genaue Kenntnisse über den Zielprozessor, damit man weiss, wann ein Register wieder benutzt werden kann, ohne die CPU anzuhalten.
  • In Schleifen werden Register ziemlich schnell wiederbenutzt. Das einzige Hilfsmittel ist Loop-Unrolling, was zu schlechter Codedichte führt.
 1. R1  = 42
 2. R0  = [R3+]    <-- Der Inhalt von R0 ist von vorherigen Werten unabhängig
 3. R0 *= R1
 4. [R4+] = R0
 5. if (-R5 == 0) jmp 2.

Diesen Code will man eigentlich parallel abarbeiten:

 1. R1 = 42
 2. R0 = [R3+]
 3. R0 *= R1      R0  = [R3+]
 4. [R4+] = R0    R0 *= R1      R0  = [R3+]
 5.               [R4+] = R0    R0 *= R1      R0  = [R3+]
 6.                             [R4+] = R0    R0 *= R1      R0  = [R3+]
 7.                                           [R4+] = R0    R0 *= R1      R0  = [R3+]
 8.                                                         [R4+] = R0    R0 *= R1      R0  = [R3+]

Hier benötigt man auch bei Vorhandensein vieler Register eine Möglichkeit, die Abhängigkeiten über gemeinsam genutzte Register aufzulösen. Hier greift die Methode des Register Renamings, in der man zwischen Registernamen und Registerinhalten strikt trennt. Diese Methode erfordert einiges an Chipfläche, hat sich aber in der Vergangenheit als sehr effektiv herausgestellt. Einen anderen Ansatz ist man mit Explicitly Parallel Instruction Computing beim Itanium gegangen, der sich als weniger erfolgreich herausgestellt hat. Dort wird die Parallelisierung zur Compilezeit in den Befehlen kodiert. Nachteilig ist, das man zu dieser Zeit zu wenig über das Zielsystem weiß und das man zur besseren Parallelisierung von Schleifen diese ausrollen muss, was viel Code erzeugt und große L1-Caches benötigt.

Zurück zum Register Renaming: Will man dies erreichen, muss man die Register umbenennen und darf den gleichen Registernamen nur für identische Inhalte verwenden. Dann ersetzt Namensabhängigkeiten und es bleiben nur wirkliche Datenabhängigkeiten übrig, die dann optimal Out-Of-Order ausgeführt werden können.

Die Register-Abhängigkeiten Write After Read (WAR) und Write After Write (WAW) werden durch Registerumbenennung aufgelöst. Dazu existiert eine große Zahl an Schattenregistern, die nicht direkt vom Programm verwendet werden können. Üblicherweise wird nun in der Dekodierstufe (ID) des Prozessors bei jeder Definition eines Registers, sprich bei jeder Instruktion, die ein Ergebnis produziert und es in einem Register ablegen möchte, das verwendete Register in ein Schattenregister umbenannt – daher der Name. Danach enthält der Code nur noch echte Datenabhängigkeiten und die unabhängigen Teile können parallel oder in einer anderen Reihenfolge ausgeführt werden.

Vorgehen[Bearbeiten]

Für das Register Renaming benötigt man folgende Ressourcen:

  • Meine Mnenomik-Register (z.B. eax, ebx, ecx, edx, esi, edi, ebp, esp) sowie eine Tabelle, auf welche physischen Register diese gerade gemappt sind.
  • Meine physischen Register (z.B. r000 bis r127) sowie einen Zähler, wie viele Operationen an diesen noch anhängig sind und ob der Wert schon verfügbar ist.
  • Einen Pool mit den gerade unbenutzten physischen Registern

Die Dekodierstufe erzeugt daraus Mikrooperationen, die nur noch physische Register enthalten und die nur noch einfache Mikroperationen beinhalten.

Die Regeln lauten:

  1. Wird ein Mnemonik-Register mit einem neuen Wert beschrieben
    • Wird es einem anderen physischen (noch freien) physischen Register zugewiesen, das dem Pool mit den gerade unbenutzten physischen Registern entnommen wird.
    • Dem neuen physischen Register wird ein UseCount von 1 gegeben
    • Dem alten physischen Register wird der UseCount um 1 reduziert
  2. Fordert eine Operation einen Wert von einem Register an und der Wert des Registers ist noch unbekannt
    • Wird der UseCount dieses Registers um 1 erhöht
  3. Wird der Wert eines solchen unbekannten Registers berechnet, wird dieser Wert an wartende Operationen ausgeliefert.
    • Der UseCount dieses Registers wird für jede Auslieferung um 1 reduziert
  4. Wird der UseCount eines Register 0
    • Wird das Register freigegeben und dem Pool mit den gerade unbenutzten physischen Registern zugeführt.

Aus Registern mit sich ändernden Werten werden Register mit konstanten Werten, die bei jeder Modifikation ihren Namen ändern.

Beispiele[Bearbeiten]

Der folgende Code kann in dieser Form nur sequentiell abgearbeitet werden, da Registerabhängigkeiten bestehen.

1:  R1 := R2 / R3
2:  R4 := R1 + R5   # RAW-Abhängigkeit mit Zeile 1
3:  R5 := R6 + R7   # WAR-Abhängigkeit mit Zeile 2
4:  R1 := R8 + R9   # WAW-Abhängigkeit mit Zeile 1

Benennt man nun konsequent das Zielregister jeder definierenden Operation um, lösen sich die WAR- und WAW-Abhängigkeiten auf:

1:  A := R2 / R3
2:  B := A  + R5   # RAW-Abhängigkeit mit Zeile 1
3:  C := R6 + R7
4:  D := R8 + R9

Die Zeilen 1, 3 und 4 können nun in beliebiger Reihenfolge oder auch parallel ausgeführt werden.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  • Jean-Loup Baer: Microprocessor Architecture: From Simple Pipelines to Chip Multiprocessors, S. 89 ff., Cambridge University Press, 2010, ISBN 9780521769921.
  • Christian Müller-Schloer, Wolfgang Karl, Sami Yehia: Architecture of Computing Systems – ARCS 2010: 23rd International Conference, Hannover, Germany, February 22-25, 2010, Proceedings, S. 127 ff., Springer Science & Business Media, 2010, ISBN 9783642119491.
  • John L. Hennessy, David A. Patterson: Computer Architecture: A Quantitative Approach, S. 208 ff., Elsevier, 2012, ISBN 9780123838728.