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 ausschließlich die Aufgabenbla ̈tter zu verwenden. Lo ̈sungsangaben außerhalb 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
(einschließlich 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 außer 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. Außerdem 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
5∗109
1∗109
1∗109
II
10∗109
1∗109
1∗109
III
9∗109
3∗109
0
IV
10∗109
2∗109
2∗109
keines der Programme wurde verwendet
Aufgabe 1 Matrikelnummer: Seite 5
d) Murx Electronics mo ̈chte außerdem 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 außerdem 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.
0x0100 L0: addi $sp, ______, _____ # Lege den Inhalt von
0x0104
0x0108
0x010C
0x0110
0x0114
0x0118
0x011C
0x0120 L1:
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