Out-of-Order Execution

Die Out-of-Order-Ausführung ermöglicht es einem Prozessor, Befehle auszuführen, sobald deren Operanden bereit sind, anstatt streng in Programmreihenfolge. Dabei werden Registerumbenennung und Pufferung verwendet, um Parallelität aufzudecken und dennoch Ergebnisse in der richtigen Reihenfolge zu erzeugen.

Definition

Out-of-Order-Execution ist eine mikroarchitektonische Technik, bei der ein Prozessor die Befehlsausführung dynamisch neu anordnet, um unabhängige Befehle auszuführen, sobald deren Operanden verfügbar sind, während Pufferung und Umbenennung verwendet werden, um den Anschein einer sequenziellen, In-Order-Vervollständigung zu wahren.

Scope

Dieses Thema behandelt die dynamische Ablaufplanung: Reservierungsstationen, Registerumbenennung zur Beseitigung falscher Abhängigkeiten, den Reorder-Puffer, der die In-Order-Commitment erzwingt, und die Wiederherstellung nach spekulativer Ausführung. Es baut direkt auf Tomasulos Algorithmus auf. Ausgeschlossen sind die Vorhersage der Sprungrichtung (Sprungvorhersage) und der breitere Begriff des Ausmaßes der Parallelität (Befehlsebene-Parallelität), wobei der Fokus auf dem Reordering-Mechanismus selbst liegt.

Core questions

• Wie kann ein Prozessor Befehle außerhalb der Programmreihenfolge ausführen und dennoch korrekte, In-Order-Ergebnisse liefern?
• Wie eliminiert die Registerumbenennung Write-After-Read- und Write-After-Write-Abhängigkeiten?
• Welchen Beitrag leisten Reservierungsstationen und der Reorder-Puffer?
• Wie werden Ausnahmen und Fehlvorhersagen in einem Out-of-Order-Kern präzise wiederhergestellt?

Key concepts

• dynamische Ablaufplanung
• Reservierungsstationen
• Registerumbenennung
• gemeinsamer Datenbus
• Reorder-Puffer
• In-Order-Commit
• präzise Ausnahmen
• Wiederherstellung nach spekulativer Ausführung

Key theories

Tomasulos Algorithmus

Tomasulos Schema verwendet Reservierungsstationen und einen gemeinsamen Datenbus, um Register umzubenennen und Befehle an Funktionseinheiten zu senden, sobald deren Operanden verfügbar sind, was eine Out-of-Order-Ausführung ermöglicht, die nur echte Datenabhängigkeiten berücksichtigt.

Präzise Ausnahmen durch In-Order-Commit

Ein Reorder-Puffer speichert die Ergebnisse von Out-of-Order-Befehlen und committet sie in Programmreihenfolge, sodass Ausnahmen und Fehlvorhersagen präzise behandelt werden können, als ob die Ausführung streng sequenziell gewesen wäre.

Mechanisms

Dekodierte Befehle werden auf physikalische Register umbenannt und in Reservierungsstationen oder einer Issue-Queue platziert, wo sie auf Operanden warten, die über einen Ergebnisbus übertragen werden. Wenn sie bereit sind, werden sie auf verfügbaren Funktionseinheiten in beliebiger Reihenfolge ausgeführt. Ein Reorder-Puffer verfolgt die ursprüngliche Programmreihenfolge und committet Ergebnisse sequenziell, wobei spekulative Ergebnisse bei einer Fehlvorhersage oder Ausnahme verworfen werden, sodass der architektonische Zustand stets präzise ist.

Clinical relevance

Die Out-of-Order-Execution ist der Kernmotor von Hochleistungs-CPUs, der Speicher- und Ausführungslatenzen verbirgt, indem er unabhängige Aufgaben findet. Sie hat auch Sicherheitsimplikationen: Da spekulative, Out-of-Order-Arbeit vor dem Verwerfen transient auf Daten zugreifen kann, ermöglichte sie die Spectre- und Meltdown-Klassen von mikroarchitektonischen Seitenkanalangriffen.

History

Tomasulo führte 1967 die dynamische Ablaufplanung im IBM System/360 Model 91 ein. Die Kombination mit dem Reorder-Puffer für präzise Ausnahmen, die in den 1980er Jahren entwickelt wurde, machte die Out-of-Order-Execution für Allzweckprozessoren praktikabel und wurde ab Mitte der 1990er Jahre zum Standard in Hochleistungsdesigns.

Debates

Leistung versus Komplexität, Stromverbrauch und Sicherheit

Die Out-of-Order-Ausführung liefert eine starke Single-Thread-Leistung, jedoch zu erheblichen Kosten in Bezug auf Hardwarekomplexität und Stromverbrauch, und ihre Spekulation hat sich als ausnutzbar erwiesen; dies befeuert die Debatte darüber, wie aggressiv spekuliert werden sollte, im Vergleich zur Bevorzugung einfacherer, effizienterer oder sichererer Designs.

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

Wenn Befehle Out-of-Order ausgeführt werden, wie bleibt das Programm dann korrekt?

Der Prozessor ordnet nur die Ausführung neu an, nicht die Ergebnisse. Die Registerumbenennung stellt sicher, dass echte Datenabhängigkeiten respektiert werden, und ein Reorder-Puffer committet die Ergebnisse in der ursprünglichen Programmreihenfolge, sodass der sichtbare architektonische Zustand genau dem entspricht, was eine sequentielle Ausführung erzeugen würde.

Was ist Registerumbenennung?

Die Registerumbenennung ordnet die in Befehlen benannten architektonischen Register einem größeren Pool physikalischer Register zu. Dies beseitigt falsche (Namens-)Abhängigkeiten, die durch die Wiederverwendung von Registernamen entstehen, wodurch mehr unabhängige Befehle parallel ausgeführt werden können, ohne sich um die Registerspeicherung zu streiten.