Begriff
Out-of-Order Execution (OoO)
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Dein Programmcode ist eine Liste von Befehlen: A, B, C, D. Eine einfache CPU arbeitet sie der Reihe nach ab (In-Order). Problem: Befehl A ("Lade Daten aus RAM") dauert 100 Takte. Befehl B ("Rechne 1+1") hat nichts mit A zu tun. Eine In-Order CPU wartet 100 Takte auf A. Langweilt sich. Eine OoO-CPU sieht: "Hey, B ist unabhängig von A. Ich mache B schon mal fertig, während A noch lädt." Sie führt Befehle aus, sobald ihre Daten da sind (Data Flow), nicht wie sie im Programm stehen. Am Ende sortiert sie die Ergebnisse wieder richtig (Reorder Buffer), damit es für den Programmierer so aussieht, als wäre alles der Reihe nach passiert. Das macht moderne CPUs (Core i9, Ryzen) massiv schneller als einfache (Arduino, Atom).
Merksatz: Ein Architekturmerkmal moderner Hochleistungsprozessoren, das es erlaubt, Befehle vorzuziehen, deren Eingabedaten bereits verfügbar sind, um Wartezeiten (z. B. auf den Speicher) zu überbrücken, wobei die Ergebnisse später wieder in die korrekte Programmreihenfolge gebracht werden.
Du merkst es nicht direkt. Aber es erklärt, warum CPU-Takt (GHz) nicht alles ist. Eine 3 GHz OoO-CPU ist viel schneller als eine 3 GHz In-Order-CPU. Aber OoO kostet Transistoren und Strom (komplexe Logik). Deshalb nutzen Effizienz-Kerne (z. B. Intel E-Cores oder ARM Little Cores) oft weniger OoO-Tiefe.
1. Tomasulo-Algorithmus
Der Algorithmus, der das möglich macht (erfunden bei IBM 1967).
Er nutzt "Reservation Stations", um Befehle zu puffern.
Und "Register Renaming", um falsche Abhängigkeiten aufzulösen ("WAR - Write after Read").
Wenn Befehl 1 EAX nutzt und Befehl 2 EAX überschreibt, benennt die CPU das interne Register um (R1, R2), damit beide parallel laufen können.
2. Reorder Buffer (ROB)
Hier warten die fertiggestellten Befehle. Sie dürfen erst "retiren" (Gültigkeit erlangen), wenn alle vorherigen Befehle retired sind. Das garantiert "Sequential Consistency" bei Exceptions. Wenn Befehl B (der vorgezogen wurde) einen Fehler wirft (Division durch Null), darf dieser Fehler erst geworfen werden, wenn Befehl A wirklich fertig ist.
1. Load-Store Queue (LSQ) & Memory Disambiguation
Das größte Hindernis für OoO ist der Speicher.
Befehl A schreibt an Adresse [0x100]. Befehl B liest von [0x100].
Wenn B vor A ausgeführt wird, liest B den falschen (alten) Wert.
Moderne CPUs haben eine Load-Store Queue. Sie überwacht alle laufenden Speicherzugriffe.
Mit Memory Disambiguation rät die CPU sogar: "Ich glaube, Adresse X und Y sind unterschiedlich, also ziehe ich den Load von Y vor den Store nach X." Stellt sich später heraus, dass sie doch gleich waren (Aliasing), wird die gesamte Pipeline verworfen und neu gestartet (Pipeline Flush). Das ist riskant, bringt aber bei Pointer-lastigem Code (C++) gewaltige Performance.
2. RAT (Register Allocation Table) & Rename Buffers
Physische Register vs. Architektonische Register.
Programmierer sehen 16 Register (RAX, RBX...). Intern hat die CPU oft 180 oder mehr physische Register.
Die RAT mappt jedes Mal, wenn ein Befehl ein Register schreibt, dieses auf ein "frisches" physisches Register.
Dadurch werden künstliche Abhängigkeiten eliminiert. Wenn zwei Schleifendurchläufe beide RCX als Counter nutzen, bekommen sie intern unterschiedliche physische Register und können parallel in der OoO-Engine laufen. Die CPU "entrollt" die Logik der Schleife also dynamisch in Hardware.
3. Commit & Retire Stage (The Window of Opportunity)
Die OoO-Engine arbeitet mit einem Instruction Window. Bei einem modernen Intel/AMD-Prozessor können ca. 200-400 Befehle gleichzeitig "in flight" sein. Nur am Ende (Retire Stage) werden die Ergebnisse in den permanenten Zustand (Architectural State) geschrieben. Dies geschieht strikt in der ursprünglichen Reihenfolge (In-Order Commit). Wenn ein Interrupt oder eine Exception auftritt, löscht die CPU einfach alle Befehle im Reorder-Buffer (ROB), die nach dem fehlerhaften Befehl kamen. So wird garantiert, dass das System stabil bleibt, egal wie viel Chaos "unter der Haube" während der OoO-Phase herrschte.
Quick-Check
Meltdown?
Meltdown nutzte aus, dass OoO-CPUs Berechtigungsprüfungen ("Darfst du Kernel-Speicher lesen?") erst beim "Retire" machen. Die spekulative Ausführung hat die Daten schon geladen und in den Cache gelegt. Hacker konnten sie per Side-Channel lesen.Hyperthreading?
SMT (Simultaneous Multithreading) nutzt die Lücken im OoO-Schedule. Wenn Thread 1 auf RAM wartet, schiebt die CPU Befehle von Thread 2 in die Lücken.Itanium?
Intels gescheiterter Versuch (VLIW), OoO in den Compiler zu verlagern (EPIC). Es stellte sich heraus: Der Compiler weiß zur Kompilierzeit nicht genug (Cache Misses sind dynamisch). Hardware-OoO gewinnt immer.