[SOLVED] MIPS graph Musterlo sung

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+(1031)3 = 2+1033 3
OF #Instrukltionen 103 103 (2) Wie gross ist der Speedup mit Forwarding?
Abbildung 4: Pipelinebelegung
#Takte 4+1103 +2103 4+3103 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 =112,5 +212,5 +1 10 +1 52 +18,25 +22,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