[SOLVED] algorithm MIPS graph Universita t Paderborn

Universita t Paderborn
Institut Elektrotechnik und Informationstechnik Fachgebiet Datentechnik
Prof. Sybille Hellebrand
Klausur
Technische Informatik / Grundlagen der Rechnerarchitektur
23. Februar 2016
Punkteverteilung
Aufgabe
1
2
3
4
5

maximale Punkte
13
20
18
19
20
90
erreichte Punkte
Note:
Aufkleber
Name:
Matrikelnummer:
Studienrichtung:

Hinweise:
Fu r die Lo sung der Klausuraufgaben sind ausschlielich die Aufgabenbla tter zu verwenden. Lo sungsangaben auerhalb der Aufgabenbla tter (Schmierzettel, etc.) werden bei der Bewertung nicht beru cksichtigt!
Beschriften Sie jede Doppelseite mit Ihrer Matrikelnummer!
Mit Bleistift oder der Korrekturfarbe rot angefertigte Lo sungen werden nicht bewertet! Die Verwendung von Tipp-Ex oder Tintenkiller ist untersagt.
Es ist ein handgeschriebener DIN-A4 Zettel als Hilfsmittel zugelassen!
Es sind keine weiteren Hilfsmittel zugelassen!

Aufgabe 1 Matrikelnummer: Seite 3 Aufgabe 1: (Leistungsbewertung) 13 Punkte
a) Auf einem Prozessor wird der SPEC2000 Floating-Point Benchmark ausgefu hrt. Wa hrend der Programmlaufzeit werden die in Tabelle 1 aufgelisteten MIPS-Instruktio- nen mit der entsprechenden Ha ufigkeit ausgefu hrt. Die durchschnittliche Anzahl von Taktzyklen pro Instruktion (CPI) ist fu r die in Tabelle 2 gezeigten Instruktionskate- gorien bekannt. Berechnen Sie die Anzahl der beno tigten Taktzyklen pro Instruktion fu r den SPEC2000 Floating-Point Benchmark auf dem verwendeten Prozessor.
(5 Punkte)
Core MIPS
Name
H aufigkeit
add unsigned
addu
24%
subtract unsigned
subu
3%
or
or
3%
nor
nor
2%
load word
lw
15%
store word
sw
7%
branch on equal
beq
2%
branch on not equal
bne
2%
FP add double
add.d
8%
FP subtract double
sub.d
4%
FP multiply double
mul.d
8%
load FP double
l.d
15%
store FP double
s.d
7%
Instruktions- kategorien
CPI
ALU
1
load and store
1,5
conditional branch
1,5
floating-point add/sub
1,0
floating-point multiply
3,0
Tabelle 2: CPI fu r MIPS- Instruktionskategorien
Tabelle 1: Ha ufigkeit der MIPS-Instruktionen im SPEC2000 Floating Point Benchmark

Aufgabe 1 GRA/TI Seite 4
b) In Aufgabenteil a) wurden keine Speicherfehlgriffe beru cksichtigt. Die CPU muss 40 Taktzyklen auf die beno tigten Daten warten, falls ein Fehlgriff auftritt. Um wie viele Taktzyklen verschlechtert sich die durchschnittliche Anzahl der Taktzyklen pro Instruktion, wenn wa hrend der Befehlsspeicherzugriffe eine Fehlgriffsrate von 10% auftritt und die Datenspeicherzugriffe eine Fehlgriffsrate von 7,5% aufweisen?
Hinweis: Nehmen Sie an, dass 50% der ausgefu hrten Befehle Speicherzugriffe sind. (2 Punkte)

Aufgabe 1 Matrikelnummer: Seite 5
Ein Prozessorhersteller steht vor der Entscheidung einen Krypto-Core in der neuen Prozessorgeneration zu integrieren. Mit Hilfe dieses Hardwaremoduls ko nnen Ver- schlu sselungsalgorithmen 5 mal schneller ausgefu hrt werden. Fu r die Ausfu hrung eines typischen Benchmarks beno tigt die bisherige Prozessorgeneration 15 Sekunden.
c) Um wie viel mal ist die neue Prozessorgeneration schneller, wenn der bisherige Prozessor wa hrend der Ha lfte der Ausfu hrungszeit des Benchmarks mit der Berechnung von Verschlu sselungsalgorithmen bescha ftigt ist.
(2 Punkte)
d) Welchen Anteil der Ausfu hrungszeit muss der bisherige Prozessor mit den Verschlu sse- lungsalgorithmen bescha ftigt sein, damit der Benchmark auf der neuen Prozessorge- neration 3 mal schneller ausgefu hrt werden kann?
(4 Punkte)

Aufgabe 2 GRA/TI Seite 6 Aufgabe 2: (Assembler Programmierung) 20 Punkte
a) Die Funktion teilersumme ermittelt die Summe der Teiler einer Zahl n in einem
Intervall [a : b], indem es die Summe der Teiler von n in Teilintervallen rekursiv
berechnet. Die Zahl n steht im Register $s0, und die jeweiligen Intervallgrenzen sind
in $a0 und $a1 abgelegt. Nehmen Sie an, dass die Funktion mit den Registerwerten
$s0=6, $s1=0, $a0=1 und $a1=4 aufgerufen wurde.Vervollsta ndigen Sie die Funktion! (4 Punkte)
teilersumme:
01 subi
02 sw
03 sw
04 sw
05 sw
06 addi
07_______ $t1, $a1, intervallteilung # falls Intervalllaenge > 1
$sp, $sp, 16
$ra, 12($sp)
$s1, 8($sp)
$a0, 4($sp)
$a1, 0($sp)
# Schaffe Platz fuer 4 Worte
# Sichere Ruecksprungadresse
# Sichere Partialsumme
# Sichere untere Intervallgrenze
# Sichere obereIntervallgrenze
$t1, $a0, 1
# Intervall weiter zerlegen
08add $v0, $zero, $a0
09rem $t1, $s0, $a0
10_______ $t1, $zero, return
11addi$v0, $zero, 0
12_______ return
intervallteilung:
# Ergebnis = a0
# t1 = Rest von s0/a0
# t1 == 0?
# Ergebnis = 0
13 add
14 addi
15 srl
16_____________________________# Rekursion in Teilintervall
17 add
$s1, $zero, $v0
# Zwischenergebnis merken
$a1, $a0, $a1
$a1, $a1, 1
$a1, $a1, 1
# Neue obere Intervallgrenze
18 add
19 lw
20_____________________________# Rekursion in Teilintervall
21 add
return:
22 lw
23 lw
24 lw
25 lw
26 addi
27 jr
$v0, $v0, $s1
$a1, 0($sp)
$a0, 4($sp)
$s1, 8($sp)
$ra, 12($sp)
$sp, $sp, 16
$ra
# Beide Ergebnisse addieren
# Vom Stack: obereIntervallgrenze
# Vom Stack: untere Intervallgrenze
# Vom Stack: Partialsumme
# Vom Stack: Ruecksprungadresse
# Entferne 4 Worte vom Stack
# Return
$a0, $zero, $a1
$a1, 0($sp)
# Neue untere Intervallgrenze
# Alte obereIntervallgrenze

Aufgabe 2 Matrikelnummer: Seite 7
b) Wieso muss die Funktion den Inhalt von $s1 auf den Stack sichern?
(2 Punkte)
c) Welche rekursiven Aufrufe arbeitet die Funktion bis zur Ermittlung der Lo sung ab? Fu llen Sie die folgende Tabelle aus, indem Sie jeweils eine Spalte anfu gen, wenn Zeile 05 des Programms erreicht wird. Schreiben Sie in das Register $ra statt einer Speicheradresse einfach die entsprechende Zeilennummer des Programms, an die gesprungen werden soll. Der Stackpointer $sp soll zu Beginn des Programms auf Adresse 0x1000FFA0 zeigen. Beim Ausfu llen du rfen sie das Pra fix 0x1000 weglassen.
(12 Punkte)
Zeile

05
05

$sp
FFA0
$a0
1
$a1
4
$s0
6
$s1
0
$ra

Tabelle fu r Registerwerte.
Zeile

05
05

$sp
FFA0
$a0
1
$a1
4
$s0
6
$s1
0
$ra

Ersatztabelle, ungu ltige Lo sungen streichen!

Aufgabe 2 GRA/TI Seite 8
d) Veranschaulichen Sie die Aufrufstruktur aus c) mit Hilfe eines Aufrufbaumes wie in Abbildung 1: Schreiben Sie in die Knoten die Intervallgrenzen und an die Kanten die von unten zuru ckgelieferten Teilsummen eines Funktionsaufrufs. Was ist das Endergebnis?
(2 Punkte)
30 32 00
30 31 31 32
Abbildung 1: Ausschnitt eines Aufrufbaums in dem kein Teiler der Zahl vorhanden ist. Ergebnis:

Aufgabe 3 Matrikelnummer: Seite 9 Aufgabe 3: (Pipelining) 18 Punkte
a) In einem Programm hat eine bestimmte Branch-Instruktion nach einem Schleifen- durchlauf das Muster T, NT, T, T, NT (mit T = taken, NT = not taken). Geben Sie an, welche Vorhersagen die aus der Vorlesung bekannte dynamische 2-bit Vorhersage- methode fu r diese Instruktion ausgeben wu rde. Nehmen Sie an, der Pra diktor sei mit likely taken initialisiert. Zeichnen Sie den Automatengraphen und berechnen Sie die Vorhersagegenauigkeit fu r diesen Fall.
(5 Punkte)
likely taken

Aufgabe 3 GRA/TI Seite 10
b) Gegeben sei ein Programm, das auf der aus der Vorlesung bekannten fu nfstufigen Pipelinesteuerung ausgefu hrt wird. Die Befehlsaufteilung ist in folgender Tabelle angegeben:
Fu r das Programm sollen folgende Methoden zur Sprungvorhersage mit ihren jeweiligen Vorhersagegenauigkeiten untersucht werden:
Durch falsch vorhergesagte Branch-Instruktionen vergro ert sich der CPI. Berechnen Sie den resultierenden CPI fu r die Methoden Always-Taken und 2-bit dynamisch. Bei der verwendeten Hardware werden sowohl die Adresse des Folgebefehls als auch die Sprungadresse in der IF-Phase berechnet. Die Sprungentscheidung steht nach der EX-Phase fest. Nehmen Sie an, dass keine Data-Hazards existieren, keine Branch Delay Slots verwendet werden und beim Zuru cksetzen der Pipeline keine Strafe entsteht.
(5 Punkte)
R-Typ
beq
jmp
lw
sw
40 %
20 %
10 %
25 %
5%
Always-taken
Always-not-taken
2-bit dynamisch
45 %
55 %
80 %

Aufgabe 3 Matrikelnummer: Seite 11
c) Nehmen Sie an, eine Verbesserung erlaubt, die Ha lfte aller Branch-Instruktionen durch jeweils eine ALU Instruktion (R-Typ) zu ersetzen. Korrekt und inkorrekt vorhergesagte Instruktionen haben die gleiche Wahrscheinlichkeit, ersetzt zu werden. Berechnen Sie den aus der Verbesserung resultierenden Speedup, wenn in beiden Fa llen die dynamische 2-bit Vorhersagemethode verwendet wird.
(5 Punkte)
d) Manche Branch-Instruktionen sind einfacher vorherzusagen, als andere. Nehmen Sie an, 75% aller ausgefu hrten Branch-Instruktionen sind einfach vorherzusagende Loop-Back Branches, die immer korrekt vorhergesagt werden. Wie hoch muss die Vorhersagegenauigkeit der dynamischen 2-bit Vorhersage fu r die schwierig vorherzusa- genden Non-Loop-Back Branch Instruktionen sein, damit wie in b) insgesamt eine Vorhersagegenauigkeit von 80% erreicht wird?
(3 Punkte)

Aufgabe 4 GRA/TI Seite 12 Aufgabe 4: (Datenpfad) 19 Punkte
a) Benennen Sie in Abbildung 2 die drei MIPS Befehlstypen und die Bereiche der Befehlseinteilung (RS, RT, ). Geben Sie auerdem die entsprechenden Bit-Grenzen an (gestrichelte Ka stchen).
Befehlstyp:
Befehlstyp:
Befehlstyp:
(2 Punkte)
31 0
31 0
31 0
Abbildung 2: Bitgrenzen der Befehlstypen
b) Wie gro ist das Register File bei dem in der Vorlesung behandelten MIPS Prozessor? (1 Punkt)
c) Tragen Sie in die gestrichelten Ka stchen von Abbildung 3 die Busbreiten der jeweiligen Leitungen ein.
RegWrite
(1 Punkt)
Read Addr 1 Data 1
Read Addr 2
Register File
Write Addr
Data 2 Write Data
Abbildung 3: Register File

Aufgabe 4 Matrikelnummer: Seite 13
d) Bei bestimmten Befehlsfolgen kann es zu Daten Hazards kommen. Diese sollen durch den Datenpfad mit Forwarding in Abbildung 4 aufgelo st werden. Markieren Sie die fu r das Forwarding notwendigen Datenleitungen. Die Steuerleitung der Forwarding Unit sollen nicht betrachtet werden (Ersatzabbildung auf Seite 15, ungu ltige Lo sung streichen!).
(2 Punkte)
Abbildung 4: Teil des MIPS Datenpfads
RegWrite
ID/EX
AluSrc1
EX/MEM
MEM/WB
Read Addr 1 Data 1
0
1 u 2 x
Read Addr 2
Register File
MemWrite
MemToReg
Write Addr Data 2
AluSrc2 0
ALU 0M
Write Data
1 Mu 2x 3
Data 1x memory
Sign extend
RegDst
MemRead
10 Mux
M
Forwarding unit
u

Aufgabe 4 GRA/TI Seite 14
e) Gegeben sei folgende Befehlsfolge addi,subi (Abbildung 5). Zum Takt T1 befindet sich der erste Befehl in der IF-Phase.
T1 T2 T3 T4 T5 T6 T7 T8 addi $2, $0, 1
subi $3, $2, 2

Abbildung 5: Befehlsfolge mit Daten Hazard
Vervollsta ndigen Sie die Phasen fu r den zweiten Befehl und zeichnen Sie das F orwarding in Abbildung 5 ein.
Setzen Sie die Steuerleitungen des Datenpfads aus Abbildung 4 in Tabelle 3.1 so, dass die Befehlsfolge korrekt ausgefu hrt wird. Markieren Sie alle nicht relevanten Steuerleitungen mit einem X.
IF
ID
EX
MEM
WB
T1 T2 T3 T4 T5 T6
(5 Punkte)
T1 T2 T3 T4 T5 T6
AluSrc1 AluSrc2 RegDst
MemToReg
AluSrc1
AluSrc2
RegDst
MemToReg
3.1: Tabelle der Steuerleitungen
3.2: Ersatztabelle der Steuerleitungen,
ungu ltige Lo sung streichen!

Aufgabe 4 Matrikelnummer: Seite 15
Abbildung 6: Ersatz Teil des MIPS Datenpfads, ungu ltige Lo sung streichen!
RegWrite
ID/EX
AluSrc1
EX/MEM MEM/WB
Read Addr 1 Data 1
0
1 u 2 x
Read Addr 2
Register File
MemWrite
MemToReg
Write Addr Data 2
AluSrc2 0
ALU 0M
Write Data
1 Mu 2x 3
Data 1x memory
Sign extend
RegDst
MemRead
10 Mux
M
Forwarding unit
u

Aufgabe 4 GRA/TI Seite 16
f) Gegeben sei nachfolgende Befehlsfolge, bei der sich der erste Befehl zum Takt T1 in der IF-Phase befindet:
T1 T2 T3 T4 T5 T6 T7 T8 add $2, $0, $4
sub $4, $3, $5
and $6, $7, $2

Vervollsta ndigen Sie die Phasen fu r die zwei na chsten Befehle und zeichnen Sie das Forwarding in Abbildung 7 ein.
Setzen Sie die Steuerleitungen des Datenpfads aus Abbildung 4 in Tabelle 4 so, dass die Befehlsfolge korrekt ausgefu hrt wird. Markieren Sie alle nicht relevanten Steuerleitungen mit einem X.
IF
ID
Abbildung 7: Befehlsfolge mit Daten Hazard
Tabelle 4: Tabelle der Steuerleitungen
EX
MEM
WB
(6 Punkte)
AluSrc1 AluSrc2 RegDst MemToReg
T1 T2 T3 T4 T5 T6

Aufgabe 4
Matrikelnummer:
Seite 17
AluSrc1 AluSrc2 RegDst MemToReg
T1 T2 T3 T4 T5 T6
Tabelle 5: Ersatztabelle der Steuerleitungen, ungu ltige Lo sung streichen!
g) Reicht diese Art des Forwardings aus, um den Daten Hazard der nachfolgenden Befehlsabfolge aufzulo sen? Begru nden Sie Ihre Antwort und geben Sie, falls no tig, eine Manahme an. (2 Punkte)

lw$2, 100($5)
and$4, $2, $5

Aufgabe 5 GRA/TI Seite 18
Aufgabe 5: (Cache) 20 Punkte Um die Fehlgriffe auf einen Cache zu reduzieren, ko nnen unterschiedliche Strategien einge-
setzt werden, wie zum Beispiel die Erho hung der Assoziativita t.
a) Geben Sie einen Vorteil des vollassoziativen Caches gegenu ber einem Cache mit geringerer Assoziativita t an. Begru nden Sie Ihre Antwort kurz.
(1 Punkt)
b) Welche zwei Nachteile ergeben sich aus einer Erho hung der Assoziativita t? Begru nden Sie Ihre Antwort kurz.
(1 Punkt)
c) Scha tzen Sie die Fehlgriffsrate fu r einen vollassoziativen Cache ab, der als Befehlscache eingesetzt wird und n Rahmen entha lt, wobei jeder Rahmen m Worte aufnehmen kann. Das Programm besteht aus rein arithmetischen Befehlen. Vergleichen Sie die Fehlgriffsrate mit einem direkt abgebildeten Cache mit den selben Spezifikationen und begru nden Sie, fu r welchen Cache Sie sich entscheiden wu rden.
(3 Punkte)

Aufgabe 5 Matrikelnummer: Seite 19
d) Benennen Sie eine weitere Strategie zur Reduzierung der Fehlgriffe und geben Sie kurz deren Vor- und Nachteile an.
(2 Punkte)
Gehen Sie im Folgenden von einem Computer aus, der zur Beschleunigung der Speicherzugriffe auf den byteadressierten Arbeitsspeicher mit einem Adressraum von 8 GB einen Cache mit 8 Rahmen vorsieht, wobei der Datenbereich jedes Blocks 8 Worte zu je 32 Bit umfasst. Der Cache sei als 4-fach mengenassoziativer Cache (4-way-set-associative) organisiert. Als Ersetzungsstrategie wird LRU (Least Recently Used) eingesetzt und fu r das Ru ckschreiben in den Hauptspeicher die write-back- Strategie. Hierzu wird jedem Cache Rahmen ein Dirty Bit (D) hinzugefu gt, welches auf 1 gesetzt wird, wenn Daten im entsprechenden Block geschrieben wurden, und so lange 1 bleibt, bis dieser Block zuru ckgeschrieben wird, sonst 0.
e) Geben Sie die Breite des Adressbusses sowie die Anzahl an Bits fu r Tag, Index und Offsets an.
Adressbus: Tag: Index: Wortoffset: Byteoffset:
(3 Punkte)

Aufgabe 5 GRA/TI Seite 20
f) Gegeben sei folgende Programmabfolge, die sequentiell abgearbeitet wird (fu hrende Nullen werden abgeschnitten).
t=1:lw $t0, 0110100010111
t=2:sw $t1, 0111110001001
t=3:lw $t2, 0110101011010
t=4:sb $a0, 0110100110001
t=5:sb $t6, 0110100010011
t=6:lw $t3, 0111001011100
t=7:lw $t0, 0111000100011
t=8:lb $t0, 0110001000111
t=9:sb $v0, 0111111001110
t=10: lw $v1, 0111110010100
Der Cache sei zu Beginn leer. Geben Sie nach jedem Befehl den Inhalt des Caches an, ob es sich um einen Hit oder einen Fehlgriff handelt und ob eine Hauptspeicheraktua- lisierung no tig ist (Ersatztabellen auf Seite 23, ungu ltige Lo sungen streichen!).
Hinweis: Geben Sie nur die Bereiche der Tabellen an, die sich a ndern.
(10 Punkte)
t=1: lw $t0, 0110100010111 t=2: sw $t1, 0111110001001
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein

Aufgabe 5 Matrikelnummer:
Seite 21
t=3: lw $t2, 0110101011010
t=4: sb $a0, 0110100110001
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein
t=5: sb $t6, 0110100010011
t=6: lw $t3, 0111001011100
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein

Aufgabe 5 GRA/TI
Seite 22
t=7: lw $t0, 0111000100011
t=8: lb $t0, 0110001000111
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein
t=9: sb $v0, 0111111001110
t=10: lw $v1, 0111110010100
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein

Zusatzblatt fu r Notizen Ersatz: t=
Matrikelnummer:
Seite 23
Ersatz: t=
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein
Ersatz: t=
Ersatz: t=
Index
D
Tag
0
1
Index
D
Tag
0
1
Hit? ja nein
Hit? ja nein
Hauptspeicher- ja aktualisierung? nein
Hauptspeicher- ja aktualisierung? nein

Zusatzblatt fu r Notizen GRA/TI Seite 24

Zusatzblatt fu r Notizen Matrikelnummer: Seite 25

Zusatzblatt fu r Notizen GRA/TI Seite 26