[SOLVED] C MIPS Universita t Paderborn

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

maximale Punkte
11
9
10
20
20
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) 11 Punkte
a) Die Firma Limited Performance Corp. hat einen Prozessor mit einem idealen CPI-Wert von 1 entwickelt, der mit 500 MHz betrieben werden kann. Im Befehlscache befinden sich bereits alle beno tigten Befehle. Um schnelle Speicherzugriffe auf Daten zu un- terstu tzen, sollen zwei Cache-Ebenen realisiert werden (L1 und L2). Die Fehlgriffsrate fu r den L1-Cache sei 5 %. Bei einem Fehlgriff im L1-Cache wird auf den L2-Cache zugegriffen. Die Zeit dafu r betra gt 80 ns. Von den notwendigen Zugriffen auf den L2-Cache sind 40 % Fehlgriffe und die Daten mu ssen dann aus dem Hauptspeicher geholt werden. Die Zeit dafu r betra gt 200 ns. Wie gro ist der realistische CPI-Wert
(einschlielich Speicherwartetakten), wenn 50% der Befehle auf Daten zugreifen? Bitte kreuzen Sie die richtige Lo sung an.
(3 Punkte)
7
3
5
1,98
keine Lo sung ist richtig
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 5 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 den richtigen Wert an.
gro er als 3/5
gro er als 4/5
gro er als 1/2
gro er als 12/25
keine Lo sung ist richtig
(3 Punkte)

Aufgabe 1 GRA Seite 4
c) Die Konkurrenzfirma Murx Electronics hat eine neue CPU entwickelt, die mit 500 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 600 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?
Kreuzen Sie bitte alle richtigen Antworten an:
(3 Punkte)
Programm
Anzahl der Befehle in Klasse
A
B
C
I
5109
1109
1109
II
10109
1109
1109
III
9109
3109
0
IV
10109
2109
2109
keines der Programme wurde verwendet

Aufgabe 1 Matrikelnummer: Seite 5
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 Pipe- linestufen aufgeteilt. Zur Abarbeitung einer Pipelinestufe wird 1 CPU-Zyklus beno tigt. Die Analyse von Benchmarkprogrammen zeigt, dass die Wahrscheinlichkeit fu r einen Konflikt 12,5 % betra gt. Bei einem Konflikt mu ssen im Durchschnitt 2 Wartezyklen 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
(2 Punkte)

Aufgabe 2 GRA Seite 6
Aufgabe 2: (Maschinenstrukturen) 9 Punkte Auf einem Rechnersystem mit Akkumulator-Architektur soll die Berechnung
c = ak + b
ausgefu hrt werden. Nach Beendigung des Programms soll sich c im Speicher befinden. Gehen Sie davon aus, dass die Variablen a und b zu Beginn im Speicher liegen und k konstant ist. Die zur Verfu gung stehenden Assemblerinstruktionen sind {mul, load, store, add}.
a) Wie lautet der Programmcode der Berechnung und wie viele Befehle werden beno tigt (in Abha ngigkeit von k)?
(4 Punkte)
b) DieBerechnungkannalternativauchaufeinemRechnersystemmitStack-Architektur ausgefu hrt werden. Hierzu stehen die Assemlerinstruktionen {mul, pop, push, add} zur Verfu gung. Geben Sie wieder den Programmcode der Berechnung in Abha ngigkeit von k an. Welche Architektur ist fu r die gegebene Berechnung bezu glich Anzahl der beno tigten Befehle besser geeignet? Begru nden Sie Ihre Antwort.
(5 Punkte)

Aufgabe 3 Matrikelnummer: Seite 7 Aufgabe 3: (Datenpfad) 10 Punkte
a) Bei der Verarbeitung von Befehlen kann es im MIPS Datenpfad mit fu nfstufiger Pipeline zu Datenhazards kommen. Um diese aufzulo sen, ko nnen sowohl Stalls (Leer- zyklen) in die Pipeline eingefu gt werden als auch eine Forwarding-Einheit integriert werden.
Welche weitere Mo glichkeit besteht meistens auch noch?
(1 Punkt)
b) Bei der Verarbeitung folgender Speicher-zu-Speicher Kopiersequenz tritt ein Daten- hazard auf.
lw$2, 100($5)
sw$2, 200($6)
Vervollsta ndigen Sie die zweite Zeile der Pipelinebelegung (siehe Abbildung 1) und fu gen Sie die minimale Anzahl an Stalls (STA) in die Pipeline ein, um den Hazard aufzulo sen. Begru nden Sie kurz Ihre Antwort.
lw$2, 100($5)
sw$2, 200($6)
lw$2, 100($5)
sw$2, 200($6)
Abbildung 1: Pipelinebelegung
IF
ID/RF
EX
MEM
IF
IF
ID/RF
EX
MEM
Abbildung 2: Ersatzgrafik, ungu ltige Lo sung streichen!
WB
WB
(3 Punkte)
IF

Aufgabe 3 GRA Seite 8
c) Der Datenhazard, der durch die Speicher-zu-Speicher Kopiersequenz aus Aufgaben- teil b) entstanden ist, soll nun durch eine Forwarding-Einheit aufgelo st werden. Modifizieren Sie den Datenpfad in Abbildung 3 entsprechend.
(Ersatzabbildung auf Seite 10, ungu ltige Lo sung streichen!)
(3 Punkte)
d) Geben Sie eine mo gliche lw-sw Instruktionssequenz an, bei der trotz der eingefu gten Forwarding-Einheit Stalls notwendig sind. Begru nden Sie Ihre Antwort.
(3 Punkte)

Aufgabe 3 Matrikelnummer: Seite 9
Instruction
PC Address
Read
register 1 Read
4
Add Add result
M u x
Add
Instruction memory
Read data 1 register 2
Zero
IF/ID
ID/EX
EX/MEM
MEM/WB
Write Read register data 2
ALU ALU result
Read Address data
Write Registers data
x
memory
M x
16
Sign extend
32
Shift left 2
M
u Data u
Abbildung 3: Fu nfstufige Pipeline des MIPS Prozessors
M u x
Write data

Aufgabe 3 GRA Seite 10
Instruction
PC Address
Read
register 1 Read
4
Add Add result
M u x
Add
Instruction memory
Read data 1 register 2
Zero
IF/ID
ID/EX
EX/MEM
MEM/WB
Write Read register data 2
ALU ALU result
Read Address data
Write Registers data
x
memory
M x
16
Sign extend
32
Shift left 2
M
u Data u
Abbildung 4: Ersatzgrafik, ungu ltige Lo sung streichen!
M u x
Write data

Aufgabe 4 Matrikelnummer: Seite 11 Aufgabe 4: (Pipelining) 20 Punkte
a) Geben Sie Rechenzeit, Speed-Up und Effizienz einer Pipeline mit 10 homogen verteilten Stufen fu r 991 Instruktionen an! Die sequentielle Abarbeitung eines Befehls betrage 0,1 ms. (2 Punkte)
Rechenzeit sequentiell: Rechenzeit Pipeline: Speed-Up:
Effizienz:
b) Geben Sie Rechenzeit, Speed-Up und Effizienz einer Pipeline mit 10 inhomogen verteilten Stufen fu r 991 Instruktionen an! Die sequentielle Abarbeitung eines Befehls betrage 0,1 ms. Die Verzo gerung der Stufen ist in nachfolgender Tabelle angegeben.
(4 Punkte)
Stufe Verzo gerung (ms)
01234 5/1000 1/100 2/100 1/100 1/100
Stufe Verzo gerung (ms)
56789 1/100 1/100 1/100 1/100 5/1000
Rechenzeit sequentiell: Rechenzeit Pipeline: Speed-Up:
Effizienz:

Aufgabe 4 GRA Seite 12
c) Geben Sie fu r die Sprungfolge NT NT T NT NT T T T die Ausgabe und die Anzahl korrekt vorhergesagter Ereignisse der statischen Sprungvorhersage always taken und der Moore-Automaten A und B mit Eingabe- und Ausgabealphabet {T,NT} und Zusta nden {00, 01, 10, 11} bzw. {0, 1} an. Die Zustandsu berfu hrungs- und Ausgabe- funktionen ko nnen den nachfolgenden Abbildungen entnommen werden. Weiterhin seien die Pra diktoren A und B mit 00 bzw. 0 initialisiert.
T
NT NT NT
00 01 10 11
T TT NT NT TTT
(a) Pra diktor A
NT
T0 1NT
(6 Punkte)
NT
Zeitpunkt
T
T
NT
Always Taken
Richtig Vorhersage Sprung oder
(b) Pra diktor B
0 NT 1 NT 2T 3 NT 4 NT 5T 6T 7T
Falsch?

Aufgabe 4 Matrikelnummer: Seite 13
Pra diktor A
Zeitpunkt
Aktueller Zustand
Vorhersage
Sprung
Richtig oder Falsch?
Folgender Zustand
0
00
NT
1
NT
2
T
3
NT
4
NT
5
T
6
T
7
T
Pra diktor B
Zeitpunkt
Aktueller Zustand
Vorhersage
Sprung
Richtig oder Falsch?
Folgender Zustand
0
0
NT
1
NT
2
T
3
NT
4
NT
5
T
6
T
7
T
Anzahl der Treffer always taken: Pr adiktor A: Pr adiktor B:

Aufgabe 4 GRA Seite 14
Ersatztabelle Always Taken, ungu ltige Lo sung streichen!
Zeitpunkt
Vorhersage
Sprung
Richtig oder Falsch?
0
NT
1
NT
2
T
3
NT
4
NT
5
T
6
T
7
T
Ersatztabelle Pra diktor A, ungu ltige Lo sung streichen!
Zeitpunkt
Aktueller Zustand
Vorhersage
Sprung
Richtig oder Falsch?
Folgender Zustand
0
00
NT
1
NT
2
T
3
NT
4
NT
5
T
6
T
7
T

Aufgabe 4 Matrikelnummer: Seite 15
Ersatztabelle Pra diktor B, ungu ltige Lo sung streichen!
Zeitpunkt
Aktueller Zustand
Vorhersage
Sprung
Richtig oder Falsch?
Folgender Zustand
0
0
NT
1
NT
2
T
3
NT
4
NT
5
T
6
T
7
T

Aufgabe 4 GRA Seite 16
d) Untersuchen Sie die Pipeline des in der Abbildung dargestellten MIPS-Prozessors! Fu r alle Befehle gelte die Registerreihenfolge: destination source1 source2. Es ist keinerlei Forwarding implementiert. Geben Sie fu r die Programme P1-P3 an, ob ein Daten-, Kontroll-, Strukturhazard oder kein Hazard vorliegt! Geben Sie auerdem die
Anzahl der mo glichen Wartezyklen an.
(6 Punkte)
P1 A: add $t1 $t2 $t3 B: add $t2 $t3 $t4 C: add $t3 $t4 $t1 D: add $t4 $t5 $t6 E: add $t5 $t6 $t7 F: add $t6 $t3 $t8 G: add $t7 $t8 $t9
P1:

Aufgabe 4 P2
Matrikelnummer:
Seite 17
P3
A: add $t1 $t2 $t3 B: lw $t2 0x99($t3) C: add $t3 $t4 $t5 D: add $t4 $t5 $t6 E: add $t5 $t6 $t7
A: add $t1 $t2 $t3 B: beq $t2 $t3 F C: add $t3 $t4 $t5 D: add $t4 $t5 $t6 E: add $t5 $t6 $t7 F: add $t6 $t7 $t8 G: add $t9 $t10 $t11
P2:
e) Zur Auflo sung von Kontrollhazards werden verzo gerte Spru nge (delayed branches) ein- gefu hrt, die 2 Delay- Slots vorsehen. A ndern Sie die Befehlsreihenfolge des Programms P3 aus Aufgabenteil d), sodass etwaige Hazards aufgelo st werden ohne die Semantik des Programms zu vera ndern! Ko nnen die Hazards komplett aufgelo st werden? Um wie viel schneller wird das Programm abgearbeitet? Begru nden Sie Ihre Entscheidungen!
Hinweis: Die Reihenfolge der Befehle kann u ber Label angegeben werden.
(2 Punkte)
P3:
P3:

Aufgabe 5 GRA Seite 18
Aufgabe 5: (Assembler) 20 Punkte
Nachfolgend ist ein MIPS Assemblerprogramm abgebildet. Die erste Spalte zeigt dabei die Adressen im Hexadezimalsystem, an denen die jeweiligen Instuktionen im Programmspeicher stehen.
0x0100L0:addi$sp, ______, _____ # Lege den Inhalt von
0x0104
0x0108
0x010C
0x0110
0x0114
0x0118
0x011C
0x0120L1:
0x0124
0x0128
0x012C
0x0130
0x0134
0x0138
sw$ra,
sw$a0,
slti$t0,
______$t0,
addi$v0,
addi$sp,
jr______
addi$a0,
jal L0
lw$a0,
lw$ra,
mul $v0,
addi$sp,
jr______
______
______
$a0,1
$zero, L1
$zero,1
______,_____# Stack Pointer aktualisieren
$a0,
-1
a) Vervollsta ndigen Sie das oben abgebildete Assemblerprogramm gema der im Code angegebenen Kommentare.
(10 Punkte)
b) Analysieren Sie eine Ausfu hrung des Assemblerprogramms mit der folgenden initialen Belegung der Register $sp, $a0, $v0 und $ra:
(8 Punkte)
Geben Sie in den beiden folgenden Tabellen die Registerbelegungen und die Belegungen der Speicherstellen zu den ersten 5 Zeitpunkten des Erreichens der Programmzeile an der Adresse 0x0100 an. Geben Sie die Inhalte jeweils vor der Ausfu hrung der Programmzeile an, sofern sie durch die Programmausfu hrung bekannt sind. Alle anderen Stellen lassen Sie leer. Sollte diese Zeile keine 5 mal erreicht werden, lassen Sie auch die verbleibenden Spalten leer.
$v0
# $ra und $a0
# auf den Stack
# Sprung zu L1, falls $a0 >= 1
# Ruecksprung
______
______
$a0,
______,_____# Stack Pointer aktualisieren
# Ruecksprung
# $a0 und $ra vom
# Stack holen
Register
Wert
$sp
0x1000
$a0
0x0003
$v0
0x0000
$ra
0x0010

Aufgabe 5 Matrikelnummer: Seite 19
1
2
3
4
5
$sp
0x1000
$a0
0x0003
$v0
0x0000
$ra
0x0010
Tabelle 1: Registerinhalte
1
2
3
4
5
0x1008
0x1004
0x1000
0x0FFC
0x0FF8
0x0FF4
0x0FF0
0x0FEC
0x0FE8
0x0FE4
0x0FE0
0x0FDC
0x0FD8
Tabelle 2: Speicherinhalt

Aufgabe 5 GRA Seite 20
1
2
3
4
5
$sp
0x1000
$a0
0x0003
$v0
0x0000
$ra
0x0010
Tabelle 3: Ersatztabelle Registerinhalte, ungu ltige Lo sung steichen!
1
2
3
4
5
0x1008
0x1004
0x1000
0x0FFC
0x0FF8
0x0FF4
0x0FF0
0x0FEC
0x0FE8
0x0FE4
0x0FE0
0x0FDC
0x0FD8
Tabelle 4: Ersatztabelle Speicherinhalt, ungu ltige Lo sung steichen!
c) Welchen Wert ha lt das Register $v0 nach Abarbeitung des Assemblerprogramms bei einer initialen Belegung von $a0 mit dem Wert 0x0004?
(2 Punkte)

Aufgabe 6 Matrikelnummer: Seite 21
Aufgabe 6: (Speicherverwaltung) 20 Punkte
Gehen Sie von einem Computer aus, der zur Beschleunigung der Speicherzugriffe auf den byteadressierten Arbeitsspeicher mit einem Adressraum von 2 GB einen Cache mit 8 Rahmen vorsieht, wobei der Datenbereich jedes Blocks 2 Worte zu je 32 Bit umfasst. Der Cache sei als direkt abgebildeter Cache organisiert.
a) Geben Sie die Breite des Adressbus sowie die Anzahl an Bits fu r Tag, Index und Offsets an.
(3 Punkte)
Adressbus: Tag: Index: Wortoffset: Byteoffset:
b) Wie viel Speicher wird fu r die Implementierung eines solchen Cache (inkl. Overhead) beno tigt? Geben Sie den Rechenweg und das Ergebnis in Byte an.
Cache-Gro e (in Byte):
(3 Punkte)

Aufgabe 6 GRA Seite 22
c) Der Prozessor la dt nun sequentiell die Daten der folgenden Byteadressen (fu hrende Nullen werden nicht mit angegeben):
t=1:0xc25
t=2:0xb7a
t=3:0xb04
t=4:0x415
t=5:0xbd1
t=6:0xc21
t=7:0x804
t=8:0xfc7
Gehen Sie von folgendem Zustand des Cache zum Zeitpunkt t = 0 aus:

Geben Sie den Zustand des Cache nach jedem Speicherzugriff in den folgenden Tabellen an und bestimmen Sie die Hitrate.
Hinweis: Es reicht aus, wenn Sie nur die Zeilen der Tabelle, die sich a ndern, angeben.
(8 Punkte) t=1: Adresse=0xc25 t=2: Adresse=0xb7a
Index
V
Tag
0
0
100000
1
0
011000
2
1
010000
3
1
110010
4
1
110000
5
1
010100
6
1
011110
7
0
101101
Index
V
Tag
0
1
2
3
4
5
6
7
Index
V
Tag
0
1
2
3
4
5
6
7

Aufgabe 6 Matrikelnummer:
Seite 23
t=3: Adresse=0xb04
t=4: Adresse=0x415
Index
V
Tag
0
1
2
3
4
5
6
7
Index
V
Tag
0
1
2
3
4
5
6
7
t=5: Adresse=0xbd1
t=6: Adresse=0xc21
Index
V
Tag
0
1
2
3
4
5
6
7
Index
V
Tag
0
1
2
3
4
5
6
7

Aufgabe 6 GRA Seite 24
t=7: Adresse=0x804 t=8: Adresse=0xfc7
Index
V
Tag
0
1
2
3
4
5
6
7
Index
V
Tag
0
1
2
3
4
5
6
7
Hitrate:

Aufgabe 6 Matrikelnummer: Seite 25
Adresse= Adresse=
Index
V
Tag
0
1
2
3
4
5
6
7
Index
V
Tag
0
1
2
3
4
5
6
7
Tabelle 5: Ersatztabelle, ungu ltige Lo sungen streichen!
d) Wie hoch ist die durchschnittliche Zugriffszeit, ausgehend von der Hitrate des Cache aus Aufgabenteil c), wenn der Zugriff auf den Cache 20ns und der Zugriff auf den Hauptspeicher 200ns betra gt? Geben Sie auch den Rechenweg an.
Durchschnittliche Zugriffszeit:
(3 Punkte)

Aufgabe 6 GRA Seite 26
e) Nehmen Sie an, der Cache sei leer und es sei folgender Ausschnitt des Hauptspeichers gegeben. Die Adressen sind bina r (fu hrende Nullen werden nicht mit angegeben), die Daten in hexadezimaler Schreibweise angegeben:
(3 Punkte)
Adresse
Adresse
Adresse
Adresse
10 0000 1000
ff
10 0000 1001
9c
10 0000 1010
ad
10 0000 1011
c8
10 0001 0000
01
10 0001 0001
d3
10 0001 0010
fa
10 0001 0011
c6
10 0001 1000
1c
10 0001 1001
c3
10 0001 1010
d4
10 0001 1011
cd
10 0010 0000
02
10 0010 0001
13
10 0010 0010
7c
10 0010 0011
51
10 0000 1100
f0
10 0000 1101
da
10 0000 1110
aa
10 0000 1111
4c
10 0001 0100
21
10 0001 0101
01
10 0001 0110
dd
10 0001 0111
df
10 0001 1100
25
10 0001 1101
e3
10 0001 1110
e2
10 0001 1111
7d
10 0010 0100
00
10 0010 0101
a0
10 0010 0110
f4
10 0010 0111
22
Es soll nun auf das Wort an der Adresse 0x218 zugegriffen werden. Geben Sie alle Daten an, die in den Cache geladen werden (nach jedem Byte getrennt durch ein Komma):
U bertragene Daten:
Data
Data
Data
Data

Zusatzblatt fu r Notizen Matrikelnummer: Seite 27

Zusatzblatt fu r Notizen GRA Seite 28

Zusatzblatt fu r Notizen Matrikelnummer: Seite 29

Zusatzblatt fu r Notizen GRA Seite 30