Pipelining: Durchsatz, Hazards und Speedup

Eine Befehlspipeline teilt die Bearbeitung eines Befehls in aufeinanderfolgende Teilaufgaben. Jede Teilaufgabe gehört zu einer Stufe. Ein Takt ist hier ein gleich langer Zeitschritt. In unserem vereinfachten Modell benötigt jede Stufe einen Takt. Ein Befehl durchläuft die Stufen nacheinander und befindet sich in jedem Takt in einer Stufe.

Verschiedene Stufen können gleichzeitig verschiedene Befehle bearbeiten. Während ein Befehl die zweite Stufe nutzt, kann der nächste schon in der ersten Stufe beginnen. Die Arbeitsschritte eines einzelnen Befehls bleiben dabei erhalten.

Der Durchsatz beschreibt die Zahl fertig bearbeiteter Befehle pro Zeit. Im Idealmodell ohne Wartezeiten beginnt in jedem Takt ein neuer Befehl. Nachdem die Pipeline gefüllt ist, wird in jedem Takt ein Befehl fertig. Ein einzelner Befehl braucht trotzdem so viele Takte, wie die Pipeline Stufen hat. Seine Zeit vom Eintritt bis zum Abschluss heißt Latenz. Mehr Durchsatz bedeutet daher keine entsprechend kürzere Latenz eines einzelnen Befehls.

Wir rechnen mit einem Idealmodell: Die Pipeline ist anfangs leer. Jede Stufe braucht gleich viel Zeit. Pro Takt kann ein neuer Befehl beginnen. Es gibt keine Wartezeiten und keinen zusätzlichen Zeitbedarf beim Übergang zwischen Stufen. Die Stufenzahl heißt k, die Zahl der Befehle heißt n. Beide sind ganze Zahlen ab eins. Die Taktzeit heißt \tau; den griechischen Buchstaben sprichst du „tau“. Eine Nanosekunde, kurz ns, ist ein Milliardstel einer Sekunde.

Die Pipeline-Laufzeit heißt T_{\mathrm{P}}. Der erste Befehl benötigt k Takte. Die übrigen n-1 Befehle werden jeweils einen Takt später fertig. Deshalb gilt T_{\mathrm{P}}=(k+n-1)\cdot\tau. Für den Vergleich ohne Pipeline nehmen wir ausdrücklich an: Ein Befehl braucht k\cdot\tau, und die Befehle werden nacheinander bearbeitet. Diese Vergleichslaufzeit heißt T_{\mathrm{ohne}}. Es gilt T_{\mathrm{ohne}}=n\cdot k\cdot\tau.

Der Speedup S ist der Beschleunigungsfaktor gegenüber diesem Vergleich. Du teilst die Laufzeit ohne Pipeline durch die Laufzeit mit Pipeline: S=\frac{T_{\mathrm{ohne}}}{T_{\mathrm{P}}}=\frac{n\cdot k}{k+n-1}. Der Speedup hat keine Einheit. Beispielsweise bedeutet S=2: Mit Pipeline braucht die gleiche Befehlsfolge halb so viel Zeit.

Bei einem einzigen Befehl ist S=1. Es gibt dann keine Überlappung mit weiteren Befehlen. Bei mehr als einer Stufe bleibt der ideale Speedup für jede endliche Befehlszahl unter k. Bei immer längeren Befehlsfolgen nähert er sich k. Das ist eine Aussage über dieses Modell. In echten Prozessoren lässt sich die Taktzeit nicht beliebig verkürzen. Mehr Stufen benötigen außerdem mehr technische Bauteile und können die Zeitverluste durch Konflikte vergrößern.

Ein Konflikt in einer Pipeline heißt auch Hazard. Er kann die geplante überlappende Bearbeitung behindern. Zum Erkennen fragst du: Fehlt ein gemeinsam genutzter Baustein, ein benötigter Wert oder die Klarheit über den nächsten Befehl?

Ein Ressourcenkonflikt entsteht, wenn zwei Stufen gleichzeitig dieselbe begrenzt verfügbare Ressource benötigen. Eine Ressource ist hier etwa ein Rechenbaustein oder ein Zugang zum Speicher. Auch wenn die benötigten Werte bereitstehen, können zwei gleichzeitige Zugriffe auf einen einzigen solchen Baustein unmöglich sein.

Ein Datenkonflikt entsteht, wenn ein Befehl einen benötigten Wert noch nicht verwenden kann. Beispielsweise soll er das Ergebnis eines vorherigen Befehls benutzen, doch dieses Ergebnis steht noch nicht bereit. Freie Rechenbausteine allein beheben diesen fehlenden Wert nicht.

Ein Kontrollflusskonflikt betrifft die Frage, welcher Befehl als Nächstes ausgeführt werden soll. Der Kontrollfluss ist die Reihenfolge der ausgeführten Befehle. Ein bedingter Sprung setzt die Bearbeitung abhängig von einer Prüfung an einer anderen Stelle fort oder lässt sie an der bisherigen Stelle weiterlaufen. Solange die richtige Fortsetzung unklar ist, besteht ein Kontrollflusskonflikt.

Ein Konflikt kann Wartezyklen verursachen. Das Warten eines Befehls heißt Stall. Eine dadurch entstehende Lücke in der Bearbeitung heißt Bubble, auf Deutsch „Blase“. Solche Lücken senken den Durchsatz gegenüber dem Idealmodell. Nicht jeder erkannte Konflikt muss zu einem Stall führen: Eine passende Gegenmaßnahme kann ihn rechtzeitig beheben oder seine Folgen mindern.

Gegenmaßnahmen müssen zum Konflikt passen. Ein zusätzlicher passender Baustein kann einen Ressourcenkonflikt beheben, wenn dadurch die gleichzeitig benötigte Leistung bereitsteht. Er erzeugt jedoch keinen noch fehlenden Ergebniswert und entscheidet keinen unklaren Sprung.

Forwarding bedeutet hier direktes Weiterreichen eines bereits verfügbaren Ergebnisses an die Stufe, die es benötigt. Das Ergebnis kann genutzt werden, bevor der erzeugende Befehl seinen regulären Abschluss erreicht. So lassen sich viele Datenkonflikte ohne Warten beheben. Forwarding kann aber kein Ergebnis weiterreichen, das noch nicht berechnet ist. Steht der Wert auch über diesen direkten Weg nicht rechtzeitig bereit, kann weiterhin ein Stall nötig sein. Ein Ressourcenkonflikt wird durch das Weiterreichen allein ebenfalls nicht behoben.

Bei der Sprungvorhersage nimmt der Prozessor eine Fortsetzung an, bevor die Entscheidung über einen bedingten Sprung feststeht. Er arbeitet auf diesem angenommenen Weg vorläufig weiter. Das heißt spekulatives Weiterrechnen. Trifft die Vorhersage zu, kann dadurch Wartezeit vermieden werden.

Eine Vorhersage kann falsch sein. Dann müssen die zwischenzeitlich auf dem falschen Weg bearbeiteten Befehle verworfen werden. Diese Bereinigung heißt Pipeline-Flush. Die Arbeit auf dem falschen Weg kostet Zeit; bei langen Pipelines können solche Verluste besonders groß sein. Sprungvorhersage garantiert daher keine richtige Fortsetzung und keinen bestimmten Speedup. Sie liefert auch keinen fehlenden Datenwert und keinen zusätzlichen Rechenbaustein.