Pipeline (Prozessor)

Grundprinzip der Prozessor-Pipeline

Eine Pipeline, auch Befehls- oder Prozessor-Pipeline, ist eine verbreitete Mikroarchitektur von Mikroprozessoren. Sie funktioniert wie ein Fließband: Die Ausführung eines Maschinenbefehls wird in mehrere einfachere Teilaufgaben zerlegt. Diese sogenannten Pipeline-Stufen, Pipeline-Stages oder Pipeline-Segmente bearbeiten gleichzeitig unterschiedliche Befehle und sind durch getaktete Pipeline-Register voneinander getrennt.

Während eines Taktzyklus wird von einem einzelnen Befehl jeweils nur eine Teilaufgabe ausgeführt. Zugleich befinden sich jedoch mehrere Befehle in verschiedenen Stufen. Ein einzelner Befehl benötigt deshalb mehrere Takte, aber im Idealfall wird nach dem Füllen der Pipeline in jedem Takt ein Befehl fertiggestellt. Dadurch steigt der Gesamtdurchsatz. Neben Befehlspipelines gibt es weitere Arten, beispielsweise Arithmetik-Pipelines in Gleitkommaeinheiten.

Stufen und Taktung

Eine beispielhafte vierstufige Befehlspipeline besteht aus:

• IF (Instruction Fetch): Der durch den Befehlszähler adressierte Befehl wird aus dem Arbeitsspeicher geladen; anschließend wird der Befehlszähler erhöht.
• ID (Instruction Decoding): Der Befehl wird in der ersten Takthälfte dekodiert. In der zweiten Takthälfte werden die benötigten Daten aus Arbeitsspeicher und Registersatz geladen.
• EX (Execution): Der dekodierte Befehl wird ausgeführt und das Ergebnis durch einen Pipeline-Latch zwischengespeichert.
• WB (Write Back): Das Ergebnis wird in den Arbeitsspeicher oder den Registersatz zurückgeschrieben.

Je einfacher eine Stufe aufgebaut ist, desto höher kann ihre Taktfrequenz sein. Bei modernen CPUs mit Kerntakten im Gigahertz-Bereich – 1 GHz entspricht ungefähr 1 Milliarde Takten pro Sekunde – kann eine Befehlspipeline mehr als 30 Stufen besitzen, etwa bei der Intel-NetBurst-Mikroarchitektur. In einer Pipeline mit k Stufen durchläuft ein Befehl diese in k Takten. Da pro Takt ein neuer Befehl aufgenommen wird, kann im Idealfall auch pro Takt einer die Pipeline verlassen.

Die Zykluszeit τ richtet sich nach der langsamsten Stufe. Sind τᵢ die Verzögerungen der einzelnen Stufen, τₘ ihr Maximum und d der Zusatzaufwand der Pipeline-Register, gilt:

τ = maxᵢ(τᵢ) + d = τₘ + d.

Durchsatz und theoretischer Leistungsgewinn

Für n Befehle, k Pipeline-Stufen und die Zykluszeit τ beträgt die Gesamtlaufzeit:

Tₖ = (k + n − 1) · τ.

Zu Beginn ist die Pipeline leer. Ihre Füllung benötigt k · τ. Danach wird nach jeder Stufe ein neuer Befehl aufgenommen und ein anderer fertiggestellt; für die restlichen Befehle kommen daher (n − 1) · τ hinzu.

Der Speed-up Sₖ beschreibt den Leistungsgewinn gegenüber einer Ausführung ohne Pipelining. Unter der Annahme, dass die Ausführung eines Befehls ohne Pipeline k · τ dauert, gilt:

Sₖ = [n · (k · τ)] / [(k + n − 1)τ] = (n · k) / (k + n − 1).

Wenn stets genügend Befehle zum Füllen der Pipeline vorhanden sind, nähert sich der Speed-up für n gegen unendlich der Stufenzahl k:

limₙ→∞ Sₖ = k.

Dieser Grenzwert ist nur theoretisch: Befehle lassen sich nicht in beliebig viele Stufen zerlegen, und τ kann nicht unbegrenzt verkleinert werden. Außerdem erhöhen zusätzliche Stufen den Hardwareaufwand und verschärfen die Folgen von Daten- und Steuerungskonflikten.

Abhängigkeiten, Konflikte und Sprungvorhersage

Muss ein Befehl auf das Ergebnis oder eine Ressource eines weiter vorne in der Pipeline befindlichen Befehls warten, besteht eine Abhängigkeit. Daraus können Konflikte, englisch Hazards, entstehen:

• Ressourcenkonflikte: Zwei Stufen benötigen gleichzeitig dieselbe Ressource.
• Datenkonflikte: Benötigte Daten sind noch nicht verfügbar. Auf Befehlsebene betrifft dies Daten eines Befehls, auf Transferebene noch nicht verfügbare Registerinhalte.
• Kontrollflusskonflikte: Die Pipeline muss abwarten, ob ein bedingter Sprung ausgeführt wird.

Bei einem Konflikt müssen Befehle am Pipeline-Anfang warten; dies heißt Stalling. Dabei entstehen Lücken, sogenannte Bubbles, und der Durchsatz sinkt. Zusätzliche Funktionseinheiten können Ressourcenkonflikte vermindern. Beim Forwarding werden bereits verfügbare Ergebnisse aus hinteren Stufen direkt nach vorn weitergegeben, anstatt bis zum regulären Abschluss des Befehls zu warten.

Gegen Kontrollflusskonflikte dient die Sprungvorhersage, englisch Branch Prediction. Der Prozessor rechnet spekulativ auf Grundlage eines vorhergesagten Sprungverlaufs weiter. Ist die Vorhersage falsch, müssen die inzwischen ausgeführten Befehle verworfen werden; dies heißt Pipeline-Flush. Bei langen Pipelines, etwa im Intel Pentium 4 oder IBM Power5, kostet ein Flush besonders viel Zeit. Ausgeklügelte Vorhersagetechniken sorgen laut Artikel dafür, dass die CPU bei weniger als einem Prozent der stattfindenden Sprünge den Inhalt der Befehlspipeline verwerfen muss.

Eine weitere Möglichkeit ist die verzweigungslose Programmierung, englisch Branchless Programming. Dabei werden bedingte Anweisungen möglichst durch Bitoperationen, bedingte Verschiebungen oder andere Prädikationen ersetzt. Verzweigungsfreier Code ist wegen Timing-Angriffen für die Kryptografie unverzichtbar.

Vor- und Nachteile sowie Nutzung durch Software

Lange Pipelines können die Verarbeitungsgeschwindigkeit stark erhöhen. Ihr Nachteil ist, dass sich viele Befehle gleichzeitig in Bearbeitung befinden. Bei einem Pipeline-Flush werden sie verworfen, anschließend muss die Pipeline mit Befehlen aus dem Arbeitsspeicher oder Befehlscache neu gefüllt werden. Dadurch entstehen hohe Latenzzeiten, in denen der Prozessor untätig ist. Pipelining wirkt daher umso besser, je mehr Befehle zwischen zwei Kontrollflussänderungen liegen.

Programmierer können Kontrollflusskonflikte durch geeignete Befehlsfolgen reduzieren. Besitzt eine Architektur ein Übertragsbit, das Carry-Flag, lässt sich damit unter Umständen eine boolesche Variable ohne bedingten Sprung setzen. Im angeführten 8086-Beispiel wird nach einem Vergleich das Carry-Flag mit CMC umgekehrt und anschließend durch ADC in FLUSH_FLAG eingerechnet. Dadurch entfällt die Verzweigung.

Ist bekannt, welcher Fall einer Bedingung seltener auftritt, sollte möglichst nur dieser Ausnahmefall einen Sprung auslösen. Das Beispiel zählt ein Register bis 100: Bei einer ungünstigen Anordnung wird in 99 von 100 Fällen gesprungen; durch Auslagern des Ausnahmeblocks erfolgt der bedingte Sprung nur in 1 von 100 Fällen.

Auch das Abwechseln verschiedener Prozessorressourcen kann helfen. Da Speicherzugriffe und die Nutzung der arithmetisch-logischen Einheit relativ lange dauern, sollten mehrere Speicheroperationen nach Möglichkeit nicht unmittelbar aufeinanderfolgen. Im 8086-Beispiel werden deshalb zwischen Speicherzugriffe andere Befehle wie das Laden eines Zählers und CLD eingeschoben, um die verfügbaren Ressourcen besser auszulasten.