Mit Google fortfahren
Pipelining: Durchsatz, Hazards und Speedup
Beim Pipelining bearbeitet eine CPU mehrere Maschinenbefehle überlappend: Jeder Befehl durchläuft mehrere Stufen, während andere Befehle bereits in früheren oder späteren Stufen stecken. Dadurch steigt vor allem der Durchsatz. Ein einzelner Befehl wird nicht automatisch schneller.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Wie arbeitet eine Befehlspipeline?
Stell dir eine Autowaschanlage mit den Stationen Waschen, Spülen und Trocknen vor. Sobald das erste Auto zur zweiten Station fährt, kann das nächste Auto gewaschen werden. Mehrere Autos werden gleichzeitig bearbeitet, aber jedes befindet sich an einer anderen Station.
Eine CPU nutzt dasselbe Grundprinzip für Maschinenbefehle.
Pipeline
Eine Pipeline zerlegt die Befehlsverarbeitung in aufeinanderfolgende Stufen. Verschiedene Stufen bearbeiten gleichzeitig verschiedene Befehle.
Ein häufig verwendetes Modell besitzt fünf Stufen:
- IF – Instruction Fetch: Befehl holen.
- ID – Instruction Decode: Befehl dekodieren und Register lesen.
- EX – Execute: Operation ausführen oder Adresse berechnen.
- MEM – Memory Access: Auf den Speicher zugreifen.
- WB – Write Back: Ergebnis zurückschreiben.
Die genaue Aufteilung hängt vom Befehlssatz und von der Hardware ab. Es gibt daher auch Pipelines mit mehr, weniger oder anders zugeschnittenen Stufen.
Bei fünf Stufen sieht die Belegung nach dem Anlaufen beispielsweise so aus:
| Takt | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | Befehl 1 | – | – | – | – |
| 2 | Befehl 2 | Befehl 1 | – | – | – |
| 3 | Befehl 3 | Befehl 2 | Befehl 1 | – | – |
| 4 | Befehl 4 | Befehl 3 | Befehl 2 | Befehl 1 | – |
| 5 | Befehl 5 | Befehl 4 | Befehl 3 | Befehl 2 | Befehl 1 |
Nach dem Füllen der idealen Pipeline wird in jedem weiteren Takt ein Befehl fertig.
Warum steigt der Durchsatz, aber nicht unbedingt die Geschwindigkeit eines Befehls?
Durchsatz
Der Durchsatz gibt an, wie viele Befehle in einer bestimmten Zeit fertig werden.
Latenz
Die Latenz ist die Zeit vom Beginn bis zum Abschluss eines einzelnen Befehls.
Ein Befehl muss weiterhin alle Pipeline-Stufen durchlaufen. Bei fünf Stufen von je einem Takt beträgt seine ideale Latenz fünf Takte. Der Vorteil zeigt sich bei einer Folge vieler Befehle: Nach der Füllphase kann idealerweise in jedem Takt ein Ergebnis erscheinen.
Eine ungepipelinte Verarbeitung benötigt für jeden Befehl fünf Takte. Vier Befehle brauchen nacheinander daher $4\cdot5=20$ Takte.
Eine ideale Pipeline mit fünf Stufen benötigt fünf Takte für den ersten Befehl. Die übrigen drei Befehle werden jeweils einen Takt später fertig. Insgesamt sind es $5+3=8$ Takte.
Der einzelne Befehl benötigt weiterhin fünf Takte. Die gesamte Befehlsfolge ist jedoch deutlich früher abgeschlossen.
Pipelining verkürzt vor allem den zeitlichen Abstand zwischen fertigen Befehlen. Es verkürzt nicht automatisch den Weg eines einzelnen Befehls durch alle Stufen.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Die Zeit eines einzelnen Befehls heißt . Die Zahl fertiggestellter Befehle pro Zeit beschreibt den . Nach dem Füllen kann eine ideale Pipeline in jedem einen Befehl abschließen.
Wie berechnest du den idealen Speedup?
Für das Idealmodell gelten folgende Annahmen:
- Die Pipeline besitzt $k$ gleich lange Stufen.
- Ein ungepipelinter Befehl benötigt insgesamt die Zeit $t$.
- Eine Pipeline-Stufe benötigt daher $t/k$.
- Es werden $n$ Befehle ohne Konflikte verarbeitet.
Der erste Befehl benötigt alle $k$ Stufen und damit weiterhin die Zeit $t$. Jeder weitere Befehl wird im Abstand von $t/k$ fertig. Deshalb gilt:
$$T_{\text{Pipeline}}=t+(n-1)\frac{t}{k}=\frac{(k+n-1)t}{k}$$
Ohne Pipeline beträgt die Laufzeit:
$$T_{\text{ohne}}=nt$$
Der Speedup vergleicht beide Laufzeiten:
$$S(n,k)=\frac{T_{\text{ohne}}}{T_{\text{Pipeline}}}=\frac{nk}{k+n-1}$$
Für sehr viele Befehle nähert sich der ideale Speedup der Stufenzahl $k$. Er erreicht diesen Grenzwert bei einer endlichen Befehlsfolge jedoch nicht vollständig.
Eine Pipeline besitzt $k=5$ Stufen. Ihre Zykluszeit beträgt $\tau=2\,\text{ns}$. Es sollen $n=8$ Befehle verarbeitet werden.
Die Pipeline benötigt:
$$T_{\text{Pipeline}}=(k+n-1)\tau=(5+8-1)\cdot2\,\text{ns}=24\,\text{ns}$$
Ohne Pipeline braucht jeder Befehl $k\tau=10\,\text{ns}$. Für acht Befehle gilt:
$$T_{\text{ohne}}=8\cdot10\,\text{ns}=80\,\text{ns}$$
Damit beträgt der ideale Speedup:
$$S=\frac{80}{24}=\frac{10}{3}\approx3{,}33$$
Das Ergebnis liegt plausibel unter dem theoretischen Grenzwert $k=5$.
Die Stufen sind in realen Prozessoren nicht vollkommen gleich lang. Mit den Stufenverzögerungen $\tau_i$ und dem Zusatzaufwand $d$ der Pipeline-Register wird die Zykluszeit durch die langsamste Stufe bestimmt:
$$\tau=\max_i(\tau_i)+d$$
Mehr Stufen bedeuten deshalb nicht automatisch mehr Leistung: Pipeline-Register erzeugen Aufwand, und Konflikte können zusätzliche Wartezeiten verursachen.
Welche Hazards bremsen die Pipeline?
Ein Hazard ist eine Situation, in der ein Befehl nicht wie geplant in die nächste Stufe wechseln kann. Die Pipeline muss warten oder bereits begonnene Arbeit verwerfen.
Ressourcenkonflikt
Ein Ressourcenkonflikt oder struktureller Hazard entsteht, wenn mehrere Stufen gleichzeitig dieselbe Hardware benötigen. Das kann etwa bei einem gemeinsam genutzten Speicherzugang geschehen.
Datenkonflikt
Ein Datenkonflikt entsteht, wenn ein Befehl ein Ergebnis benötigt, das ein früherer Befehl noch nicht bereitgestellt hat.
Die Folge LOAD R0, 5, R1 und danach ADD R1, R2, R3 enthält eine Datenabhängigkeit. LOAD muss den Speicherwert erst nach R1 laden. Greift ADD vorher auf R1 zu, verwendet es einen alten Wert.
Kontrollkonflikt
Ein Kontrollkonflikt entsteht bei einem Sprung, solange die CPU noch nicht weiß, welcher Befehl als Nächstes ausgeführt werden soll. Lädt sie Befehle vom falschen Pfad, muss sie diese später verwerfen.
Eine Warteposition heißt Stall. Dadurch entsteht eine ungenutzte Stelle, die auch Bubble genannt wird. Beide senken den realen Durchsatz.
Wie lassen sich Hazards entschärfen?
Gegenmaßnahmen können Wartezeiten verringern, aber nicht jede Abhängigkeit beseitigen.
Anhalten und NOP
Die CPU kann die Pipeline anhalten, bis die benötigten Daten bereitstehen. Eine eingefügte NOP-Operation führt keine fachliche Berechnung aus, schafft aber den nötigen zeitlichen Abstand. Das ist korrekt, senkt jedoch den Durchsatz.
Forwarding
Beim Forwarding wird ein berechnetes Ergebnis direkt an eine frühere Pipeline-Stufe weitergeleitet, ohne erst den gewöhnlichen Rückschreib- und Leseweg abzuwarten. Je nachdem, wann das Ergebnis verfügbar wird, verkürzt oder vermeidet dies einen Stall.
Unabhängige Befehle umordnen
Compiler oder Prozessor können unabhängige Befehle in eine Wartezeit vorziehen. Aus
LOAD R0, 5, R1ADD R1, R2, R3SUB R4, R5, R6
kann beispielsweise
LOAD R0, 5, R1SUB R4, R5, R6ADD R1, R2, R3
werden. Das ist nur erlaubt, wenn Abhängigkeiten und Programmbedeutung erhalten bleiben.
Sprünge vorhersagen
Bei der Branch Prediction schätzt die CPU den Ausgang eines Sprungs und führt den vermuteten Pfad spekulativ aus. Ist die Vorhersage richtig, spart sie Wartezeit. Ist sie falsch, werden die spekulativ begonnenen Befehle verworfen. Dieses Leeren heißt Pipeline-Flush.
Lange Pipelines verlieren bei einem Flush meist mehr bereits begonnene Arbeit als kurze. Spekulative und dynamische Ausführung benötigen außerdem zusätzliche Hardware und Energie und können Sicherheitsrisiken begünstigen.
Pipelining, superskalare Ausführung und Out-of-Order-Ausführung sind nicht dasselbe. Pipelining überlappt die Stufen verschiedener Befehle. Ein superskalarer Prozessor besitzt mehrere Ausführungsmöglichkeiten für parallele Befehle. Bei Out-of-Order-Ausführung zieht er unabhängige Befehle vor; ihre Ergebnisse müssen anschließend wieder in der vorgesehenen Programmreihenfolge sichtbar werden.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Pipelining
- Prinzip
- Befehle in Stufen zerlegen
- verschiedene Befehle überlappen
- Leistungswirkung
- höherer Durchsatz
- einzelne Latenz nicht automatisch kleiner
- idealer Speedup nähert sich der Stufenzahl
- Hazards
- Ressourcenkonflikt
- Datenkonflikt
- Kontrollkonflikt
- Gegenmaßnahmen
- Stall oder NOP
- Forwarding
- sichere Umordnung
- Sprungvorhersage und spekulative Ausführung
- Grenzen
- langsamste Stufe und Registeraufwand
- Flush-Kosten
- Hardware-, Energie- und Sicherheitsaufwand
- Prinzip
Abschluss-Check
Du beherrschst das Grundprinzip, wenn du bei einer Befehlsfolge zuerst die Überlappung erklärst, dann mögliche Hazards suchst und den berechneten Idealwert anschließend als obere Leistungsgrenze einordnest.