Pipeline-Hazard

Grundidee

Pipeline-Hazards sind Konflikte in der Pipeline von Prozessoren, die während der Programmlaufzeit auftreten können. Moderne Prozessoren arbeiten meist mit einer Pipeline-Architektur: Eine Instruktion läuft durch mehrere Stufen, und in jedem Taktzyklus erreicht sie die nächste Stufe. In jeder Stufe wird ein Teil der Instruktion bearbeitet.

Dabei benötigt jede Stufe bestimmte Prozessorressourcen, zum Beispiel Datenwege oder Rechenwerke. Außerdem kann eine Instruktion Ergebnisse brauchen, die von einer früheren Instruktion erst noch erzeugt werden. Wenn eine Ressource blockiert ist oder ein benötigtes Ergebnis noch nicht bereitsteht, muss die betroffene Instruktion vorübergehend angehalten werden. Dieses Anhalten heißt „stall“. Auch die folgenden Instruktionen in der Pipeline werden dann angehalten.

Man unterscheidet drei Arten von Pipeline-Konflikten: Datenkonflikte, Steuerkonflikte und Strukturkonflikte.

Datenabhängigkeiten

Datenkonflikte entstehen durch Datenabhängigkeiten zwischen Befehlen im Programm. Ein Befehl braucht also Daten, die ein anderer Befehl liest oder schreibt. Es gibt drei Arten von Datenkonflikten.

Read after Write (RAW), auch echte Abhängigkeit genannt: Ein Operand wird zuerst verändert und kurz danach gelesen. Wenn der erste Befehl den Operanden noch nicht fertiggeschrieben hat, etwa weil die Pipeline-Stufe „store“ weit hinten liegt, könnte der zweite Befehl falsche Daten verwenden. Ein „Shortcut“ im Datenweg der Pipeline kann diesen Hazard manchmal vermeiden. In schwierigeren Fällen, zum Beispiel wenn ein Rechenergebnis zur Adressierung verwendet wird oder bei berechneten und bedingten Sprüngen, ist ein Anhalten der Pipeline unumgänglich.

Beispiel für RAW: R1 = R2+R3 R4 = R1+1

Write after Read (WAR), auch Gegenabhängigkeit genannt: Ein Operand wird gelesen und kurz danach überschrieben. Wenn das Schreiben vor dem Lesen abgeschlossen wäre, könnte der Lesebefehl schon den neu geschriebenen Wert erhalten. Das ist ein mögliches Problem bei Out-of-order execution, also wenn Befehle nicht in der ursprünglichen Reihenfolge ausgeführt werden. Bei In-order execution tritt dieses Problem nicht auf.

Beispiel für WAR: R1 = R2+R3 R2 = 2

Write after Write (WAW), auch Ausgabeabhängigkeit genannt: Zwei Befehle schreiben auf denselben Operanden. Wenn der zweite Befehl vor dem ersten fertig wird, kann am Ende ein falscher Wert im Operanden stehen bleiben. Auch dies ist ein mögliches Problem bei Out-of-order execution, nicht bei In-order execution.

Beispiel für WAW: R1 = R2+R3 R1 = 2

Steuerkonflikte

Steuerkonflikte treten bei Instruktionen auf, die den Befehlszähler verändern. Der Befehlszähler bestimmt, welcher Befehl als Nächstes ausgeführt wird. Ein typisches Beispiel sind bedingte Sprungbefehle, bei denen erst entschieden werden muss, ob ein Sprung ausgeführt wird.

Zur Vermeidung solcher Konflikte nennt der Artikel zwei Verfahren. Bei der Sprungvorhersage berechnet eine zusätzliche Hardware-Einheit die Wahrscheinlichkeit, mit der es zu einem Sprung kommt. Dadurch kann der Prozessor versuchen, die Pipeline schon mit den wahrscheinlich passenden nächsten Instruktionen zu füllen.

Beim Delayed Branching wird die Zeit, in der das Sprungziel berechnet wird, genutzt, um andere Instruktionen zu berechnen, die vom Sprung unabhängig sind. Dieses Verfahren ist laut Artikel nicht mehr aktuell und wird heute durch dynamische Branch-Voraussage-Algorithmen ersetzt.

Strukturkonflikte

Strukturkonflikte entstehen, wenn innerhalb der Pipeline Ressourcenkonflikte auftreten. Eine Ressource kann dann nicht gleichzeitig so genutzt werden, wie mehrere Befehle es benötigen. Als Beispiel nennt der Artikel einen synchronen Zugriff auf einen Registerspeicher mit nur einem Eingang.

In einfachen Fällen können Prozessoren durch einen „Shortcut“ im Datenweg der Pipeline den Hazard vermeiden. In schwierigeren Situationen, etwa wenn ein Rechenergebnis zur Adressierung verwendet wird oder bei berechneten und bedingten Sprüngen, ist ein Anhalten der Pipeline aber unumgänglich.

Der Artikel betont außerdem, dass es sinnvoll ist, voneinander abhängige Befehle möglichst nicht direkt hintereinander auszuführen. Moderne Prozessoren können durch Out-of-order execution oder hardwareseitiges Multithreading in vielen Fällen Hazards und Ressourcenkonflikte vermeiden.