Was ist Out-of-Order-Ausführung?

Computer sind komplexe Maschinen, bei denen kein Teil komplexer ist als die CPU. Auf einer grundlegenden Übersichtsebene scheint es, als ob die CPU relativ einfach sein sollte. Es nimmt eine Reihe von Befehlen entgegen, verarbeitet sie und gibt dann die Daten aus. Dies hat jedoch wenig Ähnlichkeit mit der tatsächlichen Funktionsweise moderner CPUs.

Subskalar bis Superskalar

Frühe CPUs waren genau so, wie Sie es erwarten würden. Sie nahmen Anweisungen einzeln in der Reihenfolge entgegen, in der sie ihnen gegeben wurden, bearbeiteten sie bis zum Ende und gingen dann zur nächsten Anweisung über. CPUs dieses Typs waren subskalar und konnten weniger als einen Befehl pro Taktzyklus ausführen. CPU-Designer stellten fest, dass es viele verschiedene Phasen zum Abschließen einer Anweisung gab. Jede dieser Stufen erforderte unterschiedliche Hardware. Dies bedeutete, dass beim Ausführen einer einzelnen Anweisung durch die gesamte Sequenz zu einem Zeitpunkt einige Teile der Hardware im Leerlauf waren. In jeder Art von Prozessor ist ungenutzte Hardware nutzlose Hardware.

Um diese ungenutzte Hardware zu nutzen, wurden CPU-Designs aktualisiert, um einen Pipeline-Ansatz zu verwenden. Dadurch wurde die Hardware für jede Stufe weiter getrennt, aber sie konnten alle gleichzeitig durch eine Reihe von Anweisungen verwendet werden. Während es immer noch einige Zyklen dauerte, bis jede Anweisung die Pipeline durchlaufen hatte, betrug der Gesamtdurchsatz eine Anweisung pro Zyklus. Dies machte CPUs skalar.

Um mehr leisten zu können, mussten Prozessoren superskalar gemacht werden. Um dies zu erreichen, wurden mehrere parallele Pipelines implementiert.

Pipelines mit Daten füttern

Das Hauptleistungsproblem bei Computern ist normalerweise die Speicherlatenz. Viele Anweisungen arbeiten mit Daten, und daher müssen Daten verfügbar sein, damit die Anweisung ausgeführt werden kann. Die Frage ist, was tun Sie, wenn Sie auf diese Daten warten müssen, weil sie nicht sofort verfügbar sind? Traditionell bestand die Antwort darin, einfach innezuhalten und darauf zu warten, dass es verfügbar wird. Dadurch bleibt die gesamte Pipeline leer, möglicherweise für Hunderte von CPU-Zyklen. Noch schlimmer wird es, wenn zwei Befehle in parallelen Pipelines auf Speicher warten müssen, da der erste sogar die Anfrage nach den Daten des zweiten aufhält. Obwohl der CPU-Cache-Speicher helfen kann, dieses Problem zu beheben, kann er es immer noch nicht beheben. Ein neues Paradigma war nötig, um es zu lösen. Dieser Paradigmenwechsel war Out Of Order Execution oder OOO.

Die erste Stufe einer Pipeline besteht darin, die Anweisung zu decodieren. Dies bedeutet, herauszufinden, was getan werden muss, und zu überprüfen, ob die für die Operation erforderlichen Daten verfügbar sind. In einer OOO-CPU werden decodierte Anweisungen zu einer Warteschlange hinzugefügt. Sie werden erst aus der Warteschlange entfernt und tatsächlich verarbeitet, wenn die benötigten Daten verfügbar sind. Entscheidend ist, dass es keine Rolle spielt, in welcher Reihenfolge die Anweisungen zur Warteschlange hinzugefügt wurden. Wenn eine frühe Anweisung auf Daten wartet, kann eine neuere Anweisung weiterspringen, wenn sie einsatzbereit ist. OOO-Prozessoren können die Befehle, die sie verarbeiten sollen, basierend auf der Warteschlange anstehender Befehle neu ordnen und welche davon zur Ausführung bereit sind.

Kritische Abhängigkeiten

Dieser Prozess setzt zwei Dinge voraus. Erstens, dass es möglich ist, echte Abhängigkeiten zuverlässig zu erkennen und zu handhaben. Zweitens, dass Sie falsche Abhängigkeiten zuverlässig handhaben und identifizieren können. Was ist der Unterschied? Nun, eine echte Abhängigkeit ist eine Abhängigkeit, die in einem OOO-System überhaupt nicht gemildert werden kann. Das einfachste Beispiel ist das Lesen nach dem Schreiben. Wenn Sie eine Anweisung haben, die einige Daten schreiben soll, und eine andere, die diese Daten dann lesen soll, gibt es keine Möglichkeit, diese Anweisungen neu anzuordnen. Sie müssen in der Reihenfolge ausgefüllt werden, in der sie präsentiert wurden, oder Sie erhalten unsinnige Daten.

Eine falsche Abhängigkeit ist eine, die mit einem anderen cleveren Trick versteckt werden kann. Nehmen wir das Beispiel Write-after-Read. Auf den ersten Blick könnte man meinen, dass man Daten nicht überschreiben kann, bevor man sie gelesen hat. Die Dinge sind jedoch nicht so einfach. Was ist, wenn Sie einen anderen Ort haben, an dem Sie die neuen Daten schreiben können, und dann können Sie einfach die neuen und alten Daten austauschen, sobald die alten Daten gelesen wurden? Dies ist der Vorgang der Registerumbenennung und für die OOO-Verarbeitung kritisch.

Typischerweise definiert ein Befehlssatz eine festgelegte Anzahl von Architekturregistern, die in dem System verwendet werden. Sie können buchstäblich keine anderen ansprechen. Aber was ist, wenn Sie Überversorgung registrieren? Sie können sie zum größten Teil einfach ausblenden, sie zum Speichern von Daten verwenden, die noch nicht verarbeitet werden sollten, und dann einfach die Beschriftungen der verborgenen und architektonischen Register austauschen, wenn die Zeitachse wieder korrekt ist. Zu jedem Zeitpunkt gibt es genau die richtige Menge an Architekturregistern, sie befinden sich nur nicht unbedingt immer am selben Ort. Eine Analogie aus der realen Welt wäre Hot-Desking.

Abschluss

Out-of-Order-Ausführung ist ein Verarbeitungsparadigma, bei dem Anweisungen zur Ausführungszeit durch die CPU dynamisch neu geordnet werden können. Dies erfolgt auf der Grundlage der frühesten erteilten Anweisungen, für die Daten verfügbar sind. Das bedeutet, dass Anweisungen, die in die Pipeline geladen werden, immer zur Ausführung bereit sind und es keine Verzögerungen beim Warten auf Daten gibt. Natürlich ist es notwendig, eine Warteschlange zu haben, die lang genug ist, damit sie nicht mit Anweisungen gefüllt wird, die auf Daten warten, aber das ist eine Implementierungsherausforderung. Die Ausführung von OOO beruht auf der Umbenennung von Registern, um falsche Abhängigkeiten zu verbergen. Selbst wenn diese Anweisungen tatsächlich außer der Reihe ausgeführt werden, werden die Register so umbenannt, dass diese Tatsache vor dem Rest des Computers verborgen wird.