Pipeline (Prozessor)

Die Pipeline (auch Befehls-Pipeline oder Prozessor-Pipeline) bezeichnet bei Mikroprozessoren eine Art „Fließband“, mit dem die Abarbeitung der Maschinenbefehle in Teilaufgaben zerlegt wird, die für mehrere Befehle parallel durchgeführt werden. Dieses Prinzip, oft auch kurz Pipelining genannt, stellt eine weit verbreitete Mikroarchitektur heutiger Prozessoren dar.

Statt eines gesamten Befehls wird während eines Taktzyklus des Prozessors nur jeweils eine Teilaufgabe abgearbeitet, allerdings werden die verschiedenen Teilaufgaben mehrerer Befehle dabei gleichzeitig bearbeitet. Da diese Teilaufgaben einfacher (und somit schneller) sind als die Abarbeitung des gesamten Befehls am Stück, kann durch Pipelining die Effizienz der Taktfrequenz des Mikroprozessors gesteigert werden. Insgesamt benötigt ein einzelner Befehl nun mehrere Takte zur Ausführung, da aber durch die quasi parallele Bearbeitung mehrerer Befehle in jedem Zyklus ein Befehl „fertiggestellt“ wird, wird der Gesamtdurchsatz durch dieses Verfahren erhöht.

Die einzelnen Teilaufgaben einer Pipeline nennt man Pipeline-Stufen, Pipeline-Stages oder auch Pipeline-Segmente. Diese Stufen werden durch getaktete Pipeline-Register getrennt. Neben einer Befehls-Pipeline kommen in modernen Systemen verschiedene weitere Pipelines zum Einsatz, beispielsweise eine Arithmetik-Pipeline in der Gleitkommaeinheit.

Beispiel

Beispiel einer vierstufigen Befehlspipeline:

A – Befehlscode laden (IF, Instruction Fetch)

In der Befehlsbereitstellungsphase wird der Befehl, der durch den Befehlszähler adressiert ist, aus dem Arbeitsspeicher geladen. Der Befehlszähler wird anschließend hochgezählt.

B – Instruktion dekodieren und Laden der Daten (ID, Instruction Decoding)

In der Dekodier- und Ladephase wird der geladene Befehl dekodiert (1. Takthälfte) und die notwendigen Daten aus dem Arbeitsspeicher und dem Registersatz geladen (2. Takthälfte).

C – Befehl ausführen (EX, Execution)

In der Ausführungsphase wird der dekodierte Befehl ausgeführt. Das Ergebnis wird durch den Pipeline-latch gepuffert.

D – Ergebnisse zurückgeben (WB, Write Back)

In der Resultatspeicherphase wird das Ergebnis in den Arbeitsspeicher oder in den Registersatz zurückgeschrieben.

Taktung

Je einfacher eine einzelne Stufe aufgebaut ist, desto höher ist die Frequenz, mit der sie betrieben werden kann. In einer modernen CPU mit einem Kerntakt im Gigahertz-Bereich (1 GHz ≈ 1 Milliarde Takte pro Sekunde) kann die Befehlspipeline über 30 Stufen lang sein (vgl. Intel-NetBurst-Mikroarchitektur). Der Kerntakt ist die Zeit, die ein Befehl braucht, um eine Stufe der Pipeline zu durchwandern. In einer k-stufigen Pipeline wird ein Befehl also in k Takten von k Stufen bearbeitet. Da in jedem Takt ein neuer Befehl geladen wird, verlässt im Idealfall auch ein Befehl pro Takt die Pipeline.

Der Takt wird durch die Zykluszeit der Pipeline bestimmt und berechnet sich aus dem Maximum $\tau _{m}$ aller Stufenverzögerungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau_i} und einem Zusatzaufwand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} , welcher durch die Zwischenspeicherung der Ergebnisse in Pipeline-Registern verursacht wird.

Zykluszeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau = \underset{i}{\max} (\tau_i) + d = \tau_m + d}

Leistungssteigerung

Durch das Pipelining wird der Gesamtdurchsatz gegenüber Befehlsabarbeitung ohne Pipelining erhöht. Die Gesamtzeit für die Pipeline-Verarbeitung mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Stufen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Befehlen bei einer Zykluszeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau} ergibt sich aus:

Gesamtlaufzeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_k = (k+n-1) \cdot \tau}

Anfangs ist die Pipeline leer und wird in Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle k\cdot \tau } Schritten gefüllt. Nach jeder Stufe wird ein neuer Befehl in die Pipeline geladen, und ein anderer Befehl wird fertiggestellt. Die restlichen Befehle werden daher in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n-1) \cdot \tau} Schritten fertiggestellt.

Bildet man nun den Quotienten aus der Gesamtlaufzeit für Befehlsabarbeitung mit und ohne Pipelining, so erhält man den Speedup. Dieser repräsentiert den Leistungsgewinn, der durch das Pipelining-Verfahren erreicht wird:

Speed-Up: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_k = \frac{n \cdot (k \cdot \tau)}{(k+n-1) \tau} = \frac{n \cdot k}{k+n-1}}

Geht man davon aus, dass immer genügend Befehle vorhanden sind, welche die Pipeline füllen und dass die Zykluszeit ohne Pipeline um den Faktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} länger ist, dann ergibt sich der Grenzwert des Speed-Ups für n gegen unendlich:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lim_{n \to \infty}S_k =\lim_{n \to \infty} \frac{n \cdot k}{k+n-1} = k}

Das bedeutet, dass mit zunehmender Stufenanzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} die Leistung beliebig gesteigert werden kann. Jedoch lässt sich die Befehlsabarbeitung nicht in beliebig viele Stufen unterteilen, und die Zykluszeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau} kann auch nicht beliebig kleiner werden. Eine Steigerung der Stufenanzahl hat ebenfalls schwerere Auswirkungen beim Auftreten von Daten- oder Steuerungskonflikten zur Folge. Ebenfalls steigt der Aufwand der Hardware mit steigender Stufenanzahl $k$.

Konflikte

→ Hauptartikel: Pipeline-Hazard

Ist es für die Bearbeitung eines Befehls in einer Stufe der Pipeline notwendig, dass ein Befehl, der sich weiter vorne in der Pipeline befindet, zuerst abgearbeitet wird, so spricht man von Abhängigkeiten. Diese können zu Konflikten (engl. Hazards) führen. Es können drei Konfliktarten auftreten:

• Ressourcenkonflikte, wenn eine Stufe der Pipeline Zugriff auf eine Ressource benötigt, die bereits von einer anderen Stufe belegt ist
• Datenkonflikte
  • auf Befehlsebene: Daten, die in einem Befehl benutzt werden, stehen nicht zur Verfügung
  • auf Transferebene: Registerinhalte, die in einem Schritt benutzt werden, stehen nicht zur Verfügung
• Kontrollflusskonflikte, wenn die Pipeline abwarten muss, ob ein bedingter Sprung ausgeführt wird oder nicht

Diese Konflikte erfordern es, dass entsprechende Befehle am Anfang der Pipeline warten („stallen“), was „Lücken“ (auch „Bubbles“) in der Pipeline erzeugt. Dies führt dazu, dass die Pipeline nicht optimal ausgelastet ist und der Durchsatz sinkt. Daher ist man bemüht, diese Konflikte so weit wie möglich zu vermeiden:

Ressourcenkonflikte lassen sich durch Hinzufügen zusätzlicher Funktionseinheiten lösen. Viele Datenkonflikte lassen sich durch Forwarding lösen, wobei Ergebnisse aus weiter hinten liegenden Pipeline-Stufen nach vorn transportiert werden, sobald diese verfügbar sind (und nicht erst am Ende der Pipeline).

Die Anzahl an Kontrollflusskonflikten lässt sich durch eine Sprungvorhersage (engl. branch prediction) reduzieren. Hierbei wird spekulativ weitergerechnet, bis feststeht, ob sich die Vorhersage als richtig erwiesen hat. Im Falle einer falschen Sprungvorhersage müssen in der Zwischenzeit ausgeführte Befehle verworfen werden (pipeline flush), was besonders bei Architekturen mit langer Pipeline (wie etwa bei Intel Pentium 4 oder IBM Power5) viel Zeit kostet. Deshalb besitzen diese Architekturen sehr ausgeklügelte Techniken zur Sprungvorhersage, so dass die CPU nur in weniger als einem Prozent der stattfindenden Sprünge den Inhalt der Befehlspipeline verwerfen muss.

Vorteile und Nachteile

Der Vorteil langer Pipelines besteht in der starken Steigerung der Verarbeitungsgeschwindigkeit.

Der Nachteil besteht gerade darin, dass sich sehr viele Befehle gleichzeitig in Bearbeitung befinden. Im Falle eines Pipeline-Flushes müssen alle Befehle in der Pipeline verworfen und die Pipeline anschließend neu gefüllt werden. Dies bedarf des Nachladens von Befehlen aus dem Arbeitsspeicher oder dem Befehlscache der CPU, so dass sich hohe Latenzzeiten ergeben, in denen der Prozessor untätig ist. Anders formuliert ist der Gewinn durch Pipelining umso größer, je höher die Anzahl der Befehle zwischen Kontrollflussänderungen ist, da die Pipeline dann erst nach längerer Benutzung unter Volllast wieder geflusht werden muss.

Ausnutzung durch Software

Das Wissen über das Vorhandensein der Pipelines kann vom Programmierer geschickt genutzt werden, um den Prozessor optimal auszulasten. Insbesondere die Kontrollflusskonflikte lassen sich vermeiden.

Einsatz von Flags anstatt konditionaler Sprünge

Wenn auf einer Architektur ein Übertragsbit (Carry-Flag) vorhanden ist und Befehle, die es in Rechenbefehle einfließen lassen, so kann man es nutzen, um Boolesche Variablen zu setzen, ohne zu verzweigen.

Beispiel (8086 in Intel-Syntax, d. h. in der Form command destination,source ):
weniger effizient:

 ...
 mov FLUSH_FLAG,0     ; FLUSH_FLAG = false
 mov ax,CACHE_POINTER
 cmp ax,CACHE_ENDE
 jb MARKE; jump on below (<0), Verzweigung
 mov FLUSH_FLAG,1     ; FLUSH_FLAG = true
 MARKE:
 ...

effizienter:

 ...
 mov FLUSH_FLAG,0
 mov ax,CACHE_POINTER
 cmp ax,CACHE_ENDE
 cmc; complement carry flag
 adc FLUSH_FLAG,0     ; FLUSH_FLAG = FLUSH_FLAG + 0 + carry flag, keine Verzweigung
 ...

Springen im selteneren Fall

Wenn bei einer Verzweigung bekannt ist, welcher Fall wahrscheinlicher ist, so sollte im unwahrscheinlicheren Fall verzweigt werden. Wenn z. B. ein Block nur in seltenen Fällen ausgeführt wird, so sollte er bei Nichtausführung nicht übersprungen werden (wie es in der strukturierten Programmierung gemacht würde), sondern ganz woanders stehen, per konditionalem Sprung angesprungen werden und per unkonditionalem Sprung zurückkehren, sodass im Normalfall nicht verzweigt wird.

Beispiel (8086):
viele Verzweigungen:

 ...
 PROZEDUR:
 ...
 inc cx
 cmp cx,100
 jb MARKE; Verzweigung im Normalfall (99 von 100)
 xor cx,cx
 MARKE:
 ...

wenige Verzweigungen:

 MARKEA:
 xor cx,cx
 jmp MARKEB
 PROZEDUR:
 ...
 inc cx
 cmp cx,100
 jnb MARKEA; Verzweigung nur im Ausnahmefall (1 von 100)
 MARKEB:
 ...

Abwechseln von verschiedenen Ressourcen

Da Speicherzugriffe sowie der Einsatz der Arithmetisch-logischen Einheit relativ lange brauchen, kann es helfen, verschiedene Ressourcen möglichst abwechselnd zu benutzen.

Beispiel (8086):
weniger effizient:

 ...
 div CS:DIVISOR; Speicherzugriffe
 mov DS:REST,dx; nahe hintereinander
 mov ES:QUOTIENT,ax;
 mov cx,40h
 cld
 MARKE:
 ...
 loop MARKE
 ...

effizienter:

 ...
 div CS:DIVISOR;Speicherzugriffe
 mov cx,40h
 mov DS:REST,dx; mit anderen
 cld
 mov ES:QUOTIENT,ax; Befehlen durchsetzt
 MARKE:
 ...
 loop MARKE
 ...

Siehe auch

• DLX-Pipeline
• Hardwareseitiges Multithreading
• Hyper-Threading
• Superskalarität

Literatur

• Andrew S. Tanenbaum: Computerarchitektur: Strukturen – Konzepte – Grundlagen. 5. Auflage. Pearson Studium, München 2006, ISBN 3-8273-7151-1, insb. Kapitel 2.1.5. 

Weblinks

• Artikel über Pipelining; (Teil 1) (Teil 2) arstechnica.com (englisch)
• Ausarbeitung zu Grundlagen der Rechnerarchitektur, insbesondere (Kapitel 6 - Pipelining).