Arten der Befehlsverarbeitung

Sequentielle Verarbeitung

Verbreitete Modelle:

• Intel 8080 (1974, wurde z.B. im Altair 8800 eingesetzt): 0,2 Befehle pro Takt (8 Bit Wortbreite)
• MOS Technology 6502 (1975, z.B. Apple II, Commodore PET, Atari 2600)
• Zilog Z80 (1976, z.B. Tandy TRS-80, Schneider CPC, Sinclair ZX Spectrum): 0,25 Befehle pro Takt

Fließband-Verarbeitung (Pipelining)

• Intel 80386 (1985): 0,34 Befehle pro Takt (32 Bit Wortbreite)
• Intel 80486 (1989): 0,8 Befehle pro Takt

Multi-Pipelining

• Pentium (1993): 2 Pipelines, 1,88 Befehle pro Takt
• Pentium MMX (1997)

CPUs, die mehr als einen Befehl pro Takt ausführen können, werden auch als superskalare CPUs bezeichnet.

Out-of-order-Befehlsverarbeitung

• Pentium Pro (1995): 3 Pipelines, 2,7 Befehle pro Takt
• AMD K5 (1996): 3 Pipelines
• Core 2 Duo (2006): 4 Pipelines, etwa 4,6 Befehle pro Takt (pro Kern)

Quelle

Sequentielle Verarbeitung

Fließbandverarbeitung

Bei der Fließband-Verarbeitung wird die Befehlsverarbeitung in folgende Teilabschnitte, Stufen oder Phasen genannt, unterteilt:

• Fetch: Befehl aus dem Speicher holen
• Decode: Befehl in Operator und Operanden aufteilen, überprüfen ob es ein Sprungbefehl ist
• Load (Decode 2): Operanden (Daten) aus dem Speicher holen
• Execute: Befehl ausführen
• Write Back: Ergebnis im Speicher ablegen

• Es können mehrere Befehle in verschiedenen Phasen gleichzeitig verarbeitet werden. Durch die bessere Auslastung der einzelnen Funktionseinheiten der CPU wird die Leistung stark verbessert. Im Gegensatz zu einer echten Parallelverarbeitung wird beim Pipelining nur maximal ein Befehl pro Takt ausgeführt, da die Phasen zeitlich versetzt sind.

Die meisten Prozessoren haben deutlich mehr Stufen, die aber auf diesen 5 „Grundphasen“ des Intel Pentium aufbauen. Den Ausführungspfad, den ein Befehl im Prozessor folgt, bezeichnet man als Pipeline. Eine Pipeline ist vergleichbar mit einem Fließband, auf dem die Produkte die einzelnen Stationen der Fertigung durchlaufen.
Je mehr Pipeline-Stufen vorhanden sind, desto mehr Befehle können sich gleichzeitig in Verarbeitung befinden. Eine Erhöhung der Stufen ist eine efffektive Methode, die Leistung ohne großen Hardwareaufwand zu steigern, denn durch den einfacheren Aufbau einer Stufe sind höhere Taktfrequenzen möglich. Manche Modelle des Intel-Pentium-IV-Prozessors hatten mehr als 30 Stufen. Allerdings lässt sich die Stufenanzahl nicht beliebig erhöhen, da einerseits vermehrt Daten- und Ressourcenkonflikte auftreten (s. unten) und andererseits mit steigender Taktfrequenz die Temperatur zunimmt. Deshalb haben moderne CPUs mehrere Pipelines, die mehrere Befehle pro Takt gleichzeitig (in der gleichen Phase) ausführen können:

Fetch-Phase

In der Fetch-Phase werden die Programmbefehle aus dem Befehlscache geholt und in einem Puffer abgelegt. Die Adresse des jeweils nächsten Befehls ist in einem speziellen Register, dem Befehlzähler oder Instruction Pointer (IP), gespeichert. Bei einem Sprungbefehl zeigt der IP auf die Adresse des Sprungziels im Sprungziel-Puffer oder Branch Target Buffer (BTB). Im BTB werden Sprungziel-Adressen zwischengespeichert, damit die Zieladresse eines Sprungs beim nächsten Mal nicht erneut ermittelt werden muss.

Decode-Phase

Der Befehl (Opcode) wird analysiert und in eine prozessorabhängige Mikro-Instruktion umgewandelt. Dabei werden auch die Operanden (die Daten selbst) ermittelt. Danach wird der Befehl je nach Typ (z.B. Ganzzahl, Fließkomma) an die entsprechende Ausführungseinheit weitergeleitet. Wenn es sich bei dem Befehl um einen Sprungbefehl handelt, wird der Befehlszähler auf die Adresse des Sprungziels im BTB gesetzt.

Load-Phase

Die vom Befehl adressierten Daten werden aus dem Datencache geladen.

Execute-Phase

Pipeline-Stillstände

Bei Fließband-Verarbeitung muss stets gewährleistet werden, dass vor dem Ausführen des aktuellen Befehls bereits der nächste Befehl am Eingang bereitsteht. Ansonsten kommt es zu einem ungewollten Stillstand der Pipeline. Es ist wie bei einem Fließband: Dieses muss ebenfalls angehalten werden, wenn benötigte Teile nicht rechtzeitig geliefert werden können. Mögliche Ursachen eines Stillstands und zur Verhinderung eingesetzte Techniken werden in der folgenden Liste kurz erläutert:

Out-of-Order- Ausführung

Anfang der 1990er Jahre erschienen die ersten CPUs, die zwei Fließbänder enthielten (z.B. Intel Pentium, Motorola 68060) und damit theoretisch zwei Befehle pro Takt parallel ausführen konnten. Allerdings mussten die beiden Befehle unabhängig voneinander sein. Wenn der Folgebefehl etwa auf ein Ergebis des vorangegangenen Befehls angewiesen war, konnte nur ein Befehl pro Takt ausgeführt werden. Da hintereinanderfolgende Befehle oft voneinander abhängen, war die Auslastung der zweiten Pipeline gering. Deshalb wurde 1996 mit dem Intel Pentium Pro die Out-of-order-Befehlsausführung eingeführt. Sie beruht auf folgenden Prinzipien:

• Mehrere auf den Befehlszähler folgenden Befehle werden bereits vor ihrem Aufruf im Programm spekulativ ausgeführt, d.h. es steht noch nicht fest, ob diese tatsächlich ausgeführt werden. Vorteil: Operanden stehen bereits zur Verfügung, bevor sie benötigt werden.
• Befehle werden nicht mehr in der Programmreihenfolge abgearbeitet, sondern es wird zuerst der Befehl ausgeführt, dessen Operanden am ehesten zur Verfügung stehen. Stillstände durch bestehende Datenabhängigkeiten können so verhindert werden.

Aufbau einer Out-of-Order-CPU

Die Hardware-Umsetzung erfolgt bei Intel-CPUs in Form zweier Befehls-Warteschlangen:

• Im ReOrder-Puffer (ROB) werden alle bereits dekodierten Befehle aufgereiht (beim Pentium Pro bis zu 30, bei aktuellen CPUs über 100), und zwar in der gleichen Reihenfolge wie im Programm. Der zuletzt decodierte Befehl wird jeweils ans Ende der Warteschlange angehängt. Gleichzeitig wird der älteste, ausgeführte Befehl aus dem Puffer entfernt. Zu jedem Befehl wird ein eigener Eintrag erzeugt, der u.a. Statusbits (in Ausführung/bereit), Typ des Befehls (z.B. Sprungbefehl, Ladebefehl, Ganzzahl, Fließkomma), Ziel (Schattenregister oder Speicheradresse) und Ergebnis enthält.
• In die Reservation-Station (RS) werden nur die Befehle eingereiht, die bereit zur Ausführung sind und auf eine freie Recheneinheit (Execution Unit) warten,. Anders als im ReOrder-Buffer steht nicht der  Befehl am Anfang der Warteschlange, der im Programm als nächstes folgt, sondern der Befehl, dessen Operanden am frühesten bereit sind. Der Befehl wird einer geeigneten Recheneinheit zugeordnet und berechnet. Es gibt auch Umsetzungen mit mehreren Reservation-Stationen (z.B. AMD K5).

[Quelle]

Register-Renaming

Als Register-Renaming bezeichnet man die zeitlich begrenzte Zuweisung eines Registers zu einem anderen Register, um „falsche“ Datenabhängigkeiten aufzuheben. Diese entstehen nur, wenn dasselbe Register von aufeinanderfolgenden Befehlen verwendet wird. Spekulative Ausführung und Register-Renaming werden in der Regel gemeinsam genutzt, da bei beiden Techniken zwei Registersätze benötigen:

• Einen Satz Register, der von der Architektur vorgegeben und vom Programm genutzt werden kann, z.B. x86-Registersatz
• Einen Satz Schattenregister (Retirement Register), der eine große Anzahl alternativ nutzbarer Register enthält, die für Programme aber unsichtbar sind. Die Schattenregister werden auch zur zeitlich befristeten Aufbewahrung spekulativer Ergebnisse verwendet.

Eine Registerzuordnungstabelle (Register Allocation Table) weist jedem Architekturregister ein Schattenregister zu. Jedem Befehl, der in ein Architekturregister schreibt, wird in der Decode-Phase ein Schattenregister zugeteilt. Im Reorder-Puffer werden diese Schattenregister als Zielregister eingetragen. Die Zuordnung wird wieder aufgehoben, wenn das Ergebnis bestätigt und in das entsprechende Architekturregister übertragen wurde.

Out-of-order-Pipeline

Eine Out-of-order-Pipeline besteht aus folgenden Phasen:

1. Fetch
2. Decode: In dieser Phase wird zusätzlich das Register-Renaming durchgeführt.
3. Dispatch („Zustellung“): Bevor der Befehl aus dem Reorder-Buffer an die Reservation Station übertragen werden kann, muss zuerst überprüft werden, ob die zugehörigen Operanden bereits zur Verfügung stehen und ob in der RS ein Platz frei ist. Wenn der Befehl nicht bereit ist, wird einfach der nächste „out-of-order“ ausgewählt.
4. Issue: Der Befehl und die Operanden werden an die entsprechende Ausführungseinheit (z.B. ALU) übergeben, sobald diese bereit ist.
5. Execute
6. Write-Back: Das Ergebnis wird in das zugewiesenene Schattenregister oder in den ROB geschrieben.
7. Commit/Retire: Da Befehle rein spekulativ ausgeführt werden, ist zunächst nicht bekannt, ob sie tatsächlich im Programm aufgerufen werden. Deshalb muss ein Befehl zuerst bestätigt („commited“) werden, bevor das Ergebnis übernommen wird.
   • Ein Befehl kann erst bestätigt werden, wenn alle vorherigen Befehle nach der Reihenfolge im Programm bestätigt wurden.
   • Es wird immer der älteste ausgeführte Befehl im ROB bestätigt.

Nachdem der Befehl bestätigt wurde, kann das Ergebnis in das Architekturregister oder in den Datencache übertragen und der zugehörige Eintrag in der Warteschlange geleert werden. Das zugeordnete Schattenregister wird dabei wieder freigegeben („Retire“).

[Quelle]

Vorteile

•  „falsche“ Datenabhängigkeiten können durch Register-Renaming vollständig aufgelöst werden
• keine unnötigen Stillstände oder hohe Latenzzeiten, da zuerst die Befehle ausgeführt werden, deren Operanden zur Verfügung stehen
• schnellere Programmausführung

Nachteile

• hoher Hardwareaufwand
• Der Befehlspuffer kann viele Sprungbefehle enthalten. Das erfordert eine höhere Vorhersagegenauigkeit als bei einem einzelnen Sprungbefehl.
• bei einer falschen Sprungvorhersage ist aufwändiges Löschen und Neu-Befüllen des Befehlspuffers nötig
• die Commit-Phase wird bei mehreren Pipelines zum Flaschenhals, wenn der Befehlspuffer nicht genügend Ausgabepfade hat

Sprungvorhersage (Branch Prediction)

Die effektivste Methode, einen Verarbeitungsprozess ohne Wartezeiten sicherzustellen, ist es, Befehle und Daten bereits dann zur Verfügung zu stellen, bevor sie benötigt werden. Dazu werden die auf den aktuellen Befehl folgenden Operationen bereits vorab aus dem Speicher geholt und in einem Puffer gesammelt. Wenn man davon ausgeht, dass die Befehle immer in der Reihenfolge abgearbeitet werden, in der sie im Programm erscheinen, ist das kein Problem. Es gibt aber auch Sprungbefehle, durch die der gesamte Programmablauf verändert wird, z.B. Verzweigungen oder Schleifen (Folge von Befehlen, die mehrmals hintereinander ausgeführt werden). Bei Programmen mit Sprüngen ist es riskant, Befehle zu holen, die weiter vorn auf dem Verarbeitungspfad liegen, da vor der Decode-Phase nicht bekannt ist, ob der nächste Befehl ein Sprungbefehl ist. Wenn der Sprung nicht ausgeführt wird, etwa weil eine bestimmte Bedingung nicht erfüllt ist (z.B. Operand 2 muss größer als 0 sein), kann der Verarbeitungsprozess normal fortgesetzt werden. Anderenfalls müssen die Befehle am Sprungziel erst geladen werden. Alle vorab zwischengespeicherten Daten können dann nur noch „entsorgt“ werden. Deshalb beherrschen moderne CPUs die sogenannte Sprungvorhersage (branch prediction).

Statische Sprungvorhersage

Die statische Sprungvorhersage ist keine Vorhersage im engeren Sinn, sondern eher ein festgelegtes Schema, wie ein Sprungbefehl behandelt werden soll. Es gibt folgende Möglichkeiten:

• Die einfachste Methode: Die Pipeline einfach so lange anhalten, bis in der Execute-Phase entschieden wurde, ob der Sprung tatsächlich ausgeführt („genommen“) wird oder nicht (s. Abbildung).
• Der Sprung wird als „nicht gesprungen“ vorhergesagt: Die Folgebefehle nach dem Sprungbefehl werden immer im Voraus geladen. Wenn der Sprung entgegen der Vorhersage ausgeführt wird, hält die Pipeline an, bis das Sprungziel bekannt ist und beginnt anschließend mit dem Laden der Befehle am Sprungziel.
• Der Sprung wird als „gesprungen“ vorhergesagt: Sobald bekannt ist, dass es sich um einen Sprungbefehl handelt, kann das Sprungziel ermittelt und bereits vor Eintritt in die Execute-Phase der Folgebefehl geholt werden. Wenn der Sprung nicht ausgeführt wird, muss die Pipeline warten, bis der Befehl nach dem Sprungbefehl geladen wurde. Dieses Verfahren eignet sich vor allem bei Schleifen.
• Der Programmierer legt mehrere Befehle fest, die unabhängig vom Sprungbefehl ausgeführt werden können. Diese können dann dazwischengeschoben werden, wenn der Sprung ausgeführt wird, das Ziel aber noch ermittelt werden muss.
• Statische Vorhersagemethoden sind zwar einfach umsetzbar, verursachen aber bei bedingten Sprüngen weiterhin Pipeline-Stillstände, da erst in der Execute-Phase (Befehlsausführung) bekannt ist, ob der bedingte Sprung tatsächlich gesprungen wird oder nicht. Die Vorhersagegenauigkeit schwankt sehr stark (etwa 50 – 80%), am höchsten ist sie bei vielen Schleifen oder unbedingten Sprüngen (z.B. Springe zu einer berechneten Zieladresse) im Programmcode.

Dynamische Sprungvorhersage

Die dynamische Sprungvorhersage versucht, das Ziel eines (bedingten) Sprungs anhand vorheriger Sprünge vorherzusagen. Da die Sprungziele erst zur Laufzeit eines Programms ermittelt werden, spricht man von dynamischer Sprungvorhersage.

BHT (Branch History Table)

Dazu wird jeder Sprung in einer Tabelle (Branch History Table = Sprungverlauf-Tabelle) festgehalten. Bei jedem Sprung wird ein Eintrag erzeugt, der folgende Informationen enthält:

Branch-Target-Buffer (BTB)

Die zuletzt am häufigsten genutzten Einträge der Tabelle werden in einem schnellen Sprungziel-Puffer (Branch Target Buffer, BTB) oder -cache abgelegt. Sobald sich in der Decode-Phase herausstellt, dass der nächste Befehl ein Sprungbefehl ist, wird die Adresse des Sprungziels im BTB gespeichert. Wenn der Sprung bereits stattgefunden hat und der Zählerstand mindestens die Hälfte des Maximalwerts erreicht (Wahrscheinlichkeit eines Sprungs mindestens 50%), liefert der BTB in der nächsten Fetch-Phase die Adresse des Sprungziels zurück, ansonsten die Adresse des folgenden Befehls.

Call-Return-Stack

Oft befinden sich Sprungziele in Unterprogrammen bzw. in einem anderen Programmabschnitt (Prozedur). Damit die CPU nach Ausführung der Befehle beim Rückkehrbefehl zum Hauptprogramm (RETURN) wieder den richtigen Einstiegspunkt findet, wird die Adresse des letzten Unterprogrammaufrufs (CALL) in einem Stapelspeicher, dem CALL-RETURN-Stack, abgelegt.

Zweistufige, dynamische Sprungvorhersage

Beispiel

Ein einfaches Programm soll den Benutzer daran erinnern, wenn es sich bei der eingegebenen Jahreszahl um ein Schaltjahr handelt. Dazu müssen drei Bedingungen erfüllt sein:

1. Die Jahreszahl muss ohne Rest durch 4 teilbar sein (JAHR mod* 4 == 0).
2. Die Jahreszahl ist durch 100 teilbar (JAHR mod 100 == 0).
3. Die Jahreszahl muss aber auch durch 400 teilbar sein (JAHR mod 400 == 0).

*mod steht für Modulo und gibt den Rest einer Division zurück

Wenn die jeweils vorherige Bedingung erfüllt ist, wird die nächste geprüft. Nur wenn alle Sprungbedingungen erfüllt sind, wird ein Unterprogramm aufgerufen, das z.B. einen Hinweis ausgibt oder das entsprechende Jahr im Kalender markiert. Würde man diese Abhängigkeiten (Korrelationen) in die Vorhersage einbeziehen und nicht jeden Sprung für sich betrachten, ließe sich die Genauigkeit der dynamischen Vorhersage noch verbessern.

Pattern History Table (PHT)

Aus diesem Grund wird heutzutage eine zweistufige (korrelierende) Vorhersagemethode eingesetzt. Dabei wird zu jedem Sprungbefehl das Verhalten über mehrere Sprünge hinweg als Folge mehrerer Bits (0 = nicht gesprungen, 1 = gesprungen) in einer Sprunghistorie aufgezeichnet. Eine zweidimensionale Tabelle, die als Pattern History Table (PHT) bezeichnet wird, enthält zu jeder möglichen Historie eines Sprungbefehls eine eigene Spalte (bei einem 2-Bit-Schieberegister sind dies 2^2 = 4 Spalten: 00 01 10 11 ). Über die niederwertigen Adressbits des Sprungbefehls wird die entsprechende Zeile und über ein n-Bit-Schieberegister (Branch History Register) die Spalte ausgewählt. Der Inhalt des Schieberegister wird bei jedem Sprung um ein Bit nach links verschoben und zeigt damit immer auf die letzten n Sprünge. Wenn ein Sprung ausgeführt wird, erhöht sich der Zähler in der entsprechenden Spalte um 1. Falls ein Sprung nicht ausgeführt wird, verringert sich der Zähler um 1.

Beispiel

Für einen bedingten Sprungbefehl sei folgende Sprunghistorie gegeben: 0 1 0 0 1 0 1 0 0 1 (0 = nicht gesprungen, 1 = gesprungen). Daraus lassen sich mit dem 2-Bit-Zähler folgende Vorhersagen ableiten:

• auf 00 folgte immer eine 1 (Zählerstand: 01/10), also liegt in diesem Fall die Wahrscheinlichkeit (WSK) bei 75%, dass nach zwei nicht ausgeführten Sprüngen ein Sprung folgt
• auf 01 folgte immer eine 0 (00/00/00); d.h. hier beträgt die WSK 0%, dass nach einem nicht ausgeführten und einem ausgeführten Sprung wieder gesprungen wird
• auf 10 folgte einmal 0 und einmal 1 (00/01), die WSK liegt bei 25%, dass nach einem ausgeführten und einem nicht ausgeführten Sprung erneut gesprungen wird
• 11 kam gar nicht vor

Der entsprechende Eintrag in der PHT:

• in Spalte 00 steht eine 10 für eine hohe Sprungwahrscheinlichkeit, in Spalte 01 steht eine 00 für die geringste WSK usw. (s. letzter Zählerstand)

Das zweistufige Verfahren liefert zwar genauere Vorhersagen, ist aber auch hardwareaufwändiger. Außerdem dauert es bei kaltem (leerem) Cache deutlich länger, bis zuverlässige Vorhersagen möglich sind, weil die Sprunghistorie erst mit genügend Werten befüllt werden muss.

Die Vorhersagegenauigkeit einer zweistufigen Sprungvorhersage liegt bei etwa 97%. Im Fall einer erfolgreichen Vorhersage können Pipeline-Stillstände komplett verhindert werden, da das Sprungziel bereits frühzeitig bekannt ist.

SMT (Simultaneous Multi-Threading)

Hyper-Threading

Intel bezeichnet seine Version des SMT als Hyper-Threading (HT). Ein physischer Kern besteht aus zwei logischen Kernen, d.h. es werden maximal zwei Threads pro Kern abgearbeitet (2-fach SMT). Jeder logische CPU-Kern hat lediglich einen eigenen Registersatz, alle anderen Funktionseinheiten werden gemeinsam genutzt. Die ersten CPUs mit dieser Technologie waren die Pentium-4-Prozessoren, aber nur in ausgewählten Modellen. Bis zur 10. Generation der Core-i-Prozessoren gab es HT nur bei den i7- (Ausnahme: 9. Gen.) und i9-Modellen.

Clustered Multi-Threading

Die Mehrkern-CPUs von AMD (FX-CPUs und frühe A-Serie, Codename „Bulldozer“) bestanden zunächst nicht aus einzelnen Kernen, sondern aus einzelnen Modulen. Jedes Modul hatte zwei eigenständige Ganzzahl-Cluster, die jeweils eigene ALUs/AGUs, Register und Datencaches enthielten. Aufgrund dieses internen Aufbaus seiner Prozessoren brachte AMD eine eigene Version des simultanen Multi-Threading auf den Markt: Das Clustered Multi-Threading. Dabei wird jeder Ganzzahl-Cluster als logischer CPU-Kern verwaltet. Aus diesem Grund ist die Leistung eines Kerns fast so hoch wie bei einem echten Zweikern-Prozessor, aber nur wenn beide logischen Kerne ganzzahlige Daten verarbeiten.
Seit Einführung der Ryzen-CPUs auf Basis der Zen-Mikroarchitektur setzt auch AMD eine mit Hyper-Threading vergleichbare Technik ein.