[SOLVED] MIPS U bung9 RAWiSe18/19 Die folgenden Beispiele setzen eine 5-stufige MIPS Pipeline (wie in der Vorlesung bespro-

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