Lösungsvorschlag zur 4. Übung, GdI 3

Prof. Frederik Armknecht
Sascha Müller
Daniel Mäurer
Grundlagen der Informatik 3
Wintersemester 09/10
Lösungsvorschlag zur 4. Übung
1 Präsenzübungen
1.1 Schnelltest
a) Welche Aussagen zu Bewertungskriterien für Prozessoren sind richtig?
4 Die CPU-Ausführungszeit ergibt sich aus den verwendeten Operationen und
der Taktung der CPU.
2 Die CPU-Ausführungszeit ist die gemessene Zeit, welche die CPU real zum
Ausführen der Codezeilen eines Programms benötigt.
4 Die CPU-Systemzeit ist die Zeit, welche die CPU für Betriebssystemaufgaben
verwendet.
2 Die Benutzerantwortzeit ist ein geeignetes Maß für CPU-Performanz
2 Rechner mit hohen Durchsatz haben auch kürzere Ausführungszeiten als
Rechner mit niedrigem Durchsatz.
b) Welche Elemente einer Programmausführung fließen nicht in die user-CPU-time mit
ein?
4 Festplattenzugriffe
4 Verzögerung durch Cache-Misses
4 I/O-verzögerung durch Hardware
2 CPU-Ausführungszeit
c) Welche Elemente einer Programmausführung fließen in die Benutzerantwortzeit mit
ein?
4 I/O-verzögerung durch Hardware
4 Verzögerung durch Cache-Misses
4 CPU-Ausführungszeit
4 Festplattenzugriffe
1.2 Leistungsbewertung
In der Vorlesung haben wir folgende Größen im Zusammenhang mit der CPU-Zeit kennengelernt.
T
f
t
MIPS
CPI
B
Z
CPU-Zeit in Sekunden
Taktfrequenz in Zyklen pro Sekunde
Taktzykluszeit in Sekunden pro Zyklus
Millionen von Instruktionen pro Sekunde
mittlere Anzahl Zyklen pro Instruktion
Anzahl Instruktionen
CPU-Zeit in Zyklen
1
Lösungsvorschlag zur 4. Übung
Grundlagen der Informatik 3, WS 09/10
a) Leiten Sie die Formeln der gesuchten Größen aus den angegebenen Größen her.
1. gesucht: T gegeben: Z, t
T=Z*t
2. gesucht: CPI, gegeben: Z, MIPS, T
CPI = Z / (T * MIPS * 106 )
3. gesucht: T, gegeben: f, CPI, B
T = B * CPI / f
4. gesucht: B, gegeben: T, MIPS
B = T * MIPS * 106
5. gesucht: Z, gegeben: T, CPI, MIPS
Z = , T *CPI * MIPS * 106
b) Zwei unterschiedliche Prozessoren mit jeweils 2.4 Ghz und 2.233 Ghz Taktfrequenz
bearbeiten eine Berechnung, die insgesamt aus 9 · 107 Instruktionen besteht. Der erste Rechner benötigt 14 Zyklen pro Instruktion, der zweite 12. Welcher Rechner ist
schneller fertig?
T = B · CPI/ f . Also T1 =
9·107 ·14
2.4·109 Hz
≈ 52.5 ms und T2 =
9·107 ·12
2.233·109 Hz
≈ 48.4 ms.
c) Die Operationen einer komplexen Berechnung benötigen zusammengenommen 7.7 ·
107 Rechenzyklen. Wie lange dauert die Ausführung auf einem Prozessor mit 3.2 Ghz
Taktfrequenz?
T = Z/ f =
1.1·107
3.2·109 Hz
≈ 2.4 ms
d) Ein Rechner benötigt für eine komplexe Berechnung 1350ms mit 2.3 MIPS. Wie viele
Instruktionen werden dabei verarbeitet?
B = T · MIPS · 106 = 1.35s · 2.3/s · 106 = 3 105 000 Instruktionen.
e) Obiger Rechner hat eine Taktfrequenz von 750 Mhz. Wie hoch ist die mittlere Anzahl
an Rechenzyklen pro Instruktion?
T = B · CPI/ f → CPI = T · f /B =
1.35s·75·106 Hz
3105000
= 326
1.3 Performanzvergleich
Betrachten wir zwei Hardware-Implementierungen M1 und M2 eines Befehlssatzes mit vier
Befehlsklassen Add, Jmp, Mul und Shft. Die angegebene Taktfrequenz ist 1, 133 GHz für M1
und 750 MHz für M2. Desweiteren sind die Daten aus Tabelle 1 gegeben.
Befehlsklasse
Add
Jmp
Mul
Shft
CPI für M1
2
2
5
1
CPI für M2
1
2
3
1
Befehlsklasse
Add
Jmp
Mul
Shft
Tabelle 1: CPI für M1 und M2
Häufigkeit
45%
15%
25%
15%
Tabelle 2: Häufigkeiten für P1
a) Ein Programm P1 weist folgende Verteilung der Befehlshäufigkeiten auf: (siehe Tabelle 2). Wie viele CPI erreichen M1 und M2 bei der Ausführung von P1?
2
Lösungsvorschlag zur 4. Übung
CPI für M1 bei Ausführung von P1 =
CPI für M2 bei Ausführung von P1 =
Grundlagen der Informatik 3, WS 09/10
45
100
45
100
·2+
·1+
15
100
15
100
·2+
·2+
25
100
25
100
·5+
·3+
15
100
15
100
· 1 = 2,6
· 1 = 1,65
b) Wie ist die relative Performanz zwischen M1 und M2 bei Ausführung von P1?
n2 sei die Anzahl der Befehle von P1.
CPU-Zeit für M1 zur Ausführung von P1 =
CPU-Zeit für M1 zur Ausführung von P1 =
Also ist M1 um 4.09% langsamer als M2.
n2 ·2,6
s ≈ n2 · 2,29 · 10−9 s
1,133·109
n2 ·1,65
s ≈ n2 · 2,2 · 10−9 s
7,5·108
c) Das Programm P2 enthält jeweils gleich viele Befehle aus den vier Befehlsklassen. Wie
hoch ist die mittlere Anzahl der Zyklen pro Behfehl (CPI) bei Ausführung von P1 auf
M1 und M2?
CPI für M1 bei Ausführung von P2 =
CPI für M2 bei Ausführung von P2 =
2+2+5+1
4
1+2+3+1
4
= 2,5
= 1,75
d) Wie ist die relative Performanz zwischen M1 und M2 bei Ausführung von P2?
n1 sei die Anzahl der Befehle von P2.
CPU-Zeit für M1 zur Ausführung von P2 =
CPU-Zeit für M2 zur Ausführung von P2 =
Also ist M1 um 5.15% schneller als M2.
3
n1 ·2,5
s ≈ n1 · 2,21 · 10−9 s
1,133·109
n1 ·1,75
s ≈ n1 · 2,33 · 10−9 s
7,5·108
Lösungsvorschlag zur 4. Übung
Grundlagen der Informatik 3, WS 09/10
1.4 Geschachtelte Schleifen
Folgendes Programmstück bearbeitet ein Array von 5000 Worten. Die Basisadresse des Arrays befindet sich in $a0 und die Array-Größe (5000) in $a1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sll
add
add
outer : add
lw
add
add
inner : add
lw
bne
addi
skip : addi
blt
slt
bne
add
add
next : addi
blt
$a1 ,
$v0 ,
$t0 ,
$t4 ,
$t4 ,
$t5 ,
$t1 ,
$t3 ,
$t3 ,
$t3 ,
$t5 ,
$t1 ,
$t1 ,
$t2 ,
$t2 ,
$v0 ,
$v1 ,
$t0 ,
$t0 ,
$a1 , 2
$zero , $zero
$zero , $zero
$a0 , $t0
0( $t4 )
$zero , $zero
$zero , $zero
$a0 , $t1
0( $t3 )
$t4 , skip
$t5 , 1
$t1 , 4
$a1 , inner
$t5 , $v0
$zero , next
$t5 , $zero
$t4 , $zero
$t0 , 4
$a1 , outer
a) Was wird mit diesem Programm berechnet?
$v1 enthält das Element mit häufigstem Vorkommen im Array und $v0 enthält dessen Häufigkeit.
b) Auf einem bestimmten Rechner benötigen die Befehle add, addi, sll und slt jeweils
1 Taktzyklus und die Befehle lw, bne und blt jeweils 2 Taktzyklen. Wieviel Taktzyklen
benötigt dann unser Programmstück auf diesem Rechner im schlechtesten Fall.
Die outer-Schleife wiederholt sich 5000 mal mit jeweils 1 + 2 + 1 + 1 Zyklen vor der
inner-Schleife und 1 + 2 + 1 + 1 + 1 + 2 Zyklen danach im schlechtesten Fall. Wir
haben also damit zunächst 5000 · 13 Zyklen.
Die inner-Schleife wiederholt sich 5000 · 5000 mal mit jeweils 1 + 2 + 2 + 1 + 1 + 2
Zyklen, womit wir weitere 5000 · 5000 · 9 Zyklen haben.
Mit den ersten 3 Instruktionen haben wir also maximal 3 + 5000 · 13 + 5000 · 5000 ·
9 = 225065003 Taktzyklen.
c) Wie hoch ist dann im schlechtesten Fall die mittlere Anzahl der Zyklen pro Befehl
(CPI)?
Im in b) dargestellten schlechtesten Fall werden 3 + 5000 · 10 + 5000 · 5000 ·
6 = 150050003 Instruktionen ausgeführt. Damit ergeben sich also durchschnittlich
225065003
150050003 ≈ 1, 499 Zyklen pro Befehl.
4
Lösungsvorschlag zur 4. Übung
Grundlagen der Informatik 3, WS 09/10
2 Hausübungen
2.1 Performanz
Sie sind der Chefdesigner eines neuartigen hochspezialisierten Prozessors zur hardwaregestützen Organisation von Übungs und Praktikums-Aufgaben für Grundstudiumsveranstaltungen in der Informatik. Das Design und der Compiler sind fertig und wurde schon
erfolgreich im WS08 getestet, Sie müssen aber jetzt entscheiden, ob Sie die aktuelle Version
des Prozessors produzieren lassen, oder zusätzliche Zeit verwenden, den Prozessor weiter
zu verbessern. Das Compilerteam schlägt zur Steigerung der Performanz vor, den Compiler zu verbessern. Sie diskutieren das Problem mit Ihrem Hardware und Compilerteam
und kommen zu folgenden Optionen:
• Das Design bleibt wie es ist. Dieser Prozessor wird Rbasis genannt und hat eine Taktrate
von 5 MHz.
• Optimiere die Hardware. Das Hardwareteam kann das Prozessordesign weiter verbessern und eine Taktrate von 6 MHz erreichen. Diesen Prozessor nennen wir Ropt .
• Optimiere den Compiler. Das Compilerteam kann vor allem das automatische Beantworten von Mails effizienter zu gestalten. Die Kombination von verbessertem Compiler und Rbasis nennen wir Rcomp .
Die Simulation der beiden Hardware implementierungen hat die Werte aus Tabelle 3 geliefert. Der neue Compiler verändert die Befehlshäufigkeiten relativ zur ursprünglichen
Variante, wie in Tabelle 4 angegeben.
Befehlsklasse
Folien erstellen
Übung erstellen
Mails beantworten
MuLö erstellen
Leerlauf
BefehlsCPI
häufigkeit Rbasis
17%
4
33%
5
40%
5
9%
6
1%
13
CPI
Ropt
4
5
4
4
21
Tabelle 3: CPI für Rbasis und Ropt
a) Wie hoch ist die durchschnittliche CPI für Rbasis
Befehlsklasse
F
Ü
Mail
Mulö
L
Relative Häufigkeit ggü. Rbasis1
85%
110%
33%
80%
45%
Tabelle 4: Relative
Häufigkeiten für Rcomp
und Ropt ?
2 Punkte
33
40
9
1
17
100 · 4 + 100 · 5 + 100 · 5 + 100 · 6 + 100 · 13 = 5
17
33
40
9
1
100 · 4 + 100 · 5 + 100 · 4 + 100 · 4 + 100 · 21 = 4, 5
CPIRbasis =
CPIRopt =
b) Wieviel MIPS verarbeiten die Prozessoren jeweils?
1 Punkt
5 MHz
≈1
5
6 MHz
4,5 ≈ 1, 333
MIPSRbasis =
MIPSRopt =
c) Um wieviel schneller ist Ropt gegenüber Rbasis ?
1 Punkt
MIPSRopt
= 1,333
1 ≈ 1, 333 ⇒ 33, 3333% Verbesserung
MIPSRbasis
Man kann hier mittels MIPS vergleichen, da beide Rechner die gleiche Befehlsmenge
haben.
1 Das
bedeutet, dass z. B. Rcomp nur 85% der Anzahl von Instruktionen der Klasse F ausführt, die Rbasis benotigt.
5
Lösungsvorschlag zur 4. Übung
Grundlagen der Informatik 3, WS 09/10
d) Wie hoch ist die durchschnittliche CPI für Rcomp ?
2 Punkte
Für diese Aufgabe muß man die neue (relative) Anzahl an Instruktionen für Rcomp
85
33
40
33
9
80
1
45
17
· 100
+ 100
· 110
berechnen. Dies ergibt: 100
100 + 100 · 100 + 100 · 100 + 100 · 100 = 0, 716
Die neue CPI kann dann berechnet werden zu
CPIRcomp =
17
100
·
85
100
·4+
33
100
·
110
100
·5+
40
100
33
· 100
·5+
0, 716
9
100
·
80
100
·6+
1
100
·
45
100
· 13
3.5435
0, 716
≈ 4, 949
=
e) Um wieviel schneller ist Rcomp gegenüber Rbasis ? Beachten Sie hierfür, dass sich die
Anzahl der Befehle für beide Varianten unterscheidet!
2 Punkte
Hier kann CPIRcomp nicht direkt eingesetzt werden, da ein Programm zu zwei verschiedenen Kompilaten führt. Darum muss die Verringerung der Befehlsanzahl berücksichtigt werden.
5 MHz
5
CPIRbasis
·
=
≈ 1, 411
5 MHz CPIRcomp · 0, 716
4, 949 · 0, 716
Also ist Rcomp etwa 41% schneller als Rbasis .
f) Beide Verbesserungen konnen auch gemeinsam in einem Rechner Rbeide umgesetzt
werden. Um wieviel schneller ist Rbeide als Rbasis ?
2 Punkte
Man muß zuerst CPIRbeide bestimmen. Die neue CPI kann dann berechnet werden
zu
CPIRcomp =
17
100
·
85
100
·4+
33
100
·
110
100
·5+
40
100
33
· 100
·4+
0, 716
9
100
·
80
100
·4+
1
100
·
45
100
· 21
3.3035
0, 716
≈ 4, 6138
=
Hier ergibt sich analog zur vorherigen Teilaufgabe d) ein Wert von ca. 4,6138. Die
Taktraten der beiden Rechner sind 5 MHz für Rbasis und 6 MHz für Rbeide . Es ergibt
sich somit nach Einsetzen in die Gleichungen aus Teilaufgabe e)
CPIRbasis
6 MHz
5·6
·
=
≈ 1, 816
5 MHz CPIRbeide · 0, 716
4, 6138 · 0, 716 · 5
Damit ist Rbeide etwa 82% schneller als Rbasis .
6