Out-of-order execution
Out-of-order execution (englisch für etwa Ausführung in anderer Reihenfolge [als im Programmcode]) bezeichnet die Möglichkeit, Maschinenbefehle in den Ausführungseinheiten eines (meist superskalaren) Prozessors in einer anderen Reihenfolge auszuführen als sie im Programmcode stehen, ohne allerdings das Ergebnis zu verändern. Dadurch können mehr Befehle parallel ausgeführt werden, da die Recheneinheiten des Prozessors besser ausgelastet werden. Das Gegenteil von out-of-order execution ist in-order execution, bei der die Befehle strikt nach Programmreihenfolge abgearbeitet werden, wie etwa beim Von-Neumann-Zyklus. Weil das Ergebnis der Out-of-Order-Ausführung das gleiche sein muss wie bei Ausführung in Programmreihenfolge, erhöht Out-of-Order-Execution die Geschwindigkeit nur bei Befehlsfolgen, bei denen ein nachfolgender Befehl nicht vom Ergebnis des vorherigen Befehls abhängt (sondern nur von Befehlen, die „weit genug entfernt“ zuvor ausgeführt wurden).
Motivation
Ein Prozessor hat mehrere Funktionseinheiten, (Anmerkung: In der x86 Welt erstmals seit dem Intel Pentium P54) u. a. arithmetisch-logische Einheit (ALU), Gleitkommaeinheit (FPU), Lade-und-Speicher-Einheit und spezielle (Gleitkomma-)Vektoreinheiten. Bei superskalaren Prozessoren ermöglichen sie, Befehlsparallelität auszunutzen und damit die Ausführungsgeschwindigkeit zu erhöhen: Während ein vorhergehender Befehl eine Funktionseinheit noch belegt, stehen die freien Funktionseinheiten bereits dem nachfolgenden Befehl zur Verfügung. Wegen Datenabhängigkeiten zwischen den Befehlen, oder wenn sie dieselbe Funktionseinheit benötigen, ist die parallele Ausführung aber nicht immer möglich. Oft könnten Befehle zwar parallel ausgeführt werden, stehen aber nicht direkt hintereinander im Programmcode; ein Prozessor ohne Out-of-Order-Execution hält sich streng an die Ausführungsreihenfolge, die im Programm vorgegeben ist, und kann sie dann nicht parallel ausführen.
Eine Umordnung der Befehle im Programm per Hand oder durch den Compiler kann auf einem In-Order-Prozessor zwar zu besseren Ergebnissen führen, ist aber im Allgemeinen nicht optimal, weil Einflüsse während der Laufzeit nicht oder kaum berücksichtigt werden können. Insbesondere ist die Ausführungszeit von Speicherzugriffen nicht vorhersagbar. Diese hängt davon ab, ob der Cache die geforderten Daten oder der Übersetzungspuffer (TLB) die geforderte Seitenübersetzung liefern kann. Das kann man meist nicht oder nur schwer zur Kompilierzeit voraussagen.
Ein dynamisches Verfahren zum Umordnen der Befehle, wie die Out-of-Order-Execution-Ausführung, kann zur Ausführungszeit entsprechend reagieren und so mehr Befehle parallel ausführen und damit die Bearbeitung beschleunigen.
Funktionsprinzip
In früheren Prozessoren wurden die einzelnen Befehle nacheinander abgearbeitet, wobei jeder Befehl nach einer festen Folge aus Teilschritten (in-order execution) ausgeführt wurde, vgl. u. a. Von-Neumann-Zyklus. Diese Teilschritte sind:
- Befehl laden (instruction fetch)
- Wenn die Operanden verfügbar sind (zum Beispiel in Registern), wird der Befehl an die passende Funktionseinheit zur Ausführung übergeben. Wenn ein oder mehr Operanden im aktuellen Befehlszyklus nicht verfügbar sind (meist weil sie noch aus dem Speicher geladen werden müssen), wartet der Prozessor, bis diese geladen sind.
- Der Befehl wird durch die passende Funktionseinheit ausgeführt.
- Die Funktionseinheit schreibt das Ergebnis in ein Register.
Das neue Konzept (out-of-order execution) bearbeitet die Befehle in der folgenden Reihenfolge:
- Befehl laden (instruction fetch).
- Befehl in eine Warteschlange (instruction buffer) eintragen.
- Der Befehl wartet im instruction buffer, bis seine Operanden geladen sind. Danach darf der Befehl die Warteschlange verlassen, oft vor früher eingetragenen, älteren Befehlen.
- Der Befehl wird an die passende Ausführungseinheit übergeben und dort ausgeführt.
- Das Ergebnis wird in eine Warteschlange der Ergebnisse eingetragen. (register retirement file/buffer)
- Erst nachdem die Ergebnisse aller früheren, älteren Befehle in die Register geschrieben wurden, wird das Ergebnis des aktuellen Befehls ebenfalls in die Register geschrieben.
Implementierung
Implementiert wird meist Scoreboarding oder der Tomasulo-Algorithmus. Beim Scoreboarding werden belegte Ressourcen auf einem zentralen Scoreboard markiert und nach ihrer Verwendung wieder freigegeben. Der Tomasulo-Algorithmus implementiert dynamisches Scheduling. So werden mehrere Befehle gleichzeitig ausgeführt, solange die Operanden unabhängig sind. Verhindert werden Read-After-Write-Hazards, indem der Befehl verzögert wird, und Write-After-Read-Hazards, indem ein neuer Wert zwischengespeichert wird. Zur Reduzierung der Datenabhängigkeiten wird zusätzlich Registerumbenennung verwendet.
Der erste x86-Prozessor mit Out-of-order execution war der NexGen's Nx686. Fast alle modernen x86-Prozessoren ab dem Intel Pentium Pro bzw. AMD K5 können Befehle out-of-order ausführen. Bekannte Ausnahmen sind die IDT-WinChip-, VIA-C3- und -C7-Serien, die von Centaur Technology entwickelt wurden, und die Intel-Atom-Serie bis einschließlich Cedar Trail.
Literatur
- Oberschelp, Vossen: Rechneraufbau und Rechnerstrukturen. 9. Auflage. Oldenbourg, 2003, ISBN 3-486-27206-3.