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. Dadurch können die Stufen der Pipeline 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 dieser Operationen das gleiche sein muss wie bei Ausführung in Programmreihenfolge, ist OOE-Ausführung nur bei Befehlsfolgen möglich, die nicht voneinander abhängig sind.
Motivation
Ein superskalarer Prozessor hat mehrere Funktionseinheiten, u. a. arithmetisch-logische Einheit (ALU), Gleitkommaeinheit (FPU), Lade-und-Speicher-Einheit und spezielle Vektoreinheiten, mit dem Ziel, möglichst viel Befehlsparallelität auszunutzen und damit die Ausführungsgeschwindigkeit zu erhöhen. Wegen Datenabhängigkeiten zwischen den Befehlen ist die parallele Ausführung aber nicht immer möglich. Hinzu kommt die Einschränkung, dass einige Befehle zwar parallel ausgeführt werden könnten, diese aber nicht direkt hintereinander im Programmcode stehen, so dass ein Prozessor ohne OOE diese nicht parallel ausführen kann, weil er sich streng an die Ausführungsreihenfolge hält, die im Programm vorgegeben ist.
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 die Ausführungszeit von Speicherzugriffen nicht vorhersagbar ist. 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 wie die OOE-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.
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 und VIA C3/VIA C7 Serien, die von Centaur Technology entwickelt wurden, und die Intel-Atom-Serie bis einschließlich Cedar Trail.
Siehe auch
Literatur
- Oberschelp, Vossen: Rechneraufbau und Rechnerstrukturen. 9. Auflage. Oldenbourg, 2003, ISBN 3-486-27206-3.