Software Pipelining
Software Pipelining ist ein Entwurfsmuster zur Programmierung eines Prozessors mit mehreren Ausführungseinheiten, sodass möglichst viele von ihnen gleichzeitig beschäftigt sind. Das Verfahren dient dazu, die Zeit für eine Berechnung zu verkürzen, indem die Intraprozessorparallelität zur Berechnung genutzt werden kann. Diese sogenannten Befehlsfließbänder werden englisch als „Pipelines“ bezeichnet.[1]
Hintergrund
Software Pipelining dient der Parallelverarbeitung von Befehlen eines einzelnen Threads (engl. Instruction Level Parallelism). Im Gegensatz zu der Parallelverarbeitung von Befehlen wird von Software Pipelining gesprochen, wenn dieselbe Berechnung auf einen Vektor von Eingabedaten durchgeführt wird (also eine Form von SIMD) und besonderes Augenmerk auf die Anordnung der Befehle im Befehlsstrom (engl. Instruction stream) gelegt wurde.
Im Gegensatz zu einer Pipeline innerhalb eines Prozessors, die die einzelnen Verarbeitungsschritte eines Maschinenbefehls aufteilt, sodass mehrere Befehle (in verschiedenen Stadien der Komplettierung) gleichzeitig bearbeitet werden können, sind an einer Software Pipeline mehrere Maschinenbefehle beteiligt, um eine Berechnung an einer Menge von Eingangsdaten auszuführen. Das bedeutet auch, dass das Software Pipelining explizit vom Programmierer beeinflusst wird und keine Eigenschaft oder Funktionalität des Prozessors ist, vielmehr werden die Eigenschaften Superskalarität und Pipelinearchitektur genutzt, die zusammen die parallele Ausführung von Befehlen ermöglichen. Im Gegensatz dazu kann die Prozessorpipeline vom Programmierer nicht manipuliert werden.
Beispiel
Es soll y = (x + 3) * 2 durchgeführt werden, das heißt, ein Vektor von Werten x(i) soll elementweise um 3 erhöht und anschließend verdoppelt werden. Wenn der Prozessor zwei Ausführungseinheiten für Arithmetikbefehle hat, dann können diese wie folgt belegt werden:
| Takt | i | Speichereinheit A | Ausführungseinheit A | Ausführungseinheit B | Speichereinheit B |
|---|---|---|---|---|---|
| 1 | 0 | r(0) = x(0) | |||
| 2 | 1 | r(1) = x(1) | r(0) = r(0) + 3 | ||
| 3 | 2 | r(2) = x(2) | r(1) = r(1) + 3 | r(0) = r(0) * 2 | |
| 4 | 3 | r(3) = x(3) | r(2) = r(2) + 3 | r(1) = r(1) * 2 | y(0) = r(0) |
| … | |||||
| j + 1 | j | r(j) = x(j) | r(j - 1)) = r(j - 1) + 3 | r(j - 2) = r(j - 2) * 2 | y(j - 3) = r(j - 3) |
| … | |||||
| n + 3 | n + 2 | y(n - 1) = r(n - 1) | |||
Legende:
- i ist der aktuelle Index
- in der 2. Spalte sieht man die Berechnung, die von Ausführungseinheit A durchgeführt wird
- r(i) ist dabei ein Register, das den Zwischenschritt der Berechnung speichert
Software Pipelining setzt voraus, dass der Prozessor mehr als einen Befehl gleichzeitig dekodieren und ausführen kann.
Der Begriff Pipelining kommt von der Unterteilung einer auszuführenden Operation in einzelne Arbeitsschritte oder Stufen, die wie bei einem Fließband nacheinander ausgeführt werden. Da die Berechnung eines Wertes in einem Takt jeweils nur einen Schritt der Pipeline in Anspruch nimmt, können mehrere Datensätze (in verschiedenen Stadien der Komplettierung) gleichzeitig verarbeitet werden. Wenn sich eine Operation bereits im zweiten Arbeitsschritt befindet, kann in der vorherigen Stufe bereits mit der nächsten Operation begonnen werden.[1] Allgemein wird Software Pipelining von allen superskalaren Prozessoren unterstützt, häufig mit Hilfe von Loop unrolling und Registerumbenennung im Compiler. Die IA-64 unterstützt Software Pipelining besonders, loop unrolling ist nicht nötig, register renaming wird vom Prozessor während der Ausführung von der Register Stack Engine übernommen.
Literatur
- M. Lam: Software Pipelining. An Effective Scheduling Technique for VLIW Machines. In: SIGPLAN notices. ACM, New York 1966, ISSN 0362-1340.
- Hongbo Rong, Alban Douillet, R. Govindarajan, Guang Gao: Code Generation for Single-Dimension Software Pipelining of Multi-Dimensional Loops. In: Code Generation and Optimization, 2004. CGO 2004. International Symposium on. ISBN 0-7695-2102-9, doi:10.1109/CGO.2004.1281673.
- Markus Pister: Generisches Softwarepipelining auf Assemblerebene. (Diplomarbeit) Universität des Saarlandes, Saarbrücken 2005.
Weblinks
- Beispiel für Software Pipelining auf homepage.cs.uiowa.edu (PDF; 279 kB)
- Chris Aycock What is software pipelining? in: Inside HPC. vom 2. September 2006.
- Daniel Post: Parallelität in der Intel IA – 64 Architektur auf berrendorf.inf.fh-bonn-rhein-sieg.de (PDF)
Einzelnachweise
- Markus Pister: Generisches Softwarepipelining auf Assemblerebene. – Kapitel 5: Softwarepipelining. S. 48.