Die Pipeline

So, ich komme mal Niels Wunsch nach mehr Grundlagenaufsätzen zum Thema Computeerarchitekturen nach. Heute geht es um die Pipeline. Nein es handelt sich nicht um ein Spiel wo ein Klempner lecke Rohre verbinden muss und auch nicht um den Ukraine-Gas Konflikt. Es handelt sich um eine Maßnahme dem Prozessor Beine zu machen.

Die erste Verbesserung der Geschwindigkeit hat mit der Verarbeitung der Befehle zu tun. Dies ist für jeden Befehl folgender Ablauf:

• Hole den Befehl (oder bei CISC Architekturen oft auch nur das erste Byte des Befehls) vom Speicher. Dies wird als Fetch bezeichnet.

• Dekodiere den Befehl (decode)

• Eventuell, hole weitere Daten, die zum Befehl gehören. (Get Data, Memory Read)

• Führe den Befehl aus (Execute)

• Lege Daten im Zielregister ab (Write Back)

Die einzelnen Teile können unterschiedlich lang dauern, das hängt von der Architektur, aber auch dem Befehl ab, so sind logische Verknüpfungen zweier Register meistens sehr schnell erledigt und Divisionen dauern sehr lange. Bei der 8086 CPU, dem Urvater des heutigen PC, dauerten die Teile bei einem typischen Befehl z.B. so lange:

• Fetch: 4 Takte

• Decode: 2 Takte

• Get Data: 7 Takte

• Execute und Write Back: 3 Takte

Bei jedem Takt durchläuft ein Signal ein Netz von Gattern vom Eingang zum Ausgang. Der Takt wird zum einen auf die interne Architektur (in jedem Falle muss eine Teilaufgabe in dem Takt zu Ende geführt werden) aber auch auf das Speichersystem abgestimmt werden. Die 4 Takte bei Fetch entsprechen z.B. genau einem Speicherzyklus, der aus den Schritten Adresse anlegen, Read Signal setzen, Daten holen, Read Signal rücksetzen besteht.

Nach diesem seriellen Modell arbeiteten die meisten Computer bis in die sechziger Jahre. Ein Prozessor ist in Funktionsblöcke unterteilt und die haben unterschiedliche aufgaben. So gibt es den Block, der für Ein/Ausgabe zum Speicher zuständig ist (Load/Store Unit), den Befehlsdecoder, die Recheneinheit (Arithmetric-Logical Unit = ALU) und die Register als Speicher. Während der Ausführung ist aber nur jeweils eine Einheit aktiv. Bei Fetch und Get Data die Load/Store Unit, bei Decode der Befehlsdekoder, bei Execute die ALU und bei Write Back die Register.

Es lag nahe, dass man die Geschwindigkeit steigern kann, wenn diese Einheiten parallel arbeiten anstatt hintereinander. Das ist die Idee der Pipeline. Sie wurde schon rudimentär bei der IBM Stretch eingeführt, setzte sich aber erst Mitte der Sechziger Jahre durch.

Eine Pipeline wartet nicht, bis der erste Befehl ausgeführt wird, sondern sie holt bei jedem Takt einen neuen Befehl, startet also einen Fetch bei jedem Takt. Die CPU braucht dann einen Speicher für diese Befehle wie auch die folgenden Schritte. Bei jedem Takt durchwandert der Befehl die Pipeline, die eine bestimmte Länge (man spricht von Stufen) hat. Beim Durchwandern werden dann die gesamten Aktionen durchgeführt, bis schließlich am Ende der Pipeline der Befehl ausgeführt ist. Die Befehlsausführung wird nicht verkürzt, aber der zweite Befehl benötigt dann viel weniger Takte, im Idealfall nur einen. So könnte der zeitliche Ablauf bei einer Pipeline so aussehen:

Takt	Befehl 1/4	Befehl 2/5	Befehl 3
1	Befehl 1 holen
2	Befehl 1 dekodieren	Befehl 2 holen
3	Befehl 1 ausführen	Befehl 2 dekodieren	Befehl 3 holen
4	Befehl 4 holen	Befehl 2 ausführen	Befehl 3 dekodieren
5	Befehl 4 dekodieren	Befehl 5 holen	Befehl 3 ausführen
6	Befehl 4 ausführen	Befehl 5 dekodieren	Befehl 6 holen

In diesem Beispiel wird so die Ausführungszeit pro Befehl von drei auf einen Takt erniedrigt. Komplexere Befehle, wie z.B. Multiplikationen können dann auch mehrere Takte zur Ausführung benötigen. Ebenso wenn ein Datenzugriff auf den Speicher benötigt wird (Get Data). Im Beispiel habe ich auch den Write Back Teil weggelassen, der in der Theorie ein eigener Schritt ist, aber in praktischen Umsetzungen meist Bestandteil des Execute Teils ist (so auch beim obigen Beispiel der 8086 CPU).

In jedem Falle steigert die parallele, aber zeitversetzte Bearbeitung mehrerer Befehle es die Geschwindigkeit. Allerdings verkompliziert die Pipeline die Rechnerarchitektur. Es gibt hier drei Probleme:

Der Inhalt der Pipeline ist zu verwerfen und ungültig: Alle Prozessoren realisieren Schleifen, also Wiederholungen von Codeteilen, durch Sprünge zu anderen Adressen. Ebenso haben sie Befehle um Unterprogramme die woanders im Speicher liegen aufzurufen. Da in der Pipeline schon die nächsten Befehle stehen, diese nun aber gar nicht mehr ausgeführt werden, ist der gesamte Inhalt ungültig und zu verwerfen. Die Pipeline wird neu gefüllt und nun ist der Geschwindigkeitsvorteil erst mal dahin. Intel hatte beim Pentium 4 eine sehr lange Pipeline mit 20 Stufen eingeführt. Die vielen Stufen erlaubten es pro Takt sehr wenig zu tun, das bedeutete, die Taktfrequenz konnte hoch sein. Das war ein Vorteil. In Programmen mit vielen Sprüngen war der Pentium 4 aber deutlich langsamer als sein Vorgänger, eben weil erst diese lange Pipeline wieder gefüllt werden musste.

Als Zweites sind die Befehle nicht unabhängig voneinander. Es gibt Abhängigkeiten. So kann ein Befehl Daten benötigen, die ein anderer Befehl erst berechnet, diese aber zu dem Zeitpunkt, wo der Befehl die Daten braucht, noch nicht vorliegen. Ein/Ausgabeoperationen zu Peripheriegeräten oder dem Speicher können einen Befehl aufhalten und damit die Folgenden die mit seinem Ergebnis weiter arbeiten. Verhindert muss auch werden, dass sich Befehle überholen und ein langsamer Befehl ein Register überschreibt, das eigentlich durch einen nachfolgenden, schneller ausgeführten, Befehl schon verändert wurde.

Als Drittes gibt es strukturelle Verzögerungen: die Wege im Schaltnetz des Prozessors sind unterschiedlich lang und die Ausführung einer Stufe kann je nach Aufgabe unterschiedlich lang dauern. Es muss gewährleistet sein, dass jeder mögliche Weg, innerhalb der Zeit die für eine Stufe zur Verfügung steht, durchlaufen werden kann.

Die Lösung dieser Probleme, die mit einer Pipeline zu tun haben, ist also relativ aufwendig, weshalb viele frühe Implementationen nicht die oben beschriebene Instruktionspipeline implementierten, sondern eine funktionelle Pipeline. Bei dieser beschränkt man sich auf den Teil des Befehles, der ausgeführt wird, also den „execute“ Teil. Bekanntestes Beispiel sind die Rechner von Seymour cray, die zwischen 8 und 12 funktionale Einheiten hatten, die parallel arbeiten konnten. Das war schon geschwindigkeitsteigernd, weil diese Rechner mit Fließkommazahlen arbeiteten, bei denen Rechnungen einige Takte erforderten, während das holen und Dekodieren in jeweils einem Takt erledigt war. Hardwaretechnisch müssen dann nur die einzelnen Stufen der Einheiten voneinander isoliert werden und es muss die Möglichkeit geben, Konflikte zu erkennen. Das löste man mit Reservierungsflags. Die anzeigten, ob ein Register oder eine Funktionseinheit beschäftigt/belegt war oder nicht.

Bei der Instruktionspipeline ist der Aufwand, um die Konflikte ohne zusätzliche Wartezeiten zu lösen erheblich höher. Die Problematik, dass nachfolgende Befehle warten müssen, bis ein Ergebnis feststeht, wird durch das Umsortieren der Befehle gelöst, im Fachwort „our of Order Execution“. Dazu müssen die Abhängigkeiten der befehle bekannt sein, was aufwendig ist.

Ein Beispiel:

R1=R2*R3

R4=R1+R5

R6= R7-R8

Die Addition wird bei allen Prozessoren schneller ausgeführt als die Multiplikation. So muss der zweite Befehl warten, bis das Ergebnis der Multiplikation feststeht, sonst würde er mit dem alten Registerinhalt arbeiten. Diese Blockade kann man auflösen, wenn man die nächste Anweisung vorzieht, die andere Register nutzt.

Nicht jeder Mikroprozessor verfügt über diese Möglichkeit. Beim Atom Prozessor hat Intel z.B. auf dieses Feature verzichtet, das in den leistungsstärkeren Prozessoren von Intel standardmäßig eingebaut ist. Das Sprünge den Pipelineinhalt überflüssig machen hat dazu geführt, dass man eine „Sprungvorhersage“ (Branch Prediction“) eingeführt hat. Diese Logik versucht vor einem Sprung das Ergebnis zu „raten“ was heute mit 90+% Wahrscheinlichkeit gelingt und lädt dann die Befehle die nach dem Sprung durchgeführt werden vorausschauend in die Pipeline.

Die Abhängigkeit von Registern, das z.B. ein Register als Quellregister für einen Befehl benötigt wird, das bei einem nachfolgenden Befehl als Zielregister dient, dieser Befehl aber den Ersten überholen könnte löst man am besten durch Schattenregister. Das sind Register, die im Prozessor vorhanden sind, aber nach außen nicht in Erscheinung treten. Sie nehmen Zwischenergebnisse oder Kopien von Registern auf. Im Allgemeinen ist es von Vorteil möglichst viele Register zu haben, weil so zum einen Konflikte seltener sind und zum anderen man weniger Zugriffe auf den Speicher braucht, die die Ausführung von Befehlen verlangsamen.

Die Pipeline ist das mächtigste Werkzeug um die Geschwindigkeit eines Rechners nicht nur bei Spezialoperationen, sondern allgemein zu erhöhen. Der 8086 hatte noch keine Pipeline, aber einen einfachen Vorläufer der Zugriff auf den Speicher und Rechnen entkoppelte. Der 8086 brauchte im Schnitt 7,66 Takte pro Befehl. Der 80486 hatte eine fünfstufige Pipeline, er konnte 80% der Befehle in einem Takt durchfuhren und erreichte bei 25 MHz 20 MIPS, benötigte also durchschnittlich 1,25 Takte pro Befehl. Die Pipeline hat (mit anderen Technologien) die Geschwindigkeit pro Takt also versechsfacht.

Praktisch alle ab 1985 vorgestellten neuen Prozessoren setzten Pipelines ein. Möglich wurde dies auch durch Mikrocode, darunter versteht man einen noch einfacheren Code, der jeden Befehl in kleinere elementare Bestandteile zerlegt und diese ausführt. Der Mikrocode steckt in einem kleinen Festwertspeicher auf dem Prozessor. Er kann leicht geändert werden und die einfachen Instruktionen können in einer Stufe ausgeführt werden. Die früher eingesetzte Hardwareverdrahtung ist zwar schneller, aber erheblich aufwendiger. So verwundert es nicht, das die IBM 360 Serie gleichzeitig Pipelines und Mikrocode einführte.

Über die optimale Länge einer Pipeline gibt es einige theoretische Untersuchungen. Ist sie zu kurz, so verzichtet man auf einen Geschwindigkeitsgewinn. Daneben hat jede Stufe aber auch eine eigene Verzögerung, denn der Inhalt der Pipeline muss auch weitergeschoben werden. Am Schaltnetzwerk muss der Ursprungszustand vor dem Takt wiederhergestellt werden. Wird die Pipeline zu lang, so wird der Anteil dieser Vorgänge an der zur Verfügung stehenden Zeit pro Takt immer größer. Die meisten Autoren halten eine Pipeline von 6-8 Stufen für optimal.