- Out-of-Order-Execution
-
Out-of-order Execution (kurz OOO) bzw. Außer-der-Reihe-Ausführung (AdR-A) bezeichnet die Möglichkeit, Befehle in den Ausführungseinheiten eines (meist) superskalaren Prozessors außerhalb der Programmreihenfolge auszuführen, mit dem Ziel, die Pipelines möglichst gut auszulasten.
Grundidee
Aufgrund der Forderung, dass das Ergebnis dieser Operationen das gleiche sein muss wie bei Ausführung in Programmreihenfolge, ist OOO-Ausführung nur bei Befehlsfolgen möglich, die nicht voneinander abhängig sind.
Das Gegenteil von Out-of-order Execution ist In-Order Execution, bei der die Befehle strikt nach Programmreihenfolge abgearbeitet werden.
Motivation
Ein superskalarer Prozessor besitzt mehrere Funktionseinheiten (wie ALU, FPU, Load/Store-Einheit oder 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 voneinander ausgeführt werden könnten, diese aber nicht direkt hintereinander im Programmcode stehen, so dass ein Prozessor ohne OOO 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, aber niemals optimal sein, weil die Ausführungszeit von Speicherzugriffen nicht vorhersagbar ist. Diese hängt davon ab, ob der Cache die geforderten Daten oder der TLB die geforderte Seitenübersetzung liefern kann. Das kann man meist nicht oder nur schwer zur Compilier-Zeit voraussagen.
Ein dynamisches Verfahren wie die OOO-Ausführung kann zur Ausführungszeit entsprechend reagieren und so mehr Befehle parallel ausführen und damit die Bearbeitung beschleunigen.
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, in dem 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 K6 besitzen die Möglichkeit, Befehle „out-of-order” auszuführen. Bekannte Ausnahmen sind die IDT WinChip und VIA C3/VIA C7 Serien, die von Centaur Technologies entwickelt wurden, und die Intel Atom Serie.
Siehe auch: Multithreading (hardwareseitig)
Wikimedia Foundation.
