Home Computer Prozessor Basics Site Map counter

Pipelines, Prefetch und Branch Prediction

Einführung

Schon immer war man bestrebt, die Geschwindigkeit eines Rechners zu erhöhen, dazu gibt es viele Ansätze, wie RISC oder CISC, SIMD und VLIW oder paralleles Rechnen. Andere Ansätze setzen am Speicher an, wie Caches oder synchrone RAMs. In diesem Aufsatz geht es um die Verkürzung der Bearbeitungszeit von Befehlen.

Das Problem

Nie ist ein Prozessor schnell genug. Um die Geschwindigkeit zu steigern kann man natürlich den Takt erhöhen. Dies hat aber Grenzen, insbesondere muss auch das Gesamtsystem (Ein/Ausgabe und der Arbeitsspeicher) schneller werden. Man kann aber auch versuchen die Ausführungszeit eines Befehles zu verringern. Doch wie soll man dies bewerkstelligen? Nun mit einer Pipeline!

Die Befehlsverarbeitung

Zuerst einmal muss man verstehen wie Befehle in einem Mikroprozessor verarbeitet werden und warum sie unterschiedlich lange zur Ausführung benötigen. Im einfachsten Falle verläuft die Ausführung eines Befehles in folgenden 4 Schritten:

  1. Befehl aus dem Speicher holen
  2. Befehl dekodieren
  3. Befehl ausführen
  4. Ergebnis schreiben

Bei einfachen Architekturen wie z.B. den 8 Bit Prozessoren 8080 und Z80 ist das auch deutlich erkennbar, denn die am schnellsten ausführbaren Befehle brauchen dort 4 Takte. Doch betrachten wir die vier Schritte einmal genauer.

Befehl aus dem Speicher holen

Zuerst einmal fordert der Prozessor vom Speicher das nächste Byte an, er legt dazu die benötigte Adresse auf den Adressbus. Nach einer gewissen Latenzzeit liegen die Daten auf dem Datenbus an und können vom Prozessor in Schritt 2 verarbeitet werden. Wenn der Prozessor mehr Daten braucht, z.B. weil ein Befehl länger als 1 Byte lang ist oder weil an dem Befehl Daten als Operanden angehängt sind, so muss er diesen Schritt mehrmals machen, Doch dies weiß der Prozessor erst nach Ausführung von Schritt 2.

Befehl dekodieren

Um den Code möglichst klein zu halten und die Speicherzugriffe für Schnitt 1 zu minimieren ist der Code eines Befehls meistens gepackt. Für die häufigsten Befehle hat man sich meist 1 oder 2 Byte Befehle ausgedacht. Ein Prozessor mit 4 Registern könnte z.B. für die häufigsten Registeroperationen folgende Befehlsstruktur haben :

Damit ließen sich 16 sehr häufige Befehle, die nur auf Registern arbeiten, wie MOV, ADD, AND, CMP etc. in einem Byte unterbringen. Nun muss in diesem Schritt aus den Bytes durch logische Verknüpfungen wieder der Opcode und die beiden Register extrahiert werden.

Meistens sind jedoch Befehle länger, weil die meisten Prozessoren wesentlich mehr als 16 Befehle und 4 Register haben. Auch dies wird hier festgestellt und dann werden weitere Daten über Schritt 1 vom Speicher geholt. Architekturen wie RISC benutzen daher gerne eine feste Befehlslänge um mehrfache Wiederholungen des Schritts 1 zu vermeiden, denn während dieser Zeit dreht der Prozessor Däumchen, er kann nicht in der Abarbeitung weitermachen. Sie laden in diesem Fall nicht nur das erste Byte sondern den kompletten Befehl bei Schritt 1.

Befehl ausführen

Auch die Ausführungszeit eines Befehls ist nicht immer gleich. Fast jeder Prozessor kann bestimmte Befehle sehr schnell ausführen. Dazu zählen das Bewegen von Daten (MOV), logische Verknüpfungen (AND,OR,XOR,NOT), Vergleiche (CMP) und einfache mathematische Operationen (ADD,SUB, INC, DEC). Andere Operationen können länger dauern wie z.B. Multiplikationen und Divisionen oder Verbundbefehle, die z.B. bei dem Kopieren und Durchsuchen von Strings eingesetzt werden.

Aber auch bei einem Befehl kann die Ausführungszeit unterschiedlich sein, abhängig von dem Modi. Nehmen wir einmal den Befehl MOV, der Daten von einem Platz an einen anderen bewegt. Sind beide Orte Register so geht dies schnell, müssen dagegen die Daten aus dem Hauptspeicher kommen oder gibt ein Register den Ort an (indirekte oder indizierte Adressierung), so braucht der Befehl natürlich länger.

Daten Zurückschreiben

Zuletzt müssen die Daten am Zielort abgelegt werden. Bei vielen Register zu Register Operationen kann dies entfallen, denn mit der Ausführung des Befehls sind die Daten schon am Zielort. Dies gilt zumindest für Architekturen die bei Operationen ein Operandenregister mit dem Ergebnis überschreiben wie der Intel IA86 Architektur. Architekturen die das Ergebnis in ein Ergebnisregister ablegen wie PowerPC oder SPARC brauchen auch hier Zeit um die Daten zu schreiben. Auf jeden Fall ist dieser Schritt nötig wenn die Daten im Hauptspeicher abgelegt werden oder an einen Ausgabeport gesandt werden.

Die Pipeline

Cyber CDC 6600 (1965)Schon bei Großrechnern versuchte man die Befehlsverarbeitung zu beschleunigen. Die Lösung die Mitte der sechziger Jahre erfunden wurde und bis heute gültig ist, ist die Pipeline. Zuerst ist noch alles gleich: Ein Befehl wird aus dem Speicher geholt. Doch anstatt ausgeführt zu werden, landet er in einem Speicher, der Pipeline. Bei jedem Takt wird ein neues Datenwort vom Speicher geholt und an den Anfang der Pipeline angefügt. Dieses Holen von Daten im Voraus nennt man Prefetch. Bei jedem Takt transportiert aber auch die Pipeline die Daten um eine Stelle weiter. Die Anzahl der Daten die gleichzeitig sich in Bearbeitung befinden können, nennt man Stufen der Pipeline.

Doch die Pipeline macht noch mehr. Nehmen wir an es wäre eine 4 stufige Pipeline. Dann könnte folgendes Passieren:

Jede Stufe kann sich darauf verlassen, das die vorherigen Stufen ihre Arbeit schon getan haben. Bei Stufe 3 sind also die Daten schon aus dem Speicher geholt und dekodiert worden. Es ist logisch, dass eine solche Pipeline die Geschwindigkeit um den Faktor 4 steigern kann, denn nun wird pro Takt ein Befehl ausgeführt anstatt das ein Befehl 4 Takte benötigt. Nach einer Vorlaufzeit von 3 Takten purzelt am Ende der Pipeline jeweils ein abgearbeiteter Befehl von der Pipeline. Die Anzahl der Stufen der Pipeline gibt also an, wie viele Befehle gleichzeitig in Bearbeitung sind.

Dies ist jedoch nur ein einfaches Modell, denn wie schon geschrieben brauchen manchen Befehle länger zur Ausführung oder brauchen weitere Daten aus dem Speicher. In der Praxis ist eine Pipeline daher länger als nur 4 Stufen. Wie lange hängt von der Architektur des Prozessors und der Taktrate ab. Bei einem hohen Takt ist es sinnvoller mehr Stufen zu haben, denn pro Zeiteinheit kann man weniger tun. Man kann dann durchaus das Holen von Daten über mehrere Stufen laufen lassen. Spitzenreiter ist aktuell (Juli 2004) der Pentium 4 HT mit 32 Stufen. Die meisten Prozessoren liegen heute zwischen 10 und 16 Stufen. Anfang der 80er Jahre wurde für Supercomputer als optimale Länge 8 Stufen ermittelt.

Bei der Intel IA86 Architektur, also der des Prozessors 8086 und seiner Nachfolger wurde die Pipeline beim 80486 Prozessor mit 5 Stunden eingeführt. Der erste Einsatz bei Großrechnern war die 1965 konstruierte Cyber CDC 6600 des genialen Ingenieurs Seymour Cray.

Ausnahmen für die Pipeline

Pentium 4 ProzessorAuch eine Pipeline kann nicht verhindern dass Befehle wie Division oder Quadratwurzelziehen nicht in einem Takt ablaufen, einfach weil ihre Laufzeit länger als die Durchlaufzeit der Pipeline ist. Dasselbe gilt für Befehle mit vielen Daten, z.B. einem angehängten 64 Bit Fliesskommawert bei einer FPU Operationen.

Doch das ist nicht das Problem. Solche Befehle halten zwar den Befehlsfluss länger auf, doch danach geht es in vollem Tempo weiter. Anders sieht es bei Verzweigungen aus. Es gibt bei jedem Mikroprozessor mindestens zwei Möglichkeiten eine Verzweigung im Code zu machen:

Unterprogrammaufruf (CALL) und Sprung (JUMP). Erstere entsprechen in einer Hochsprache einem Funktionsaufruf oder einem Unterprogrammaufruf, letztere braucht man um Schleifen in Assembler zu implementieren.

Das Dumme dabei ist: Da nun die Abarbeitung des Codes woanders stattfindet, ist die bisherige Arbeit in der Pipeline umsonst gewesen. Das bedeutet, dass alle Befehle die in der Pipeline sind, verworfen werden müssen. Die Daten aus dem Cache (oder schlimmer noch dem Hauptspeicher) angefordert werden müssen und zuletzt die Pipeline wieder gefüllt werden muss. Wenn ein Prozessor wie der Pentium 4 HT (Hyperthreading Version) eine Pipeline von 32 Stufen hat, dauert dies 32 Takte und ist damit langsamer als die Ausführung der meisten Befehle ohne Pipeline.

Sprungvorhersage

Daher haben Prozessoren eine Einheit die Sprungvorhersagen macht (Branch Prediction). Diese Einheit versucht vorherzusagen wohin ein Sprung geht und verfügt dazu über eine Sprungvorhersagetabelle die Adressen und Daten des neuen Ortes beinhaltet. Je größer diese Tabelle ist. Da die meisten Sprünge bedingt sind (abhängig von einem Rechenergebnis) ist dies nicht trivial.

Die Bedeutung dieser kann man daran erkennen, dass ein Pentium 4 zwar nur jeden 116.ten Sprung falsch voraussagt, aber durch die langen Pipelines dies deutlich Performance kostet nämlich 20/116 = 17 % der Gesamtleistung. In einigen Testprogrammen erreicht man bis zu 30 % Performanceverlust durch falsche Sprungvorhersagen. So ist auch die Verbesserung auf 1 falschen Sprung bei 133 Vorhersagen beim Pentium 5 HT deutlich Performance steigender, als man dies anhand der Prozentangaben der falschen Sprunge (0.75 und 0.86 Prozent) glauben mag.

Eine Sprungvorhersagetabelle hat eine typische Größe von 1024-16384 Einträgen und ist mit der Sprungvorhersage, einem Algorithmus der vom Prozessor neben der normalen Arbeit abgearbeitet wird, verbunden. Was dieser Algorithmus im einzelnen macht, ist Herstellergeheimnis. Doch fast alle versuchen das Verfahren mehrstufig zu lösen indem zuerst die einfachen Fälle abgearbeitet werden und dann schwierige Zweifelsfälle. Nach der Vorhersage wird dann die Pipeline mit den Daten gefüttert die von der erwarteten Lokalisation stammen, so dass es idealerweise zu keinem Pipeline Stall kommt.

Je schneller ein Prozessor arbeitet (Taktrate) , desto länger ist im allgemeinen die Pipeline und desto ausgeklügelter die Sprungvorhersage und desto größer die Sprungvorhersagetabellen. Es verwundert daher nicht, dass der Pentium 4 HT in all diesen Disziplinen führt, denn er ist der Prozessor mit dem höchsten Kerntakt von (Juli 2004) 3.6 GHz (ein Athlon 64 hat nur 2.5 GHz und der schnellste Power5 PC Prozessor 1.9 GHz Takt).

Um die lange Pipeline beim Pentium 4 bei einem Pipeline Stall nicht ganz auf die Performance durchschlagen zu lassen, hat man ihr auch einen Zwischenspeicher für schon dekodierte Befehle, den Trace Exekution Cache vorgeschaltet. Aus diesem kann die Pipeline schneller gefüllt werden, wenn ihr Inhalt ungültig wird.

Eine weitere Möglichkeit die Pipeline zu beschleunigen ist das Einführen mehrerer Pipelines. Dies wird meist auch nötig, wenn ein Prozessor mehrere Recheneinheiten hat, die von einer Pipeline nicht alle gefüttert werden können. Von Vorteil ist es aber, dass das Blockieren einer Pipeline (einen Pipeline Stall) durch Befehle mit langen Ausführungszeiten so vermindert werden kann. Man bewerkstelligt dies bei mehreren Pipelines, indem man die Befehle in der zweiten Pipeline so umgruppiert, dass auch dort ein langsamer Befehl zeitgleich ausgeführt wird. So sind beide Pipelines wieder im Gleichtakt.

Diese Vorgehensweise wird auch dynamisches Scheduling oder "Out of Order Exekution" bezeichnet und wurde schon im Jahre 1965 von der Cyber CDC 6600 eingeführt. Dynamisches Scheduling kann die Auslastung mehrerer Pipelines um bis zu 60 Prozent erhöhen. Man hat beim Itanium Prozessor auf dieses Feature verzichtet. Wissenschaftler errechneten dass dies 40 % Performance kostet. dies ist auch ein Grund warum der Itanium Prozessor nicht die Leistung erreicht die man sich von seinem Design erhoffte. Durch Multithreading (wie beim Pentium 4 HT) kann man auch die Einheiten auslasten und dies ist eine der Verbesserung des Nachfolgers des Itanium 2 (Montecito Kern).

Probleme

Intel hat für die "Net Burst" Architektur des Pentium 4 das Prozessordesign auf einen sehr hohen Takt optimiert. Der Pentium 4 wurde Mitte 2001 mit 1.4 GHz Takt eingeführt und der Takt sehr schnell bis Ende 2002 auf 3 GHz erhöht. Auf Konferenzen für Entwickler wurden sogar noch höher getaktete Modelle vorgeführt und man sprach von einem maximalen Takt von 7.5 GHz für diese Architektur. Dadurch wurde die Pipeline so lang. Da allerdings die Verlustleistung bei höherem Takt rapide anstieg war bei 3.8 GHz Maximaltakt war SSchluss und die folgende Architektur setzt nun mehr auf niedrigere Taktfrequenzen, aber mehrere Kerne mit größeren Caches.

So haben heutige Dual Core Prozessoren wieder eine kürzere Pipeline, da sie mehr Zeit haben pro Schritt. Auch die trickreichen Optimierungen zur Sprungvorhersage wurden teilweise bei neueren Modellen wieder etwas reduziert und die einfacheren Verfahren eingesetzt. Dies hängt zusammen: Je länger eine Pipeline ist, desto größer ist der Geschwindigkeitsverlust wenn durch einen Sprung der Inhalt ungültig wird. Je kürzer sie ist, desto schneller kann sie aber auch neu befüllt werden.

Zusammenfassung

Obgleich ein Pipeline Stall verhängnisvoll sein kann, hat man dies heute recht gut im Griff und nur ein geringer Prozentsatz der Sprünge wird heute falsch vorhergesagt. Allerdings ist dies auch nötig, denn es gibt eine Tendenz zu immer längeren Pipelines. Die nachfolgende Tabelle informiert über die Länge der Pipeline bei einigen Prozessoren Auch wenn diese Tabelle weder vollständig noch systematisch sein kann (da die Pipelinelänge nicht nur Takt, sondern auch von der Architektur abhängt), zeigt sie doch, dass je höher die Taktrate eines Prozessors ist, desto länger ist die Pipeline.

Prozessor Pipeline Stufen max. Takt
Pentium Pro 13 275 MHz
Athlon 11 2500 MHz
Opteron 12 2400 MHz
Pentium 4 20 3000 MHz
Pentium 4 HT 32 3600 MHz
Pentium III 10 1260 MHz
Itanium 1 10 1000 MHz
Itanium 2 8 1600 MHz
Power4 12 1600 MHz
Power PPC 970 16 1900 MHz
I 486 5 133 MHz
i 286 und i386 3 40 MHz
VAX 11/780 3 10 MHz
MIPS 5 16,7 MHz

Stand: Juli 2004



© des Textes: Bernd Leitenberger. Jede Veröffentlichung dieses Textes im Ganzen oder in Auszügen darf nur mit Zustimmung des Urhebers erfolgen.

Zum Thema Computer ist auch von mir ein Buch erschienen. "Computergeschichte(n)" beinhaltet, das was der Titel aussagt: einzelne Episoden aus der Frühzeit des PC. Es sind Episoden aus den Lebensläufen von Ed Roberts, Bill Gates, Steve Jobs, Stephen Wozniak, Gary Kildall, Adam Osborne, Jack Tramiel und Chuck Peddle und wie sie den PC schufen.

Das Buch wird abgerundet durch eine kurze Erklärung der Computertechnik vor dem PC, sowie einer Zusammenfassung was danach geschah, als die Claims abgesteckt waren. Ich habe versucht ein Buch zu schreiben, dass sie dahingehend von anderen Büchern abhebt, dass es nicht nur Geschichte erzählt sondern auch erklärt warum bestimmte Produkte erfolgreich waren, also auf die Technik eingeht.

Die 2014 erschienene zweite Auflage wurde aktualisiert und leicht erweitert. Die umfangreichste Änderung ist ein 60 Seiten starkes Kapitel über Seymour Cray und die von ihm entworfenen Supercomputer. Bedingt durch Preissenkungen bei Neuauflagen ist es mit 19,90 Euro trotz gestiegenem Umfang um 5 Euro billiger als die erste Auflage. Es ist auch als e-Book für 10,99 Euro erschienen.

Mehr über das Buch auf dieser eigenen Seite.

Hier geht's zur Gesamtübersicht meiner Bücher mit direkten Links zum BOD-Buchshop. Die Bücher sind aber auch direkt im Buchhandel bestellbar (da ich über sehr spezielle Themen schreibe, wird man sie wohl kaum in der Auslage finden) und sie sind natürlich in den gängigen Online-Plattformen wie Amazon, Libri, Buecher.de erhältlich.

Sitemap Kontakt Neues Hier werben Bücher vom Autor Buchempfehlungen Top 99