Pipelining

Definition

• Pipelining

  Pipelining auf einer Maschine liegt dann vor, wenn die Bearbeitung eines Objektes in Teilschritte zerlegt und diese in einer sequentiellen Folge (Phasen der Pipeline) ausgeführt werden. Die Phasen der Pipeline können für verschiedene Objekte überlappt abgearbeitet werden. (Bode 95)

  

• Befehlspipelining (Instruction Pipelining)

  Zerlegung der Ausführung einer Maschinenoperation in Teilphasen, die dann von hintereinander geschalteten Verarbeitungseinheiten taktsynchron bearbeitet werden, wobei jede Einheit genau eine spezielle Teiloperation ausführt.

• Pipeline: Gesamtheit der Verarbeitungseinheiten

• Pipeline-Stufe: Stufen der Pipeline, die jeweils durch Pipeline-Register getrennt sind

RISC (Reduced Instruction Set Computers)

• Charakterisierung

  • Einfache Maschinenbefehle

    • Einheitliches und festes Befehlsformat

  • Load/Store Architektur

    • Befehle arbeiten auf Registeroperanden

    • Lade- und Speicherbefehle greifen auf Speicher zu

  • Einzyklus-Maschinenbefehle

    • Effizientes Pipelining des Maschinenbefehlszyklus
    • Einheitliches Zeitverhalten der Maschinenbefehle, wovon nur Lade- und Speicherbefehle sowie die Verzweigungsbefehle abweichen

  • Optimierende Compiler

    • Reduzierung der Befehle im Programm

• Pipelining des Maschinenbefehlszyklus

  
  • IF: Instruction Fetch
  • ID: Instruction Decode
  • EX: EXecution
  • MA: Memory Access
  • WB: Write Back

  Tutorials:

  • DLX/MIPS Tutorial
  • http://www.edsko.net/2005/05/19/dlx-mips-tutorial/

• Leistungsaspekte

  • Ausführungszeit eines Befehls

    • Zeit, die zum Durchlaufen der Pipeline benötigt wird
    • Ausführung ein es Befehls in $k$ Taktzyklen (ideale Verhältnisse)
    • Gleichzeitige Behandlung von $k$ Befehlen (ideale Verhältnisse)

  • Latenz

    • Anzahl der Zyklen zwischen einer Operation, die ein Ergebnis produziert, und einer Operation, die das Ergebnis verwendet

  • Laufzeit $T$ $$ T = k + n - 1 $$

    • $n$: Anzahl der Befehle in einem Programm (Annahme: ideale Verhältnisse!)

    • $k$: #Pipeline-Stufe

  • Beschleunigung $S$ $$ S = \frac{n \cdot k}{k + n - 1} $$

    • Ohne Pipeline: $n \times k$ Zyklen
    • Mit $k$-stufiger Pipeline: $k + (n-1)$ Zyklen

Verfeinerung der Pipeline-Stufen

• Weitere Unterteilung der Pipeline-Stufen

• Weniger Logik-Ebenen pro Pipeline-Stufe

• Erhöhung der Taktrate

• Führt aber auch zu einer Erhöhung der Ausführungszeit pro Instruktion

$\rightarrow$ “Superpipelining”

Visualizierung:

Bsp: MIPS R4000

Pipeline-Konflikte (Pipeline Hazards, Pipeline-Hemmnisse)

Was ist Pipeline-Konflikte?

Situationen, die verhindern, dass die nächste Instruktion im Befehlsstrom im zugewiesenen Taktzyklus ausgeführt wird

• Unterbrechung des taktsynchronen Durchlaufs durch die einzelnen Stufen der Pipeline

$ \rightarrow$ Verursachen Leistungseinbußen im Vergleich zum idealen Speedup 🤪

Einfaches Verfahren zur Auflösung von Konflikten: Anhalten der Pipeline (Pipeline stall)

• Wenn eine Instruktion angehalten wird, werden auch alle Befehle, die nach dieser Instruktion zur Ausführung angestoßen wurden, angehalten
• Alle Befehle, die vor dieser Instruktion zur Ausführung angestoßen wurden, durchlaufen weiter die Pipeline

Typen der Konflikte

• Strukturkonflikte

  • Ergeben sich aus Ressourcenkonflikten
  • Die Hardware kann nicht alle möglichen Kombinationen von Befehlen unterstützen, die sich in der Pipeline befinden können
  • Bsp: Gleichzeitiger Schreibzugriff zweier Befehle auf eine Registerdatei mit nur einem Schreibeingang

• Datenkonflikte

  • Ergeben sich aus Datenabhängigkeiten zwischen Befehlen im Programm
  • Instruktion benötigt das Ergebnis einer vorangehenden und noch nicht abgeschlossenen Instruktion in der Pipeline
    • D.h. ein Operand ist noch nicht verfügbar

• Steuerkonflikte

  • Treten bei Verzweigungsbefehlen und anderen Instruktionen, die den

    Befehlszähler verändern, auf

Auflösung der Pipeline-Konflikte

• Einfache Lösung: Anhalten der Pipeline (Pipeline stall)
• Einfügen eines Leerzyklus (Pipeline Bubble)
• Führt zu Leistungseinbußen