1

7 Die Superskalartechnik7.1 Befehlsbereitstellung

Ein Superskalarprozessor besteht aus einem Ausführungsteil und einem Befehlsbereitstellungsteil.

Beide Teile werden durch das Befehlsfenster voneinander entkoppelt.

Aufgabe des Befehlsbereitstellungsteils ist es, den Ausführungsteil mit genügend Befehlen zu versorgen.

Der Ausführungsteil wird von der Anzahl der Ausführungseinheiten und der Zuordnungsbandbreite bestimmt.

2

7.1.1 Code-Cache-Speicher

Die erste Stufe: Befehlsholestufe oder IF-Stufe: • Ein Befehlsblock wird aus dem nächst gelegenen Befehlsspeicher, i.e. Code-Cache-

Speicher, geholt und in einen Befehlspuffer geschrieben.

Harvard-Cache-Architektur• separate Code- und Daten-Cache-Speicher, • jeweils eigene Speicherverwaltungseinheiten und • separate Zugriffspfade für Befehle und Daten

Selbstmodifizierender Code ist auf heutigen Superskalarprozessoren nicht effizient implementierbar.

Organisation eines Code-Cache-Speichers ist einfacher als diejenige eines Daten-Cache-Speichers

Code-Cache-Speicher: 8 – 64 KByte On-Chip-Cache-Speicher, direkt-abgebildet oder zwei- bis vierfach satzassoziativer Cache

3

7.1.2 Befehlsholestufe

Probleme für die Befehlsholestufe entstehen durch die Steuerfluss-befehle, die das lineare Weiterschalten des Befehlszählers unterbrechen.

• Steuerflussbefehl kann zu Anfang oder in der Mitte eines Befehlsblocks stehen.

Ähnliches Problem, wenn die Befehlszähleradresse durch eine vorangegangene Steuerflussänderung nicht auf den Beginn eines Cache-Blocks im Code-Cache-Speicher zeigt.

• Man spricht dann von einem nicht ausgerichteten Cache-Zugriff (non aligned). • Hardware-Lösung: selbstausrichtende Code-Cache-Speicher (self-aligned

instruction caches): lesen und konkatenieren zweier aufeinander folgender Cache-Blöcke innerhalb eines Taktes

Vorabladen der Befehle aus dem Cache-Speicher in einen Befehlspuffer zur Decodierstufe entkoppelt die Befehlsholestufe von der Decodierstufe.

4

Befehlsholestufe zukünftiger Superskalarprozessoren mit hohen Zuordnungsbandbreiten

Notwendig: pro Takt Befehle aus mehreren, nicht aufeinander folgenden Code-Cache-Blöcken bereitstellen

Lösungen:• mehrere Befehlsholeeinheiten • verschränkte Code-Cache-Speicher • Mehrkanal-Cache-Speicher • Trace-Cache-Speicher

5

7.1.3 Trace Cache

Ein Trace ist eine Folge von Befehlen, die an einer beliebigen Stelle des dynamischen Befehlsablaufs starten und sich über mehrere Grundblöcke, d.h. über mehrere Sprungbefehle hinweg, erstrecken kann.

Bei Voranschreiten einer Programmausführung werden die aus dem Code-Cache geladenen Traces im Trace Cache abspeichert.

Wird die entsprechende Befehlsfolge erneut ausgeführt, so werden die Befehle nicht mehr dem Code-Cache, sondern dem Trace Cache entnommen.

Ein Trace Cache enthält die dynamischen Befehlsablauffolgen, während der Code-Cache-Speicher die statischen Befehlsfolgen speichert.

I -c a c h e T ra c e C a c h e

6

Trace Cache (2)

Trace-Cache-Füllung nicht auf einem kritischen Pfad in der Pipeline.

Trace im Trace Cache kann sogar bereits Befehle aus mehreren Sprungvorhersagen umfassen.

Sprungspekulation kann durch eine Next-Trace-Spekulation ergänzt werden

Eine erste Implementierung eines Trace Cache im Intel Pentium-4:• Verzicht auf den Code-Cache • im Falle eines Trace-Cache-Fehlzugriffs werden die Befehle direkt aus dem

Sekundär-Cache geladen.

7

7.2 Sprungvorhersage und spekulative Ausführung7.2.1 Grundlagen

Exzellente Sprungvorhersage ist sehr wichtig, da viele Befehle in verschiedenen Ausführungszuständen im Superskalarprozessor

Bedingungen für eine exzellente Sprungvorhersage:• Die Sprungrichtung muss möglichst rasch festgestellt werden

(branch resolution),• Sprungzieladress-Cache (BTAC),• Sprungvorhersage mit hoher Genauigkeit und spekulative

Befehlsausführung, • häufig muss ein weiterer Sprung vorhergesagt werden, obwohl

der Ausgang des vorhergehenden Sprungs noch nicht bekannt ist, • schneller Rückrollmechanismus mit geringem

Fehlspekulationsaufwand (misprediction penalty)

8

Kosten für das Rückrollen einer Fehlspekulation - Misprediction Penalty

Misprediction penalty hängt ab von: • Pipelinelänge (kürzere besser als längere), • Bei manchen Prozessoren ist es nicht möglich Befehle aus internen Puffern

zu löschen, d.h., auch wenn Befehle als ungültig erkannt werden, müssen diese ausgeführt und dann von der Rückordnungsstufe verworfen werden.

• dynamische Einflüsse wie z.B. die Anzahl der spekulativen Befehle im Befehlsfenster oder dem Rückordnungspuffer.

• Typischerweise können aus diesen meist recht großen Puffern immer nur eine kleine Anzahl Befehle pro Takt gelöscht werden.

Kosten für das Rückrollen selbst bei einfachen RISC-Pipelines meist bei zwei oder mehr Takte.

• 11 oder mehr Takte beim Pentium II und dem Alpha 21264 Prozessor

9

Statische Sprungvorhersage

Die statische Sprungvorhersage sagt für einen bestimmten Sprungbefehl immer dieselbe Richtung voraus.

Hardware-fixe oder compiler-beeinflussbare Vorhersagen. Einfache hardware-fixe Vorhersagen:

• Predict always not taken• Predict always taken• Backward branch predict taken, forward branch predict

not taken compiler-beeinflussbare Vorhersagen: Opcode-Bits (branch

hints) können die Richtung beeinflussen.

10

7.2.2 Dynamische Sprungvorhersagetechniken

Bei der dynamischen Sprungvorhersage wird die Entscheidung über die Spekulationsrichtung in Abhängigkeit vom bisherigen Programmablauf getroffen.

Die Sprungverläufe werden beim Programmablauf in Sprungverlaufstabellen gesammelt und auf der Grundlage der Tabelleneinträge werden aktuelle Sprungvorhersagen getroffen.

Bei Fehlspekulationen werden die Tabellen per Hardware abgeändert.

Im Allgemeinen liefern dynamische Verfahren bessere Vorhersagen als die statischen.

11

Dynamische Sprungvorhersagetechniken

Es wird zusätzlich die Sprungzieladresse genötigt Sprungzieladress-Cache

Mögliche Implementierungstechnik: Erweiterung des Sprungziel-adress-Cache um die zusätzlichen Bits der Sprungverlaufstabelle.

Normalfall: der Sprungzieladress-Cache und die Sprungverlaufs-tabelle bleiben getrennte Hardware-Einrichtungen.

unterschiedliche Organisation: • Sprungzieladress-Cache ist meist ein vollassoziativ organisierter Cache-

Speicher, der die gesamte Sprungbefehlsadresse zur Identifikation eines Eintrags speichert.

• Eine Sprungverlaufstabelle wird über einen Teil der Sprungbefehlsadresse adressiert und enthält dann nur das oder die Vorhersagebit(s) als Einträge. Üblicherweise werden die niederwertigen Bits der Befehlsadresse genommen, um einen Eintrag zu adressieren.

12

Fehlspekulation kann es aus drei Gründen geschehen

Warmlaufphase nach dem Programmstart: Qualität der dynamischen Sprungvorhersage wird erst zunehmend genauer

Spekulation für den Sprung wird falsch vorhergesagt, da der Sprung eine unvorhergesehene Richtung nimmt.

Interferenz (branch interference, aliasing) zwischen zwei Sprungbefehlen:Durch die Indizierung der im Speicherplatz beschränkten Sprungverlaufstabelle wird die Verlaufsgeschichte eines anderen Sprungbefehls miterfasst.

13

Interferenzen

Der Index zur Adressierung eines Tabelleneintrags besteht aus einem Teil der Sprungbefehlsadresse.

Wenn zwei Sprungbefehle in dem betreffenden Adressteil dasselbe Bitmuster aufweisen, werden sie bei den einfachen Verfahren auf den gleichen Eintrag abgebildet.

Kleine Sprungverlaufstabellen häufige Fehlvorhersagen Die Anzahl der Interferenzen lässt sich verringern, wenn die

Sprungverlaufstabelle vergrößert wird. Idealfall: jeder Sprungbefehl hat einen eigenen Eintrag in der

Sprungverlaufstabelle Interferenzen ganz vermieden für beliebig große Programme nicht möglich (Chip-Platz).

14

7.2.3 Ein- und Zwei-Bit-Prädiktoren

NT

NTT

T

Predict TakenPredict Not

Taken

Ein-Bit-Prädiktor:

Speichert für jeden Sprungbefehl die zwei Zustände „genommen“ oder „nicht genommen“ in einem Bit speichert. Diese Zustände beziehen sich dabei immer auf die zeitlich letzte Ausführung des Sprungbefehls.

15

Ein-Bit vs. Zwei-Bit Prädiktor

Ein-Bit-Prädiktor sagt jeden Sprung am Ende einer Schleifeniteration richtig voraus, solange die Schleife iteriert wird.

Bei geschachtelten Schleifen erzeugt jede Iteration der äußeren Schleifen zwei Fehlvorhersagen der inneren Schleife.

Mit einem Zwei-Bit-Prädiktor wird bei geschachtelten Schleifen eine dieser zwei Fehlvorhersagen vermieden.

Zwei-Bit-Prädiktor: • zwei Bits pro Eintrag in der Sprungverlaufstabelle • vier Zustände „sicher genommen“ (strongly ta ken), „vielleicht ge nommen“

(weakly taken), „vielleicht nicht genom men“ (weakly not taken) und „sicher nicht genommen“ (strongly not taken).

• Befindet sich ein Sprungbefehl in einem „sicheren“ Vorhersagezustand, so sind zwei aufeinander folgende Fehlspekulationen nötig, um die Vorhersagerichtung umzudrehen.

Zwei-Bit-Prädiktor mit Sättigungszähler

NT

NTT

T

(11)

Predict Strongly

Taken

NT

T

NT

T

(00)

Predict Strongly

Not Taken

(01)

Predict Weakly

Not Taken

(10)

Predict Weakly

Taken

Zwei-Bit-Prädiktor mit Hysteresezähler

NT

NT

T

T

(11)

Predict Strongly

Taken

NT

T

NT

T

(00)

Predict Strongly

Not Taken

(01)

Predict Weakly

Not Taken

(10)

Predict Weakly

Taken

18

Zwei-Bit-Prädiktor

Die Technik der Zwei-Bit-Prädiktoren lässt sich leicht auf n Bits erweitern.

• Es zeigten sich jedoch keine Verbesserungen mehr.

Zwei-Bit-Prädiktor kann ebenfalls in einem Sprungzieladress-Cache implementiert werden, wobei jeder Eintrag um zwei Vorhersagebits erweitert wird,

oder getrennt: Sprungzieladress-Cache für die Zieladressen und eine separate Sprungverlaufstabelle für die Vorhersagen.

19

Zwei-Bit-Prädiktoren

Zwei-Bit-Prädiktoren sehr gut bei Programmen mit Schleifen mit vielen Iterationen (numerische Programmen wie die SPECfp-Benchmark-Programme).

Anzahl der Fehlspekulationen steigt bei allgemeinen, ganzzahlintensiven Programmen wie den SPECint-Benchmark-Programmen stark an, da die Schleifen häufig nur wenige Iterationen aufweisen, dafür aber viele if-then- und if-then-else-Konstrukte vorkommen.

Aufeinander folgende Sprünge sind oft in der Art des folgenden in C-Code geschriebenen Programmstücks voneinander abhängig (correlated):

if (d == 0) // Sprung s1

d = 1;

if (d == 1) // Sprung s2

...

20

Korrelation

der zweite Sprung immer dann genommen, wenn der erste genommen wurde.

Das ist eine Korrelationsinformation, die von Ein- und Zwei-Bit-Prädiktoren nicht genutzt werden kann.

von einem Ein-Bit- oder Zwei-Bit-Prädiktor kann sogar jeder Sprung falsch vorhergesagt werden (Beispiel siehe Buch S. 277)

if (d == 0) // Sprung s1d = 1;

if (d == 1) // Sprung s2...

21

7.2.4 Korrelationsprädiktoren

Zwei-Bit-Prädiktoren ziehen für eine Vorhersage immer nur den Verlauf des Sprungs selbst in Betracht.

Die Beziehungen zwischen verschiedenen Sprüngen werden nicht berücksichtigt.

Korrelationsprädiktoren (correlating predictors) berücksichtigen neben der eigenen Vergangenheit eines Sprungbefehls auch die Historie benachbarter, im Programmlauf vorhergegangener Sprünge.

Zwei-Bit-Prädiktoren nutzen nur self-history, Korrelationsprädiktoren nutzen zusätzlich neighbor history.

Notation: (m,n)-Prädiktor nutzt das Verhalten der letzten m Sprünge für die Auswahl aus 2m Prädiktoren, wobei jeder Prädiktor einen n-Bit-Prädiktor für einen einzelnen Sprung darstellt.

Sprungverlaufsregister oder BHR (Branch History Register): speichert die globale Vergangenheit der letzten m Sprünge in einem m-Bit-Schieberegister.

Der Inhalt des BHR wird als Adresse (index) benutzt, um eine Sprungverlaufstabelle oder PHT (Pattern History Table) zu selektieren.

22

Implementierung eines (2,2)-Prädiktors

...

...

...

...

...

...

P a tte rn H is to ry Tab le s P H Ts (2 -b it p red ic to rs)

...

...

1 1

B ran ch ad d re ss

1 0

0B ran ch H is to ry R eg is te r B H R (2 -b it sh ift reg is te r) 1

se lec t

23

7.2.5 Zweistufig adaptive Prädiktoren (Überblick)

Die zweistufig adaptiven (two-level adaptive) Prädiktoren wurden von Yeh und Patt 1992 etwa zur gleichen Zeit wie die Korrelationsprädiktoren entwickelt.

Wie der Korrelationsprädiktor ist ein zweistufig adaptiver Prädiktor aus zwei Tabellenebenen aufgebaut, wobei der Eintrag in der ersten Tabelle dazu dient, die Vorhersagebits auf der zweiten Tabellenebene zu selektieren.

Varianten zweistufig adaptiver Prädiktoren nach Yeh und Patt 1993:

  global PHT

per-set PHTs

per-address PHTs

globale Schemata (global BHR) GAg GAs GAp

per-address-Schemata (per-address BHT)

PAg PAs PAp

per-set-Schemata (per-set BHT) SAg SAs SAp

24

7.2.6 gselect- und gshare-Prädiktoren

Gselect-Prädiktor: Konkatenation einiger Adressbits des Sprungbefehls mit dem BHR- Inhalt für die Selektion des PHT-Eintrags,

Gshare-Prädiktor: bitweise Exklusiv-Oder-Verknüpfung einiger Adressbits des Sprungbefehls mit dem BHR- Inhalt.

gshare etwas besser als gselect

Adressteil des

Sprungbefehls BHR gselect4/4 gshare8/8

00000000 00000001 00000001 00000001

00000000 00000000 00000000 00000000

11111111 00000000 11110000 11111111

11111111 10000000 11110000 01111111

25

7.2.7 Hybridprädiktoren

Ein Kombinations- (combining) oder Hybridprädiktor besteht aus zwei unterschiedlichen Prädiktoren und einem Selektorprädiktor, der für jede Sprungvorhersage eine der beiden Vorhersagen auswählt.

Als Selektorprädiktor kann wiederum ein beliebiger Prädiktor eingesetzt werden.

Beispiele:• McFarling: Zwei-Bit-Prädiktor mit einem gshare-Prädiktor ,• Young and Smith: compilerbasierte statische

Sprungvorhersage mit einen zweistufig adaptiven Prädiktor• und viele weitere Kombinationen!

Hybridprädiktoren oft besser als einzelne Prädiktoren.

26

Simulations of Grunwald 1998

committed conditional takenApplication instructions branches branches (in millions) (in millions) (%) SAg gshare combining

compress 80.4 14.4 54.6 10.1 10.1 9.9gcc 250.9 50.4 49.0 12.8 23.9 12.2perl 228.2 43.8 52.6 9.2 25.9 11.4go 548.1 80.3 54.5 25.6 34.4 24.1m88ksim 416.5 89.8 71.7 4.7 8.6 4.7xlisp 183.3 41.8 39.5 10.3 10.2 6.8vortex 180.9 29.1 50.1 2.0 8.3 1.7jpeg 252.0 20.0 70.0 10.3 12.5 10.4mean 267.6 46.2 54.3 8.6 14.5 8.1

misprediction rate(%)

SAg, gshare und MCFarling‘s Hybridprädiktor

27

Weitere Resulte

Simulationen von Keeton et al. 1998 mit einer OLTP (online transaction processing) Last auf einem PentiumPro Multiprozessor: Fehlvorhersagerate von 14% und einen Sprungbefehlsanteil von 21%.

Daraus lassen sich zwei verschiedenartige Schlüsse ziehen: • Sprungvorhersagetechniken weiter zu verbessern • und/oder nicht alle Sprünge sind vorhersagbar.

Falls Sprünge von irregulären Eingaben abhängen, so ist auch das Sprungverhalten irregulär und damit kaum vorhersagbar.

Lösungen für nicht vorhersagbare Sprünge sind die Prädikation und die Mehrpfadausführung.

28

7.2.8 Zuverlässigkeitsabschätzung

Zuverlässigkeitsabschätzung (confidence estimation) ist eine Technik, um die Verlässlichkeit einer Sprungvorhersage zu bewerten.

Ein Zuverlässigkeitsschätzer (confidence estimator) bestimmt die Vorhersagequalität der Sprungvorhersage eines Sprungbefehls für eine spezielle Sprungvorhersagetechnik.

vier Zuverlässigkeitsklassen:• korrekt vorhergesagt mit großer Zuverlässigkeit (Correctly predicted with

High Confidence C(HC) ) • korrekt vorhergesagt mit geringer Zuverlässigkeit (Correctly predicted with

Low Confidence C(LC) )• falsch vorhergesagt mit großer Zuverlässigkeit (Incorrectly predicted with

High Confidence I(HC) ) und • falsch vorhergesagt mit geringer Zuverlässigkeit (Incorrectly predicted with

Low Confidence I(LC) ).

Einsatz der Zuverlässigkeitsschätzung für die Spekulationssteuerung!

29

Implementierung eines Zuverlässigkeitsschätzers

Information aus den Sprungverlaufstabellen genutzt Smith [1981]: Sättigungszähler für die Konstruktion eines

Zuverlässigkeitsschätzers zu nutzen. • agressivere Spekulation durchführen, wenn das Zuverlässigkeitsniveau höher

ist.

JRS (Jacobsen, Rotenberg, Smith) Zuverlässigkeitsschätzer: benutzt zusätzlich zur Sprungvorhersage eine sogenannte MDC (Miss Distance Counter table).

• Bei jeder Sprungvorhersage wird der MDC-Wert mit einem Schwellenwert verglichen. Falls der MDC-Wert höher als der Schwellwert ist, wird die Zuverlässigkeit der Sprungvorhersage als hoch eingeschätzt bzw. umgekehrt.

Tyson et al. [1997]: eine kleine Zahl von Sprungverlaufsmustern führt üblicherweise bei einem PAs-Prädiktor zu korrekten Vorhersagen.

• Zuverlässigkeitsschätzer beruht auf einem festen Satz von Bitmustern, denen eine hohe Zuverlässigkeit der Sprungvorhersage zugeordnet wird, während für alle anderen Muster eine niedrige Zuverlässigkeit angenommen wird

30

7.2.9 Weitere Prädiktoren zur Interferenzverringerung

Die Vorhersagegenauigkeit zweistufig adaptiver Prädiktoren dadurch verbessern, dass versucht wird, die Anzahl der PHT-Interferenzen zu verringern.

PHT-Interferenzklassen: • Neutrale Interferenzen (neutral interferences), durch die keine Änderung der

Vorhersage geschieht.• Destruktive Interferenzen (destructive interferences), bei denen von einem anderen

Sprungbefehl eine Fehlspekulation ausgelöst wird, die ohne diese Interferenz nicht passiert wäre.

• Positive Interferenzen (positive interferences), bei denen durch eine Interferenz eine Fehlspekulation vermieden wird.

Ziel der neuen Prädiktoransätze: destruktive in neutrale Interferenzen verwandeln Lösungen:

• Anzahl der Einträge der Prädiktortabellen, insbesondere der PHT, zu vergrößern, um jeden Sprungbefehl auf einen anderen Eintrag abzubilden,

• das Verfahren zur Selektion eines PHT-Eintrags zu verbessern, um die Einträge besser über die gesamte Tabelle zu verteilen und

• die Sprungbefehle so in verschiedene Klassen zu unterteilen, dass sie nicht dasselbe Prädiktorschema benutzen.

31

7.2.10 Prädikation

Idee: statt einer Sprungspekulation die Befehle beider Sprungrichtungen ausführen und im Nachhinein die fälschlicherweise ausgeführten Befehle verwerfen

zwei Architekturerweiterungen notwendig:• Prädikatsregister (werden von Vergleichsbefehlen gesetzt)• möglichst alle Befehle des Befehlssatzes müssen diese

Prädikatsregister im Befehlsformat ansprechen können

Falls alle Befehle eines Befehlssatzes prädikativ sind, so spricht man von einem voll prädikativen Befehlssatz.

32

Beispiel für Prädikation

if (x==0) { // branch b1

a=b+c;

d=e-f; }

g=hi; // instruction independent of branch b1...

(Pred = (x==0)) // replaces branch b1:

// Pred is set to true if x==0

if Pred then a=b+c; // The operations are only performed

if Pred then d=e-f; // if Pred is set to true

g=hi;

33

Prädikation: Vor- und Nachteile

+ Prädikation ermöglicht es, bedingte Sprungbefehle aus dem Maschinencode zu eliminieren.

+ Eine Fehlspekulation ist nicht mehr möglich, die Kosten für das Rückrollen und Neuaufsetzen der Befehlsausführung wird eingespart.

+ Die Grundblocklänge wird vergrößert; Compiler erhält mehr Spielraum für eine Optimierung der Befehlsanordnung.

– Prädikation führt zu unnötigen Befehlsausführungen.– Prädikation benötigt zusätzliche Bits im Befehlsformat. Prädikation eingesetzt bei

• Signalprozessoren; • IA-64-Befehlssatz und Befehlssatz der ARM-Prozessoren sind voll prädikativ.• Alpha-, MIPS-, PowerPC- und SPARC-Befehlssätze enthalten prädikative

Ladebefehle.

34

7.2.11 Mehrpfadausführung

Bei der Mehrpfadausführung (multipath) oder Eager Execution werden nach einem bedingten Sprung beide möglichen Ausführungspfade in die Pipeline geladen und ausgeführt.

Sobald Sprungrichtung entschieden werden alle Befehlsresultate und noch in der Pipeline befindlichen Befehle des nicht genommenen Ausführungspfades gelöscht.

Mehrpfadausführung vermeidet Fehlspekulationen. Mehrpfadausführung noch selten implementiert, wird durch

Prädikation ersetzt.

35

7.2.12 Vorhersage bedingter Sprungbefehle mit indirekter Adressierung

Sprungvorhersagetechniken betreffen nur bedingte Sprungbefehle mit befehlszählerrelativer Adressierung

Bei der befehlszählerindirekten Adressierung wird die Sprungzieladresse einem Register entnommen und kann sich vor jeder Ausführung des Sprungbefehls erneut ändern.

Solche Sprünge sind wesentlich schwerer vorherzubestimmen. Kommen vor in Compilaten von objektorientierten Programmiersprachen

• z.B. Tabellen virtueller Funktionen

Mögliche Realisierung wäre, die PHT so zu erweitern, dass die Sprungzieladresse mit enthalten ist.

In heutigen Prozessoren nicht vorhanden.

7.2.13 Stand der Technik Prädiktortechnikkeine Sprungvorhersagestatische Sprungvorhersagen:nie genommen immer genommen rückwärts genommen, vorwärts nicht

genommencompilerbasiertdynamische Sprungvorhersagen: 1-Bit-Prädiktor2-Bit-Prädiktorzweistufig adaptive PrädiktorengshareHybridprädiktorenPrädikation

begrenzte Mehrpfadausführung

Implementierungsbeispiele

Intel 8086, praktisch alle 8- und 16-Bit-controlller

Intel i486

Sun SuperSPARC

HP PS-7x00

frühe PowerPC-Prozessoren

DEC Alpha 21064, AMD K5

PowerPC604, MIPS R10000, Cyrix 6x86, M2, …

Intel PentiumPro, Pentium II, AMD K6

Intel Pentium III, AMD Athlon

DEC Alpha 21264

Intel IA-64: Itanium und Nachfolger, ARM- Prozessoren, TI TMS320C6201 und viele weitere Signalprozessoren

IBM-Großrechner: IBM 360/91, IBM 3090

37

7.3 Decodierung und Registerumbenennung 7.3.1 Decodierung

Um eine hohe Verarbeitungsleistung zu erzielen, muss der Prozessor mindestens so viele Befehle bereitstellen und decodieren wie die Zuordnungsbandbreite beträgt.

• Decodierbandbreite = Bandbreite der Befehlsbereitstellung.

Befehlsformat fester Länge erleichtert Decodieren mehrerer Befehle pro Takt. Variable Befehlslängen mehrstufige Decodierung angewandt.

• erste Decodierstufe: Grenzen der Befehle bestimmen• zweite Decodierstufe: Befehle decodieren und aus jedem Befehl einen oder mehrere

Mikrobefehle erzeugen

Komplexe CISC-Befehle werden in einfachere Befehle aufgespalten, die mit den RISC-Befehlen vergleichbar sind.

38

7.3.2 Registerumbenennung

Ziel der Registerumbenennung: scheinbare Datenabhängigkeiten (name dependences) zwischen Registeroperanden beseitigen.

• Scheinbare Datenabhängigkeiten: Gegenabhängigkeiten und Ausgabeabhängigkeiten Die Registerumbenennung kann erfolgen:

• auf statische Weise (durch den Compiler) oder • auf dynamische Weise (per Hardware).

Dynamischen Registerumbenennung: jedem im Befehl spezifizierten Zielregister wird ein noch nicht belegtes physikalisches Register zugeordnet.

Ausgabe- und Gegenabhängigkeiten zwischen Registeroperanden werden automatisch beseitigt.

Nachfolgende Befehle, die auf dasselbe Architekturregister als Operandenregister zugreifen, erhalten bei der Registerumbenennung das zuletzt zugeordnete physikalische Register als Eingabeoperand.

39

Dynamische Registerumbenennung- zwei Arten der Implementierung

Für jede Registerart sind zwei verschiedene Registersätze physikalisch auf dem Chip vorhanden:

• Architekturregister: speichern die „gültigen“ Registerwerte• Umbenennungspufferregister: nur für temporäre Resultatwerte • Bei der Registerumbenennung werden den Architekturregistern Umbenennungspufferregister

zugeordnet.

Für jede Registerart existiert nur ein Satz von so genannten physikalischen Registern, die in den Maschinenbefehlen nicht ansprechbar sind.

• speichern die temporären wie auch die bereits gültigen Werte. • Architekturregister werden dynamisch auf die physikalisch vorhandenen Register abgebildet. • Es gibt nur eine Abbildungstabelle pro Registerart, die Architekturregister sind als solche

physikalisch nicht vorhanden.

40

Implementierung der Registerumbenennungslogik

Diese Zuweisungen müssen für mehrere Befehle gleichzeitig durchgeführt werden

Map Table

Dependence Check Logic (Slice)

. . .

. . .

Logical Source Regs

Logical Dest Regs

Logical Source Reg R

Physical Source Regs

Physical Dest Regs

. . . MUX

Physical Reg Mapped

to Logical Reg R

41

7.4 Befehlszuordnung

Befehlsfenster (instruction window): alle Befehlspufferplätze zwischen Decodierung/Umbenennung und Ausführung

• Das Befehlsfenster entkoppelt den Befehlsbereitstellungs- und Decodierteil vom Ausführungsteil des Prozessors.

Befehle im Befehlsfenster sind • durch die Sprungvorhersage frei von Steuerflussabhängigkeiten • und durch die Registerumbenennung frei von Namensabhängigkeiten.

Befehlszuordnung (instruction issue) prüft in einem Takt, welche Befehle aus dem Befehlsfenster zugeordnet werden können und weist Befehle bis zur maximalen Zuordnungsbandbreite den Ausführungseinheiten zu.

Die Programmreihenfolge der zugewiesenen Befehle wird im Rückordnungspuffer vermerkt.

42

Begriffe

Zuordnung (issue) bezeichnet die Zuordnung zu den Ausführungeinheiten oder, falls vorhanden, zu den Umordnungspuffern (reservation stations) vor einer Ausführungseinheit oder einer Gruppe von Ausführungseinheiten.

Falls solche Umordnungspuffer vorhanden sind, so heißt die zweite Zuordnungsstufe Dispatch.

Zuordnungsstrategie (instruction-issue policy) beschreibt das Protokoll, mit dem Befehle für die Zuordnung ausgewählt werden.

Je nach Prozessor können die Befehle nur in sequenzieller Programmreihenfolge (in order) oder auch außerhalb der Reihenfolge (out of order) zugewiesen werden.

Die Vorausschaufähigkeit (lookahead capability) gibt an, wie viele Befehle im Befehlsfenster untersucht werden, um die als nächstes zuordenbaren Befehle zu finden.

Die Befehlszuordnungslogik, die feststellt, welche Befehle ausführbereit sind, wird oft auch als Scheduler bezeichnet.

43

Aktivierungslogik des Befehlsfensters

rdyL opd tagL opd tagR rdyR

OR = = = = OR

. . .

tagIW tag1

inst0

. . . rdyL opd tagL opd tagR rdyR instN-1

. . .

44

Selektionslogik

req0

gran

t0re

q1gr

ant1

req2

gran

t2re

q3gr

ant3

a n y req en ab le an y req en ab le an y req en ab le an y req en ab le

. . .

. . .Issu e W in d o w

req0

gran

t0re

q1gr

ant1

req2

gran

t2re

q3gr

ant3

a n y req en ab le

req0

req1

req2

req3 gr

ant0

gran

t1gr

ant2

gran

t3

A rb ite r C e llO R P rio rityE n co d e r

an y req en a b le

req0

gran

t0e n ab le

ro o t ce ll

fro m /to o th e r su b tree s

45

Organisationmöglichkeiten des Befehlsfensters

Einstufige Zuweisung und zentrales Befehlsfenster:

46

Organisationmöglichkeiten des Befehlsfensters (2)

Einstufige Zuordnung mit entkoppelten Befehlsfenstern:

47

Organisationmöglichkeiten des Befehlsfensters (3)

Mehrstufige Zuordnung und damit ein Befehlsfenster aus mehreren hintereinander gelagerten Befehlspuffern

Kombination einer mehrstufigen Zuordnung und entkoppelter Befehlsfenster:• Spezialfall: Zweistufige Zuweisung mit verteilten Umordnungspuffern:

48

7.5 Ausführungsstufen

In der oder den Ausführungsstufen werden die in den Opcodes der Befehle spezifizierten Operationen ausgeführt und die Resultate in Umbenennungspufferregistern oder physikalischen Registern gespeichert.

Meist gibt es mehrere spezialisierte Ausführungseinheiten auf dem Prozessor-Chip, die alle parallel zueinander arbeiten können.

Ausführungseinheiten benötigen für die Ausführung einer Operation: • einen Takt oder • mehrere Takte

- ohne Pipelining - intern selbst wieder mit Pipelining (arithmetische Pipeline oder Ausführungs-

Pipeline)

49

Arten von Ausführungseinheiten

Einzykleneinheiten (Latenz = 1, Durchsatz = 1): einfache Ganzzahl-, einfache Multimediaeinheiten

Mehrtakteinheiten (Latenz > 1) • (mehrstufige) Pipeline: in jedem Takt oder jedem zweiten Takt wird eine neue

Befehlsausführung gestartet (Durchsatz = 1 oder 1/2): komplexe Ganzzahl- und gleitkommaorientierte Multimediaeinheiten

• ohne Pipelining (Durchsatz = 1 / Latenz): Divisions-, Quadratwurzel- und komplexe Multimediaeinheiten

Einheiten mit variabler Taktzahl: Lade-/Speichereinheiten (mögliche Cache-Fehlzugriffe!!)

50

Lade-/Speichereinheiten

Für Lade- und für Speicherbefehle existieren oft zwei verschiedene Wege (Wartepuffer für stores) innerhalb der Lade-/Speichereinheit.

Die Speicherbefehle benötigen zusätzlich zur Adressrechnung auch noch den zu speichernden Wert.

Oft: Ladebefehle, können vor den Speicheroperationen ausgeführt werden, sofern nicht dieselbe Adresse betroffen ist.

 

51

Vorziehen eines Ladebefehls vor einen Speicherbefehl

Reihenfolge nach außen nicht mehr in Programmordnung

abgeschwächtes Konsistenzmodell

Nicht bei Spezialbefehlen (Synchronisationsbefehl, swap-Befehl oder markierter Befehl)

Üblicherweise nur falls Zieladressen in den überholten Befehle bereits berechnet

Jedoch sind „spekulativ“ ausgeführten Ladebefehle möglich Adresspuffer ARB (Address Resolution Buffer) und eventuell Rückrollen nötig

52

Lade-/Speichereinheiten

Ein Ladebefehl gilt als von der Lade-/Speichereinheit beendet (completed), wenn der zu ladende Wert in einem Pufferregister steht.

Eine Speicheroperation kann nicht mehr rückgängig gemacht werden!! Der Speicherbefehl kann erst „beendet“ werden, also der Wert wirklich in den

(Cache-)Speicher geschrieben werden, wenn er in der Rückordnungsstufe als „gültig“ markiert (committed) wird.

53

Multimediaeinheiten

Multimediaeinheiten führen mehrere gleichartige Operationen auf Teilen von Registersätzen gleichzeitig aus.

Subword Parallelism oder SIMD-Parallelität (Single Instruction Multiple Data).

Multimediaoperationen (videostromorientiert):• arithmetische oder logische Befehle auf gepackten Datentypen wie z.B. acht

8-Bit-, vier 16-Bit- oder zwei 32-Bit-Teilwörtern • Weiterhin: Packen und Entpacken in bzw. von Teilwörtern sowie Maskier-,

Selektions-, Umordnungs-, Konversions-, Vergleichsoperationen

Multimediaoperationen (grafikorientiert):• zwei (oder vier) 32-Bit-Gleitkommaoperationen gleichzeitig

54

7.6 Gewährleistung der sequenziellen Programmsemantik7.6.1 Rückordnungsstufe

In der Rückordnungsstufe werden:• die Resultate der Befehlsausführungen gültig gemacht oder verworfen, • das Rückrollen von falsch spekulierten Ausführungspfaden nach einem Sprung

überwacht • und präzise Unterbrechungen durchgeführt.

55

Begriffsunterscheidungen

Beendigung eines Befehls (completion): die Ausführungseinheit hat die Ausführung des Befehls abgeschlossen, das Resultat steht in einem Pufferregister und wird datenabhängigen Befehlen als Operand zur Verfügung gestellt.

Nach der Beendigung werden die Befehle in Programmordnung gültig gemacht (commitment): die Resultate können nicht mehr rückgängig gemacht werden und der Befehl wird aus dem Rückordnungspuffer entfernt.

Löschen eines Befehls (removement): der Befehl wird aus dem Rückordnungspuffer entfernt wird, ohne dass der Resultatwert weiter verwendbar ist.

Rückordnung (retirement): Entfernen des Befehls aus dem Rückordnungspuffer mit oder ohne das Gültigmachen des Resultats.

56

7.6.2 Präzise Unterbrechungen

Eine Unterbrechung (interrupt oder exception) wird als präzise bezeichnet, wenn der bei Ausführung der Unterbrechungsroutine gesicherte Prozessorzustand mit dem sequenziellen Ausführungsmodell der von-Neumann-Architektur konform geht, bei dem eine Befehlsausführung vollständig beendet ist, bevor mit der nächsten Befehlsausführung begonnen wird.

57

Bedingungen für eine präzise Unterbrechung

Alle Befehle, die in der Programmordnung vor dem Befehl stehen, der die Unterbrechung ausgelöst hat, sind vollständig ausgeführt worden und haben den Prozessorzustand entsprechend modifiziert.

Alle Befehle, die in der Programmordnung nach dem Befehl stehen, der die Unterbrechung ausgelöst hat, sind nicht ausgeführt worden und haben den Prozessorzustand nicht beeinflusst.

Falls die Unterbrechung von einem Ausnahmezustand bei der Befehlsausführung ausgelöst wurde, zeigt der Befehlszähler auf den Befehl, der die Unterbrechung ausgelöst hat. Je nach Art des Befehls sollte der auslösende Befehl noch vollständig ausgeführt oder vollständig aus der Pipeline gelöscht werden.

58

Klassen von Unterbrechungen

Programmunterbrechungen oder Traps: nicht statthaften Code, Privilegienverletzungen, Überlauf, Unterlauf, Division durch Null

• Diese fatalen Ausnahmen führen meist zu einem kontrollierten Programmabbruch durch die aktivierte Trap-Routine.

Programmunterbrechungen durch Seitenfehler oder TLB-Fehlzugriffe: Teil der normalen Ausführung

• der Befehl darf nicht ausgeführt werden sondern muss nach Ausführung der Unterbrechungsroutine wiederholt werden

Externe Unterbrechungen: von Quellen außerhalb des Prozessors ausgelöst: Ein-/Ausgabe- oder Zeitgeber-Unterbrechungen

• Weiterführen der Programmausführung durch Gewährleistung einer präzisen Unterbrechung nötig.

59

7.6.3 Rückordnungspuffer

Der Rückordnungspuffer (reorder buffer) speichert die Programmordnung der Befehle nach ihrer Zuordnung und ermöglicht die Serialisierung der Resultate (result serialization) während der Rückordnungsstufe.

Meist Bandbreite der Rückordnungseinheit dieselbe wie die Zuordnungsbandbreite.

Organisationsvarianten für Rückordnungspuffer:• enthält nur die Zustände der Befehlsausführungen • kann aber auch zusätzlich die Resultatwerte selbst enthalten

Alternative Verfahren:• Checkpoint Repair-Verfahren• History Buffer

60

7.7 Verzicht auf die Sequenzialisierung bei der Rückordnung

Die Rückordnung geschieht immer strikt in Programmordnung, um die vom von-Neumann-Prinzip geforderte Resultatserialisierung zu gewährleisten.

Rückordnung außerhalb der Programmordnung ist bei heutigen Superskalarprozessoren nicht zugelassen.

Einzige Ausnahme: das Vorziehen der Lade- vor die Speicherbefehle, das einige Prozessoren erlauben.

Superskalarprozessor muss nach außen hin wie ein einfacher von-Neumann-Rechner wirken

• Gut für Programmverifikation• Schlecht für parallele Verarbeitung