PR RECHNERORGANISATION 621.701 – 621.

703 WS 2018/19

Institut für Informationstechnologie (ITEC) Raffelsberger / Taschwer / Timmerer

_________________________________________________________

Übungsblatt 7

7.1 Loop Unrolling

Gegeben sei folgendes MIPS-Assemblercodefragment, das auf einem Pipelined-Prozessor

ohne „Branch Prediction“, aber mit „Delayed Branching“ (1 Takt Branch Delay) ausgeführt
wird. Die Latenzen zwischen abhängigen Befehlen sind in der Tabelle am Ende des
Übungsblattes angegeben.

# initialize c as $f0, d as $f2 – not shown

loop: l.d $f4, 0($t0) # load x[i]
sub.d $f6, $f4, $f0 # x[i] - c
l.d $f8, 0($t1) # load y[i]
mul.d $f10, $f6, $f8 # (x[i] – c) * y[i]
add.d $f12, $f10, $f2 # (x[i] - c) * y[i] + d
s.d $f12, 0($t2) # store result element z[i]
addi $t2, $t2, -8
addi $t1, $t1, -8
addi $t0, $t0, -8
bne $t0, $t4, loop
nop

(a) Identifizieren sie alle Daten- und Kontrollabhängigkeiten, die Leerzyklen (Stalls)
verursachen. Wie viele Takte werden für ein Ergebniselement (durch s.d gespeicherter
Wert) benötigt?

(b) Optimieren Sie den Code durch Umordnen von Befehlen so, dass er auf dem gegebenen
Prozessor möglichst schnell ausgeführt wird. Wie viele Takte werden für die Verarbeitung
eines Ergebniselements (z[i]) durchschnittlich benötigt?

(c) Rollen Sie die Schleife zweimal ab (zwei Kopien des Code-Fragments in einer
Schleifeniteration), und ordnen Sie den Code so um, dass er auf dem gegebenen
Prozessor möglichst schnell ausgeführt wird. Wie viele Takte werden nun pro
Ergebniselement benötigt?

(d) Wodurch wird die Leistungssteigerung beim Abrollen von Schleifen im Allgemeinen
erreicht?

Seite 1 von 4
7.2 Loop Unrolling, Superskalare Prozessoren

Gegeben sei das unten stehende Code Fragment. Ordnen Sie den Code der zweimal
abgerollten Schleife so an, dass er optimal auf einem superskalaren Prozessor mit „Delayed
Branching“ entsprechend VO-Folie 3-154 ausgeführt werden kann. Es gelten die Latenzen
zwischen abhängigen Befehlen wie in der am Ende des Übungsblattes stehenden Tabelle
angegeben. Wie viele Takte werden pro Ergebniselement benötigt?
# $f0 (v) and $f8 (u) contain constants
loop: l.d $f2, 0($t0) # load x[i]
add.d $f2, $f2, $f8 # x[i] + u
l.d $f12, 0($t1) # load y[j]
add.d $f12, $f12, $f0 # y[j] + v
div.d $f10, $f2, $f12 # x[i] / y[j]
add.d $f2, $f10, $f12 # y[j] + x[i] / y[j]
mul.d $f4, $f2, $f10 # (y[j] + x[i]/y[j])*((x[i] + v)/ y[j])

s.d $f4, 0($t2) # store z[i]

addi $t0, $t0, 8
addi $t1, $t1, 8
addi $t2, $t2, 8
bne $t0, $t3, loop
nop

7.3 Statische „Dual Issue“ Prozessoren

Gegeben sei ein statischer „dual-issue“-Prozessor (vgl. VO-Folie 3-135) mit fünf Pipeline-
Stufen, auf dem ein Programm mit folgenden Befehlshäufigkeiten ausgeführt wird:

Befehlsklasse Häufigkeit

ALU-Operationen 40%

beq (Sprung richtig vorhergesagt) 10%

beq (Sprung falsch vorhergesagt) 5%

lw 30%

sw 15%

Sie können folgende Annahmen treffen:

 der Prozessor kann stets zwei beliebige Instruktionen im gleichen Takt ausführen
(ausgenommen Branch-Befehle)

 die Sprungvorhersage erfolgt in der ersten Pipeline-Stufe und Sprünge für „branch“-
Befehle werden in der zweiten Pipeline-Stufe ausgeführt

 im Programm sind Branch-Befehle nicht unmittelbar hintereinander angeordnet; die

Häufigkeit der Branch-Befehle an geraden bzw. ungeraden Wortadressen ist gleich
 es treten keine Leertakte aufgrund von Datenabhängigkeiten auf
Seite 2 von 4
  „delay slots“ werden nicht verwendet.

(a) Bestimmen Sie den CPI-Wert für die Ausführung dieses Programms.

(b) Welcher Speedup im Vergleich zu (a) würde erreicht, wenn die Sprungvorhersage perfekt
wäre?

(c) Angenommen, der Prozessor habe nur ein Write-Port in der Registereinheit, d.h. es
können nicht zwei Befehle parallel in die Registereinheit schreiben (vgl. VO-Folie 3-133).
Welcher Speedup wird erreicht, wenn ein zweiter Write-Port hinzugefügt wird?

7.4 Dynamisches Pipeline-Scheduling

Stellen Sie die Ausführung des (nicht abgerollten und nicht umgeordneten) Codes aus
Aufgabe 7.1 auf dem superskalaren Beispielprozessor mit „Dynamic Scheduling“ und „Branch
Prediction“ wie auf VO-Folie 3-159 dar. Wie viele Takte werden pro Ergebniselement
benötigt?

Eigenschaften des Beispielprozessors:

 Es gibt zwei „Issue“-Pipelines, sodass in jedem Takt mit der Verarbeitung von zwei
Befehlen begonnen werden kann: ein FP-Befehl und ein anderer Befehlstyp (INT, Branch,
Load/Store).

 Es sind genügend Reservierungsstationen und Funktionseinheiten vorhanden, um alle

Befehle der Schleife aufzunehmen.

 Zwischen abhängigen Befehlen in derselben Pipeline findet „Forwarding“ statt, sodass die
Fertigstellung (Commit) eines Befehls und der Ausführungsbeginn eines abhängigen
Befehls im selben Takt erfolgen können.

 Die „Commit“-Reihenfolge muss nicht mit der „Issue“-Reihenfolge übereinstimmen („out-

of-order completion“).

 Die Dauer der „Execute“-Phase für verschiedene Befehlsgruppen sei durch folgende
Tabelle gegeben. Die Dauer von „Branch“- und „Store“-Befehlen ist hier nicht relevant,
weil sie jedenfalls kleiner als die Ausführungsdauer einer Iteration des gegebenen Codes
ist und die Sprungvorhersage für die gegebene Schleife fast immer richtig ist.

Befehlsgruppe FP Load FP Arithmetik Übrige Befehle

Execute/Takte 2 3 1

Seite 3 von 4
7.5 VLIW

Ordnen Sie den Code der sechsmal abgerollten Schleife aus Aufgabe 7.1 so an, dass er
optimal auf einem VLIW-Prozessor entsprechend VO-Folien 3-158 ausgeführt werden kann.
Nehmen Sie an, dass der Prozessor 64 FP-Register besitzt und Branch Prediction
implementiert. Die Latenzen zwischen abhängigen Befehlen entnehmen Sie bitte
untenstehender Tabelle.

(a) Wie viele Takte werden pro Ergebniselement benötigt?

(b) Bestimmen Sie für die Ausführung dieses Codes die Effizienz der Prozessorauslastung
und den „Instructions per Cycle (IPC)“-Wert.

Latenzen der Bsp. Prozessoren für Bsp. 7.1 und Bsp. 7.5 (FP=Floating Point):

Erzeugender Befehl Benutzender Befehl Latenz / Zwischentakte

(schreibt Register $x) (liest Register $x) (um Leerzyklen zu vermeiden)

FP ALU operation FP ALU operation 3

FP ALU operation Store FP double 2

Load FP double FP ALU operation 1

Load FP double Store FP double 0

Load integer Integer operation 1

Load integer Branch 2

Integer operation Integer operation 0

Integer operation Branch 1

Seite 4 von 4