Universita ̈t Paderborn
Institut Elektrotechnik und Informationstechnik Fachgebiet Datentechnik
Prof. Sybille Hellebrand
Klausur
Technische Informatik / Grundlagen der Rechnerarchitektur
20. September 2016
Punkteverteilung
Aufgabe
1
2
3
4
5
Σ
maximale Punkte
15
20
20
20
15
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) 15 Punkte
a) Fu ̈r ein gegebenes CPU Design, sollen verschiedene Compiler getestet werden. Zur Bewertung stehen folgende Daten zur Verfu ̈gung:
Der Befehlssatz la ̈sst sich in drei Klassen gema ̈ß nachstehender Tabelle einteilen:
Befehlsklasse CPI fu ̈r die Befehlsklasse A3 B2 C1
Fu ̈r den untersuchten Beispielcode erzeugen die beiden Compiler Befehlssequenzen mit den folgenden Eigenschaften:
Anzahl der Befehle in Klasse Compiler A B C I212
II 1 1 4
Geben Sie fu ̈r beide Compiler jeweils die Codela ̈nge, die Ausfu ̈hrungszeit fu ̈r den Beispielcode und den CPI Wert an.
Anzahl der Befehle fu ̈r Compiler I:
Anzahl der Befehle fu ̈r Compiler II: Ausfu ̈hrungszeit (# Taktzyklen) fu ̈r Compiler I: Ausfu ̈hrungszeit (# Taktzyklen) fu ̈r Compiler II: CPI Wert fu ̈r Compiler I:
CPI Wert fu ̈r Compiler II:
(3 Punkte)
Aufgabe 1 GRA/TI Seite 4
b) Ein Rechner beno ̈tigt zur Ausfu ̈hrung dreier Programme folgende Ausfu ̈hrungszeiten:
Programm Instruktionen Ausfu ̈hrungszeit 1 81000·106 9s
2 144000 · 106 12 s
3 120000 · 106 10 s
Wie hoch ist die durchschnittliche MIPS-Rate des Rechners?
(4 Punkte)
Aufgabe 1 Matrikelnummer: Seite 5
c) Ein Mikroprozessorhersteller entwirft einen Mikroprozessor mit 20 Pipelinestufen. Zur Leistungsbewertung wird ein typisches Anwendungsprogramm mit 106 Befehlen verwendet. Die ideale Ausfu ̈hrungszeit einer Pipelinestufe betra ̈gt 100 ps.
(4 Punkte)
1. Wie lange wu ̈rde der gleiche Mikroprozessor ohne Pipelinestufen zur Berechnung des Anwendungsprogramms beno ̈tigen?
Bitte kreuzen Sie an!
100 μs
200 μs
2ms
Keine Lo ̈sung ist richtig
2. Wie groß ist der asymptotische Speedup des Mikroprozessors mit Pipelinestufen im Vergleich zum Mikroprozessor ohne Pipelinestufen, wenn wir annehmen, dass es sich um eine ideale Pipeline handelt und keine Pipelinehindernisse (Hazards) auftreten?
SpeedUp:
3. In der Realita ̈t ist eine Pipeline nicht perfekt, so treten z.B. Pipelinehindernisse (Hazards) auf. Wirken Sich diese Pipelinehindernisse auf die Befehlslatenz, den
Befehlsdurchsatz oder beides aus?
Bitte kreuzen Sie an!
Befehlslatenz Befehlsdurchsatz
Beides
Keine Lo ̈sung ist richtig
Aufgabe 1 GRA/TI Seite 6
d) Ein Rechner beno ̈tigt zur Ausfu ̈hrung eines Programms 200 s. Durch die Verwendung eines neuen Prozessors ko ̈nnen Fließkomma Instruktionen sechs mal schneller verar- beitet werden. Wie groß muss der Anteil der Fließkomma Instruktionen sein, damit ein Speedup von zwei erzielt werden kann?
Bitte kreuzen Sie an!
3 5
4 5
1 3
3 4
Keine Lo ̈sung ist richtig
(4 Punkte)
Aufgabe 3 Matrikelnummer: Seite 7
Aufgabe 2: (Cache) 20 Punkte
Gehen Sie von einem Computer aus, der zur Beschleunigung der Speicherzugriffe auf den byteadressierten Arbeitsspeicher mit einem Adressraum von 1 GB einen Cache mit 8 Rahmen vorsieht, wobei der Datenbereich jedes Blocks 2 Worte zu je 32 Bit umfasst. Der Cache sei als 2-fach mengenassoziativer Cache (2-way-set-associative) 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 3 GRA/TI Seite 8
c) Der Prozessor la ̈dt nun sequentiell die Daten der folgenden Byteadressen (fu ̈hrende Nullen werden nicht mit angegeben):
t=10: 0x45
t=11: 0x1d
t=12: 0xf7
t=13: 0xe5
t=14: 0xe8
t=15: 0x04
t=16: 0xf0
t=17: 0x95
Als Ersetzungsstrategie wird FIFO (First In First Out) eingesetzt. Gehen Sie von folgendem Zustand des Cache zum Zeitpunkt t = 9 aus (die Spalte t gibt an, zu welchem Zeitpunkt die Daten in den Cache u ̈bertragen wurden):
Index
V
t
Tag
Daten
0
1
7
…010
MEM[0x40-0x47]
1
6
…101
MEM[0xa0-0xa7]
1
0
1
…110
MEM [0x00-0x07]
0
3
…111
MEM [0xe8-0xef]
2
0
6
…010
MEM [0x00-0x07]
0
2
…101
MEM [0x00-0x07]
3
1
4
…000
MEM [0x18-0x1f]
0
7
…111
MEM [0x00-0x07]
Geben Sie nach jedem Speicherzugriff den Zustand des Caches an. Fu ̈llen Sie hierzu die na ̈chsten Zeilen aus. Geben Sie zum Schluss die Hitrate an.
Hinweis: Beachten Sie das Valid-Bit (V)!
(12 Punkte)
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
t=10: 0x45
Aufgabe 3
Matrikelnummer:
Seite 9
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
t=11: 0x1d
t=12: 0xf7
t=13: 0xe5
t=14: 0xe8
t=15: 0x04
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
Aufgabe 3
GRA/TI Seite 10
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
t=16: 0xf0
t=17: 0x95
Hitrate:
Index
V
t
Tag
Daten
MEM[ ]
MEM[ ]
Index
V
t
Tag
Daten
Ersatzzeile, ungu ̈ltige Lo ̈sung streichen!
Index
V
t
Tag
Daten
Ersatzzeile, ungu ̈ltige Lo ̈sung streichen!
Aufgabe 3 Matrikelnummer: Seite 11
Index
V
t
Tag
Daten
Ersatzzeile, ungu ̈ltige Lo ̈sung streichen!
Index
V
t
Tag
Daten
Ersatzzeile, ungu ̈ltige Lo ̈sung streichen!
d) Wie hoch ist die durchschnittliche Zugriffszeit, ausgehend von der Hitrate des Cache aus Aufgabenteil c), wenn der Zugriff auf den Cache 10ns und der Zugriff auf den Hauptspeicher 100ns betra ̈gt? Geben Sie auch den Rechenweg an.
Durchschnittliche Zugriffszeit:
(2 Punkte)
Aufgabe 2 GRA/TI Seite 12 Aufgabe 3: (Assembler) 20 Punkte
a) Vervollsta ̈ndigen Sie folgendes Programm, das als Parameter in $a0 eine Zahl und in
$a1 eine Speicheradresse u ̈bergeben bekommt.
(4 Punkte)
01 addi
02 addi
03 mul
04 add
05 addi
06 addi
$t0, $a1, 0
$t1, $zero, 4
$t1, $t1, $a0
$t1, $t1, $a1
$t8, $zero, 0
$t9, $zero, 0
# initialize pointer into v1 #
# t1=4*dim
# initialize pointer into v2 # initialize partial sum
# initialize loop counter
loop:
07 ______________________ # in $t0 into register $t2
# load word from address stored
08 ______________________ # in $t1 into register $t3
09 mul $t4, $t2, $t3 # multiply values
10 ______________________ # add result to partial sum
11 addi $t0, $t0, 4 # next value in v1
12 addi $t1, $t1, 4 # next value in v2
13 ______________________ # increment loop counter
14 blt___________________ # loop if counter < dim
15 addi $v0, $t8, 0 # save result
# load word from address stored
b) Das Programms entha ̈lt Pseudoinstruktionen, zum Beispiel in Zeile 14: blt (branch on less than). Dru ̈cken Sie Zeile 14 in regula ̈ren MIPS Instruktionen aus. Sie du ̈rfen dafu ̈r die Befehle slt, beq, bne und das Hilfsregister $at fu ̈r tempora ̈re Hilfsvariablen verwenden.
(3 Punkte)
Aufgabe 2 Matrikelnummer: Seite 13
c) Gegeben sei folgender Inhalt der Register und des Speichers eines MIPS Systems. Wenn das Programm aus a) in diesem Zustand aufgerufen wird, was berechnet es dann? Fu ̈llen Sie untenstehende Tabelle aus, indem Sie jeweils eine neue Spalte ausfu ̈llen, wenn der Programmablauf Zeile 7 (Marke loop) erreicht, und eine extra Spalte nach Ablauf des Programms (nach Zeile 15)! Bei den Speicheradressen ko ̈nnen Sie das Pra ̈fix 1001 weglassen, aus 0x10010004 wu ̈rde beispielsweise 0x0004.
Wert
Wert
...
(12 Punkte)
Register
Wert
$v0
42
$v1
-1
$a0
3
$a1
0x1001000C
$a2
123
$a3
8128
$t0
0
$t1
12
$t2
81
$t3
9999
$t4
-245
$t5
4192
$t6
0x10010004
$t7
0x10010028
$t8
13
$t9
-1
Speicher- adresse
Wert
0x10010000
24
0x10010004
255
0x10010008
3
0x1001000C
2
0x10010010
123
0x10010014
5
0x10010018
5
0x1001001C
0
0x10010020
5
0x10010024
1
0x10010028
25
0x1001002C
0
0x10010030
0x10010000
0x10010034
99374
0x10010038
0
0x1001003C
16535
Register- und Speicherinhalt zu Beginn der Berechnung.
Register
$v0
42
$t0
0
$t1
12
$t2
81
$t3
9999
$t8
13
$t9
-1
Tabelle fu ̈r Registerwerte. d) Was berechnet die Funktion in c)?
(1 Punkt)
Aufgabe 2 GRA/TI Seite 14
Register
Wert
Wert
...
$v0
42
$t0
0
$t1
12
$t2
81
$t3
$t8
9999
13
$t9
-1
Ersatztabelle fu ̈r Registerwerte, ungu ̈ltige Lo ̈sungen streichen!
Aufgabe 4 Matrikelnummer: Seite 15
Aufgabe 4: (Datenpfad) 20 Punkte
Bei der Mehrzyklenimplementierung eines MIPS Prozessors (Abbildung 3) soll der neue I- Typ Befehl Jump And Link Register Immediate (jalri $rs(imm)) realisiert werden. Bei dem Befehl wird ein unbedingter Sprung zur Instruktion ausgefu ̈hrt, deren Basis- adresse im Register $rs gespeichert ist und durch einen Offset aus dem Immediate Wert erga ̈nzt wird(PC = rs+imm). Außerdem wird die Ru ̈cksprung-Adresse im Register $ra ($31) gespeichert. (ra = PC + 4)
a) Zeichnen Sie das neue Instruktionsformat fu ̈r den I-Typ in Abbildung 1 ein. Abschnitte im Instruktionsformat, die fu ̈r die nicht beno ̈tigt werden, kennzeichnen Sie mit einem X.
31 2625
31 2625
Abbildung 1: neues Instruktionsformat
Abbildung 2: Ersatz, ungu ̈ltige Lo ̈sung streichen!
(3 Punkte)
0
0
op=jalri
op=jalri
Aufgabe 4 GRA/TI Seite 16
Abbildung 3: Daten- und Kontrollpfad der Mehrzyklenimplementierung, Ersatzbild auf Seite 19.
Instruction PC 0M [31-26]
PC [31-28]
u Address Instruction 1 x [25-21]
Read Register 1
Read Data 1
0 Mu
Mem Data Instruction [20-16]
Read Register 2
A 1x B 0M
Zero
Write Data Instruction Memory [15-0]
0
Write Read Register Data 2
ALUOut
PCWriteCond PCWrite
PCSource ALUOp
IorD MemRead MemWrite
Outputs Control
ALUSourceA
MemtoReg IRWrite
Op [5-0]
ALUSourceB RegWrite
Instruction Register
1u x
Write 4 12 u
Memory Data Register
Instruction [15-0]
16
Shift Left 2
ALU Control
Instruction [15-11] M
ALU
ALU Result
Instruction [5-0]
RegDest
Instruction [25-0]
26
Shift Left 2
28 32
Jump 0M Address 1 u [31-0] 2 x
0M u 1x
Data Registers Sign 32
3x
Extend
Aufgabe 4 Matrikelnummer: Seite 17
b) Modifizieren Sie, wenn no ̈tig, den Daten- und Kontrollpfad in Abbildung 3 so, dass der neue Befehl jalri realsisiert werden kann und begru ̈nden Sie Ihre Entscheidung. Ohne Begru ̈ndung gibt es keine Punkte!
(3 Punkte)
c) Modifzieren bzw. erweitern Sie die Steuerung in Abbildung 4, so dass der Befehl jalri unterstu ̈tzt wird.
Memory address computation
Branch Execution complesion
Start
Instruction fetch
MemRead = 1 IorD = 0 IRWrite = 1 ALUSrcA = 0 ALUSrcB = 1 ALUOp = 0 ⇒ + PCWrite = 1 PCSource = 0
(10 Punkte)
Instruction decode/ register fetch
0
1
ALUSrcA = 0
ALUSrcB = 3 ALUOp = 0 ⇒ +
Jump complesion
PCWrite = 1 PCSource = 2
2689
ALUSrcA = 1
ALUSrcB = 2 ALUOp = 0 ⇒ +
Memory access
ALUSrcA = 1
ALUSrcB = 0 ALUOp = 1 ⇒ - PCWriteCond = 1 PCSource = 1
R-type completion
RegDst = 1 RegWrite = 1 MemToReg = 0
ALUSrcA = 1 ALUSrcB = 0 ALUOp = 2
...
Memory access
357 MemRead = 1 MemWrite = 1
IorD = 1
IorD = 1
Memory read completion step
4
RegDst = 0 RegWrite = 1 MemToReg = 1
Abbildung 4: Steuerung als endlicher Automat, Ersatzbild auf Seite 20.
(Op = 'jalri')
(Op = 'LW') or (Op = 'SW')
(Op = R-type)
(Op = 'BEQ')
(Op = 'SW')
(Op = 'LW')
(Op = 'J')
Aufgabe 4 GRA/TI Seite 18
In der folgenden Tabelle sehen Sie die Ha ̈ufigkeiten der Befehlstypen, die innerhalb eines typischen Programms auftreten.
Instruktion Relative Ha ̈ufigkeit R-Type 20% 4 LW 20% 5 SW 10% 4 J 30% 3 other 20% 4
In einem Programm mit 10.000 Instruktionen sind von den 20 % R-Type Befehlen 25% jalr Befehle, welche zusa ̈tzlich ein Offset auf die Sprungadresse im Register $j beno ̈tigen: ...
addi $t1, $j, offset
jalr $t1 ...
d) Wie viele Takte ko ̈nnen durch den neuen Befehl jalri eingespart werden? Hinweis: Der addi Befehl ist bei der Instruktion other einzuordnen.
(4 Punkte)
Takte
Aufgabe 4 Matrikelnummer: Seite 19
Abbildung 5: Ersatz Mehrzyklenimplementierung des Daten- und Kontrollpfads,
ungu ̈ltige Lo ̈sung streichen!
Instruction PC 0M [31-26]
PC [31-28]
u Address Instruction 1 x [25-21]
Read Register 1
Read Data 1
0 Mu
Mem Data Instruction [20-16]
Read Register 2
A 1x B 0M
Zero
Write Data Instruction Memory [15-0]
0
Write Read Register Data 2
ALUOut
PCWriteCond PCWrite
PCSource ALUOp
IorD MemRead MemWrite
Outputs Control
ALUSourceA
MemtoReg IRWrite
Op [5-0]
ALUSourceB RegWrite
Instruction Register
1u x
Write 4 12 u
Memory Data Register
Instruction [15-0]
16
Shift Left 2
ALU Control
Instruction [15-11] M
ALU
ALU Result
Instruction [5-0]
RegDest
Instruction [25-0]
26
Shift Left 2
28 32
Jump 0M Address 1 u [31-0] 2 x
0M u 1x
Data Registers Sign 32
3x
Extend
Aufgabe 4
GRA/TI
Seite 20
Instruction fetch
MemRead = 1 IorD = 0 IRWrite = 1 ALUSrcA = 0 ALUSrcB = 1 ALUOp = 0 ⇒ + PCWrite = 1 PCSource = 0
Instruction decode/ register fetch
Start
0
1
ALUSrcA = 0
ALUSrcB = 3 ALUOp = 0 ⇒ +
Jump complesion
PCWrite = 1 PCSource = 2
Memory address computation
Branch Execution complesion
2689
ALUSrcA = 1
ALUSrcB = 2 ALUOp = 0 ⇒ +
Memory access
ALUSrcA = 1
ALUSrcB = 0 ALUOp = 1 ⇒ - PCWriteCond = 1 PCSource = 1
R-type completion
RegDst = 1 RegWrite = 1 MemToReg = 0
ALUSrcA = 1 ALUSrcB = 0 ALUOp = 2
...
Memory access
357 MemRead = 1 MemWrite = 1
IorD = 1
IorD = 1
Memory read completion step
4
RegDst = 0 RegWrite = 1 MemToReg = 1
Abbildung 6: Ersatz der Steuerung, ungu ̈ltige Lo ̈sung streichen!
(Op = 'jalri')
(Op = 'LW') or (Op = 'SW')
(Op = R-type)
(Op = 'BEQ')
(Op = 'SW')
(Op = 'LW')
(Op = 'J')
Aufgabe 5 Matrikelnummer: Seite 21
Aufgabe 5: (Pipelining) 15 Punkte
Ein Prozessor verwendet eine aus der Vorlesung bekannte 5-stufige MIPS Pipeline (IF, ID, EX, ME, WB). Es wird kein Forwarding unterstu ̈tzt. Das folgende Assemblerprogramm wird auf dem Prozessor ausgefu ̈hrt. Gehen Sie davon aus, dass die Sprungbedingung in Zeile 3 nicht erfu ̈llt wird.
1 2 3 4 5 6 7
lw $10, 4($8)
add $3, $4, $10
beq $3, $10, L1
add $4, $3, $8
sll $8, $8, $2
L1:add$5,$4,$3 sw $9, 0($4)
a) Lo ̈sen Sie die Konflikte, indem die Pipeline entsprechend angehalten wird. Erstellen Sie ein Diagramm, aus dem die Pipelinebelegung ersichtlich wird. Tritt bei einer Codezeile ein Hazard auf, tragen Sie in Tabelle 1 ein X bei dem entsprechenden
Hazard ein.
(6 Punkte)
Takte
1 lw $10, 4($8)
2 add $3, $4, $10
3 beq $3, $10, L1
4 add $4, $3, $8
5 sll $8, $8, $2
6 L1:add$5, $4, $3
7 sw $9, 0($4)
1
IF
2
ID
3
EX
4
ME
5
WB
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Abbildung 7: Pipelinebelegung zu a) Tabelle 1: Hazards bei Bearbeitung von a)
Codezeile
1
2
3
4
5
6
7
Daten-Hazard
Kontroll-Hazard
Struktur-Hazard
Aufgabe 5
GRA/TI Seite 22
1 2 3 4 5 6 7
Takte
lw $10, 4($8)
add $3, $4, $10
beq $3, $10, L1
add $4, $3, $8
sll $8, $8, $2
L1:add$5, $4, $3 sw $9, 0($4)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 IF ID EX ME WB
Abbildung 8: Ersatz Pipelinebelegung zu a), ungu ̈ltige Lo ̈sung streichen!
b) Der Prozessor aus a) unterstu ̈tzt jetzt zusa ̈tzlich jedes mo ̈gliche Forwarding. Im Fall eines durch das Forwarding nicht auflo ̈sbaren Konflikts wird die Pipeline angehalten. Geben Sie die Pipelinebelegung mithilfe des folgenden Diagramms an und machen Sie das Forwarding mit einem Pfeil kenntlich. Tragen Sie auftretende Hazards in Tabelle 2
ein.
(5 Punkte)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 IF ID EX ME WB
1 2 3 4 5 6 7
lw $10, 4($8)
add $3, $4, $10
beq $3, $10, L1
add $4, $3, $8
sll $8, $8, $2
L1:add$5, $4, $3 sw $9, 0($4)
Takte
Abbildung 9: Pipelinebelegung zu b) Tabelle 2: Hazards bei Bearbeitung von b)
Codezeile 1234567 Daten-Hazard
Kontroll-Hazard
Struktur-Hazard
Aufgabe 5 Matrikelnummer: Seite 23
Takte
1 lw $10, 4($8)
2 add $3, $4, $10
3 beq $3, $10, L1
4 add $4, $3, $8
5 sll $8, $8, $2
6 L1:add$5, $4, $3
7 sw $9, 0($4)
1
IF
2
ID
3
EX
4
ME
5
WB
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Abbildung 10: Ersatz Pipelinebelegung zu b), ungu ̈ltige Lo ̈sung streichen!
c) Berechnen Sie den Speedup des in b) modifizierten Prozessors. (1 Punkt)
d) Nennen Sie 3 Mo ̈glichkeiten, Kontroll-Hazards aufzulo ̈sen. (3 Punkte) •
•
•
Zusatzblatt fu ̈r Notizen GRA/TI Seite 24
Zusatzblatt fu ̈r Notizen Matrikelnummer: Seite 25
Zusatzblatt fu ̈r Notizen GRA/TI Seite 26