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?
add $3, $4, $6
sub $5, $3, $2
lw $7, 100($5)
add $8, $7, $2
sub $4, $1, $1
Abbildung 1: Pipelinebelegung
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.
Seite 1 / 3
U ̈bung9 RAWiSe18/19
Abbildung 2: Pipelinebelegung
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 durch Forwarding?
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
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):
Seite 2 / 3
U ̈bung9 RAWiSe18/19
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
(3) Dynamische Sprungvorhersage: 1-bit Pra ̈diktor, initialisiert mit taken
(4) Dynamische Sprungvorhersage: 2-bit Pra ̈diktor, initialisiert mit taken, weak
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%
Seite 3 / 3