[SOLVED] 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 ausschlielich die Aufgabenbla tter zu verwenden. Lo sungsangaben auerhalb 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 81000106 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 Fliekomma Instruktionen sechs mal schneller verar- beitet werden. Wie gro muss der Anteil der Fliekomma 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
09mul$t4, $t2, $t3 # multiply values
10______________________ # add result to partial sum
11addi $t0, $t0, 4 # next value in v1
12addi $t1, $t1, 4 # next value in v2
13______________________ # increment loop counter
14blt___________________ # loop if counter < dim15addi $v0, $t8, 0 # save result# load word from address storedb) 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.WertWert…(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 0x1001000024 0x10010004255 0x100100083 0x1001000C2 0x10010010123 0x100100145 0x100100185 0x1001001C0 0x100100205 0x100100241 0x1001002825 0x1001002C0 0x100100300x10010000 0x1001003499374 0x100100380 0x1001003C16535 Register- und Speicherinhalt zu Beginn der Berechnung.Register $v042$t00$t112$t281$t39999$t813$t9-1 Tabelle fu r Registerwerte. d) Was berechnet die Funktion in c)?(1 Punkt) Aufgabe 2 GRA/TI Seite 14 RegisterWertWert… $v042$t00$t112$t281$t3 $t89999 13$t9-1 Ersatztabelle fu r Registerwerte, ungu ltige Lo sungen streichen!Aufgabe 4 Matrikelnummer: Seite 15 Aufgabe 4: (Datenpfad) 20 PunkteBei 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). Auerdem 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 262531 2625Abbildung 1: neues InstruktionsformatAbbildung 2: Ersatz, ungu ltige Lo sung streichen!(3 Punkte)00 op=jalri op=jalri Aufgabe 4 GRA/TI Seite 16Abbildung 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 1Read Data 10 MuMem Data Instruction [20-16]Read Register 2A 1x B 0MZeroWrite Data Instruction Memory [15-0]0Write Read Register Data 2ALUOutPCWriteCond PCWritePCSource ALUOpIorD MemRead MemWriteOutputs ControlALUSourceAMemtoReg IRWriteOp [5-0]ALUSourceB RegWriteInstruction Register1u xWrite 4 12 uMemory Data RegisterInstruction [15-0]16Shift Left 2ALU ControlInstruction [15-11] MALUALU ResultInstruction [5-0]RegDestInstruction [25-0]26Shift Left 228 32Jump 0M Address 1 u [31-0] 2 x0M u 1xData Registers Sign 323xExtendAufgabe 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 computationBranch Execution complesionStartInstruction fetchMemRead = 1 IorD = 0 IRWrite = 1 ALUSrcA = 0 ALUSrcB = 1 ALUOp = 0 + PCWrite = 1 PCSource = 0(10 Punkte)Instruction decode/ register fetch 01ALUSrcA = 0ALUSrcB = 3 ALUOp = 0 +Jump complesionPCWrite = 1 PCSource = 2 2689 ALUSrcA = 1ALUSrcB = 2 ALUOp = 0 +Memory accessALUSrcA = 1ALUSrcB = 0 ALUOp = 1 – PCWriteCond = 1 PCSource = 1R-type completionRegDst = 1 RegWrite = 1 MemToReg = 0ALUSrcA = 1 ALUSrcB = 0 ALUOp = 2 …Memory access357 MemRead = 1 MemWrite = 1IorD = 1IorD = 1 Memory read completion step 4RegDst = 0 RegWrite = 1 MemToReg = 1Abbildung 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% 4In 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, offsetjalr $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 19Abbildung 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 1Read Data 10 MuMem Data Instruction [20-16]Read Register 2A 1x B 0MZeroWrite Data Instruction Memory [15-0]0Write Read Register Data 2ALUOutPCWriteCond PCWritePCSource ALUOpIorD MemRead MemWriteOutputs ControlALUSourceAMemtoReg IRWriteOp [5-0]ALUSourceB RegWriteInstruction Register1u xWrite 4 12 uMemory Data RegisterInstruction [15-0]16Shift Left 2ALU ControlInstruction [15-11] MALUALU ResultInstruction [5-0]RegDestInstruction [25-0]26Shift Left 228 32Jump 0M Address 1 u [31-0] 2 x0M u 1xData Registers Sign 323xExtendAufgabe 4GRA/TISeite 20Instruction fetchMemRead = 1 IorD = 0 IRWrite = 1 ALUSrcA = 0 ALUSrcB = 1 ALUOp = 0 + PCWrite = 1 PCSource = 0Instruction decode/ register fetch Start01ALUSrcA = 0ALUSrcB = 3 ALUOp = 0 +Jump complesionPCWrite = 1 PCSource = 2Memory address computationBranch Execution complesion2689 ALUSrcA = 1ALUSrcB = 2 ALUOp = 0 +Memory accessALUSrcA = 1ALUSrcB = 0 ALUOp = 1 – PCWriteCond = 1 PCSource = 1R-type completionRegDst = 1 RegWrite = 1 MemToReg = 0ALUSrcA = 1 ALUSrcB = 0 ALUOp = 2 …Memory access 357 MemRead = 1 MemWrite = 1IorD = 1IorD = 1 Memory read completion step 4RegDst = 0 RegWrite = 1 MemToReg = 1Abbildung 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 PunkteEin 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 7lw$10, 4($8)add $3,$4,$10beq $3,$10, L1add $4,$3,$8sll $8,$8,$2L1: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 entsprechendenHazard ein.(6 Punkte)Takte1 lw $10, 4($8)2 add $3, $4, $103 beq $3, $10, L14 add $4, $3, $85 sll $8, $8, $26 L1:add$5, $4, $37 sw $9, 0($4)1IF2ID3EX4ME5WB6789101112131415161718192021 Abbildung 7: Pipelinebelegung zu a) Tabelle 1: Hazards bei Bearbeitung von a)Codezeile 12 345 6 7 Daten-Hazard Kontroll-Hazard Struktur-HazardAufgabe 5GRA/TI Seite 221 2 3 4 5 6 7Taktelw$10, 4($8)add $3,$4,$10beq $3,$10, L1add $4,$3,$8sll $8,$8,$2L1: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 WBAbbildung 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 2ein.(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 WB1 2 3 4 5 6 7lw$10, 4($8)add $3,$4,$10beq $3,$10, L1add $4,$3,$8sll $8,$8,$2L1:add$5, $4, $3 sw $9, 0($4)Takte Abbildung 9: Pipelinebelegung zu b) Tabelle 2: Hazards bei Bearbeitung von b)Codezeile 1234567 Daten-HazardKontroll-HazardStruktur-Hazard Aufgabe 5 Matrikelnummer: Seite 23 Takte1 lw $10, 4($8)2 add $3, $4, $103 beq $3, $10, L14 add $4, $3, $85 sll $8, $8, $26 L1:add$5, $4, $37 sw $9, 0($4)1IF2ID3EX4ME5WB6789101112131415161718192021 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