Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Die folgenden Beispiele setzen eine 5-stufige MIPS Pipeline (wie in der Vorlesung bespro- chen) voraus. Der Registerzugriff erfolgt im Halbtaktverfahren.
Aufgabe 1 (Pipelining – Data Hazards)
Stellen Sie fu ̈r folgende Codesequenz die Belegung der 5-stufigen MIPS-Pipeline fest, indem Sie Abbildung 1 vervollsta ̈ndigen. An welchen Stellen wird Forwarding beno ̈tigt, um die Pipline nicht anhalten zu mu ̈ssen? Kommt es trotzdem irgendwo zu einem Pipeline Stall?
1: add $3, $4, $6
2: sub $5, $3, $2
3: lw $7, 100($5)
4: add $8, $7, $2
5: sub $4, $1, $1
Musterlo ̈sung
Abbildung 1: Pipelinebelegung
Forwarding wird zwischen Instruktion 1 und 2 (wg. Register $3), Instruktion 2 und 3 (wg. Register $5) und Instruktion 3 und 4 (wg. Register $7) beno ̈tigt. Zwischen Instruktion 3 (lw) und 4 (add) kommt es zu einem Stall der Pipeline, da der geladene Wert der lw- Instruktion erst nach der MEM-Phase zur Verfu ̈gung steht und durch Forwarding erst dann weitergeleitet werden kann (load-use Konflikt).
Hinweis: Es gibt mehrere Mo ̈glichkeiten, die Pipelinebelegung graphisch darzustellen. Die Graphik in Abbildung 1 verwendet die in der Vorlesung vorgestellte Darstellungs- art. Dabei werden bei den Instruktionen, die aufgrund eines Pipeline Stalls angehalten
Seite 1 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
werden mu ̈ssen, die nachfolgenden Phasen zu bubbles. Diese Instruktionen befinden sich aber nach wie vor in der Phase, in der sie angehalten wurden. Erst nach dem Ablauf der Stall Cycles la ̈sst der Controller diese Instruktionen weiter durch die Pipeline laufen. Be- achten Sie, dass bei dieser Darstellungsart die angehaltenen Instruktionen in jeweils zwei Zeilen dargestellt werden. Beachten Sie weiters, dass man gut erkennen kann, in welchem Taktzyklus welche Instruktion in welcher Phase ist. Eine Ausnahme bilden die bubbles. So stellen die bubbles der angehaltenen sub Instruktion in Abbildung 1 keine echten Pi- pelinephasen dar, sondern sind nur eine Eigenart der Pipelinedarstellung. Zum Beispiel wird nach der IF-Phase der sub Instruktion (Taktzyklus 6 in Abbildung 1) kein bubble in die ID-Phase eingefu ̈gt, da sich dort ja noch die angehaltene add Instruktion befindet. Der Vorteil dieser Darstellungsart ist, dass in jedem Takt eine Instruktion (eventuell eine Leerinstruktion) die Pipeline verla ̈sst. Dies entspricht der realen Implementierung.
Eine alternative Pipelinedarstellung zeichnet alle Phasen einer Instruktion (vor und nach dem Stall) in eine Zeile. Das hat den Vorteil, dass die Liste der Instruktionen links in der Graphik keine doppelten Instruktionen aufweist und damit exakt dem Programmcode entspricht. Diese kompaktere Darstellungsart wird in Aufgabe 3 gezeigt.
Seite 2 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Aufgabe 2 (Pipelining – Data Hazards)
Folgende Codesequenz wird auf der 5-stufigen MIPS-Pipeline ausgefu ̈hrt:
lw $4, 100($2)
sub $6, $4, $3
add $2, $4, $5
Wie viele Taktzyklen werden fu ̈r die Ausfu ̈hrung dieser Codesequenz beno ̈tigt? Zeich- nen Sie die einzelnen Schritte in Abbildung 2 ein und geben Sie an, an welchen Stellen Forwarding beno ̈tigt wird bzw. wo Pipeline Stalls auftreten.
Musterlo ̈sung
Abbildung 2: Pipelinebelegung
Fu ̈r die Ausfu ̈hrung werden 8 Taktzyklen beno ̈tigt. Forwarding wird zwischen der lw- und der sub-Instruktion beno ̈tigt. Die sub-Instruktion muss um einen Takt ”verzo ̈gert“ werden (= Pipeline Stall), da das gelesene Wort der lw-Instruktion erst nach deren MEM-Phase zur Verfu ̈gung steht.
Aufgabe 3 (Pipelining – CPI)
Ein Programm mit 103 Instruktionen besteht aus einer Sequenz von Lade- und Addier- instruktionen: lw, add, lw, add, ….. Die Addierinstruktionen ha ̈ngen von den vor- hergehenden Ladeinstruktionen ab, die Ladeinstruktionen ha ̈ngen wiederum von den vor- hergehenden Addierinstruktionen ab. Andere Abha ̈ngigkeiten existieren nicht. Das Pro- gramm wird auf einer 5-stufigen MIPS Pipeline ausgefu ̈hrt.
(1) Wie gross ist der resultierende CPI-Wert ohne Forwarding? (2) Wie gross ist der Speedup mit Forwarding?
Seite 3 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Musterlo ̈sung
(1) Wie gross ist der resultierende CPI-Wert ohne Forwarding?
Abbildung 3: Pipelinebelegung CPI = #Takte = 2+3+(103−1)∗3 = 2+103∗3 ≈ 3
OF #Instrukltionen 103 103 (2) Wie gross ist der Speedup mit Forwarding?
Abbildung 4: Pipelinebelegung
#Takte 4+1∗103 +2∗103 4+3∗103 3
CPI 3 CPI= =2 2=2 ≈,Speedup=OF≈=2
MF #Instrukltionen 103 103 2 CPIMF 3 2
Seite 4 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Hinweis: In den Abbildungen 3 und 4 wird eine kompaktere Pipelindarstellung als in den Aufgaben 1 und 2 verwendet. Dabei wird pro Instruktion nur eine Zeile angegeben, in der alle Phasen inklusive der stall cycles eingezeichnet werden.
Aufgabe 4 (Pipelining – Delayed Branch)
Wie kann folgende Codesequenz modifiziert werden, damit der bedingte Sprung auf einer Pipeline mit einem delay slot keine Performanceverluste bewirkt?
L1: lw $2, 100($3)
addi $3, $3, 4
beq $3, $4, L1
Musterlo ̈sung
Der Code kann wie folgt modifiziert werden:
L1: addi $3, $3, 4
beq $3, $4, L1
lw $2, 96($3)
Die lw-Instruktion wird hinter den bedingten Sprung gesetzt. Der Adressoffset muss an- gepasst werden, da die Adresse von Register $3 abha ̈ngig ist, das in der addi-Instruktion vera ̈ndert wird.
Aufgabe 5 (Pipelining – Control Hazards)
Ein Schleife in einem Programm hat fu ̈nf bedingte Spru ̈nge. Die folgende Liste gibt fu ̈r einen Schleifendurchlauf die Resultate der Spru ̈nge an (T = branch taken; N = branch not taken):
branch 1: T-T-T
branch 2: N-N-N-N branch 3: T-N-T-N-T-N branch 4: T-T-T-N-T branch 5: T-T-N-T-T-N-T
Nehmen Sie an, dass das Verhalten der Spru ̈nge fu ̈r alle Schleifendurchla ̈ufe dasselbe ist. Geben Sie die Pra ̈diktionen fu ̈r die einzelnen Spru ̈nge und die resultierenden Vorhersage- genauigkeiten (in Prozent) fu ̈r die Schleife an, die folgende Pra ̈diktoren machen:
(1) Statische Sprungvorhersage: branch taken
(2) Statische Sprungvorhersage: branch not taken
Seite 5 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
(3) Dynamische Sprungvorhersage: 1-bit Pra ̈diktor, initialisiert mit taken
(4) Dynamische Sprungvorhersage: 2-bit Pra ̈diktor, initialisiert mit taken, weak
Musterlo ̈sung
(1) Statische Sprungvorhersage: branch taken
Alle ”branch taken“ (15x) werden richtig vorhergesagt, alle ”branch not taken“ (10x) falsch. Die Vorhersagegenauigkeit betra ̈gt 60 %.
(2) Statische Sprungvorhersage: branch not taken
Alle ”branch not taken“ (10x) werden richtig vorhergesagt, alle ”branch taken“ (15x)
falsch. Die Vorhersagegenauigkeit betra ̈gt 40 %.
(3) Dynamische Sprungvorhersage: 1-bit Pra ̈diktor, initialisiert mit taken 1 = Vorhersage richtig, 0 = Vorhersage falsch.
branch 1: T(1)-T(1)-T(1)
branch 2: N(0)-N(1)-N(1)-N(1)
branch 3: T(1)-N(0)-T(0)-N(0)-T(0)-N(0) branch 4: T(1)-T(1)-T(1)-N(0)-T(0)
branch 5: T(1)-T(1)-N(0)-T(0)-T(1)-N(0)-T(0)
Richtige Vorhersagen: 13
Falsche Vorhersagen: 12
Die Vorhersagegenauigkeit betra ̈gt 52 %.
(4) Dynamische Sprungvorhersage: 2-bit Pra ̈diktor, initialisiert mit taken, weak 1 = Vorhersage richtig, 0 = Vorhersage falsch.
branch 1: T(1)-T(1)-T(1)
branch 2: N(0)-N(1)-N(1)-N(1)
branch 3: T(1)-N(0)-T(1)-N(0)-T(1)-N(0) branch 4: T(1)-T(1)-T(1)-N(0)-T(1)
branch 5: T(1)-T(1)-N(0)-T(1)-T(1)-N(0)-T(1)
Richtige Vorhersagen: 18
Falsche Vorhersagen: 7
Die Vorhersagegenauigkeit betra ̈gt 72 %.
Seite 6 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Aufgabe 6 (Performancevergleich)
Die Performance einer Einzyklenimplementierung, einer Mehrzyklenimplementierung und einer Pipelineimplementierung der MIPS Architektur soll anhand von folgendem Instruk- tionsmix verglichen werden:
Fu ̈r die Einzyklenimplementierung sind folgende kombinatorische Verzo ̈gerungszeiten ge- geben: Speicherzugriff 200 ps, ALU-Operation bzw. eine Adder-Operation 100 ps und Zugriff auf das Registerfile 50 ps. Alle anderen Verzo ̈gerungszeiten (zB. der Multiplexer, Kontroller, Leitungen, etc.) werden vernachla ̈ssigt. Die Mehrzyklen- und die Pipelining- implementierung beno ̈tigen zusa ̈tzliche Register. Die Verzo ̈gerungszeiten dieser Register werden vernachla ̈ssigt.
Fu ̈r die Pipeliningimplementierung wird angenommen: Die Ha ̈lfte aller load-Instruktionen fu ̈hren zu einem load-use Konflikt. Ein Viertel aller bedingten Sprunginstruktionen werden falsch vorhergesagt und die branch penalty betra ̈gt einen Taktzyklus. Unbedingte Spru ̈nge fu ̈hren immer zu einem Pipeline Stall von einem Taktzyklus. Weitere mo ̈gliche Konflikte werden vernachla ̈ssigt.
Stellen Sie die relative Performance zwischen den Implementierungsvarianten fest.
Instruktionsklasse
relative Ha ̈ufigkeit
lw
25%
sw
10%
R-Type
52%
beq
11%
j
2%
Musterlo ̈sung
Einzyklenimplementierung:
Instruktion
Instr.Memory
Reg.Read
ALUOperation
DataMemory
Reg.Write
Summe
R-Type
200 ps
50 ps
100 ps
0
50 ps
400 ps
lw
200 ps
50 ps
100 ps
200 ps
50 ps
600 ps
sw
200 ps
50 ps
100 ps
200 ps
0
550 ps
beq
200 ps
50 ps
100 ps
0
0
350 ps
j
200 ps
0
0
0
0
200 ps
TEZ = 600ps CPIEZ =1
Tabelle 1: Verzo ̈gerungszeiten fu ̈r die Instruktionen, Lo ̈sung
Seite 7 / 8
Musterlo ̈sung
U ̈bung9 RAWiSe18/19
Mehrzyklenimplementierung:
TMZ =200ps
CPIMZ =5∗ 25 +4∗ 10 +4∗ 52 +3∗ 11 +3∗ 2 =4,12 100 100 100 100 100
Der Takt der Mehrzyklenimplementierung muss 200ps betragen (langsamste Stufe). Der CPI Wert berechnet sich aus den relativen Ha ̈ufigkeiten und den CPI-Werten der einzel- nen Instruktionen.
Instruktionsklasse
relative Ha ̈ufigkeit
CPI
lw
25%
5
sw
10%
4
R-Type
52%
4
beq
11%
3
j
2%
3
Pipeliningimplementierung:
TP =200ps
CPIP =1∗12,5 +2∗12,5 +1∗ 10 +1∗ 52 +1∗8,25 +2∗2,75 +2∗ 2 =1,1725 100 100 100 100 100 100 100
Instruktionsklasse
CPI
relative Ha ̈ufigkeit
lw
1
12,5%
lw (Konflikt)
2
12,5%
sw
1
10%
R-Type
1
52%
beq
1
8,25%
beq (Konflikt)
2
2,75%
j
2
2%
PerfEZ/PerfMZ = (CPI ∗ T)MZ/(CPI ∗ T)EZ = (4,12 ∗ 200)/(1 ∗ 600) ≈ 1,37 PerfEZ/PerfP = (CPI ∗ T)P /(CPI ∗ T)EZ = (1,1725 ∗ 200)/(1 ∗ 600) ≈ 0,39 PerfMZ/PerfP = (CPI ∗ T)P /(CPI ∗ T)MZ = (1,1725 ∗ 200)/(4,12 ∗ 200) ≈ 0,28
Seite 8 / 8