Quelltext der Seite Out-of-order execution

{{lang|en|'''Out-of-order execution'''}} ({{enS}} für etwa ''Ausführung in anderer Reihenfolge [als im Programmcode]'') bezeichnet die Möglichkeit, Maschinenbefehle in den Ausführungseinheiten eines (meist [[Superskalarität|superskalaren]]) [[Prozessor]]s 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 {{lang|en|''out-of-order execution''}} ist {{lang|en|'''in-order execution'''}}, bei der die Befehle strikt nach Programmreihenfolge abgearbeitet werden, wie etwa beim [[Von-Neumann-Zyklus]]. Weil das Ergebnis 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). 

Die schwerwiegenden Sicherheitslücken [[Spectre (Sicherheitslücke)|Spectre]] und [[Meltdown (Sicherheitslücke)|Meltdown]] können nur gegen Prozessoren eingesetzt werden, die zu {{lang|en|''out-of-order execution''}} fähig sind.

== Motivation ==
Ein Prozessor hat mehrere Funktionseinheiten (bei [[x86-Prozessor]]en erstmals seit dem [[Intel Pentium#Die Pentium-1-Familie|Intel Pentium P54]]),  u.&nbsp;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ängigkeit]]en 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 {{lang|en|''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 ([[Translation Lookaside Buffer|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 ==
[[Datei:Architektur-fuer-ungeordnete-befehlsausfuehrung.svg|miniatur|Grundprinzip der ungeordneten Befehlsausführung]]

In früheren Prozessoren wurden die einzelnen Befehle nacheinander abgearbeitet, wobei jeder Befehl nach einer festen Folge aus Teilschritten ({{lang|en|''in-order execution''}}) ausgeführt wurde, vgl. u.&nbsp;a. [[Von-Neumann-Zyklus]]. Diese Teilschritte sind:
# Befehl laden ({{lang|en|''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 ({{lang|en|''out-of-order execution''}}) bearbeitet die Befehle in der folgenden Reihenfolge:
# Befehl laden ({{lang|en|''instruction fetch''}}).
# Befehl in eine [[Warteschlange]] ({{lang|en|''instruction buffer''}}) eintragen.
# Der Befehl wartet im {{lang|en|''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. ({{lang|en|''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-[[Pipeline-Hazard|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|x86]]-Prozessor mit {{lang|en|''out-of-order execution''}} war der [[NexGen#Nx686|Nx686]]. Fast alle modernen [[X86-Prozessor|x86]]-Prozessoren ab dem [[Intel Pentium Pro]] bzw. [[AMD K5]] können Befehle {{lang|en|''out-of-order''}} ausführen. Bekannte Ausnahmen sind die [[IDT WinChip|IDT-WinChip]]-, [[VIA C3|VIA-C3]]- und [[VIA C7|-C7]]-Serien, die von [[Centaur Technology]] entwickelt wurden, und die [[Intel Atom|Intel-Atom]]-Serie bis einschließlich Cedar Trail.

== Siehe auch ==
* [[Hardwareseitiges Multithreading]]

== Literatur ==
* {{Literatur|Autor=Oberschelp, Vossen|Titel=Rechneraufbau und Rechnerstrukturen|Verlag=Oldenbourg|Auflage=9.|Jahr=2003|ISBN=3486272063}}

[[Kategorie:Rechnerarchitektur]]