Anweisungspipelining - Instruction pipelining

Grundlegende fünfstufige Pipeline
Taktzyklus
Instr. Nein.
1 2 3 4 5 6 7
1 WENN ICH WÜRDE EX MEM WB
2 WENN ICH WÜRDE EX MEM WB
3 WENN ICH WÜRDE EX MEM WB
4 WENN ICH WÜRDE EX MEM
5 WENN ICH WÜRDE EX
(IF = Befehlsabruf, ID = Befehlsdecodierung, EX = Ausführen, MEM = Speicherzugriff, WB = Zurückschreiben des Registers).

Im vierten Taktzyklus (grüne Spalte) befindet sich der früheste Befehl in der MEM-Stufe, und der neueste Befehl ist noch nicht in die Pipeline eingetreten.

In der Informatik ist Instruction Pipelining eine Technik zum Implementieren von Parallelität auf Instruktionsebene innerhalb eines einzelnen Prozessors. Das Pipelining versucht, jeden Teil des Prozessors mit einem Befehl zu beschäftigen, indem eingehende Befehle in eine Reihe von sequentiellen Schritten (die namensgebende " Pipeline ") unterteilt werden, die von verschiedenen Prozessoreinheiten mit verschiedenen parallel verarbeiteten Befehlsteilen ausgeführt werden.

Konzept und Motivation

In einem Pipeline-Computer fließen Anweisungen in Stufen durch die Zentraleinheit (CPU). Zum Beispiel könnte es eine Stufe für jeden Schritt des von-Neumann-Zyklus haben : Hole die Anweisung, hol die Operanden, führe die Anweisung aus, schreibe die Ergebnisse. Ein Computer mit Pipeline verfügt normalerweise nach jeder Stufe über "Pipeline-Register". Diese speichern Informationen aus dem Befehl und den Berechnungen, damit die Logikgatter der nächsten Stufe den nächsten Schritt ausführen können.

Diese Anordnung lässt die CPU in jedem Taktzyklus einen Befehl abschließen. Es ist üblich, dass geradzahlige Stufen an einer Flanke des Rechteckwellentakts arbeiten, während ungeradzahlige Stufen an der anderen Flanke arbeiten. Dies ermöglicht mehr CPU- Durchsatz als ein Multicycle-Computer bei einer gegebenen Taktrate , kann jedoch die Latenz aufgrund des zusätzlichen Overheads des Pipelining-Prozesses selbst erhöhen . Auch wenn die elektronische Logik eine feste maximale Geschwindigkeit hat, kann ein Pipeline-Computer durch Variieren der Anzahl von Stufen in der Pipeline schneller oder langsamer gemacht werden. Bei mehr Stufen verrichtet jede Stufe weniger Arbeit, sodass die Stufe weniger Verzögerungen von den Logikgattern hat und mit einer höheren Taktrate laufen könnte.

Ein Computermodell mit Pipeline ist oft am wirtschaftlichsten, wenn die Kosten als Logikgatter pro Befehl pro Sekunde gemessen werden. Zu jedem Zeitpunkt befindet sich ein Befehl nur in einer Pipeline-Stufe, und im Durchschnitt ist eine Pipeline-Stufe weniger kostspielig als ein Mehrzyklus-Computer. Außerdem wird, wenn sie gut gemacht ist, der Großteil der Logik des Pipeline-Computers die meiste Zeit verwendet. Im Gegensatz dazu haben Computer, die nicht in Ordnung sind, zu jedem gegebenen Zeitpunkt normalerweise große Mengen an Leerlauflogik. Ähnliche Berechnungen zeigen normalerweise, dass ein Pipeline-Computer weniger Energie pro Befehl verbraucht.

Ein Pipeline-Computer ist jedoch normalerweise komplexer und kostspieliger als ein vergleichbarer Multicycle-Computer. Es hat typischerweise mehr Logikgatter, Register und eine komplexere Steuereinheit. Auf ähnliche Weise könnte es mehr Gesamtenergie verbrauchen, während pro Anweisung weniger Energie verbraucht wird. CPUs, die nicht in Ordnung sind, können normalerweise mehr Befehle pro Sekunde ausführen, da sie mehrere Befehle gleichzeitig ausführen können.

In einem Pipeline-Computer sorgt die Steuereinheit dafür, dass der Fluss als Programmbefehle gestartet, fortgesetzt und gestoppt wird. Die Befehlsdaten werden normalerweise in Pipeline-Registern von einer Stufe zur nächsten weitergegeben, mit einer etwas getrennten Steuerlogik für jede Stufe. Die Steuereinheit stellt auch sicher, dass der Befehl in jeder Stufe den Betrieb von Befehlen in anderen Stufen nicht beeinträchtigt. Wenn beispielsweise zwei Stufen dasselbe Datenelement verwenden müssen, stellt die Steuerlogik sicher, dass die Verwendungen in der richtigen Reihenfolge erfolgen.

Bei effizientem Betrieb verfügt ein Pipeline-Computer in jeder Stufe über eine Anweisung. Es arbeitet dann an all diesen Anweisungen gleichzeitig. Es kann ungefähr einen Befehl für jeden Zyklus seines Taktgebers beenden. Wenn ein Programm jedoch zu einer anderen Befehlsfolge wechselt, muss die Pipeline manchmal die verarbeiteten Daten verwerfen und neu starten. Dies wird als "Stall" bezeichnet.

Ein Großteil des Designs eines Pipeline-Computers verhindert Interferenzen zwischen den Stufen und reduziert Blockierungen.

Anzahl der Schritte

Die Anzahl der abhängigen Schritte variiert mit der Maschinenarchitektur. Beispielsweise:

  • Das IBM Stretch- Projekt 1956-61 schlug die Begriffe Fetch, Decode und Execute vor, die sich durchgesetzt haben.
  • Die klassische RISC-Pipeline umfasst:
    1. Anweisung abrufen
    2. Befehlsdecodierung und Registerabruf
    3. Ausführen
    4. Speicherzugriff
    5. Registrieren zurückschreiben
  • Der Atmel AVR und der PIC-Mikrocontroller verfügen jeweils über eine zweistufige Pipeline.
  • Viele Designs beinhalten Pipelines mit einer Länge von 7, 10 und sogar 20 Stufen (wie beim Intel Pentium 4 ).
  • Die späteren "Prescott"- und "Cedar Mill" -Netburst- Kerne von Intel, die in den letzten Pentium-4-Modellen und deren Pentium D- und Xeon- Derivaten zum Einsatz kamen, haben eine lange 31-stufige Pipeline.
  • Der Xelerated X10q Netzwerkprozessor hat eine Pipeline von mehr als tausend Stufen, obwohl in diesem Fall 200 dieser Stufen unabhängige CPUs mit individuell programmierten Befehlen darstellen. Die verbleibenden Stufen werden verwendet, um Zugriffe auf Speicher und Funktionseinheiten auf dem Chip zu koordinieren.

Da die Pipeline "tiefer" gemacht wird (mit einer größeren Anzahl von abhängigen Schritten), kann ein gegebener Schritt mit einfacheren Schaltungen implementiert werden, wodurch der Prozessortakt schneller laufen kann. Solche Pipelines können Superpipelines genannt werden.

Ein Prozessor wird als vollständig Pipeline bezeichnet, wenn er in jedem Zyklus einen Befehl abrufen kann. Wenn daher einige Befehle oder Bedingungen Verzögerungen erfordern, die das Abrufen neuer Befehle verhindern, wird der Prozessor nicht vollständig in die Pipeline geleitet.

Geschichte

Wegweisende Anwendungen von Pipelining fanden sich im ILLIAC II- Projekt und im IBM Stretch- Projekt, obwohl eine einfache Version früher in der Z1 im Jahr 1939 und der Z3 im Jahr 1941 verwendet wurde.

Pipelining begann ernsthaft in den späten 1970er Jahren in Supercomputern wie Vektorprozessoren und Array-Prozessoren. Einer der frühen Supercomputer war die Cyber-Serie, die von der Control Data Corporation gebaut wurde. Sein Hauptarchitekt, Seymour Cray , leitete später Cray Research. Cray entwickelte die XMP-Reihe von Supercomputern, die Pipelining sowohl für Multiplikations- als auch für Additions-/Subtraktionsfunktionen verwendet. Später fügte Star Technologies Parallelismus (mehrere parallel arbeitende Pipeline-Funktionen) hinzu, die von Roger Chen entwickelt wurden. 1984 fügte Star Technologies die von James Bradley entwickelte Pipeline-Divider-Schaltung hinzu. Bis Mitte der 1980er Jahre wurde Pipelining von vielen verschiedenen Unternehmen auf der ganzen Welt eingesetzt.

Pipelining war nicht auf Supercomputer beschränkt. 1976 hatte der Universal-Mainframe der 470er-Serie der Amdahl Corporation eine 7-stufige Pipeline und eine patentierte Verzweigungsvorhersageschaltung.

Gefahren

Das Modell der sequentiellen Ausführung geht davon aus, dass jeder Befehl abgeschlossen ist, bevor der nächste beginnt; diese Annahme trifft auf einen Pipeline-Prozessor nicht zu. Eine Situation, in der das erwartete Ergebnis problematisch ist, wird als Gefahr bezeichnet . Stellen Sie sich die folgenden zwei Registerbefehle an einen hypothetischen Prozessor vor:

1: add 1 to R5
2: copy R5 to R6

Wenn der Prozessor die 5 Schritte hat, die in der anfänglichen Illustration aufgeführt sind (die 'Grundlegende fünfstufige Pipeline' am Anfang des Artikels), würde die Anweisung 1 zum Zeitpunkt t 1 abgerufen und seine Ausführung wäre zum Zeitpunkt t 5 abgeschlossen . Anweisung 2 würde bei t 2 abgerufen und wäre bei t 6 abgeschlossen . Der erste Befehl könnte die inkrementierte Zahl als fünfter Schritt (Registerrückschreiben) bei t 5 in R5 ablegen . Aber der zweite Befehl könnte in seinem zweiten Schritt (Befehlsdecodierung und Registerabruf) zum Zeitpunkt t 3 die Zahl von R5 erhalten (um nach R6 zu kopieren) . Es scheint, dass die erste Anweisung den Wert bis dahin nicht erhöht hätte. Der obige Code ruft eine Gefahr hervor.

Das Schreiben von Computerprogrammen in einer kompilierten Sprache wirft diese Bedenken möglicherweise nicht auf, da der Compiler so ausgelegt sein könnte, dass er Maschinencode erzeugt, der Gefahren vermeidet.

Problemumgehungen

Bei einigen frühen DSP- und RISC-Prozessoren rät die Dokumentation Programmierern, solche Abhängigkeiten in benachbarten und fast benachbarten Befehlen (sogenannte Verzögerungsschlitze ) zu vermeiden , oder erklärt, dass der zweite Befehl einen alten Wert anstelle des gewünschten Wertes verwendet (im obigen Beispiel die Prozessor könnte den nicht inkrementierten Wert widersinnig kopieren) oder erklärt, dass der von ihm verwendete Wert nicht definiert ist. Der Programmierer hat möglicherweise unabhängige Arbeiten, die der Prozessor in der Zwischenzeit erledigen kann; oder um korrekte Ergebnisse zu gewährleisten, kann der Programmierer NOPs in den Code einfügen, wodurch die Vorteile des Pipelining teilweise zunichte gemacht werden.

Lösungen

Pipeline-Prozessoren verwenden im Allgemeinen drei Techniken, um wie erwartet zu funktionieren, wenn der Programmierer davon ausgeht, dass jeder Befehl abgeschlossen ist, bevor der nächste beginnt:

  • Die Pipeline könnte anhalten oder aufhören, neue Befehle zu planen, bis die erforderlichen Werte verfügbar sind. Dies führt zu leeren Schlitzen in der Pipeline oder Blasen , in denen keine Arbeit verrichtet wird.
  • Ein zusätzlicher Datenpfad kann hinzugefügt werden, der einen berechneten Wert an einen zukünftigen Befehl an anderer Stelle in der Pipeline weiterleitet, bevor der Befehl, der ihn erzeugt hat, vollständig zurückgezogen wurde, ein Vorgang, der als Operandenweiterleitung bezeichnet wird .
  • Der Prozessor kann andere Befehle lokalisieren, die nicht von den aktuellen abhängig sind und die sofort ohne Gefahren ausgeführt werden können, eine Optimierung, die als Out-of-order-Execution bekannt ist .

Geäst

Eine Verzweigung aus der normalen Befehlsfolge birgt oft eine Gefahr. Sofern der Prozessor die Verzweigung nicht in einem einzigen Zeitzyklus bewirken kann, fährt die Pipeline damit fort, Befehle sequentiell abzurufen. Solche Anweisungen können nicht wirksam werden, weil der Programmierer die Kontrolle auf einen anderen Teil des Programms umgeleitet hat.

Noch problematischer ist eine bedingte Verzweigung. Der Prozessor kann verzweigen oder nicht, abhängig von einer Berechnung, die noch nicht stattgefunden hat. Verschiedene Prozessoren können ins Stocken geraten, können eine Verzweigungsvorhersage versuchen und können in der Lage sein, mit der Ausführung von zwei verschiedenen Programmsequenzen ( Eager-Ausführung ) zu beginnen, wobei jede davon ausgeht, dass die Verzweigung ausgeführt wird oder nicht, wobei alle Arbeiten verworfen werden, die sich auf die falsche Schätzung beziehen.

Ein Prozessor mit einer Implementierung einer Verzweigungsvorhersage, die normalerweise korrekte Vorhersagen macht, kann die Leistungseinbußen durch Verzweigungen minimieren. Wenn Verzweigungen jedoch schlecht vorhergesagt werden, kann dies zu mehr Arbeit für den Prozessor führen, z. B. das Leeren des falschen Codepfads, der mit der Ausführung begonnen hat, aus der Pipeline , bevor die Ausführung an der richtigen Stelle wieder aufgenommen wird.

Programme, die für einen Pipeline-Prozessor geschrieben wurden, vermeiden bewusst Verzweigungen, um mögliche Geschwindigkeitsverluste zu minimieren. Beispielsweise kann der Programmierer den üblichen Fall mit sequentieller Ausführung behandeln und nur beim Erkennen ungewöhnlicher Fälle verzweigen. Durch die Verwendung von Programmen wie gcov zur Analyse der Codeabdeckung kann der Programmierer messen, wie oft bestimmte Verzweigungen tatsächlich ausgeführt werden, und Erkenntnisse gewinnen, mit denen der Code optimiert werden kann. In einigen Fällen kann ein Programmierer mit verzweigungsfreiem Code sowohl den üblichen als auch den ungewöhnlichen Fall behandeln .

Besondere Situationen

Selbstmodifizierende Programme
Die Technik des selbstmodifizierenden Codes kann bei einem Pipeline-Prozessor problematisch sein. Bei dieser Technik besteht einer der Effekte eines Programms darin, seine eigenen bevorstehenden Befehle zu modifizieren. Wenn der Prozessor über einen Befehls-Cache verfügt , wurde der ursprüngliche Befehl möglicherweise bereits in eine Vorabruf-Eingangswarteschlange kopiert und die Änderung wird nicht wirksam. Einige Prozessoren wie der Zilog Z280 können ihre On-Chip-Cache-Speicher nur für Datenabrufe oder als Teil ihres gewöhnlichen Speicheradressraums konfigurieren und solche Schwierigkeiten mit selbstmodifizierenden Befehlen vermeiden.
Unterbrechungsfreie Anweisungen
Eine Anweisung kann unterbrechungsfrei sein, um ihre Atomarität sicherzustellen , beispielsweise wenn sie zwei Elemente austauscht. Ein sequentieller Prozessor erlaubt Interrupts zwischen Befehlen, aber ein Pipelining-Prozessor überlappt Befehle, so dass das Ausführen eines unterbrechungsfreien Befehls auch Teile gewöhnlicher Befehle ununterbrechbar macht. Der Cyrix-Koma-Bug würde ein Single-Core-System mit einer Endlosschleife hängen lassen, in der immer eine unterbrechungsfreie Anweisung in der Pipeline war.

Überlegungen zum Entwurf

Geschwindigkeit
Pipelining hält alle Teile des Prozessors besetzt und erhöht die Menge an nützlicher Arbeit, die der Prozessor in einer bestimmten Zeit erledigen kann. Pipelining reduziert typischerweise die Zykluszeit des Prozessors und erhöht den Durchsatz von Befehlen. Der Geschwindigkeitsvorteil wird in dem Maße verringert, in dem die Ausführung auf Gefahren trifft , die erfordern, dass die Ausführung unter ihre ideale Geschwindigkeit verlangsamt wird. Ein Prozessor ohne Pipeline führt jeweils nur einen einzigen Befehl aus. Der Beginn der nächsten Anweisung wird nicht gefahrenbedingt, sondern unbedingt verzögert.
Die Notwendigkeit eines Pipeline-Prozessors, seine gesamte Arbeit in modulare Schritte zu organisieren, kann die Duplizierung von Registern erfordern, was die Latenz einiger Befehle erhöht.
Wirtschaft
Indem jeder abhängige Schritt einfacher gemacht wird, kann Pipelining komplexe Operationen wirtschaftlicher ermöglichen als das Hinzufügen komplexer Schaltungen, beispielsweise für numerische Berechnungen. Ein Prozessor, der beim Pipelining keine höhere Geschwindigkeit anstrebt, kann jedoch einfacher und billiger herzustellen sein.
Vorhersagbarkeit
Im Vergleich zu Umgebungen, in denen der Programmierer Gefahren vermeiden oder umgehen muss, kann die Verwendung eines Prozessors ohne Pipeline die Programmierung und Ausbildung von Programmierern erleichtern. Der Prozessor ohne Pipeline macht es auch einfacher, den genauen Zeitpunkt einer gegebenen Befehlsfolge vorherzusagen.

Illustriertes Beispiel

Rechts befindet sich eine generische Pipeline mit vier Stufen: Abrufen, Decodieren, Ausführen und Zurückschreiben. Das obere graue Kästchen ist die Liste der Befehle, die auf ihre Ausführung warten, das untere graue Kästchen ist die Liste der Befehle, deren Ausführung abgeschlossen ist, und das mittlere weiße Kästchen ist die Pipeline.

Die Ausführung ist wie folgt:

Generische 4-Stufen-Pipeline; die farbigen Kästchen stellen voneinander unabhängige Anweisungen dar
Uhr Ausführung
0
  • Vier Anweisungen warten darauf, ausgeführt zu werden
1
  • Der grüne Befehl wird aus dem Speicher geholt
2
  • Die grüne Anweisung ist dekodiert
  • Die violette Anweisung wird aus dem Speicher geholt
3
  • Der grüne Befehl wird ausgeführt (der eigentliche Vorgang wird ausgeführt)
  • Die violette Anweisung ist entschlüsselt
  • Die blaue Anweisung wird geholt
4
  • Die Ergebnisse des grünen Befehls werden in die Registerdatei oder den Speicher zurückgeschrieben
  • Die violette Anweisung wird ausgeführt
  • Die blaue Anweisung ist dekodiert
  • Die rote Anweisung wird geholt
5
  • Die Ausführung der grünen Anweisung ist abgeschlossen
  • Die lila Anweisung wird zurückgeschrieben
  • Die blaue Anweisung wird ausgeführt
  • Die rote Anweisung ist dekodiert
6
  • Die Ausführung der lila Anweisung ist abgeschlossen
  • Die blaue Anweisung wird zurückgeschrieben
  • Die rote Anweisung wird ausgeführt
7
  • Die Ausführung der blauen Anweisung ist abgeschlossen
  • Die rote Anweisung wird zurückgeschrieben
8
  • Die Ausführung der roten Anweisung ist abgeschlossen
9
  • Die Ausführung aller vier Anweisungen ist abgeschlossen

Pipeline-Blase

Eine Blase in Zyklus 3 verzögert die Ausführung.

Ein Pipeline-Prozessor kann mit Gefahren umgehen, indem er anhält und eine Blase in der Pipeline erzeugt, was zu einem oder mehreren Zyklen führt, in denen nichts Nützliches passiert.

In der Abbildung rechts kann der Prozessor in Zyklus 3 die violette Anweisung nicht decodieren, vielleicht weil der Prozessor feststellt, dass die Decodierung von Ergebnissen abhängt, die durch die Ausführung der grünen Anweisung erzeugt werden. Die grüne Anweisung kann wie geplant zur Execute-Phase und dann zur Write-back-Phase übergehen, aber die violette Anweisung wird für einen Zyklus in der Fetch-Phase angehalten. Der blaue Befehl, der während Zyklus 3 abgeholt werden sollte, wird für einen Zyklus angehalten, ebenso wie der rote Befehl danach.

Wegen der Blase (die blauen Ovale in der Abbildung) ist die Decodierungsschaltung des Prozessors während Zyklus 3 im Leerlauf. Seine Ausführungsschaltung ist während Zyklus 4 im Leerlauf und seine Rückschreibeschaltung ist während Zyklus 5 im Leerlauf.

Wenn die Blase die Pipeline verlässt (bei Zyklus 6), wird die normale Ausführung wieder aufgenommen. Aber jetzt ist alles einen Zyklus zu spät. Es dauert 8 Zyklen (Zyklus 1 bis 8) statt 7 um die vier farbig dargestellten Anweisungen vollständig auszuführen.

Siehe auch

Anmerkungen

Verweise

Externe Links