Klausur zur Vorlesung
Grundlagen der Rechnerarchitektur (GRA)
Prof. Marco Platzner Fachgebiet Technische Informatik Universita ̈t Paderborn
27.09.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
15
20
25
15
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) Wie nennt man die Konvention, nach der das niederwertigste Byte eines Wortes an der niedrigsten Byte-Adresse im Speicher abgelegt wird?
Little Endian Big Endian CISC
RISC
(b) Der CPI-Wert (Cycles-Per-Instruction), den ein ausgefu ̈hrtes Programm auf einem Prozessor erreicht, wird beeinflusst durch:
Programmiersprache
Compiler
Instruktionssatz des Prozessors Technologie des Prozessors
(c) Welche MIPS-Rate muss man fu ̈r einen Prozessor mit einer Taktperiode von 1 ns und einem CPI-Wert von 0,5 angeben?
Nicht bestimmbar, da zu wenige Parameter angegeben sind. 1000 MIPS
2000 MIPS
5000 MIPS
Seite 2 / 22
NAME: Matrikelnummer:
(d) Welche Maßnahmen reduzieren die Miss-penalty eines Caches? gro ̈ßerer Cache
ho ̈herer Grad an Assoziativita ̈t Victim Cache
breite Speicherorganisation
(e) Wie gross ist die durchschnittliche Rotationslatenz bei einer Festplatte mit 8000 Umdrehungen pro Minute?
7,75 μs 1,50 ms 3,75 ms 40,00 ms
Seite 3 / 22
GRA/TI Aufgabe 2 (Assembler) [15 Punkte]
(a) Gegeben ist eine unvollsta ̈ndige Implementierung der rekursiven Fibonacci-Funktion f(n). Vervollsta ̈ndigen Sie die rekursive Implementierung. Beachten Sie dabei die in der Vorlesung behandelte Konvention fu ̈r die Verwendung verschiedener Registertypen bei Funktionsaufrufen. Kommentieren Sie bitte Ihren Code.
f:
# Sichern relevanter Register
# ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Abbruchbedingung fu ̈r die Rekursion
# $v0 = 1
# ist n < 3 ?
# dann springe zu RET
# ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Wiederherstellen relevanter Register # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________
RET:
addi $a0, $a0, -1
jal f
sw $v0, 0($sp)
addi $a0, $a0, -1
jal lw add
f
$t0, 0($sp)
$v0, $v0, $t0
Seite 4 / 22
NAME: Matrikelnummer: Ersatzlo ̈sung (inkorrekte Lo ̈sung bitte streichen):
f:
# Sichern relevanter Register
# ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Abbruchbedingung fu ̈r die Rekursion
# $v0 = 1
# ist n < 3 ?
# dann springe zu RET
# ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # Wiederherstellen relevanter Register # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________ # ____________________________________
RET:
addi $a0, $a0, -1
jal f
sw $v0, 0($sp)
addi $a0, $a0, -1
jal lw add
f
$t0, 0($sp)
$v0, $v0, $t0
Seite 5 / 22
GRA/TI (b) Wie viele Worte werden auf dem Stack bei der Berechnung von f(n) mit n = 3,4,5
ho ̈chstens belegt? Vervollsta ̈ndigen Sie bitte die folgende Tabelle.
Ersatzlo ̈sung (inkorrekte Lo ̈sung bitte streichen):
n
3
4
5
maximale Stackbelegung in Worten
n
3
4
5
maximale Stackbelegung in Worten
(c) Die Fibonacci Funktion f(n) kann auch durch einen iterativen Algorithmus berechnet werden. Welche Vorteile wu ̈rde eine iterative Implementierung von f(n) gegenu ̈ber der rekursiven Implementierung bieten?
Seite 6 / 22
NAME: Matrikelnummer:
Seite 7 / 22
GRA/TI Aufgabe 3 (Instruktionssatzarchitekturen) [20 Punkte]
(a) EssollendiedreiInstruktionssatzarchitekturenStack-,Speicher-Speicher-undRegister- Register-Architektur hinsichtlich des Speicherbedarfs und der Speicherbandbreite untersucht werden. Gegeben sei dafu ̈r folgendes Programm fu ̈r eine dieser Architek- turen:
1: add Adresse_A Adresse_I Adresse_I
2: mul Adresse_A Adresse_A Adresse_S
3: add Adresse_B Adresse_B Adresse_A
Fu ̈r welche der Instruktionssatzarchitekturen ist dieses Programm? Stack-Architektur
Speicher-Speicher-Architektur
Register-Register-Architektur
(b) Was berechnet das Programm? Schreiben Sie die arithmetischen Ausdru ̈cke hin.
1A= 2
3
Tabelle 1: Programm als arithmetische Sequenz
(c) Erstellen Sie nun fu ̈r jede der drei Architekturen eine Assemblercodesequenz, die das Programm implementiert, und bestimmen Sie den Speicherbedarf der Instruktionen, sowie die Menge der u ̈bertragenen Daten in Bytes. Geben Sie fu ̈r die Stack- und Register-Register-Architektur außerdem die Belegung des Stacks (Abb. 1) und der Register (Abb. 3) an.
Alle auftretenden Operanden (z.B. I, S, ...) sind 32 bit groß und liegen im Spei- cher. Alle Ergebnisse (A und B) sind ebenfalls 32 bit groß und mu ̈ssen nach Ablauf des Programms im Speicher abgelegt sein. Nehmen Sie an, dass der opcode einer Instruktion 1 Byte betra ̈gt, die Speicheradressen 16 bit und die Registeradressen 4 bit lang sind. Die Instruktionsla ̈nge muss ein Vielfaches von einem Byte sein.
Seite 8 / 22
NAME: Matrikelnummer:
(i) Stack-Architektur. Verfu ̈gbare Instruktionen: push, pop, add, mul
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Tabelle 2: Programm in Stack-Architektur
Nach Instruktion 1
Nach Instruktion 2
Nach Instruktion 3
Nach Instruktion 4
Nach Instruktion 5
Nach Instruktion 6
Nach Instruktion 7
Nach Nach Nach
Nach
Instruktion 11 Instruktion 12 Instruktion 13 Instruktion 14 Instruktion 15 Instruktion 16 Instruktion 17 Instruktion 18 Instruktion 19 Instruktion 20
Abbildung 1: Belegung des Stacks
Nach
Nach
Nach
Nach
Nach
Nach
Nach Nach Nach
Instruktion 8
Instruktion 9 Instruktion 10
Seite 9 / 22
GRA/TI
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Tabelle 3: Programm in Stack-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen!
Nach Instruktion 1
Nach Instruktion 2
Nach Instruktion 3
Nach Instruktion 4
Nach Instruktion 5
Nach Instruktion 6
Nach Instruktion 7
Nach Instruktion 8
Nach Nach Instruktion 9 Instruktion 10
Nach
Instruktion 11 Instruktion 12 Instruktion 13 Instruktion 14 Instruktion 15 Instruktion 16 Instruktion 17 Instruktion 18 Instruktion 19 Instruktion 20
Abbildung 2: Belegung des Stacks - Ersatz, ungu ̈ltige Lo ̈sung streichen! Seite 10 / 22
Nach
Nach
Nach
Nach
Nach
Nach
Nach Nach Nach
NAME: Matrikelnummer:
(ii) Register-Register-Architektur. Verfu ̈gbare Instr.: load, store, add, mul
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Reg0 Reg1 Reg2 Reg3 Reg4 Reg5
Nach Instruktion 1
Nach Instruktion 2
Nach Instruktion 3
Nach Instruktion 4
Nach Instruktion 5
Nach Instruktion 6
Nach Instruktion 7
Nach Nach Nach
Tabelle 4: Programm in Register-Register-Architektur
Abbildung 3: Belegung der Register
Instruktion 8
Instruktion 9 Instruktion 10
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 5: Programm in Register-Register-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen!
Reg0 Reg1 Reg2 Reg3 Reg4 Reg5
Nach Instruktion 1
Nach Instruktion 2
Nach Instruktion 3
Nach Instruktion 4
Nach Instruktion 5
Nach Instruktion 6
Nach Instruktion 7
Nach Nach Nach
Abbildung 4: Belegung der Register - Ersatz, ungu ̈ltige Lo ̈sung streichen! Seite 11 / 22
Instruktion 8
Instruktion 9 Instruktion 10
GRA/TI (iii) Speicher-Speicher-Architektur. Verfu ̈gbare Instruktionen: add, mul.
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 6: Programm in Speicher-Speicher-Architektur
Assembler-Instruktion
Speicherbedarf
U ̈bertragene Daten
1
2
3
4
5
6
7
8
9
10
Tabelle 7: Programm in Speicher-Speicher-Architektur - Ersatz, ungu ̈ltige Lo ̈sung streichen!
Seite 12 / 22
NAME: Matrikelnummer:
Aufgabe 4 (Pipelining)
[25 Punkte]
(a) Ein Prozessorhersteller entwirft eine neue Prozessorgeneration mit 10 Pipelinestu- fen. Wie hoch ist der zu erwartende Speedup gegenu ̈ber einer Mehrzyklenimple- mentierung, in der jeder Befehl des Testprogramms (9991 Instruktionen) alle 10 Taktphasen durchla ̈uft?
Speedup:
(b) Im folgenden soll ein Prozessor mit 5-stufiger Pipeline (IF, ID, EX, MEM, WB) be- trachtet werden. Der Registerfilezugriff erfolgt im Ganztaktverfahren. Der Prozessor verwendet eine Harvard-Architektur. Die Pipeline verwendet kein Forwarding.
Folgendes Assembler Codefragment soll auf dem Prozessor ausgefu ̈hrt werden:
0: sub $t2, $t1, $t3 1: and $t4, $t2, $t5 2: or $t4, $t4, $t2 3: add $t9, $t4, $t2
Seite 13 / 22
GRA/TI
(i) Geben Sie die Pipelinebelegung – fu ̈r das oben gezeigte Codefragment – fu ̈r den Fall an, dass die Pipeline bei einem auftretenden Konflikt angehalten wird. Fu ̈llen Sie hierzu das Diagramm in Abbildung 5 aus.
Takte
sub $t2, $t1, $t3
and $t4, $t2, $t5
or $t4, $t4, $t2
add $t9, $t4, $t2
Takte
sub $t2, $t1, $t3
and $t4, $t2, $t5
or $t4, $t4, $t2
add $t9, $t4, $t2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB
Abbildung 5: Pipelinebelegung fu ̈r (i)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB
Abbildung 6: Ersatzdiagramm: Pipelinebelegung fu ̈r (i)
(ii) Wie vera ̈ndert sich die Pipelinebelegung wenn Forwarding verwendet wird? Fu ̈llen Sie hierzu das Diagramm in Abbildung 7 aus. Machen Sie das Forwar- ding mit Hilfe von Pfeilen deutlich.
Takte
sub $t2, $t1, $t3
and $t4, $t2, $t5
or $t4, $t4, $t2
add $t9, $t4, $t2
Takte
sub $t2, $t1, $t3
and $t4, $t2, $t5
or $t4, $t4, $t2
add $t9, $t4, $t2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB
Abbildung 7: Pipelinebelegung fu ̈r (ii)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 IF ID EX ME WB
Abbildung 8: Ersatzdiagramm: Pipelinebelegung fu ̈r (ii)
Seite 14 / 22
NAME: Matrikelnummer:
(c) Nun soll das folgende Codefragment auf dem Prozessor ohne Forwarding ausgefu ̈hrt werden. Der Registerfilezugriff findet im Ganztaktverfahren statt. Die Zeile 1: liegt im Befehlsspeicher an der Adresse 0x00200010.
1: addi 2: addi 3: addi 4: sub 5: add
$t1, $zero, 20 $t2, $zero, 22 $t3, $zero, 11 $t4, $t1, $t1 $t5, $t2, $t3
Wie sind die Busbelegungen an
Stellen (siehe Abbildung 9) innerhalb der einzelnen Pipelinestufen, zu dem Zeit- punkt in dem der Befehl der Zeile 5 die IF Stufe erreicht hat?
Geben Sie die Busbelegung in Hexadezimal- oder Bina ̈rdarstellung an. Fu ̈llen Sie hierzu die Tabelle 8 aus.
Hinweis:
add:
sub:
addi:
den mit den Buchstaben (a-p) gekennzeichneten
opcode 000000
rs
rt
rd
shamt 00000
funct 100000
opcode 000000
rs
rt
rd
shamt 00000
funct 100010
opcode 001000
rs
rt
immediate
Seite 15 / 22
GRA/TI
Abbildung 9: Pipeline-Datenpfad
Seite 16 / 22
a
Address
Read Data2
4
p o
M U X
IF RF EX MEM
WB
Instruction Memory b
M
M U X
c Read Reg.1
d Read Reg.2
Read Data1
ik jl
e Write Reg.
n
Data Memory
f Write RF Data
U X
g
h
M
m
U X
Address
Read Data
Write Data
Sign. Extend
ALU
ADD
PC
Shift left 2
ADD
NAME:
Matrikelnummer:
a: b:
c: d: e: f:
g:
h: i: j: k: l: m: n: o: p:
opcode 000000
rs
rt
rd
shamt 00000
funct 100000
opcode 000000
rs
rt
rd
shamt 00000
funct 100010
Tabelle 8: Busbelegung fu ̈r (c)
Seite 17 / 22
GRA/TI
a: b:
c: d: e: f:
g:
h: i: j: k: l: m: n: o: p:
opcode 000000
rs
rt
rd
shamt 00000
funct 100000
opcode 000000
rs
rt
rd
shamt 00000
funct 100010
Tabelle 9: Ersatztabelle: Busbelegung fu ̈r (c)
Seite 18 / 22
NAME: Matrikelnummer:
Aufgabe 5 (Arbitrierung)
[15 Punkte]
Abbildung 10(a) zeigt ein System mit zwei CPUs, die an einen gemeinsamen Bus ange- schlossen sind. Da beide CPUs Busmaster werden ko ̈nnen, wird der Buszugriff durch einen zentralen Arbiter gesteuert. Die CPUs fordern u ̈ber request-Signale (r1=1 bzw. r2=1) den Bus an. Falls einer CPU der Buszugriff gewa ̈hrt wird, antwortet der Arbiter mit einem grant-Signal (g1=1 bzw. g2=1). Gibt eine CPU den Bus wieder frei, wird das entsprechen- de request Signal wieder auf 0 gesetzt, worauf der Arbiter das entsprechende grant-Signal auch wieder auf 0 setzt.
(a) Blockdiagramm (b) Zustandsautomat fu ̈r den Arbiter
Abbildung 10: System mit zwei CPUs und zentralem Arbiter
(a) Abbildung 10(b) zeigt den Moore-Zustandsautomat des zentralen Arbiters. Die Aus- gabesignale (g1,g2) sind in den Zusta ̈nden angegeben. Begru ̈nden Sie, ob dieser Arbiter den CPUs unterschiedliche Priorita ̈ten zuweist. Wenn ja, welche der CPUs hat die ho ̈here Prioria ̈t?
r1.r2
S0
0 0
Sx g1 g2
r1.r2
r2
r1
r1 r2
r2
10 01
S1
S2
Arbiter
g1r1 r2g2
Bus
CPU1
CPU2
Seite 19 / 22
GRA/TI
(b) Skizzieren Sie ein Blockdiagramm fu ̈r ein System mit zwei CPUs und einem gemein- samen Bus, das Daisy-Chain Arbitrierung verwendet. Zeichnen Sie alle Steuersignale ein und benennen Sie diese. Die Arbitrierung soll dieselben Priorita ̈ten fu ̈r die CPUs imple- mentieren wie die zentrale Arbitrierung in Abbildung 10(b).
(c) Entwerfen Sie einen zentralen Busarbiter, der keine festen Priorita ̈ten vergibt, sondern ”fair” ist. Ein ”fairer” Arbiter weist den CPUs abwechselnd den Bus zu, falls sie ihn gleichzeitig anfordern. Geben Sie den Moore-Zustandsautomat Ihres ”fairen” Arbiters an.
Seite 20 / 22
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 21 / 22
GRA/TI
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 22 / 22