Out-of-Order-Execution (OoO, deutsch „Ausführung außer der Reihe") ist eine Technik moderner Prozessoren, Befehle nicht in der Programmreihenfolge abzuarbeiten, sondern dann, wenn ihre Eingabewerte wirklich bereit sind. Das Ergebnis wird anschließend in der ursprünglichen Reihenfolge festgeschrieben — nach außen hin verhält sich die CPU, als hätte sie exakt so gerechnet wie im Maschinencode vorgegeben.
Das Grundprinzip: Datenfluss statt Programmfluss
Ein Programm besteht aus Befehlen mit Abhängigkeiten: Der nächste Befehl braucht oft das Ergebnis des vorherigen. Eine klassische In-Order-CPU wartet dann, bis das Ergebnis vorliegt — verlorene Takte, etwa bei einem langsamen Cache-Zugriff. Die OoO-Hardware erkennt dagegen die tatsächlichen Datenabhängigkeiten und führt all jene Befehle parallel aus, die voneinander unabhängig sind. Befehle aus späteren Codestellen können so früher laufen als davorstehende, die noch auf Daten warten.
Die Bausteine
Drei Mechaniken machen OoO möglich: Das Register-Renaming entfernt scheinbare Konflikte, indem interne Register umbenannt werden, damit zwei Befehle nicht um dasselbe Register kämpfen. Reservation Stations warten auf ihre Operanden und melden sich, sobald diese fertig sind — das Konzept geht auf den Tomasulo-Algorithmus des IBM System/360 Model 91 (1967) zurück und weiter auf das Scoreboarding des CDC 6600 (1964). Ein Reorder Buffer (ROB) sammelt die fertigen Ergebnisse und schreibt sie in der ursprünglichen Befehlsfolge ins Architektur-Register — erst dann sind sie für andere Programme sichtbar.
Warum sich das lohnt
OoO steigert die Zahl der pro Takt abgeschlossenen Befehle (IPC) und versteckt Latenzen: Wartezeiten auf Speicher, auf langsame Gleitkommaoperationen der FPU oder auf Pipeline-Konflikte werden mit Arbeit aus anderen Programmteilen überbrückt. In einem superskalaren Kern laufen mehrere Ausführungseinheiten gleichzeitig; ohne OoO blieben sie bei jeder Datenabhängigkeit teilweise leer.
Die Gegenentwürfe
Die statische Alternative ist VLIW: Dort plant bereits der Compiler die Parallelität und die Hardware bleibt einfach. Frühe RISC-Designs setzten bewusst auf In-Order-Kerne, um Komplexität und Energie zu sparen — moderne x86- und ARM-Kerne kombinieren jedoch CISC-Dekodierung mit OoO-Ausführung. Die Grenze zur spekulativen Ausführung ist fließend: OoO entscheidet, wann ein Befehl läuft, die Spekulation, ob er überhaupt benötigt wird.
Risiken und Nebenwirkungen
OoO ist Ursache der 2017 publik gewordenen Meltdown-Lücke: Ein Befehl kann auf geschützten Speicher zugreifen, bevor die Berechtigungsprüfung abgeschlossen ist; die Ergebnisse werden zwar verworfen, hinterlassen aber messbare Spuren im Cache. Auch Exceptions und Spezialfälle müssen im Reorder Buffer sauber abgewickelt werden, damit der sichtbare Zustand stets der Programmreihenfolge entspricht.