[SOLVED] C MIPS Universita t Paderborn

Universita t Paderborn
Institut Elektrotechnik und Informationstechnik Fachgebiet Datentechnik
Prof. Sybille Hellebrand
Klausur Grundlagen der Rechnerarchitektur
24. Februar 2014
Punkteverteilung
Aufgabe
1
2
3
4
5

maximale Punkte
15
18
21
16
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) 15 Punkte
a) Die Firma Limited Performance Corp. mo chte die verwendeten Prozessoren verbessern. Ein Benchmarkprogramm beno tigt auf der alten CPU, die mit 100 MHz getaktet wird, eine Ausfu hrungszeit von 10 Sekunden. Die Ausfu hrungszeit auf der neuen CPU soll nur noch 3 Sekunden betragen. Das Design Team ist in der Lage eine CPU zu entwerfen, die schneller getaktet werden kann. Allerdings werden fu r das Programm dann 1,8 mal so viele Taktzyklen beno tigt. Mit welcher Frequenz muss die neue CPU getaktet werden, damit die gewu nschte Ausfu hrungszeit von 3 Sekunden erreicht wird?
Bitte kreuzen Sie alle richtigen Antworten an.
60 MHz
180 MHz
540 MHz
600 MHz
keine Lo sung ist richtig
(3 Punkte)
b) DerChef-IngenieurvonLimitedPerformanceschla gteineVerbesserungderGleitkomma- Einheit vor. Bisher beno tigen einfache Befehle (alle Befehle auer Gleitkommabefehlen) im Durchschnitt 2 Taktzyklen und Gleitkommabefehle 10 Taktzyklen. Durch die Ver- besserung werden fu r Gleitkommabefehle nur noch 6 Taktzyklen beno tigt, einfache Befehle brauchen dann jedoch 3 Taktzyklen. Auerdem muss die Zykluszeit von 40 ns auf 60 ns erho ht werden. Wie gro muss der Anteil der Gleitkommabefehle mindestens sein, damit sich die Verbesserung lohnt (d.h. insgesamt ein Speedup > 1 erreicht wird)?
Bitte kreuzen Sie alle richtigen Antworten an.
gro er als 4/7
gro er als 5/7
gro er als 1/2
gro er als 12/25
keine Lo sung ist richtig
(4 Punkte)

Aufgabe 1 GRA/TI Seite 4
c) Bei der Konkurrenzfirma Murx Electronics wird ebenfalls an einem neuen Design gearbeitet. Fu r den Befehlssatz der neuen CPU werden zwei verschiedene Implementie- rungen diskutiert. Implementierung A erlaubt eine Zykluszeit von 10 ns und erreicht 2 CPI fu r ein Benchmarkprogramm. Implementierung B kommt bei einer Zykluszeit von 20 ns auf 1,2 CPI. Welches Verha ltnis ergibt sich fu r die Ausfu hrungszeiten des Benchmarkprogramms?
Bitte kreuzen Sie alle richtigen Antworten fu r Ausfu hrungszeitB an. Ausfu hrungszeitA
1,67
2
0,6
1,2
keine Lo sung ist richtig
(2 Punkte)
d) Murx Electronics mo chte auerdem eine Prozessor-Variante mit Pipelining auf den Markt bringen. Der Befehlsablauf wird a hnlich wie beim MIPS-Prozessor in 5 Pipeli- nestufen aufgeteilt. Zur Abarbeitung einer Pipelinestufe wird 1 CPU-Zyklus beno tigt. Die Analyse von Benchmarkprogrammen zeigt, dass die Wahrscheinlichkeit fu r einen Konflikt 25 % betra gt. Bei einem Konflikt muss im Durchschnitt 1 Wartezyklus eingefu gt werden. Wie hoch ist der asymptotische Speedup (unendliche viele Befehle) der Pipeline-Implementierung gegenu ber einer Mehrzyklen-Implementierung?
Bitte kreuzen Sie alle richtigen Antworten an.
5
0,25
4
2,5
keine Lo sung ist richtig
(3 Punkte)

Aufgabe 1 Matrikelnummer: Seite 5
e) Die Konkurrenzfirma Murx Electronics hat eine neue CPU entwickelt, die mit 100 MHz getaktet werden kann. Die Befehle lassen sich grob in drei Klassen einteilen (vgl. Tabelle).
Befehlsklasse CPI fu r die Befehlsklasse A1 B2 C3
Bei einem Testlauf mit einem Beispielprogramm werden 70 MIPS erreicht. In der folgenden Tabelle sind Benchmarkprogramme mit verschiedenen Verteilungen der Befehle auf die einzelnen Befehlsklassen gezeigt. Welche davon ko nnen fu r den Testlauf verwendet worden sein?
Bitte kreuzen Sie alle richtigen Antworten an.
(3 Punkte)
Programm
Anzahl der Befehle in Klasse
A
B
C
I
4109
3109
0
II
10109
1109
1109
III
9109
3109
0
IV
10109
2109
2109
keines der Programme wurde verwendet

Aufgabe 2 GRA/TI Seite 6
Aufgabe 2: (Pipelining) 18 Punkte
Gegeben sei der aus der Vorlesung bekannte MIPS-Prozessor mit 5-stufiger Pipeline (IF, ID, EX, MEM, WB) und einer statischen Sprungvorhersage branch not taken. Die Pipeline nutzt alle Mo glichkeiten fu r Forwarding aus.
a) Folgendes Programm soll ausgefu hrt werden
1:main:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11: func:
addi $t3,
addi $t1,
addi $t4,
add$t0, $t3, $t4
lw $t3, 0($a0)
add$t7, $t0, $t3
sub$s1, $t0, $t1
beq$s1, $zero, func
addi $s1, $s1, 1
j exit
$zero, 4
$zero, 6
$zero, 2
Liegt die Sprungvorhersage des Prozessors hier richtig? Begru nden Sie kurz Ihre Antwort.
(2 Punkte)
b) Kann das Programm in Aufgabenteil a) durch Umsortieren der Befehle schneller ausgefu hrt werden? Begru nden Sie kurz Ihre Antwort und geben Sie, falls mo glich, eine bessere Anordnung an.
(3 Punkte)

Aufgabe 2 Matrikelnummer: Seite 7
c) Zur Effizienzsteigerung sollen dynamische Pra diktoren eingesetzt werden. Hierzu stehen die Pra diktoren 1-bit Pra diktor, 2-bit Pra diktor weak und 2-bit Pra diktor strong zur Verfu gung, siehe Abbildung 1.
(a) 1-bit Pra diktor
(b) 2-bit Pra diktor weak (c) 2-bit Pra diktor strong
Abbildung 1: Dynamische Pra diktoren
Fu r die Sprungfolge NT-T-NT-NT-T-T-T-NT sollen die Pra ditkoren miteinander verglichen werden. Fu llen Sie dazu folgende Tabelle aus und geben Sie die Vorher- sagegenauigkeit in Prozent an (Ersatz- Tabellen ab Seite 9 , ungu ltige Lo sung streichen!).
(13 Punkte)
1-bit Pra diktor
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
0
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT

Aufgabe 2 GRA/TI Seite 8
2-bit Pra diktor weak
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
01
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT
2-bit Pra diktor strong
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
01
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT
Vorhersagegenauigkeit 1-bit Pra diktor: Vorhersagegenauigkeit 2-bit Pra diktor weak: Vorhersagegenauigkeit 2-bit Pra diktor strong:

Aufgabe 2 Matrikelnummer: Seite 9 Ersatz- Tabellen, ungu ltige Lo sung streichen!
1-bit Pra diktor
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
0
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT
2-bit Pra diktor weak
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
01
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT

Aufgabe 2 GRA/TI Seite 10
2-bit Pra diktor strong
Zeitpunkt
Sprung
Aktueller Zustand
Vorhersage
Richtig oder Falsch?
Folgender Zustand
0
NT
01
1
T
2
NT
3
NT
4
T
5
T
6
T
7
NT
Vorhersagegenauigkeit 1-bit Pra diktor: Vorhersagegenauigkeit 2-bit Pra diktor weak: Vorhersagegenauigkeit 2-bit Pra diktor strong:

Aufgabe 3 Matrikelnummer: Seite 11
Aufgabe 3: (Assembler) 21 Punkte
Gegeben ist die folgende MIPS-Assembler-Funktion. Die Funktion bekommt 3 Werte als Parameter u bergeben (eine Adresse fu r ein aufsteigend sortiertes Feld mit Ganzzahlen ($a0), die Anzahl der Elemente im Feld ($a1) und eine weitere Ganzzahl x ($a2)) und liefert 2 Werte zuru ck.
1: func: addi$s1, $a1,-1
2: sll
3: add
4: add
5: add $v0, $zero,$zero
6: add $v1, $zero,$zero
7: jump1:beq $s0, $s1,jump4
8: lw$t0, 0($s0)
9: lw$t1, 0($s1)
10:add $t1, $t0,$t1
11:beq $t1, $a2,jump3
12:slt $t0, $t1,$a2
13:beq $t0, $zero,jump2
14:addi$s0, $s0,4
15: j jump1
16:jump2:addi$s1, $s1, -4
17:j
18:
19:jump3:sub
20: sub
21: srl
22: srl
23:jump4: jr
jump1
$v0, $s0, $a0
$v1, $s1, $a0
$v0, $v0, 2
$v1, $v1, 2
$ra
$s1, $s1,2
$s1, $a0,$s1
$s0, $a0,$zero
a) Was muss an der Funktion gea ndert werden, damit sie problemlos von anderen Programmierern verwendet werden kann?
(1 Punkt)

Aufgabe 3 GRA/TI Seite 12
b) Wie lautet die Ru ckgabe der Funktion funct, wenn Speicher und Register zum Zeitpunkt des Aufrufs mit den Werten aus Abbildungen 2 und 3 belegt sind?
(12 Punkte)
0x00000000
0x00120000
0x0011FFFF
0x0011FFFE
0x0011FFFE
0x10000104
0x0000000B
0x00000025
0x10000100
0x00110000
0x00110001
0x00110002
0x00110003
0x00110004
0x0011FFFE
0x0011FFFC
.
$zero $at $v0 $v1 $v1 $a0 $a1 $a2 $a3 $t0 $t1 $t2 $t3 $t4 $t5 $t6 .
Abbildung 2: Speicherabbild
c) Beschreiben Sie in 1-2 Sa tzen was die Funktion funct berechnet?
10
43
37
23
51
43
41
37
35
31
28
25
19
9
5
3
2
0x10000140
0x1000013C
0x10000138
0x10000134
0x10000130
0x1000012C
0x10000128
0x10000124
0x10000120
0x1000011C
0x10000118
0x10000114
0x10000110
0x1000010C
0x10000108
0x10000104
0x10000100
Abbildung 3: Registerabbild
(2 Punkte)

Aufgabe 3 Matrikelnummer: Seite 13
d) Die unten aufgefu hrten Instruktionen sind Pseudobefehle und ko nnen von einem MIPS- Prozessor nicht nativ ausgefu hrt werden. Ersetzen Sie die Instruktion durch a quivalente Befehle/Befehlsfolgen. Falls Zwischenergebnisse gespeichert werden mu ssen, benutzen Sie $at. Des Weiteren du rfen nur folgende Befehle verwendet werden:
(6 Punkte)
add addi and
beq bne j
jr nor or
slt slti sll srl
Ersatzfelder sind auf der folgenden Seite.
not $t1 (invertiere $t1 bitweise):
andi $t1, 0xACDC ($t1=$t1 & 0xACDC):
lw $t1, 100 ($t1 = MEM[100]):
subi $t1, $t2, 7:
andi sub jal lui ori xor
ori $t1, $t2, 0xACDCACDC (32 Bit):
ble $t1, $t2, label: (branch if lower or equal)

Aufgabe 3 GRA/TI Seite 14 Ersatz, ungu ltige Lo sung streichen!:
not $t1 (invertiere $t1 bitweise):
andi $t1, 0xACDC ($t1=$t1 & 0xACDC):
lw $t1, 100 ($t1 = MEM[100]):
subi $t1, $t2, 7:
ori $t1, $t2, 0xACDCACDC (32 Bit):
ble $t1, $t2, label: (branch if lower or equal)

Aufgabe 4 Matrikelnummer: Seite 15 Aufgabe 4: (Datenpfad) 16 Punkte
a) Geben Sie fu r die 3 MIPS Befehlstypen die jeweiligen Bit Grenzen an. Benennen Sie dazu in Abbildung 4 die Befehlstypen und geben Sie die noch fehlenden Grenzen
31 26
25
0
opcode
Typename
Typename
Typename
(3 Punkte)
31 26 25 0
31 26 25 0
Abbildung 4: Bitgrenzen der Befehlstypen
(gestrichelt Ka stchen) an.
opcode
opcode
b) Bei der Fertigung von Chips kann es passieren, dass Leitungen permanent mit 0 verbunden werden (logische Null). Beschreiben Sie kurz die Auswirkung dieses De- fekts fu r die Steuerleitungen RegWrite, RegDest, MemRead und MemToReg des Datenpfads in Abbildung 6).
Beispiel: Branch: Es ko nnen keine Branch-Befehle ausgefu hrt werden. RegWrite:
RegDest:
MemRead:
MemToReg:
(2 Punkte)

Aufgabe 4 GRA/TI Seite 16
c) Markieren sie die Steuersignal-Instruktions-Kombinationen in der Tabelle, bei der die Instruktionen mit dem oben beschriebenen Defekt nicht mehr korrekt funktionieren.
add addi sll
(4 Punkte) beq bne j lw nop
RegWrite=0 RegDest=0 MemRead=0 MemToReg=0
Tabelle 1: Steuersignal-Instruktions-Kombinationen
add addi sll beq bne j lw nop
RegWrite=0 RegDest=0 MemRead=0 MemToReg=0
Tabelle 2: Ersatz Steuersignal-Instruktions-Kombinationen, ungu ltige Lo sung streichen!
d) Die Einzyklenimplementierung des MIPS Datenpfads (Abbildung 6) soll um die Instruktion addui rt rs imm (add upper immediate) erga nzt werden. Dieser Befehl besetzt die 16 ho herwertigen Bits des Registers rt durch die Summe von der im Befehl angegebenen Konstanten imm und der 16 ho herwertigen Bits von rs. Die niederwertigen Bits von rt werden mit den niederwertigen Bits von rs beschrieben.
(rt[31..16] = rs[31..16] + imm, rt[15..0] = rs[15..0])
Ein Beispiel zur Verdeutlichung: Der Befehl addui $t1 $t0 0x00ff besitzt folgende
Bitinterpretation:
opcode
001111 01010 01001 00000000 11111111 (0x00ff)
rs rt imm
Inhalt von $t0: Konstante 0x00ff:
$t1 nach Ausfu hrung des Befehls:
00100010 00111101 10101101 11111111 00000000 11111111

00100011 00111100 10101101 11111111

Aufgabe 4 Matrikelnummer: Seite 17 Modifizieren Sie die Einzyklenimplementierung in Abbildung 6 so, dass der Befehl
addui ausgefu hrt werden kann.
Als zusa tzliche Bauteile stehen Ihnen nur Multiplexer zur Verfu gung. Benutzen Sie fu r das Auftrennen bzw. Zusammenfu hren von Leitungsbu ndeln (Bussen) die Notation aus Abbildung 5. Beim Zusammenfu hren ko nnen Leitungen auch auf logisch Null oder Eins festgelegt werden (Abbildung 5c)
Gehen Sie davon aus, dass die ALU die korrekte Operation ausfu hrt.
leitung[3-0]
leitung[0] 1
leitung[0] leitung[0]
1 leitung[3-0] 1 leitung[3-0]
414 33
leitung[3-1] leitung[3-1]
(6 Punkte)
4
3
leitung[3-1]
e) Muss auch der Steuerpfad bzw. die Steuerung vera ndert werden? Bergu nden Sie Ihre Antwort!
(1 Punkt)
(b) Zusammenfu hren (c) mit fester Eins Abbildung 5: Auftrennen bzw. Zusammenfu hren von Leitungsbu ndeln (Bussen)
(a) Auftrennen

Aufgabe 4 GRA/TI Seite 18
PC
Read address
Mux 0 4 ALU Mu
Instruction [31-26]
Instruction [31-0]
Shift left 2
Add result
1
x
Instruction memory
Branch MemRead MemToReg ALUOp MemWrite ALUSrc RegWrite RegDest
Instruction [25-21] Instruction [20-16]
Read register 1
Read data 1
M Instruction [15-11] ux
Write register
Mu
Instruction [15-0]
16
0
Read 0 data 2 Mu
ALU ALU result
Read Address data
1
Add
0
Control
Jump
&
1
Read register 2
Zero
1Writex x
Instruction [5-0]
data
Registers 1 Sign 32
0
extend
ALU control
Abbildung 6: Einzyklenimplementierung des MIPS Datenpfads
Write data
Data memory

Aufgabe 4 Matrikelnummer: Seite 19
PC
Read address
Mux 0 4 ALU Mu
Instruction [31-26]
Instruction [31-0]
Shift left 2
Add result
1
x
Instruction memory
Branch MemRead MemToReg ALUOp MemWrite ALUSrc RegWrite RegDest
Instruction [25-21] Instruction [20-16]
Read register 1
Read data 1
M Instruction [15-11] ux
Write register
Mu
Instruction [15-0]
16
0
Read 0 data 2 Mu
ALU ALU result
Read Address data
1
Add
0
Control
Jump
&
1
Read register 2
Zero
1Writex x
Instruction [5-0]
data
Registers 1 Sign 32
0
extend
ALU control
Abbildung 7: Ersatz Einzyklenimplementierung des MIPS Datenpfads. ungu ltige Lo sung streichen!
Write data
Data memory

Aufgabe 5 GRA/TI Seite 20
Aufgabe 5: (Cache) 20 Punkte
Zur Beschleunigung der Speicherzugriffe auf den byteadressierten Hauptspeicher mit einer Kapazita t von 4GB sei ein Computersystem mit einem Instuktions- und einem Datencache ausgestattet und u ber einen Bus mit dem Hauptspeicher verbunden, siehe Abbildung 8.
Abbildung 8: Speicherorganisation
Der Instuktionscache ist als direkt abgebildeter Cache (direct mapping) mit einer Kapazita t von 2KB implementiert, wobei jeder Rahmen 32 Byte aufnehmen kann. Der Datencache hingegen ist 2-way-set-associative mit 4 Rahmen, wobei jeder Rahmen 2 Worte umfasst. Ein Wort ist jeweils 32 bit.
Der Prozessor ist mit 1GHz getaktet und die Kommunikation zwischen Prozessor und Caches beno tigt keine zusa tzliche Zeit, wa hrend der Bus eine Taktrate von 100MHz und eine Breite von 32 bit hat. Hauptspeicherzugriffe beno tigen fu r das erste Wort 7 Buszyklen und fu r jedes weitere Wort 1 Buszyklus pro Blocku bertragung. Es soll nun von der CPU ein Programm mit 256 Instruktionen `a 32 Bit ausgefu hrt werden, welches sequentiell ab Adresse 0x0000 im Hauptspeicher angeordnet ist. Bei den Instruktionen handelt es sich nur um arithmetische und load- Befehle.
a) Geben Sie, ausgehend fu r eine CPU mit einem CPI von 2, die CPU-Zeit an, die zur Ausfu hrung des Programms beno tigt wird. Gehen Sie davon aus, dass der Befehlscache zu Beginn leer sei und dass sich alle erforderlichen Daten im Datencache befinden.
(6 Punkte)

Aufgabe 5 Matrikelnummer: Seite 21
b) Geben Sie fu r den Datencache die Breite des Adressbus sowie die Anzahl an Bits fu r Tag, Index und Offsets an.
Adressbus:
Tag:
Index:
Wortoffset:
(3 Punkte)
Byteoffset:
c) Gegeben sei folgender Programmbeginn, wobei das Register $s0 mit der Adresse
0x28 vorgeladen sei :
0x0000: lw $t0, 0($s0)
0x0004: lb $t1, 7($s0)
0x0008: lb $t2, -1($s0)
0x000c: lh $t3, 8($s0)
0x0010: lb $t4, 1($s0)
0x0014: lw $t5, 16($s0)
0x0018: lb $t6, 0($s0)
Als Ersetzungsstrategie wird FIFO (first-in first-out) eingesetzt. Gehen Sie im Fol- genden davon aus, dass der Datencache zu Beginn leer sei.
Geben Sie fu r jede Adresse an, ob es sich im Datencache um einen miss oder einen hit handelt. Geben Sie bei einem hit weiterhin an, zu welchem Zeitpunkt t die Daten in den Cache geschrieben wurden. Fu llen Sie dazu folgende Tabelle aus (Ersatz-Tabelle auf der na chsten Seite, ungu ltige Lo sung streichen):
(8 Punkte) hit/miss? Bei hit: t=?
t=1: 0x0000: lw $t0, 0($s0) t=2: 0x0004: lb $t1, 7($s0) t=3: 0x0008: lb $t2, -1($s0) t=4: 0x000c: lh $t3, 8($s0) t=5: 0x0010: lb $t4, 1($s0) t=6: 0x0014: lw $t5, 16($s0) t=6: 0x0018: lb $t6, 0($s0)

Aufgabe 5 GRA/TI Ersatz- Tabelle, ungu ltige Lo sung streichen!
t=1: 0x0000: lw $t0, 0($s0) t=2: 0x0004: lb $t1, 7($s0) t=3: 0x0008: lb $t2, -1($s0) t=4: 0x000c: lh $t3, 8($s0) t=5: 0x0010: lb $t4, 1($s0) t=6: 0x0014: lw $t5, 16($s0) t=6: 0x0018: lb $t6, 0($s0)
Seite 22
hit/miss? Bei hit: t=?
d) Der Datencache soll nun als 4-way-set-associative Cache implementiert werden. A ndert sich hierdurch etwas an der hit-Rate fu r das Programm aus Aufgabenteil c)? Begru nden Sie Ihre Antwort!
(3 Punkte)

Zusatzblatt fu r Notizen Matrikelnummer: Seite 23

Zusatzblatt fu r Notizen GRA/TI Seite 24

Zusatzblatt fu r Notizen Matrikelnummer: Seite 25

Zusatzblatt fu r Notizen GRA/TI Seite 26