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 =2∗0,4+3∗0,4+5∗0,2=3 CPII2,C1 =1∗0,4+2∗0,4+2∗0,2=1,6
Performance = PerformanceI1 = AusfuehrungszeitI2 = IC∗CPII2,C1∗TI2
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 IC∗CPII1,C1∗TI1
CPII ,C ∗TI CPII ,C ∗ 1 1,6∗2 32
= 2 1 2 = 2 1 3GHz = = =1,06
CPII,C∗TI CPII,C∗ 1 3∗1 30 1 1 1 1 1 6GHz
CPII1,C2 =2∗0,4+3∗0,2+5∗0,4=3,4 CPII2,C2 =1∗0,4+2∗0,2+2∗0,4=1,6
Performance = PerformanceI2 = AusfuehrungszeitI1 = IC∗CPII1,C2∗TI1 I2,II,C2,C2 PerformanceI1 AusfuehrungszeitI2 IC∗CPII2,C2∗TI2
CPII ,C ∗TI 1 2
CPII ,C ∗ 1
1 2 6GHz =
CPII ,C ∗ 1
2 2 3GHz
3,4∗1 1,6∗2
17
=
1 = 2 2 2
= =1,0625 16
CPII ,C ∗TI
Seite 1 / 6
Musterlo ̈sung
U ̈bung5 RAWiSe18/19
(2) CPII1,C1 =2∗0,4+3∗0,4+5∗0,2=3
CPII1,C2 =2∗0,4+3∗0,2+5∗0,4=3,4
CPII1,C3 =2∗0,5+3∗0,25+5∗0,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 =1∗0,4+2∗0,4+2∗0,2=1,6
CPII2,C2 =1∗0,4+2∗0,2+2∗0,4=1,6
CPII2,C3 =1∗0,5+2∗0,25+2∗0,25=1,5
Fu ̈r Instruktionssatzarchitektur I 2 sollte Compiler C 3 verwendet werden.
(3) Performancex = 1 = 1 Ausfuehrungszeitx Ic∗CPI∗T
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 =1∗10−9s=1ns I1 fI1 6GHz 6∗109Hz 6 6
T=1=1=1 =1∗10−9s=1ns I2 fI2 3GHz 3∗109Hz 3 3
∗TI1 ∗ TI1 ∗TI1 ∗ TI2 ∗ TI2 ∗ TI2
=3∗1ns=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
=3∗1ns=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
TEXE∗106 Ic∗CPI∗T∗106 CPI∗T∗106 CPIMFP =6∗0,1+4∗0,15+20∗0,05+2∗0,70=3,6
CPIMNFP =2∗1=2
MIPS=1 =1 =1=1000=277,7 MFP CPIMFP ∗T∗106 3,6∗ 1 ∗106 3,6∗ 1 3,6
MIPS = 1 = 1 =1 =1000≈500 MFNP CPIMFP ∗T∗106 12∗ 1 ∗106 2∗ 1 2
1000∗106 1000
1000∗106 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 ∗CPI∗T =300∗106 ∗3,6∗ 1 = 1080∗106 = 1080 =1,08 EXE,MFP c 1000MHz 1000∗106Hz 1000Hz
T =I ∗CPI∗T=2760∗106∗2∗ 1 = 5520∗106 = 5520 =5,52s EXE,MNFP c 1000MHz 1000∗106Hz 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)
ADD R2,R2,R1
zu ersetzen durch
ADD R2,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 =CPI·Tclk−alt ·ICalt
Fu ̈r die modifizierte Variante gilt:
CPU-Zeitneu = CP Ineu · Tclk−neu · ICneu
= CPI · (1,1 · Tclk−alt) · (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 · Tclk−alt · ICalt = CPI · (1,1 · Tclk−alt) · (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 anschließendem 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)
ADD R1,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 anschließend den Wert verdoppeln. Dadurch steht in R1 anschließend eine 6. Wenn man den Abschnitt nun durch
ADD R1,0(R1).
ersetzt, so erha ̈lt man als Ergebnis 45 (R1 + M [0 + R1] = 3 + 42).
Seite 6 / 6