Klausur zur Vorlesung
Grundlagen der Rechnerarchitektur (GRA)
Prof. Marco Platzner Fachgebiet Technische Informatik Universita ̈t Paderborn
24.02.2017
• Die Bearbeitungsdauer betra ̈gt fu ̈r alle Studenten 90 Minuten. Es sind alle 5 Aufgaben zu bearbeiten.
• Es sind keine Hilfsmittel zugelassen.
• Schreiben Sie nicht mit Bleistift oder Rotstift.
• Verwenden Sie kein eigenes Papier. Bei Bedarf bekommen Sie Papier bei der Klau- suraufsicht.
• Schreiben Sie auf jedes Blatt (auch auf das Konzeptpapier) in Blockschrift Ihren Namen und Ihre Matrikelnummer.
• Bei mehreren pra ̈sentierten Lo ̈sungen wird die Aufgabe nicht gewertet! Streichen Sie daher bei Angabe mehrerer Lo ̈sungsansa ̈tze die nicht zu bewertenden Lo ̈sungen durch! Verwenden Sie kein Tipp-Ex.
• Abschreiben und abschreiben lassen oder Hilfe Dritter fu ̈hrt zum Nichtbestehen der Klausur.
Nachname: Vorname: Matrikelnummer: Studiengang:
Aufkleber
Aufgabe
1
2
3
4
5
Punkte
15
10
20
25
20
90
Erreicht
1
GRA/TI Aufgabe 1 (Multiple Choice) [15 Punkte]
Bei den folgenden Fragen ko ̈nnen keine, eine oder mehrere Antworten richtig sein. Kreuzen Sie die richtigen Antworten deutlich an.
(a) Welche Aussagen zu MIPS Adressierungsarten sind korrekt?
Die j Instruktion verwendet PC-relative Adressierung
Bei pseudodirekter Adressierung wird eine 26-Bit Adresse mit den oberen 4 Bits des PC Registers konkateniert
Bei PC-relativer Adressierung steht ein Operand im Hauptspeicher Die beq Instruktion verwendet Basisadressierung
(b) Zu den Aufgaben des Linkers za ̈hlen. . .
Bestimmung der Speicherbereiche, die durch die einzelnen Programm-
teile belegt werden
Auflo ̈sen der Querverweise zwischen den Programmteilen auf Basis der relocation information
Kopieren der Befehle und Daten aus der Programmdatei in den Hauptspeicher
Festlegen eines ausreichend großen Adressbereichs im Hauptspeicher fu ̈r Programmtext und Daten
(c) Welche Aussagen zu Caches sind korrekt?
Die Gro ̈ße des Caches ist abha ̈ngig vom Adressraum des Prozessors
Der Datencache wird ausschließlich fu ̈r die Speicherhierarchie verwendet
Um den Prozessor beim Schreiben nicht durch den Hauptspeicher zu bremsen, wird bei write-back ein Pufferspeicher (write buffer) verwendet
Einem page fault geht immer ein TLB miss voraus Seite 2 / 15
NAME: Matrikelnummer:
(d) Welche Aussagen zu Pipelining und Mehrfachzuordnung sind korrekt?
Durch Umordnen von Instruktionen ko ̈nnen Data Hazards reduziert
werden
Dynamisches Scheduling vereinfacht den Compilerentwurf im Vergleich zu statischem Scheduling
Code fu ̈r VLIW Prozessoren ist bina ̈rkompatibel zu anderen Prozessoren derselben ISA
Bei VLIW Prozessoren wird die Zuordnung zu den Ausfu ̈hrungs- einheiten vom Compiler durchgefu ̈hrt
(e) Welche Aussagen zu Arbitrierung sind korrekt?
Bei zentraler Arbitrierung kann Fairness garantiert werden
Wenn es mehrere Slaves gibt, muss der Bus arbitriert werden
Arbitrierung durch Selbstselektion ist ein verteiltes Arbitrierungsverfahren Daisy-Chain Arbitrierung ist ein verteiltes Arbitrierungsverfahren
Seite 3 / 15
GRA/TI
Aufgabe 2 (Amdahl’s Law) [10 Punkte]
Ein Unternehmen hat eine neuere Version eines Prozessors auf den Markt gebracht. Ein Kunde mo ̈chte auf einem Server die Vorga ̈ngerversion des Prozessors durch die neuere Ver- sion austauschen. Von dem neuen Prozessor ist bekannt, dass Load-/Store-Instruktionen drei mal schneller geworden sind. Zusa ̈tzlich soll es eine Verbesserung der Integerberech- nungen geben. Auf dem Server wird hauptsa ̈chlich ein Programm ausgefu ̈hrt, dessen In- struktionen zu 60% aus Load/Store-Instruktionen, zu 30% aus Integerberechnungen und zu 10% aus sonstigen Instruktionen bestehen. Die neue Gesamtausfu ̈hrungszeit des Pro- grammes betra ̈gt 36 Sekunden, was einen Speedup von 2 bedeutet.
(a) Wie groß ist die Verbesserung durch die Integerberechnungen?
(b) Wie groß wa ̈re der Speedup gewesen, wenn das Unternehmen auf die Verbesserung der Integerberechnung verzichtet ha ̈tte und wie lange wu ̈rde das Programm in dem Fall ausgefu ̈hrt werden?
Seite 4 / 15
NAME: Matrikelnummer:
Aufgabe 3 (Pipelining-Sprungvorhersage)
[20 Punkte]
Gegeben sind folgende zwei Automatengraphen fu ̈r 2-bit Sprungpra ̈diktoren:
taken
ST
T
WN N
not taken
taken
not taken
taken
Pra ̈diktor P1
WT T
SN N
taken
ST T
WN N
not taken WT taken T
not taken SN taken N
Pra ̈diktor P2
not taken
not taken
Hierbei soll bedeuten:
ST = taken ”strong“, WT = taken ”weak“,
WN = not taken ”weak“, SN = not taken ”strong“.
In den ”taken“ Zusta ̈nden sagen die Pra ̈diktoren voraus, dass dem bedingten Sprung gefolgt wird (T), in den ”not taken“ Zusta ̈nden hingegen, dass das Programm ohne Sprung fortgesetzt wird (N).
(a) Fu ̈llen Sie folgende Tabellen aus. Ersatztabellen finden Sie auf der na ̈chsten Seite.
Branch
1
2
3
4
5
6
7
8
9
10
Treffer
B1
Tatsa ̈chlich
T
N
T
T
N
T
T
N
N
N
—
Zustand P1
WT
Zustand P2
WT
B2
Tatsa ̈chlich
N
T
T
N
N
T
T
N
N
T
—
Zustand P1
WT
Zustand P2
WT
(b) Konstruieren Sie nun selbst eine Sequenz von tatsa ̈chlichen Sprungentscheidungen fu ̈r einen bedingten Sprung B3, bei der P1 mindestens 2 Treffer mehr als P2 erzielt. Eine Ersatztabelle finden Sie auf der na ̈chsten Seite.
Branch
1
2
3
4
5
6
7
8
9
10
Treffer
B3
Tatsa ̈chlich
—
Zustand P1
WT
Zustand P2
WT
Seite 5 / 15
taken
not taken
taken
not taken
GRA/TI
(c) Generalisieren Sie ihre Lo ̈sung zu Aufgabenteil (b). Unter welchen Umsta ̈nden ist P1 besser als P2, beziehungsweise wie muss eine Sprungentscheidungssequenz beschaffen sein, damit P2 eine schlechte Trefferquote hat, P1 aber nicht?
Ersatztabellen fu ̈r Teil (a). Ungu ̈ltige Lo ̈sungen streichen!
Branch
1
2
3
4
5
6
7
8
9
10
Treffer
B1
Tatsa ̈chlich
T
N
T
T
N
T
T
N
N
N
—
Zustand P1
WT
Zustand P2
WT
B2
Tatsa ̈chlich
N
T
T
N
N
T
T
N
N
T
—
Zustand P1
WT
Zustand P2
WT
Ersatztabelle fu ̈r Teil (b). Ungu ̈ltige Lo ̈sungen streichen!
Branch
1
2
3
4
5
6
7
8
9
10
Treffer
B3
Tatsa ̈chlich
—
Zustand P1
WT
Zustand P2
WT
Seite 6 / 15
NAME: Matrikelnummer:
Seite 7 / 15
GRA/TI Aufgabe 4 (Caches) [25 Punkte]
(a) Gegeben sei eine byte-adressierbare Architektur mit einem 32-bit Adressraum. Die jeweils 16 kB großen L1 Instruktions- und Datencaches sind 2-fach satzassoziativ und haben eine Blockgro ̈ße von vier Worten. Jedes Wort besteht aus 4 Bytes. Bitte erga ̈nzen Sie:
Der Blockindex umfasst die Bits Der Index umfasst die Bits
Der Tag umfasst die Bits
bis bis
bis
(b) Wie viele Speicherbits braucht man fu ̈r die Implementierung beider Caches aus (a), wenn neben dem valid-Bit auch zwei Bits fu ̈r die Ersetzungsstrategie abspeichert werden? Sie brauchen den Ausdruck nicht auszurechnen.
(c) Die Hit-Time des Instruktionscaches aus (a) betra ̈gt einen Taktzyklus bei einer Miss-Rate von 2%. Der Datencache wird von 30% aller Instruktionen angesprochen und besitzt eine Hit-Time von einem Taktzyklus bei einer Hit-Rate von 92%. Die Miss-Penalty betra ̈gt fu ̈r beide Caches 500 Taktzyklen. Wie hoch ist die mittlere Zugriffszeit pro Instruktion bei einer 3 GHz schnellen CPU?
Seite 8 / 15
NAME: Matrikelnummer:
(d) In dieser Aufgabe sollen fu ̈r den Instruktionscache aus der Aufgabe (a) die Least und Most Recently Used Ersetzungsstrategien verglichen werden. Der Cache ist nun nicht mehr 16 kB sondern 128 Byte groß. Weiterhin ist dazu die folgende Adressse- quenz fu ̈r Lesezugriffe gegeben:
120, 90, 40, 170, 130, 144, 180, 60
Bitte erga ̈nzen Sie die Tabellen zu Cachebelegungen sowie Hits und Misses fu ̈r beide
Ersetzungsstrategien. Welche Ersetzungsstrategie hat eine bessere Hit-Rate?
Bitte beachten Sie, dass das Feld Time den Zeitpunkt des Zugriffs angibt. Sollte ein Block u ̈berschrieben werden, schreiben Sie bitte die Speicheradressen der neuen Werte mit einem Komma getrennt neben die alten Werte. “m[x:y]” steht dabei fu ̈r den Inhalt des Hauptspeichers von Byteadresse x bis y.
Least Recently Used:
Time
5
6
7
8
9
10
11
12
Adresse
120
90
40
170
130
144
180
60
Hit/Miss
Index
V
Data
Time
V
Data
Time
00-15
0
m[128:143]
1
1
m[00:15]
1
16-31
0
m[80:95]
6
1
m[80:95]
0
32-47
1
m[160:175]
2
1
m[96:111]
3
48-63
0
m[112:127]
5
1
m[48:63]
4
Most Recently Used:
Time
5
6
7
8
9
10
11
12
Adresse
120
90
40
170
130
144
180
60
Hit/Miss
Index
V
Data
Time
V
Data
Time
00-15
0
m[128:143]
1
1
m[00:15]
1
16-31
0
m[80:95]
6
1
m[80:95]
0
32-47
1
m[160:175]
2
1
m[96:111]
3
48-63
0
m[112:127]
5
1
m[48:63]
4
Seite 9 / 15
GRA/TI
Ersatztabellen:
Time
5
6
7
8
9
10
11
12
Adresse
120
90
40
170
130
144
180
60
Hit/Miss
Index
V
Data
Time
V
Data
Time
00-15
0
m[128:143]
1
1
m[00:15]
1
16-31
0
m[80:95]
6
1
m[80:95]
0
32-47
1
m[160:175]
2
1
m[96:111]
3
48-63
0
m[112:127]
5
1
m[48:63]
4
Ersatztabellen:
Time
5
6
7
8
9
10
11
12
Adresse
120
90
40
170
130
144
180
60
Hit/Miss
Index
V
Data
Time
V
Data
Time
00-15
0
m[128:143]
1
1
m[00:15]
1
16-31
0
m[80:95]
6
1
m[80:95]
0
32-47
1
m[160:175]
2
1
m[96:111]
3
48-63
0
m[112:127]
5
1
m[48:63]
4
Seite 10 / 15
NAME: Matrikelnummer:
Aufgabe 5 (Statische Mehrfachzuordnung) [20 Punkte]
Abbildung 1 zeigt eine for-Schleife und Abbildung 2 den fu ̈r den Schleifenrumpf erzeugten MIPS-Code. Register $s1 wird vor der Ausfu ̈hrung des Schleifenrumpfs mit der Adresse von x[0], Register $s2 mit der Adresse von y[0] und der Schleifenza ̈hler $s3 mit 512 initialisiert.
for (i=0; i<512; i++)
x[i] = x[i]*8 + y[i];
L1: lw
sll $t0, $t0, 3
lw $t1, 0($s2)
add $t1, $t1, $t0
sw $t1, 0($s1)
addi $s1, $s1, 4
addi $s2, $s2, 4
addi $s3, $s3, -1
bne $s3, $zero, L1
Abbildung 2: MIPS-Code
Abbildung 1: for-Schleife
Die Schleife wird auf eine MIPS-Architektur mit statischer Mehrfachzuordnung abge- bildet. Die Architektur besitzt vier Ausfu ̈hrungseinheiten, zwei ALU/BR-Einheiten fu ̈r arithmetische-logische Instruktionen sowie bedingte und unbedingte Spru ̈nge und zwei LD/ST-Einheiten fu ̈r Datentransfer-Instruktionen.
(a) Geben Sie den idealen CPI-Wert an, der mit dieser MIPS-Architektur erreichbar ist.
CPIideal =
(b) Bilden Sie den Code in Abbildung 2 durch statisches Pipelinescheduling auf die Architektur ab. Vervollsta ̈ndigen Sie dazu Tabelle 1. In dieser Tabelle wird jeder Ausfu ̈hrungseinheit eine Spalte zugeordnet und jede Zeile entspricht einem Takt- zyklus. Eine Instruktion in einer Zelle der Tabelle bedeutet, dass die Instruktion in dem entsprechenden Taktzyklus in der Ausfu ̈hrungseinheit bearbeitet wird. Die Architektur benutzt forwarding, dh. Instruktionen mit Datenabha ̈ngigkeiten ko ̈nnen direkt aufeinander folgen, außer bei einem load-use Konflikt, der einen stall cycle erfordert. Nehmen Sie an, dass die Sprungvorhersage perfekt funktioniert und dass es keine branch-delay slots gibt.
$t0, 0($s1)
Seite 11 / 15
ALU/BR #1
ALU/BR #2 LD/ST #1
Tabelle 1: Code fu ̈r statische 4-fach Zuordnung
ALU/BR #2 LD/ST #1
GRA/TI
LD/ST #2
addi $s2, $s2, 4
lw $t0, 0($s1)
bne $s3, $zero, L1
L1:
ALU/BR #1
LD/ST #2
addi $s2, $s2, 4
lw $t0, 0($s1)
bne $s3, $zero, L1
L1:
Tabelle 2: Code fu ̈r statische 4-fach Zuordnung (Ersatztabelle) Geben Sie den CPI-Wert an, den der Code in Tabelle 1 erreicht.
CPICode-Tabelle-1 =
Seite 12 / 15
NAME: Matrikelnummer:
(c) Entrollen Sie die Schleife 2-fach, so dass der neue Schleifenrumpf zwei Iterationen der urspru ̈nglichen Schleife berechnet. Fu ̈hren Sie dazu das loop unrolling und das register renaming durch und geben Sie den resultierenden MIPS-Code in Abbildung 3 an.
L1: lw $t0, 0($s1)
bne $s3, $zero, L1
Abbildung 3: MIPS-Code, Schleife 2-fach entrollt
(d) Bilden Sie den Code aus Aufgabenteil (c) durch statisches Pipelinescheduling auf die Architektur ab, indem Sie Tabelle 3 vervollsta ̈ndigen.
Seite 13 / 15
GRA/TI
ALU/BR #1 ALU/BR #2 LD/ST #1 LD/ST #2
L1:
Tabelle 3: Code fu ̈r statische 4-fach Zuordnung, Schleife 2-fach entrollt
ALU/BR #1 ALU/BR #2 LD/ST #1 LD/ST #2
L1:
Tabelle 4: Code fu ̈r statische 4-fach Zuordnung, Schleife 2-fach entrollt (Ersatztabelle) Geben Sie den CPI-Wert an, den der Code in Tabelle 3 erreicht.
CPICode-Tabelle-3 =
Seite 14 / 15
NAME: Matrikelnummer:
Konzeptpapier: Falls der Platz unter den einzelnen Aufgaben nicht ausreicht, ko ̈nnen Sie diese Seiten fu ̈r Zwischenrechnungen nutzen. Bitte Lo ̈sung und Lo ̈sungsweg eindeutig mit der Aufgabennummer markieren!
Seite 15 / 15