Kapitel 3

Transcrição

Kapitel 3

Grundlagen der Informatik III
WS 2008 / 2009
[Folien basierend auf VL von Prof. Dr. Claudia Eckert,
WS 07/08]
Prof. Dr. rer. nat. Frederik Armknecht
Sascha Müller
Daniel Mäurer
Fachbereich Informatik / CASED
Mornewegstraße 30
64293 Darmstadt
Gliederung der Vorlesung GdI 3
1. Einführung
2. Assemblerprogrammierung
3. Leistungsbewertung
4. Speicherhierarchie
5. Ein-Ausgabe
6. Betriebssysteme (Grundlagen)
7. Assembler, Binder, Lader
8. Rechnernetze (Grundlagen)
9. Compiler (Grundlagen)
Fachbereich Informatik | Prof. Dr. Frederik Armknecht | 2
Gliederung dieses Kapitels
3.1 Einführung
3.2 Bewertungskriterien für Prozessoren
3.3. Bewertungskriterium Ausführungszeit
3.4 Leistungsbewertung
3.5 Taktung
3.6 CPU-Performanz
3.7 Beispiele
3.8 Benchmarks
3.9 Verbesserungen der CPU-Leistung
3.1 Einführung
Hardware: bestimmt die Leistungsfähigkeit des
Rechners, d.h. um die Software-Performance zu
erhöhen, muss man die Performanz-Faktoren der
Hardware und des BS verstehen
• Bisher: rein qualitative Betrachtung der funktionalen
Eigenschaften des Prozessors
• Erforderlich: Quantifizierbare Maße für die Messung
der Leistungsfähigkeit von Prozessoren
• Problem: Auswahl geeigneter Bewertungskriterien
• Wann „ist ein Prozessor besser als ein anderer“?
3.1 Einführung
Bewertungskriterien
• Perspektive des Käufers: Prozessoren:
• welcher hat die beste Leistung?
• die niedrigsten Kosten?
• das beste Preis-/Leistungsverhältnis?
• Perspektive des Designers: Designoptionen:
• welche hat die beste Leistungsverbesserung?
• die geringsten Kosten?
• das beste Preis-/Leistungsverhältnis?
Beide benötigen eine Metrik zur Bewertung
Ziel: Verständnis für die Auswirkungen von DesignEntscheidungen auf Kosten & Leistung
Analogie zur Illustration: Passagierflugzeuge
Flugzeug
Passagierkapazität (#p)
Reichweite
(Meilen mi)
Reisegeschwindigkeit (mi/h)
Passagierdurchsatz (#p × mi/h)
Boeing 747
470
4150
610
286 700
Boeing 777
375
4630
610
228 750
Airbus A380
656
8400
600
393 600
BAC/Sud Concorde
132
4000
1350
178 200
Douglas DC-8-50
146
8720
544
79 424
 Bewertung: Welches ist das „beste“ Flugzeug?
 Kriterien: Passagierkapazität / Reisegeschwindigkeit Reichweite / ...
Analogie zur Illustration: Passagierflugzeuge
Die „besten“ Flugzeuge?
 Passagierkapazität:
Airbus A380
 Reichweite:
Douglas DC 8
 Geschwindigkeit:
Reisegeschwindigkeit: BAC/Sud Concorde
Airbus A380
 Passagierdurchsatz:
(#Passagiere × Reisegeschwindigkeit)
unterschiedliche Bewertungskriterien für unterschiedliche
Anwender!
 Analoges gilt auch für die Bewertung von Rechnern
Welche Leistungsmaße sind denkbar?
• Antwortzeiten, Durchsatz, Ausführungszeiten
(response/execution time, latency):
• Aus Sicht einzelner Benutzer:
Kriterium: Antwortzeit :
• Wie schnell wird eine einzelne
Aufgabe vom Prozessor gelöst?
• Der schnellste Prozessor ist derjenige, der eine
gegebene Aufgabe am schnellsten löst.
• Frage: Welche Aufgabe ist repräsentativ?
Aus Sicht eines Rechenzentrumsbetreibers:
Kriterium: Durchsatz (throughput):
• Wie viel Arbeit kann ein Rechner pro
Tag/Stunde/Woche/sec/ns erledigen?
• Der schnellste Prozessor ist derjenige, der die
meisten Jobs pro Tag bearbeitet.
Kriterium: Ausführungszeit (execution time)
• Die Leistung eines Prozessor wird am besten durch
die Ausführungszeit für ein Programm beschrieben
Benutzerantwortzeit (elapsed time):
• Zeit, die real vergeht, bis eine gegebene Aufgabe
vom Rechner gelöst wurde.
• zählt alles (Festplatten, Speicherzugriffe, EA, …)
• bewertet Systemperformanz
• aber i.d.R. ungeeignet für Prozessor-Vergleiche
CPU-Ausführungszeit (CPU execution time)
• Zeit, die die CPU bei der Lösung der Aufgabe
benötigt ohne Ein-/Ausgabe und Zeit für andere
Aufgaben (Scheduling etc.)
CPU-Ausführungszeit (Forts.)
• besteht aus
• system CPU time (CPU-Zeit für Betriebssystemaufgaben) und
• user CPU time (CPU-Zeit, die zur Ausführung der Codezeilen
eines Programms benötigt wird)
• bewertet CPU-Performanz
Beispiel: Unix time Befehl
Ausgabe sei: 90.7u 12.9s 2:39 65%
Interpretation:
• user CPU: 90.7, system CPU: 12.9,
• Antwortzeit: 159 sec (=2:39)
• Anteil der CPU-Zeit: (90.7 + 12.9)/159 = 0.65
 d.h. > 1/3 der Zeit ist Wartezeit (u.a. E/A)
3.4 Leistungsbewertung
Leistungsbewertung (performance evaluation)
erfolgt in „Einheiten von Dingen pro Sekunde“
• Daumenregel: größer ist besser
• Falls Hauptkriterium Ausführungszeit ist, dann
gilt:
• Performanz(x) = 1 / Ausführungszeit(x)
• „x ist n-mal schneller als y“ bedeutet dann:
Performanz( x)
n =
Performanz( y )
Beispiel
 Ausführungszeit (Geschwindigkeit) von Concorde vs. Airbus A380 ?
 Concorde ist 1350 mph / 600 mph = 2.25-mal schneller
 Durchsatz von Concorde vs. Airbus A380 ?
 Concorde ist 178 200 pmph / 393 600 pmph = 0.45-mal besser
 Airbus A380 ist 393 600 pmph / 178 200 pmph = 2.2-mal besser
 Bewertung:
 A380 ist 2.2-mal (um „120%“) besser hinsichtlich Durchsatz.
 Concorde ist 2.25-mal (um „125%“) schneller hinsichtlich Flugzeit.
3.5 Taktung
 Anwender denken an Ausführungszeit in gemessener Zeit.
 Prozessorentwickler verwendet eher ein Maß, das in
Bezug dazu steht, wie schnell die Hardware elementare
Funktionen durchführen kann.
 Nahezu alle heutigen Computer beruhen auf einer
konstanten Taktrate, die das Auftreten von
(synchronisierenden) Schaltereignissen in der Hardware
bestimmt ((clock) cycles, (clock) ticks, clock periods):
3.5 Taktung
Taktzykluszeit (clock period):
• Länge für einen kompletten Taktzyklus
(z.B. 0.5 Nanosekunden bzw. 0.5ns)
Taktfrequenz (clock rate):
• Inverse der Taktzykluszeit
(z.B. 2 Gigahertz bzw. 2 GHz)
Zeit
3.5 Taktung
...
6.
5.
4.
3. Instruktion
2. Instruktion
1. Instruktion
 Wie viele Zyklen benötigt ein Programm?
 Man könnte annehmen, dass # Instruktionen = # Takte, d.h.
Zeit
 Diese Annahme ist falsch!
 Verschiedene Instruktionen benötigen unterschiedliche Zeit auf
unterschiedlichen Prozessoren (Instruktion ≠ C-Programmzeile).
 Warum ist das so?
3.5 Taktung
• Ein Takt pro Instruktion (d.h. alle Instruktionen gleiche Taktlänge)
ist sehr ineffizient, u.a. weil
• die Ausführungszeit dann durch die am längsten dauernde
Instruktion bestimmt wird,
• Hardware-Einheiten (ALU, ...) mehrfach vorhanden sein müssen.
• Stattdessen Mehrtakt-Implementierungen:
• Pro Instruktion mehrere, aber kürzere Taktzyklen
• Anzahl der Taktzyklen pro Instruktion:
clock cycles per instruction, CPI
Zeit
3.5 Taktung
Damit wird unterschiedlichen Ausführungsdauern Rechnung getragen:
 Multiplikation benötigt mehr Zeit als Addition.
 Gleitpunkt-Operationen benötigen mehr Zyklen als solche auf ganzen
Zahlen.
 Zugriff auf Speicher erfordert mehr Zeit als auf Register.
Achtung:
 Eine Veränderung der Taktzykluszeit ändert in der Regel auch die Anzahl
der für die verschiedenen Instruktionen erforderlichen Takte.
3.5 Taktung
Mit Hilfe der Kenntnis von Taktzyklen ...
 Ein gegebenes Programm benötigt
 eine gewisse Anzahl an Maschineninstruktionen,
 eine gewisse Anzahl an Taktzyklen,
 eine gewisse Anzahl an Sekunden.
 Wir können diese Größen jetzt in Bezug setzen:
 Taktzykluszeit (Sekunden pro Zyklus)
 Taktfrequenz (Zyklen pro Sekunde)
 CPI (Zyklen pro Instruktion)
 MIPS (Millionen von Instruktionen pro Sekunde)
3.6 CPU-Performanz
Zusammenhang zwischen Ausführungszeit und Takt:
CPU-Ausführungszeit =
# CPU Taktzyklen des Programms × Taktzykluszeit =
# CPU Taktzyklen des Programms / Taktfrequenz
Wg: CPU Taktzyklen des Progr = # Instruktionen × Ø CPI
gilt: CPU-Ausführungszeit =
# Instruktionen × Ø CPI × Taktzykluszeit =
# Instruktionen × Ø CPI / Taktfrequenz
Performanzgleichung:
CPU - Zeit =
Sekunden Instruktionen
Taktzyklen
Sekunden
=
×
×
Programm
Programm
Instruktionen Taktzyklus
Beispiel
 Unser Testprogramm benötigt 10 Sekunden auf Computer A mit 2 GHz
Taktfrequenz.
 Wir möchten einem Rechnerarchitekten helfen, einen neuen Computer B
zu entwickeln, auf dem unser Testprogramm nur 6 Sekunden benötigt.
 Der Rechnerarchitekt kann neue (d.h. teurere) Technologien zur
Erhöhung der Taktfrequenz verwenden, hat uns aber informiert, dass dies
das übrige CPU-Design beeinflussen wird.
 Deshalb wird Computer B 1.2-mal so viele Taktzyklen für dasselbe
Programm benötigen wie Computer A.
Welche Taktfrequenz soll Computer B haben?
Lösung mit Perfomanzgleichung
Anzahl Taktzyklen für Testprogramm auf Computer A:
CPU-Zeit(A) = # CPU-Taktzyklen(A) / Taktfrequenz(A)
10 sec = # CPU-Taktzyklen(A) / (2×109 Taktzyklen/sec)
# CPU-Taktzyklen(A) = 2×1010 Taktzyklen
CPU-Zeit für Computer B
CPU-Zeit (B) = 1.2 × CPU-Taktzyklen(A) / Taktfrequenz(B)
6 sec = 1.2 × 2×1010 Taktzyklen / Taktfrequenz(B)
Insgesamt
 Taktfrequenz(B) = 1.2 × 2×1010 Taktzyklen/6 sec = 4 GHz
 B benötigt die doppelte Taktfrequenz von A zur Reduktion der
Ausführungszeit von 10 auf 6 sec.
3.6 CPU-Performanz
Performanz wird durch Ausführungszeit bestimmt.
Was als Performanzindikator verwendbar?
Frage: ist eine der folgenden Variablen mit Performanz gleich zu setzen?
• # Taktzyklen für Programmausführung ?
• # Instruktionen des Programms ?
• # Taktzyklen pro Sekunde ?
• durchschnittliche # Taktzyklen pro Instruktion ?
• durchschnittliche # Taktzyklen pro Sekunde ?
Häufiger Fehler: Nur eine dieser Variablen wird als Indikator für
Performanz angesehen.
3.7 Beispiele: irreführende Performanzindikatoren
Beispiel 1: CPI ist irreführender Performanz-Indikator
 Angenommen wir haben zwei Implementierungen der gleichen
Befehlssatzarchitektur (instruction set architecture, ISA).
Für ein Programm gelte:
 Maschine A hat Zyklenzeit von 1ns und CPI von 2.0
 Maschine B hat Zyklenzeit von 2ns und CPI von 1.2
 Welche Maschine ist für dieses Programm schneller?
Lösung:
 A ist schneller und zwar um einen Faktor 1.2
Beispiel 2: # Instruktionen allein ist irreführend
 Gegeben 2 Codesequenzen für eine Maschine
 Die Hardware bietet drei verschiedene Instruktionsklassen A, B, C, die einen, zwei,
drei Zyklen benötigen.
 Die erste Codesequenz habe 5 Instruktionen:
2 von A, 1 von B und 2 von C
 Die zweite Codesequenz habe 6 Instruktionen:

4 von A, 1 von B und 1 von C.
 Frage: Welche Folge ist schneller? Was ist die CPI?
 CPI= # Zyklen/Instruktionsanzahl
 Antwort: Sequenz 1 benötig 10 und Sequenz 2 benötigt 9 Zyklen
 CPI_1 = 2 und CPI_2 = 1.5, also Sequenz 2 ist schneller
Beispiel 3: MIPS-Kennzahl als Indikator
 Annahme: Zwei Compiler werden für eine 500 MHz Maschine mit drei
Instruktionsklassen A, B, C getestet, die je einen, zwei oder drei Zyklen benötigen.
 Der Code des ersten Compilers verwendet
 5 Milliarden Instruktionen der Klasse A,
 1 Milliarde der Klasse B und 1 Milliarde der Klasse C.
 Der Code des zweiten Compilers verwendet
 10 Milliarden Instruktionen der Klasse A,
 1 Milliarde der Klasse B und 1 Milliarde der Klasse C.
Fragen:
 Welche Folge wird hinsichtlich MIPS schneller sein?
 Welche Folge wird hinsichtlich Ausführungszeit schneller sein?
Antwort:
Berechnen der Ausführungszeiten für die beiden Compiler:
Ausführungszeit = Clock-Zyklen/Taktrate
Clock-Zyklus_1 = (5x1+ 1x2 + 1x3)x109 = 10x109
Clock-Zyklus_2 = (10x1+ 1x2 + 1x3)x109 = 15x109
Ausführungszeit_1 = (10x109)/(500 X 106) = 20 Sekunden
Ausführungszeit_2 = (15x109)/(500 X 106) = 30 Sekunden
MIPS = (#Instruktionen)/(Ausführungszeit x 106)
MIPS_1 = (5+1+1)x 109)/(20x 106) = 350
MIPS_2 = 400
• Lesson Learned: Code von Compiler 2 hat höhere MIPS-Zahl,
aber der Code von Compiler 1 wird schneller ausgeführt
d.h. auch MIPS-Werte können in die Irre führen!
Zwischenfazit: Zusammenfassung der Begriffe
Ein gegebenes Programm benötigt zur Ausführung
 Eine Anzahl von Instruktionen (Maschinenbefehlen)
 Eine Anzahl von Takten (Zyklen)
 Eine Anzahl von Sekunden
Beziehungen zwischen den Metriken:
 Zykluszeit oder Taktlänge (Sekunden pro Zyklus)
 Taktrate (Zyklen pro Sekunde)
 CPI (durchschnittliche Anzahl Zyklen pro Instruktion)
 MIPS (Millionen von Instruktionen pro Sekunde)
ist höher für ein Programm mit einfachen Instruktionen
 Zeit = Instruktionen/Programm x Takte/Instruktion x Sekunden/Takt
Aspekte der CPU-Performanz
Taktzyklen
Sekunden
CPU - Zeit =
=
×
×
Programm
Programm
Instruktionen Taktzyklus
Anzahl
Instruktionen
Taktzyklen pro
Instr. (CPI)
Programm
X
Compiler
X
X
Instruktionssatz
X
X
Rechnerorganisation
Technologie
X
Takt-frequenz
X
X
Ressourcen zur Performanzsteigerung sollten dort eingesetzt werden, wo die
Ausführungszeit tatsächlich verbraucht wird!
Beispiel (RISC Prozessor)
Basisprozessor
Operation
Häufigkeit
ALU
50%
Load
20%
Store
10%
Branch
20%
typische Mischung
Cycles CPI(i)
1
.5
5
1.0
3
.3
2
.4
2.2 Ø
% Time
23%
45%
14%
18%
Typische Fragestellungen:
 Wie viel schneller wäre der Prozessor mit einem besseren Datencache, der die
durchschnittliche Ladezeit auf 2 Zyklen reduzieren würde?
 Was würde sich ändern, wenn zwei ALU Instruktionen gleichzeitig ausgeführt
werden könnten?
 ….
3.8 Benchmarks
• Sinnvolle Performanzmaße lassen sich nur durch
Vergleich der Laufzeiten identischer Programme auf
verschiedenen Rechnern ermitteln!
• Benchmarks sind repräsentative Programme, die auf den zu
vergleichenden Rechnern ausgeführt werden.
• Es gilt der Rechner als der Leistungsfähigste, bei dem die
Benchmark-Programme am schnellsten ausgeführt werden.
• Benchmarks sind nutzbar von Rechnerarchitekten,
Compiler-Entwicklern, Anwendern etc.
Vorsicht: Spielraum für Manipulationen!
In der Praxis wurden häufig Compiler oder auch
Instruktionssätze so optimiert, dass gängige
Benchmarks besonders schnell abliefen.
4 Typen von Benchmarks
• Reale Programme: Verwendung häufiger Anwendungen
wie C-Compiler, Textprozessoren (latex), CAD-Programme
(SPICE)
• Kernels: Kurze kritische Auszüge aus realen
Programmen, die isoliert zur Ausführung gebracht werden
Beispiel: SPEC ‘89
Performanz von Compilern: Missbrauchs-Beispiel
800
Benchmark Matrix300:
Matrixmultiplikationen,
• 99% der Rechenzeit
allein durch wiederholte
Ausführung einer Codezeile,
• Compiler-Bauer hat seinen
Compiler so getuned, dass
genau diese Berechnung
optimiert wurde: 700 mal
schnellere Ausführung als
auf einer Vax
700
SPEC performance ratio
600
500
400
300
200
100
0
gcc
espresso
spice
doduc
nasa7
li
eqntott matrix300
fpppp
tomcatv
Benchmark
Compiler
Enhanced compiler
3.8 Benchmarks
„Toy Benchmarks“
• Kleine, einfach zu schreibende Programme, die leicht
zur Ausführung gebracht werden können (z.B. Quicksort)
Synthetische Benchmarks
• Speziell entwickelte Programme, die die
Leistungsfähigkeit einzelner Instruktionen oder einzelner
Komponenten der zu vergleichenden CPUs aufdecken
sollen (z.B. Dhrystone)
• Heute nicht mehr beliebt, da sehr realitätsfern
3.8 Benchmarks
Beispiel: Standard-Benchmark Suites: SPEC
 Standard Performance Evaluation Corporation www.spec.org
 gegründet 1989 durch mehrere Rechnerhersteller (Apollo/HP, DEC,
MIPS, Sun Microsystems)
 Beschaffen eines Satzes von zunächst realen Programmen, die auf allen
Rechnern lauffähig sind und in ihrer Gesamtheit zur Messung der
Prozessorleistung herangezogen werden.
 Die SPEC-Benchmark-Suite durchlief mehrere Generationen, in denen
die einzelnen Programme jeweils den aktuellen Eigenschaften der
Rechner und der Systemsoftware angepasst wurden.
 SPEC besteht heute aus einer Mischung von realen Programmen und
Kernels.
3.8 Benchmarks
SPEC Benchmarks
 CPU89 (1989)
 10 Programme liefern eine einzelne Zahl (“SPECmarks”)
 CPU92 (1992)
 SPECInt92 (6 integer Programme) and SPECfp92 (14 floating point Programme)
 CPU95
 neue Programme: SPECint95 (8 Integer Programme) und SPECfp95 (10 Floating Point Programme)
 ein Compilerflag für alle Programme: SPECint_base95, SPECfp_base95
 CPU2000
 CINT2000 11 integer (gzip, gcc, crafty, perl, ...)
 CFP2000 14 floating-point (swim, mesa, art, ...)
 Alle Ergebnisse gemessen relativ zu Basisrechner Sun 300MHz 256Mb-RAM Ultra5_10; diese hat
score 100
 CPU2006
 CINT2006 Benchmark für Integer-Performanz
 CFP2006 Benchmark für Gleitpunkt-Performanz
 Neben den SPEC CPU-Benchmarks gibt es weitere SPEC Benchmarks.
Wie können Verbesserungen erreicht werden?
 Erhöhung der Taktfrequenz
 Verbesserungen der Prozessororganisation zur Reduzierung der CPI
 Compilerverbesserungen: z.B. geringere Instruktionsanzahl, Pipeline
Reorganisation
Leistungsverbesserung hängt ab von
 dem Anteil an der Ausführungszeit, die ein bestimmter Task mit der
verbesserten Hardware verbringt
 der Verbesserungsrate, die durch die verbesserte Hardware erreicht
wird
Amdahl's Gesetz: speed-up sollte sich an dem Prinzip:
„make the common case fast“ orientieren
Amdahl’s Gesetz: Beispiel
• Floatingpoint Instruktionen werden um einen Faktor 2 beschleunigt;
der Anteil der Floatingpoint Instruktionen an der Gesamtausführungszeit
des Programms ist aber nur 10% der Gesamtzeit
Zeitneu = Zeitalt x (0.9 + 0.1/2) = 0.95 x Zeitalt
Speedupgesamt
CPU - Zeit neu
=
1
=
1.053
0.95

Anteilverbessert 
= CPU - Zeit alt × (1 − Anteilverbessert ) +

Faktor
verbessert 

Verbesseru ng =
CPU - Zeit alt
CPU - Zeit neu
 Prozessorvergleich: Beispiel
 i860
 2 Gleitpunkt-Operationen + 1 Integer-Operation pro Taktzyklus
 @50MHz: 100 MFLOPs und 150 MOPs
 MIPS R 3000
 @33MHz: 16 MFLOPs und 33 MOPs
 Erwartung:
 i860 ist mehr als 5-mal schneller
 SPEC Benchmarks:
 R3000 war 15% schneller
Fazit
Performanz ist programmspezifisch
• Ausführungszeit ist wichtigstes Maß
• Eine Verbesserung individueller Kennzahlen (z.B. CPI,
Taktrate) erhöht nicht notwendigerweise die
Gesamtperformanz!
• nur das Produkt aus allen Einzelfaktoren:
Zyklen
Sekunden
=
×
×
Programm
Programm Instruktionen
Zyklus
ist ein verlässliches Performanzmaß
• Nicht alle Performanzangaben kritiklos glauben!

Kapitel 3

Transcrição

Documentos relacionados

Frederik Schroyens Synthesis 9.1 (English Edition)

Angebot Kopenhagen

Career Planning and Job Application Other Offers at FSU Jena

Antrag auf Wiederherstellung meines HTW

Dänische Spuren im Schloss

5. intensivkammer- musikkurs

Programm - Johann-Gottfried-Herder

Kreativ Backkurs - süß und pikant - Fa. LUMARA

Erfahrungsbericht Nadja Donauer

Girls`Day 2007