Dynamische Ablaufplanung mit Spekulativer Ausführung M

Prozessorarchitektur

Dynamische Ablaufplanung mit Spekulativer Ausführung

M. Schölzel

Steuerflussabhängigkeit

Es sei b eine bedingte Sprungoperation an der Adresse a mit Sprungziel z.

Eine Operation c ist nicht steuerflussabhängig von b, wenn die Ausführung von c nicht davon abhängt, ob b an Adresse z verzweigt oder nicht.

Ansonsten ist die Operation c steuerflussabhängig.

Beispiele:

c

b

c

b a:

a+1: z:

c nicht steuerflussabhängig von b

a+1: z:

a:

c nicht steuerflussabhängig von b

b1 a:

a+1: z:

c steuerflussabhängig von b1 und b2

b2

c

Beschränkungen durch Steuerflussabhängigkeiten

… bei statischer Ablaufplanung steuerflussabhängiger Operationen: Sei c steuerflussabhängig von b

Dann kann c nicht vor b ausgeführt

werden

… bei statischer Ablaufplanung nicht steuerflussabhängiger Operationen: Sei c eine nicht steuerflussabhängige

Operation vor b

Dann kann c nicht hinter b verschoben werden

c

b

b

b

c

c

b c

Performanceprobleme in Prozessoren mit tiefer Pipeline

Problem: − Ziel einer Sprungoperationen erst nach deren vollständiger Ausführung

bekannt − Bei tiefen Pipelines müsste das Holen der richtigen Operationen nach

dem Holen einer Sprungoperation lange angehalten werden

Lösung: − Kombination von Sprungvorhersage mit spekulativem Holen,

Dekodieren und Ausführen von Operationen

b Befehls- warteschlange

Speicher

Sprungoperation

PC

? Neue Adresse für PC noch nicht bekannt

zu Reservation Stations

Prinzip Sprungvorhersage

Für geholte Operation b von Adresse a wird sofort geprüft, ob es eine Sprungoperation ist

Falls ja, PC auf eine Adresse z setzen, die ein wahrscheinliches Sprungziel ist

Vorhergesagtes Sprungziel z wird der Operation mit in die Verarbeitung gegeben

Bis zur Beendigung der Ausführung von b werden weitere Operationen ab Adresse z spekulativ geholt

Nach Ausführung von b wird geprüft, ob tatsächliches Sprungziel mit z übereinstimmt − Ja: Alle spekulativ geholten Befehle weiter verarbeiten (sind nicht mehr spekulativ) − Nein: Alle spekulativ geholten Befehle aus der Pipeline löschen (falsche Befehle geholt)

b Befehls- warteschlange

Speicher PC

Keine Sprungoperation, dann PC inkrementieren; sonst PC auf

wahrscheinliches Sprungziel z setzen

Neue Adresse für PC

zu Reservation Stations

Sprungoperation?

Spekulative Ausführung

Tomasulo-Algorithmus unterstützt bereits spekulatives Holen und Dekodieren von Befehlen: − Holen und dekodieren kann leicht revidiert werden − Zustand der Architekturregister und/oder des Speichers wurde nicht geändert

Problem beim Ausführen spekulativ geholter Operationen:

− Änderung des Datenflusses (Zustand von Architekturregistern/Speicher wird geändert) − Verhalten bei Exceptions kann sich ändern

Beispiel:

b

c

b c

Teil des Steuerflussgraphs des Programms

Spekulativ ausgeführter

Programmzweig

Tatsächlich auszuführender Programmzweig

Könnte bei dynamischer Ablaufplanung zur

Ausführung von c vor b führen

Beispiele (Fortsetzung)

Veränderung des Datenflusses c wird spekulativ vor b ausgeführt

mul-Operation erhält Wert in r1 jetzt

von sub- statt von add-Operation

Veränderung der Exceptions c wird spekulativ vor b ausgeführt

Division durch 0 möglich

b c a add r1 <- r2,r3

sub r1 <- r4,r5

mul r0 <- r1,r6

schreibt nicht in

r1 c

b c a

if r5 = 0 then x else y div r1 <- r4,r5

Keine Division

ausführen c

x: y:

Lösung

WB-Phase aus Tomasulo-Algorithmus in zwei Schritte zerlegen: − Weiterleiten von Ergebnissen zu RSs (WB-Phase) − Schreiben in Architekturregister (Commit-Phase)

Dadurch :

− Ausführen der Instruktion und Verwendung der Ergebnisse möglich, ohne Register-/Speicherwerte fälschlicherweise zu überschreiben

Realisierung durch: − Reorder-Buffer zum Puffern von Ergebnissen, die in WB-Phase

geschrieben werden (insbesondere spekulativ errechneter Ergebnisse) − Zurückschreiben der gepufferten Ergebnisse aus dem Reorder-Buffer in-

oder erst dann, wenn Ergebnis nicht mehr spekulativ ist

Architektur für Tomasulo mit spekulativer Ausführung

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…

Operandenbus A Operationsbus

EU-Bus EU-Bus EU-Bus

Reorder Buffer

Arch

itekt

urre

gist

er

Reorder Buffer (ROB)

Organisiert als Warteschlange: − Einreihen einer Operation durch

• Reservieren eines Eintrags in der Warteschlange während der Ausgabe der Operation • last auslesen und inkrementieren (modulo)

− Abschließen der Operation in-order durch Ausgeben des gepufferten Ergebnisses an Architekturregister

• Entnehmen der Operation aus der Warteschlange • first-Position auslesen und inkrementieren

Schreiben des Ergebnisses einer Operation während der WB-Phase an die reservierte Position

Einträge im ROB haben Funktion der virtuellen Register

Eintrag 1

Eintrag 2

Eintrag n

DeM

ux

Mux

Reservierte Position von RS

first last

Ergebnisbus …

Zu d

en

Arch

itekt

urre

gist

ern

Bypass zu den RS

Zur D

ecod

e-Ph

ase busy

Einträge im ROB

Aufbau eines Eintrages

Bedeutung der Felder abhängig von Operation

Unterscheidung nach: − Sprungoperationen − Speicheroperation (Schreiben in den Speicher) − ALU-Operationen

Feld/Bedeutung res addr type busy valid

Sprungoperation Berechnetes Sprungziel (wird in PC geschrieben)

c = Spekulation war korrekt w = Spekulation war falsch

3 Eintrag belegt 0 = Ergebnis wird noch berechnet 1 = Ergebnis steht bereit Speicheroperation Wert, der in den Speicher

zu schreiben ist Adresse an die res geschrieben werden soll

2

ALU-Operation Ergebnis der Operation - 1

res type addr valid busy

Reservation Station

RS behält bisherige Funktion (wie bei Tomasulo): − Puffert Operation, bis alle Operanden bereitstehen

− Puffert Operanden, sobald sie berechnet wurden

Identifikation noch nicht berechneter Quelloperanden jetzt über ROB-Eintrag (Registerumbenennung)

opc …

Qj Qk Vj Vk busy

opc Qj Qk Vj Vk busy

opc Qj Qk Vj Vk busy

Reservation Station

Operandenbus B


EU-Bus

Auszuführende Operation (z.B. add, sub, mul, …) Qj = x, wenn ROB-Eintrag x das Ergebnis für Operand A bekommt, sonst 0

Qk = x, wenn ROB-Eintrag x das Ergebnis für Operand B bekommt, sonst 0

Wert für Operand B Wert für Operand A

ROB-Eintrag, der das Ergebnis der Operation bei WB aufnimmt

type type

type

Typ der Operation (siehe Tabelle auf voriger Folie)

DeM

ux

Mux

rob rob

rob

RS ist belegt/frei

stat stat

stat

Status der Ausführung (RO, EX, WB)

misc misc

misc

Für verschiedene Daten

Registerbankerweiterung

Architekturregister n speichert ROB-Eintrag, der letzten Operation, die den Wert für n berechnet (Registerumbenennung)

Ermöglicht die Abbildung von Architekturregistern auf virtuelle Register (ROB-Einträge)

Beispiel:

Reg 0 Reg 1 Reg 2

Reg r

…

rob rob rob

rob

Reg[n].rob = x, wenn ROB-Eintrag x das Ergebnis der letzten Operation aus dem Befehlsstrom enthält, die gerade den Wert für Reg n berechnet, sonst 0

Operandenbus B Operandenbus A

Ergebnisbus

Reg 0 Reg 1 Reg 2

Reg r

…

5 0 1

0

ROB-Eintrag 5 enthält letzte Operation mit Zielregister 0

ROB-Eintrag 1 enthält letzte Operation mit Zielregister 2

Register 1 wird gerade von keiner Operation berechnet

Überblick Pipeline-Phasen

Issue − Vorderste Operation aus der Warteschlange ausgeben − Operandenwerte auslesen bzw. Register umbenennen (WAR- und WAW-Hazard auflösen) − Ausgabe erfolgt in-order

Execute

− Warten auf Operanden und auf Verfügbarkeit der EU − Operationen ausführen, sobald Operanden verfügbar und EU frei (RAW-Hazard auflösen) − Ausführung ist out-of-order

Write-Back

− Ergebnis über Ergebnisbus in ROB schreiben − WB ist out-of-order

Commit

− Ergebnisse werden aus dem ROB in der Reihenfolge in der die Plätze allokiert wurden, in die Zielregister geschrieben (korrekten Datenfluss und korrekte Exceptions garantieren)

− Commit ist in-order

Überblick Pipeline-Phasen (Issue)

Vorderste Operation aus der Warteschlange holen und an eine Reservation Station und die assoziierte EU ausgeben, falls − RS ist frei und − ROB ist nicht voll

Sonst Issue-Phase anhalten

Operanden lesen, falls diese

− In Registerbank vorhanden oder − Im ROB vorhanden

RS und ROB-Eintrag als allokiert markieren

ROB-Index übernimmt Funktion

des virtuellen Registers

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



Reorder Buffer

Arch

itekt

urre

gist

er

Op A

Op A

reservierter Platz für Op A

Überblick Pipeline-Phasen (Execute)

Operation wartet in RS auf Operanden und auf Verfügbarkeit der EU

Operation ausführen, sobald Operanden verfügbar und EU frei

RS speichert Status der Operation während der Ausführung

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



Reorder Buffer

Arch

itekt

urre

gist

er

Op A

Op A


Überblick Pipeline-Phasen (Write-Back)

Ergebnis über Ergebnisbus in ROB schreiben

Zu verwendender ROB-Eintrag wurde in RS gespeichert

Alle Reservation-Stations, die den Wert brauchen, lesen ihn auch vom Ergebnisbus (wird identifiziert durch ROB-Eintrag = virtuelle Register)

RS freigeben

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



Reorder Buffer

Arch

itekt

urre

gist

er

Op A

reservierter Platz für Op A Ergebnis

Überblick Pipeline-Phasen (Commit)

Ergebnisse werden aus dem ROB in der Reihenfolge in der die Plätze allokiert wurden, in die Zielregister geschrieben

ROB-Eintrag freigeben

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



Reorder Buffer

Arch

itekt

urre

gist

er


Ergebnis

Issue-Phase – Details (ALU-Operation)

Für vorderste Operation in Warteschlange sei: − opc … die auszuführende Operation (add, sub, mul, …) − src1, src2 … die zwei Quelloperanden (Register) − dst … der Zieloperand (Register)

Ausgabe möglich, falls

− es ex. x mit RS[x].busy = 0 und − ROB[last].busy = 0

Aktualisierung nach Zuteilung

− if Reg[src1].rob = 0 then // Linken Operanden bereitstellen RS[x].Qj := 0; RS[x].Vj := Reg[src1] // Linker Operand ist in Registerbank else // Linker Operand wird noch berechnet/ist in ROB if ROB[Reg[src1].rob].valid = 1 then RS[x].Qj := 0; RS[x].Vj := ROB[Reg[src1].rob].res // Ergebnis im ROB; also aus ROB lesen else RS[x].Qj := Reg[src1].Qj // Ergebnis wird noch berechnet; also warten fi

− if Reg[src2].rob = 0 then // Analog Bereitstellen des rechten Operanden …

− RS[x].busy := 1; RS[x].rob := tail RS[x].opc := opc; RS[x].type := 1; RS[x].status := RO

Issue-Phase – Details (Beispiel 1)

Situation: − Op kann ausgegeben werden − Wert von r1 wird aus Registerbank gelesen − Wert von r2 kommt aus ROB

Aktualisierung nach Ausgabe − if Reg[srcy].rob = 0 then

RS[x].Qj/k := 0; RS[x].Vj/k := Reg[srcy] else if ROB[Reg[srcy].rob].valid = 1 then RS[x].Qj/k := 0; RS[x].Vj/k := ROB[Reg[srcy].rob].res else RS[x].Qj/k := Reg[src1].Qj/k fi

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [56,-,1,1,1]

5: [-,-,-,0,0]

add r0 <- r1, r2 // Op A sub r3 <- r0, r1 // Op B …

OP A


R0: 5 R1: 14 R2: 89 R3: 17

0 0 4 0


Situation: − Op A wurde ausgegeben − verwendeter ROB-Eintrag: 5

Aktualisierung nach Ausgabe − if Reg[srcy].rob = 0 then

RS[x].Qj/k := 0; RS[x].Vj/k := Reg[srcy] else if ROB[Reg[srcy].rob].valid = 1 then RS[x].Qj/k := 0; RS[x].Vj/k := ROB[Reg[srcy].rob].res else RS[x].Qj/k := Reg[src1].Qj/k fi

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

[add,0,0,14,56,-,1,5,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [56,-,1,1,1]

5: [-,-,1,0,1]



opc Qj Qk Vj Vk busy type rob stat misc

R0: 5 R1: 14 R2: 89 R3: 17

5 0 4 0


Situation: − Ausgabe von Op A − Wert von r1 wird aus Registerbank gelesen − Auf Wert von r2 muss gewartet werden

Aktualisierung nach Ausgabe:

− if Reg[srcy].rob = 0 then RS[x].Qj/k := 0; RS[x].Vj/k := Reg[srcy] else if ROB[Reg[srcy].rob].valid = 1 then RS[x].Qj/k := 0; RS[x].Vj/k := ROB[Reg[srcy].rob].res else RS[x].Qj/k := Reg[src1].Qj/k fi W

arte

- sc

hlan

ge

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,100,-,-,2,4,RO,1]

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [-,-,1,0,1]

5: [-,-,-,0,0]


OP A



R0: 5 R1: 14 R2: 89 R3: 17

0 0 4 0


Situation: − Op A wurde ausgegeben − Verwendeter ROB-Eintrag: 5 − Auf Wert von r2 muss gewartet werden

Aktualisierung nach Ausgabe:

− if Reg[srcy].rob = 0 then RS[x].Qj/k := 0; RS[x].Vj/k := Reg[srcy] else if ROB[Reg[srcy].rob].valid = 1 then RS[x].Qj/k := 0; RS[x].Vj/k := ROB[Reg[srcy].rob].res else RS[x].Qj/k := Reg[src1].Qj/k fi W

arte

- sc

hlan

ge

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,100,-,-,2,4,RO,1]

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [-,-,1,0,1]

5: [-,-,1,0,1]




R0: 5 R1: 14 R2: 89 R3: 17

0 0 4 0

[add,0,4,14,-,-,1,5,RO,1]

Execute– Details

Ausführung der Operation von RS möglich, falls − RS[x].status = RO und − RS[x].Qj = 0 und RS[x].Qk = 0

Aktualisierung nach Beginn der Ausführung: − Berechnung mit den Werten in RS[x].Vj und RS[x].Vk starten − RS[x].status := EX

Aktualisierung nach Ende der Ausführung: − RS[x].Vj := res // Feld für Ergebnis missbrauchen − RS[x].status := WB

Execute-Phase – Details (Beispiel 3)

Beide Operanden stehen bereit: − RS[x].status = RO und − RS[x].Qj = 0 und RS[x].Qk = 0

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,100,-,-,2,4,RO,1]

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



1: 0 0 4

0

2:

3:

4: [-,-,1,0,1]

5:


OP A




Operation ist in Ausführung: − RS[x].status = EX

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,100,-,-,2,4,EX,1]

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



1: 0 0 4

0

2:

3:

4: [-,-,1,0,1]

5:


OP A




Ergebnis ist berechnet: − Ergebnis befindet sich in Vj − RS[x].status = WB

Ergebnis ist bereit für WB-Phase

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,89,-,-,2,4,WB,1]

…

Execute 1

RS RS

RS

…

Execute m

RS RS

RS

…

Reg 0 Reg 1 Reg 2

Reg r

Ergebnisbus

Operandenbus B

…

…

…



1: 0 0 4

0

2:

3:

4: [-,-,1,0,1]

5:


OP A



Write-Back– Details (ALU-Operation)

Write-Back des Ergebnisses res der Operation von RS x möglich, falls − RS[x].status = WB und − Ergebnisbus verfügbar

Aktualisierungen durch WB: − ROB[RS[x].rob] := RS[x].Vj // Ergebnis in ROB-Eintrag kopieren − RS[x].busy := 0 // RS freigeben − ROB[RS[x].rob].valid := 1 // ROB-Eintrag als gültig markieren

− for all y ¹ x: // Alle RS können den Wert übernehmen

if RS[y].Qj = RS[x].rob then RS[y].Vj := RS[x].rob; RS[y].Qj := 0 if RS[y].Qk = RS[x].rob then RS[y].Vk := RS[x].rob; RS[y].Qk := 0

Write-Back-Phase – Details (Beispiel 4)

Situation: − Ergebnis der ld-Operation wird zurückgeschrieben − Ergebnisbus transportiert:

• ROB-Eintrag • ROB-Wert

− add-Operation wartet auf den rechten Operanden

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

[ld,0,0,20,-,-,2,4,WB,1]

…

Execute 1

[add,0,4,14,-,-,1,5,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [-,-,1,0,1]

5: [-,-,1,0,1]


OP B


(4,89)


R0: 5 R1: 14 R2: 89 R3: 17

5 0 4 0

Write-Back-Phase – Details (Beispiel 4)

Situation: − Wert wurde in ROB-Eintrag 4 übernommen − RS mit add-Operation hat ebenfalls den Wert gespeichert − RS wurde frei gegeben

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

[add,0,0,14,20,-,1,5,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [20,-,1,1,1]

5: [-,-,1,0,1]


OP B



R0: 5 R1: 14 R2: 89 R3: 17

5 0 4 0

Commit– Details (ALU-Operation)

Testen bei Commit − ROB[first].valid = 1

Aktualisierungen durch Commit: − for all Architekturregister r mit Reg[r].rob = head do

Reg[r] := ROB[head].res Reg[r].rob := 0

Commit-Phase – Details (Beispiel 5)

Situation: − Im ROB sei head = 4 − R2 erwartet Wert von ROB-Eintrag 4

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

[add,0,0,56,89,-,1,5,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [20,-,1,1,1]

5: [-,-,1,0,1]


OP B


(4,89)


R0: 5 R1: 14 R2: 89 R3: 17

5 0 4 0

Commit-Phase – Details (Beispiel 5)

Situation: − R2 hat Wert aus ROB übernommen

Anmerkung:

− WAW-Hazard wird wie bei Scoreboard aufgelöst

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS RS

RS

…

Execute 1

[add,0,0,56,89,-,1,5,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1:

2:

3:

4: [20,-,1,0,0]

5: [-,-,1,0,1]


OP B


(4,89)


R0: 5 R1: 14 R2: 20 R3: 17

5 0 0 0

Verarbeitung von Sprüngen

Issue: − Vk-Feld speichert Sprungziel z − misc-Feld vermerkt Adresse a der Sprungoperation − misc-Feld vermerkt auch, welche der beiden Adressen vorausgesagt wurde (‚z‘ oder ‚a‘)

Execute: − tatsächliche Zieladresse wird in Vk-Feld der RS geschrieben

• Vk := z, falls der Sprung ausgeführt werden muss • Vk := a+1, falls der Sprung nicht ausgeführt wird

− misc-Feld speichert, ob Vorhersage korrekt war (‚c‘ = korrekt; ‚w‘ = falsch)

Write-Back: − res-Feld bekommt tatsächliches Sprungziel zugewiesen − addr-Feld bekommt ‚c‘ oder ‚w‘ zugewiesen

Commit:

− Falls addr = c, dann passiert nichts (PC wird auch nicht aktualisiert) − Falls addr = w, dann wird res-Feld in PC geschrieben und die gesamte Pipeline geleert:

• Alle nachfolgenden ROB-Einträge • Alle RS-Station Einträge • Befehlswarteschlange

Sprung – Details (Beispiel 6)

Situation: − Sprungoperation ausgegeben − Sprungoperation wartet auf ld-Operation − Op A, Op B, … werden spekulativ ausgeführt

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[ld,0,0,-,200,-,2,1,EX,1]

RS

RS

…

Execute 1

[bz,1,0,-,123,112a,3,2,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 89 R3:

Ergebnisbus

Operandenbus B



1: [-,-,2,0,1] 0 0 1 0

2: [-,-,3,0,1]

3: [-,-,-,0,0]

4: [-,-,-,0,0]

5: [-,-,-,0,0]

111: ld r2 <- (200) 112: bz r2, #123 113: add r1 <- r1, r0 // Op A 114: sub r3 <- r0, r1 // Op B 115: …

OP A



OP B

OP C

1

ld


Situation: − Op A wird spekulativ ausgeführt − Op B wartet auf Ergebnis von Op A

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[ld,0,0,-,200,-,2,1,EX,1]

RS

RS

…

Execute 1

[bz,1,0,-,123,112a,3,2,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 89 R3:

Ergebnisbus

Operandenbus B



1: [-,-,2,0,1] 0 3 1 4

2: [-,-,3,0,1]

3: [-,-,1,0,1]

4: [-,-,1,0,1]

5: [-,-,-,0,0] OP C



OP D

OP E

1

ld

OP A OP B

OP A



Situation: − Op A hat Ergebnis in ROB geschrieben, aber noch

nicht in R1 − Op B wird spekulativ ausgeführt

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[ld,0,0,-,200,-,2,1,EX,1]

RS

RS

…

Execute 1

[bz,1,0,-,123,112a,3,2,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 89 R3:

Ergebnisbus

Operandenbus B



1: [-,-,2,0,1] 0 3 1 4

2: [-,-,3,0,1]

3: [19,-,1,1,1]

4: [-,-,1,0,1]

5: [-,-,-,0,0] OP C



OP D

OP E

1

ld

OP B



Situation: − Op B hat Ergebnis in ROB geschrieben − ld hat Ergebnis in ROB geschrieben − bz kann ausgeführt werden

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

[bz,0,0,6,123,112a,3,2,RO,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 89 R3:

Ergebnisbus

Operandenbus B



1: [6,-,2,1,1] 0 3 1 4

2: [-,-,3,0,1]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0] OP C



OP D

OP E

1

RS



Situation: − bz wird verarbeitet: Sprung wird nicht ausgeführt − Commit für ld-Operation wird durchgeführt

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

[bz,0,0,6,123,112a,3,2,EX,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 6 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [-,-,3,0,1]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0] OP C



OP D

OP E

1

RS

BZ



Situation: − bz wurde ausgeführt − WB für bz wurde abgeschlossen − Vorhersage war korrekt

(ROB[2].addr := c)

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 6 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [113,c,3,1,1]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0] OP C



OP D

OP E

1

RS RS



Situation: − Commit der Sprungoperation erfordert keine

Aktion, weil Vorhersage korrekt war

− Jetzt kann auch Commit für spekulativ ausgeführte Operationen A und B ausgeführt werden

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 6 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [-,-,-,0,0]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0] OP C



OP D

OP E

0

RS RS



Situation: − Gleiche Situation wie im letzten Beispiel − ld-Operation hat aber Wert 0 in R2 gelesen − bz wird verarbeitet: Sprung

wird diesmal ausgeführt

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

[bz,0,0,0,123,112a,3,2,EX,1]

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 0 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [-,-,3,0,1]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0]

OP C



OP D

OP E

1

RS

BZ

OP F



Situation: − Sprung wird ausgeführt − Vorhersage war falsch

(ROB[2].addr := w) − Korrektes Sprungziel steht

in Feld res

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 6 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [123,w,3,1,1]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0]

OP C



OP D

OP E

1

RS RS

OP F

OP G

OP C



Situation: − Commit der Sprungoperation setzt PC auf korrekte

Adresse

− Leeren der Pipeline

War

te-

schl

ange

Programmspeicher PC

123

Memory Unit

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

R0: 5 R1: 14 R2: 6 R3:

Ergebnisbus

Operandenbus B



1: [-,-,-,0,0] 0 3 0 4

2: [-,-,-,0,0]

3: [19,-,1,1,1]

4: [-14,-,1,1,1]

5: [-,-,-,0,0]



0

RS RS OP C OP D

OP E

OP F

OP G

OP C


Verarbeitung von Speicheroperationen

Bei out-of-order-Ausführung von Speicheroperationen: − Reihenfolge von load-Operationen kann untereinander vertauscht werden − Reihenfolge von load- und store-Operationen sowie store- und store-Operationen

muss erhalten bleiben

Beispiel:

Schreiben in den Speicher in-order während der Commit-Phase

Lesen aus dem Speicher während der Execute-Phase

Lesen immer nur dann, wenn valid-Feld aller vorangegangenen Schreiboperationen im ROB 1 ist

ld r2 <- (r0) ld r1 <- (r4) st r4 -> (r0) ld r5 <- (r6) st r7 -> (r8)

Beispiel (store-Operation)

Issue-Phase − Ausgabe der st-Operation wie bei ALU-Operation

Execute-Phase

− Ausführung der store-Operation kann starten, wenn beide Quelloperanden vorhanden

− Ausführung selbst hat keine Aktion − Geht sofort in WB-Phase über

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[st,0,0,17,5,-,2-,1,RO,1]

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [-,-,2,0,1]

2:

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 0

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)


Aktion bei WB der st-Operation − ROB[x].res := RS[y].Vj − ROB[x].addr := RS[y].Vk

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[st,0,0,17,5,-,2-,1,WB,1]

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [-,-,2,0,1]

2:

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 0

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)


Commit bei st-Operation − MEM[ROB[first].addr] := ROB[first].res

War

te-

schl

ange

Programmspeicher PC

Memory Unit

RS

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [17,5,2,1,1]

2:

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 0

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)

RS

Beispiel (load-Operation)

Issue-Phase: − Ausgabe der ld-Operation wie bei ALU-Operation

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[st,0,0,17,5,-,2,1,RO,1]

[ld,0,0,14,-,-,2,2,RO,1]

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [-,-,2,0,1]

2: [-,-,2,0,1]

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 2

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)


Execute-Phase: − Warten bis Quelloperand verfügbar und − alle vorhergehenden store-Operationen im ROB

gültige res- und addr-Felder haben

Execute-Phase: − Lesen aus dem Speicher oder aus ROB

Situation im Beispiel:

− Warten auf st-Operation War

te-

schl

ange

Programmspeicher PC

Memory Unit

[st,0,0,17,5,-,2,1,RO,1]

[ld,0,0,14,-,-,2,2,RO,1]

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [-,-,2,0,1]

2: [-,-,2,0,1]

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 2

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)


Execute-Phase: − Warten bis Quelloperand verfügbar und − alle vorhergehenden store-Operationen im ROB

gültige res- und addr-Felder haben

Execute-Phase: − Lesen aus dem Speicher oder aus ROB

Situation im Beispiel:

− ld-kann ausgeführt werden War

te-

schl

ange

Programmspeicher PC

Memory Unit

[ld,0,0,14,-,-,2,2,RO,1]

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [17,5,2,1,1]

2: [-,-,2,0,1]

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 2

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)

RS


WB- und Commit-Phasen wie bei Alu-Operationen

War

te-

schl

ange

Programmspeicher PC

Memory Unit

[ld,0,0,14,-,-,2,2,RO,1]

RS

…

Execute 1

RS

RS

…

Execute m

RS RS

RS

…

Ergebnisbus

Operandenbus B

…

…



1: [17,5,2,1,1]

2: [20,-,2,1,1]

3:

4:

5:



R0: 5 R1: 14 R2: 20 R3: 17

0 0 0 2

M 0 0

RS

st r3 -> (r0) ld r3 <- (r1) st r1-> (r2)

RS

Tomasulo (Beispiel 9: Schleifenausführung, Takt 0)

Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 0 R1: 100 R2: 13

Ergebnisbus



0 0

0 0

0 0

Execute 2

0 0 0

R3: 0 0 R4: 0 0 W

arte

- sc

hlan

ge

Loop: ld r0 <- (r1) mul r4 <- r0, r2 add r3 <- r3, r4 add r1 <- r1,1 bne loop, r1,200 …

ld r0,(r1)

mul r4,r0,r2

PC 0

add r3,r3,r4

1:

2:

3:

4:

5:


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 0 R1: 100 R2: 13

Ergebnisbus



1 0

0 0

0 0

Execute 2

1 0 0

R3: 0 0 R4: 0 0 W

arte

- sc

hlan

ge

PC 0

ld r0,(100)

mul r4,r0,r2

add r3,r3,r4

add r1,r1,1


1:

2:

3:

4:

5:

ld r0,(100)


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 0 R1: 100 R2: 13

Ergebnisbus



1 0

1 0

0 0

Execute 2

1 0 0

R3: 0 0 R4: 0 2 W

arte

- sc

hlan

ge

PC 0

bne loop,r1,200

mul r4,rob1,13

add r3,r3,r4

add r1,r1,1

ld r0,(100)

ld r0,(100)


1:

2:

3:

4:

5:

ld r0,(100)

mul r4


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 0 R1: 100 R2: 13

Ergebnisbus



1 0

1 1

0 0

Execute 2

1 0 0

R3: 0 3 R4: 0 2 W

arte

- sc

hlan

ge

PC 0

bne loop,r1,200

add r3,0,rob2

add r1,r1,1

ld r0,(100)

ld r0,(r1)

mul r4,rob1,13 ld r0,(100)


1:

2:

3:

4:

5:

ld r0,(100)

mul r4

add r3


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 0 R1: 100 R2: 13

Ergebnisbus



0 0

1 1

1 0

Execute 2

1 4 0

R3: 0 3 R4: 0 2 W

arte

- sc

hlan

ge

PC 0

bne loop,r1,200

add r3,0,rob2

add r1,100,1

ld r0,(r1)

mul r4,20,13

mul r4,r0,r2

ld r0,(100)


1:

2:

3:

4:

5:

20

mul r4

add r3

add r1


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 20 R1: 100 R2: 13

Ergebnisbus



0 0

1 1

1 1

Execute 2

0 4 0

R3: 0 3 R4: 0 2 W

arte

- sc

hlan

ge

PC 5

bne loop,rob4,200 add r3,0,rob2

add r1,100,1

ld r0,(r1)

mul r4,20,13

mul r4,r0,r2

add r3,r3,r4

mul r4,20,13 add r1,100,1


1:

2:

3:

4:

5:

mul r4

add r3

add r1

bne


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 20 R1: 100 R2: 13

Ergebnisbus



1 0

0 1

0 1

Execute 2

1 4 0

R3: 0 3 R4: 0 2 W

arte

- sc

hlan

ge

PC 5

bne loop,101,200 add r3,0,260

add r1,100,1 ld r0,(101) mul r4,20,13

mul r4,r0,r2

add r3,r3,r4

add r1,r1,1


Operationen werden spekulativ geholt und

dekodiert

Es befinden sich Operationen aus verschiedenen

Iterationen gleichzeitig in der Pipeline

ld nicht mehr abhängig von Sprungoperation

1:

2:

3:

4:

5:

260

add r3

101

ld r0

bne


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 20 R1: 100 R2: 13

Ergebnisbus



1 0

1 1

0 1

Execute 2

1 4 0

R3: 0 3 R4: 260 2 W

arte

- sc

hlan

ge

PC 5

bne loop,101,200 add r3,0,260

ld r0,(101) mul r4,rob1,13

add r3,r3,r4

add r1,r1,1

bne loop,101,200 add r3,0,260

bne loop,r1,200


Spekulative Ausführung jetzt

möglich

1:

2:

3:

4:

5:

add r3

101

ld r0

mul r4

ld r0,(101)

bne


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 20 R1: 100 R2: 13

Ergebnisbus



1 0

1 0

1 0

Execute 2

1 4 0 3

R4: 260 2 War

te-

schl

ange

PC 5

bne loop,101,200 add r3,0,260

ld r0,(101) mul r4,rob1,13

R3: 0


1:

2:

3:

4:

5:

260

101

ld r0

mul r4

ld r0,(101)

Spekulative Ausführung jetzt

möglich

bne c add r3,r3,r4

add r1,r1,1

bne loop,r1,200


Memory Unit

RS 1 RS 2

Execute 1

RS 3 RS 4

RS 5 RS 6

R0: 20 R1: 100 R2: 13

Ergebnisbus



1 0

1 1

1 0

Execute 2

1 4 0 3

R4: 260 2 War

te-

schl

ange

PC 5

ld r0,(101) mul r4,8,13

add r1,101,1

R3: 260 ld r0,(r1)

add r3,260,rob2


1:

2:

3:

4:

5:

101

8

mul r4

bne c add r1,r1,1

bne loop,r1,200

add r3

Zusammenfassung

Tomasulo-Algorithmus mit Spekulation

Funktion des Reorder-Buffers für spekulative Aus

Verarbeitung von − Alu-Operationen − Sprungoperationen − Lade-/Speicher-Operationen

Documents

Dynamische Ablaufplanung mit Spekulativer Ausführung M