代写 C MIPS compiler Universita ̈t Paderborn

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