[SOLVED] R C MIPS compiler Musterlo sung

Musterlo sung
U bung5 RAWiSe18/19
Aufgabe 1 (Prozessor-Leistungsgleichung)
Gegeben sind zwei verschiedene Implementierungen einer Instruktionssatzarchitektur, I 1 mit einer Taktfrequenz von 6 GHz und I 2 mit einer Taktfrequenz von 3 GHz. Der In- struktionssatz kann in drei Klassen von Instruktionen A, B und C mit unterschiedlichen CPI-Werten aufgeteilt werden. Die CPI-Werte fu r die zwei Prozessoren I 1 und I 2 sind in den Spalten 2 und 3 von Tabelle 1 angegeben.
Ausserdem stehen drei verschiedene Compiler zur Verfu gung. Compiler C 1 wird vom Her- steller des Prozessors I 1 geliefert, Compiler C 2 vom Hersteller von I 2 und Compiler C 3 ist ein Produkt eines Fremdanbieters. Wir nehmen an, dass fu r ein bestimmtes Pro- gramm alle drei Compiler zwar dieselbe Anzahl von Instruktionen generieren, sich aber der resultierende Instruktionsmix unterscheidet. Die relativen Ha ufigkeiten der jeweils verwendeten Instruktionsklassen sind in den Spalten 4-6 der Tabelle 1 angegeben.
Tabelle 1: CPI-Werte und relative Ha ufigkeiten von Instruktionen
(1) Wie gross ist die relative Performance von I 1 im Vergleich zu I 2, wenn fu r beide Prozessoren der Compiler C 1 verwendet wird? Wie gross ist die relative Performance von I 2 im Vergleich zu I 1, wenn beidesmal der Compiler C 2 verwendet wird?
(2) Welchen der drei Compiler sollte man fu r Prozessor I 1 verwenden, welchen fu r Prozessor I 2?
(3) Welche Kombination von Prozessor und Compiler liefert die gro sste Performance? Musterlo sung
(1) CPII1,C1 =20,4+30,4+50,2=3 CPII2,C1 =10,4+20,4+20,2=1,6
Performance = PerformanceI1 = AusfuehrungszeitI2 = ICCPII2,C1TI2
Instruktionsklasse
CPI-Wert I 1
CPI-Wert I 2
C1
C2
C3
A B C
2 3 5
1 2 2
40% 40% 20%
40% 20% 40%
50% 25% 25%
I1 ,I2 ,C1 ,C1
PerformanceI2 AusfuehrungszeitI1 ICCPII1,C1TI1
CPII ,C TI CPII ,C 1 1,62 32
= 2 1 2 = 2 1 3GHz = = =1,06
CPII,CTI CPII,C 1 31 30 1 1 1 1 1 6GHz
CPII1,C2 =20,4+30,2+50,4=3,4 CPII2,C2 =10,4+20,2+20,4=1,6
Performance = PerformanceI2 = AusfuehrungszeitI1 = ICCPII1,C2TI1 I2,II,C2,C2 PerformanceI1 AusfuehrungszeitI2 ICCPII2,C2TI2
CPII ,C TI 1 2
CPII ,C 1
1 2 6GHz =
CPII ,C 1
2 2 3GHz
3,41 1,62
17
=
1 = 2 2 2
= =1,0625 16
CPII ,C TI
Seite 1 / 6

Musterlo sung
U bung5 RAWiSe18/19
(2) CPII1,C1 =20,4+30,4+50,2=3
CPII1,C2 =20,4+30,2+50,4=3,4
CPII1,C3 =20,5+30,25+50,25=3
Je kleiner der CPI Wert, umso besser die Performance. Deshalb sollte fu r Instruk- tionssatzarchitektur I 1 entweder Compiler C 1 oder C 3 verwendet werden.
CPII2,C1 =10,4+20,4+20,2=1,6
CPII2,C2 =10,4+20,2+20,4=1,6
CPII2,C3 =10,5+20,25+20,25=1,5
Fu r Instruktionssatzarchitektur I 2 sollte Compiler C 3 verwendet werden.
(3) Performancex = 1 = 1 Ausfuehrungszeitx IcCPIT
Da die Anzahl der Machineninstruktionen Ic des Programms nicht gegeben ist, ko nnen keine absoluten Performancewerte berechnet werden. Da wir aber anneh- men, dass alle drei Compiler fu r das Programm dieselbe Anzahl von Instruktionen generieren, kann der Parameter Ic bei der Bestimmung der relativen Performance geku rzt werden. Daraus folgt: Je kleiner der Quotient CP I T , umso gro sser ist die Performance.
T=1=1=1 =1109s=1ns I1 fI1 6GHz 6109Hz 6 6
T=1=1=1 =1109s=1ns I2 fI2 3GHz 3109Hz 3 3
TI1 TI1 TI1 TI2 TI2 TI2
=31ns=0,5ns 6
CPII1,C1
CPII1,C2
CPII1,C3
CPII2,C1
CPII2,C2
CPII2,C3
(I1, C1), (I1, C3), (I2, C3) haben die gro sste Performance.
= 3,4 1 ns = 0,56ns 6
=31ns=0,5ns 6
= 1,6 = 1,6 = 1,5
1 ns = 0,53ns 3
1 ns = 0,53ns 3
1 ns = 0,5ns 3
Seite 2 / 6

Musterlo sung
U bung5 RAWiSe18/19
Aufgabe 2 (Prozessorperformance)
Zu vergleichen sind zwei Implementierungen eines Prozessors anhand der Ausfu hrung eines Programmes P. Das Programm P besitzt folgenden Instruktionsmix:
Die Prozessorimplementierung MFP realisiert Gleitkommaoperationen (floating-point) di- rekt in Hardware und beno tigt folgende Anzahl von Taktzyklen fu r die verschiedenen Instruktionsklassen:
Die Prozessorimplementierung MNFP hat keine Hardwareunterstu tzung fu r Gleitkomma- operationen, sondern emuliert diese durch Sequenzen von Integerinstruktionen. Integerin- struktionen beno tigen 2 Taktzyklen. Die Anzahl der beno tigten Integerinstruktionen fu r die Emulation der Gleitkommaoperationen ist:
Beide Prozessorimplementierungen haben eine Taktfrequenz von 1000 MHz. (1) Wie gross sind die MIPS-Raten fu r die beiden Prozessoren MFP und MNFP?
(2) Prozessor MFP beno tigt 300 Millionen Instruktionen fu r Programm P. Wieviele In- tegerinstruktionen beno tigt MNFP fu r P?
(3) Wie gross sind die Ausfu hrungszeiten fu r Programm P auf MFP und MNFP?
Instruktionsklasse
relative H aufigkeit
Floating-point multiply Floating-point add Floating-point divide Integer instructions
10% 15% 5% 70%
Instruktionsklasse
ben otigte Taktzyklen
Floating-point multiply Floating-point add Floating-point divide Integer instructions
6
4 20 2
Instruktionsklasse
ben otigte Integerinstruktionen
Floating-point multiply Floating-point add Floating-point divide
30 20 50
Seite 3 / 6

Musterlo sung
U bung5 RAWiSe18/19
Musterlo sung (1) MIPS-Rate = Ic = Ic = 1
TEXE106 IcCPIT106 CPIT106 CPIMFP =60,1+40,15+200,05+20,70=3,6
CPIMNFP =21=2
MIPS=1 =1 =1=1000=277,7 MFP CPIMFP T106 3,6 1 106 3,6 1 3,6
MIPS = 1 = 1 =1 =1000500 MFNP CPIMFP T106 12 1 106 2 1 2
1000106 1000
1000106 1000 Prozessor MNFP hat die gro ssere MIPS-Rate.
(2) MFP: 300 Mill. Instruktionen insgesamt
MFP: 90 Mill. Gleitkommainstruktionen +210 Mill. Integerinst.
MFP: 30 Mill. FP mul +45 Mill. FP add +15 Mill. FP div +210 Mill. Integerinst.
MNFP: 30 30 Mill. +20 45 Mill. +50 15 Mill. +210 Mill. = 2760 Mill. Integerinst.
(3) T =I CPIT =300106 3,6 1 = 1080106 = 1080 =1,08 EXE,MFP c 1000MHz 1000106Hz 1000Hz
T =I CPIT=27601062 1 = 5520106 = 5520 =5,52s EXE,MNFP c 1000MHz 1000106Hz 1000Hz
Aufgabe 3 (Amdahls Gesetz)
Im Zuge der Entwicklung eines neuen Computers werden zwei mo gliche Verbesserun- gen gegenu ber einem a lteren, existierenden Modell diskutiert: Zum einen ko nnte man die Multiplikationsinstruktion vier mal schneller machen. Zum anderen wa re es mo glich, Speicherzugriffe zwei mal schneller zu machen.
Der Computer wird hauptsa chlich fu r die Abarbeitung eines Programms verwendet, das auf dem existierenden System eine Laufzeit von 100 Sekunden hat. Durch Messungen der Programmausfu hrungen (Profiling) weiss man, dass von dieser Zeit 20% fu r die Multiplika- tion, 50% fu r Speicherzugriffe und die restlichen 30% fu r andere Instruktionen verwendet werden.
Wie gross ist der Speedup, wenn die Multiplikation verbessert wird?
Wie gross ist der Speedup, wenn die Speicherzugriffe verbessert werden? Wie gross ist der Speedup, wenn beide Verbesserungen gemacht werden?
Seite 4 / 6

Musterlo sung
U bung5 RAWiSe18/19
Musterlo sung
Wie gross ist der Speedup, wenn Speedup=TEXEohneVerbesserung =
TEXE mitV erbesserung
Wie gross ist der Speedup, wenn
die Multiplikation verbessert wird? 100 = 100 = 100 = 20 1,176
20 +50+30 5+50+30 85 17 4
die Speicherzugriffe verbessert werden? 100 = 100 =100 =4 =1,3
Speedup=TEXEohneVerbesserung =
TEXEmitVerbesserung 20+50+30 20+25+30 75 3
2
Wie gross ist der Speedup, wenn beide Verbesserungen gemacht werden? Speedup=TEXEohneVerbesserung = 100 = 100 =100 =5 =1,6
TEXEmitVerbesserung 20+50+30 5+25+30 60 3 42
Aufgabe 4 (Adressierung)
Es wird vorgeschlagen, fu r eine LOAD-STORE Maschine einen Register-Speicher Adres- sierungsmodus hinzuzufu gen. Die Idee ist, Befehlssequenzen der Art
LOAD R1,0(Rb)
ADDR2,R2,R1
zu ersetzen durch
ADDR2,0(Rb).
Durch den neuen Instruktionstypen erho ht sich die Taktperiode um 10%. Die Ha ufigkeit, mit der eine Instruktion ausgefu hrt wird, ist durch die Benchmark-Programme aus Tabelle 2 gegeben. Die neue Instruktion betrifft lediglich die Taktperiode, nicht aber den CPI- Wert.
Instruktion
Ha ufigkeit
Instruktion
Ha ufigkeit
load
22,8%
jump
1,3%
store
14,3%
call
1,1%
add
14,6%
return, jmp ind
1,5%
sub
0,5%
shift
6,2%
mul
0,1%
and
1,6%
compare
12,4%
or
4,2%
load imm
6,8%
other(xor, not)
0,5%
cond branch
11,5%
Tabelle 2: Instruktionsmix fu r fu nf SPECint92 Programme mit dem gcc Compiler
Seite 5 / 6

Musterlo sung
U bung5 RAWiSe18/19
(1) Wie viele der LOAD Operationen mu ssen auf der Maschine mit der neuen Instruk- tion weniger ausgefu hrt werden, um wenigstens die selbe Performance zu erreichen?
(2) Geben Sie ein Beispiel an, bei dem ein LOAD nach R1, gefolgt von einer Addition (oder einer beliebigen anderen Instruktion), nicht durch den neuen Register-Speicher Befehl ersetzt werden kann.
Musterlo sung
(1) Zum Vergleich der Maschinen werden die Ausfu hrungszeiten eines Programms be-
rechnet.
CPU-Zeitalt = CPI Zykluszeit Instruction Count =CPITclkalt ICalt
Fu r die modifizierte Variante gilt:
CPU-Zeitneu = CP Ineu Tclkneu ICneu
= CPI (1,1 Tclkalt) (ICalt R)
Die neue Maschine hat also eine um 10% erho hte Taktperiode und kann R Instruktio- nen einsparen. Um die Anzahl der zu entfernenden Instruktionen R herauszufinden, mu ssen die Ausfu hrungszeiten gleichgesetzt werden.
CPI Tclkalt ICalt = CPI (1,1 Tclkalt) (ICalt R) ICalt R = 0,909
I Calt
R = 0,091 ICalt
Dies bedeutet, dass 9,1% aller Instruktionen eingespart werden mu ssen, um die sel-
ben Ausfu hrungszeiten zu erhalten. Da nur LOAD-Operationen eingespart werden
ko nnen, mu ssen die 9,1% von den 22,8% der LOAD-Operationen abgezogen werden.
Dies bedeutet, dass 39,9% (= 9,1% ) aller LOAD-Operationen mit anschlieendem 22,8%
ADD Befehl durch den neuen Instruktionstypen ersetzt werden mu ssen.
(2) Eine nicht mo gliche Befehlssubstitution erha lt man, wenn man die Register R2 und Rb durch R1 ersetzt.
LOAD R1,0(R1)
ADDR1,R1,R1
Angenommen R1 hat in dem Beispiel vor der Ausfu hrung den Wert 42 und im Speicher steht an dieser Position eine 3, so wu rde der Programmabschnitt die Spei- cherstelle nach R1 laden und anschlieend den Wert verdoppeln. Dadurch steht in R1 anschlieend eine 6. Wenn man den Abschnitt nun durch
ADDR1,0(R1).
ersetzt, so erha lt man als Ergebnis 45 (R1 + M [0 + R1] = 3 + 42).
Seite 6 / 6