Laufzeiteffizienz

Inhalt:

Vorbemerkung

• Warum Laufzeiteffizienz?
• Wie erreicht man eine effizientere Laufzeit?

Ein Fallbeispiel: Das N-Körper-Problem

• Der Algorithmus
• Optimierungsmaßnahmen

Designebenen

• Computersystem
• Designebenen im Einzelnen

The Back Of The Envelope

• Das Mississippi-Problem

Nützliche Daumenregeln

• Die Dimensionen müssen passen!
• Casting Out Nines
• 72er-Regel / Verdopplungsregel
• "Pi Sekunden sind ein Nano-Jahrhundert"!
• Sicherheitsfaktoren

Little's Law

Aufgabe

Vorbemerkung

Warum Laufzeiteffizienz?

Zu Beginn gilt es, die Frage zu klären, warum überhaupt Laufzeiteffizienz so wichtig ist; schließlich ist ein geringer Platzbedarf oder die Korrektheit eines Programms ebenso gefordert.

Geringe Laufzeit, geringer Platzbedarf und Korrektheit eines Programms stehen untereinander in einer Art Konkurrenzsituation: Oft schließt ein geringer Platzbedarf einen schnellen Algorithmus aus (Beispiel: einfach verkettete Liste; Algorithmus: Vorgänger eines Elementes bestimmen), oder man erreicht durch den Einsatz platzsparender Datenstrukturen eine bessere Laufzeit (Beispiel: Einsatz von 32 Bit-Fließkommazahlen statt 64 Bit-FPN), büßt dabei jedoch an Genauigkeit (d.h. Korrektheit) ein.

Laufzeitoptimierung hat oberste Priorität! Denn durch einen in der Laufzeit verbesserten Algorithmus muss nicht zwangsläufig ein wesentlich größerer Platzbedarf oder ein geringe Genauigkeit resultieren; oft bietet der neue Einblick in das Problem sogar die Möglichkeit, Platz einzusparen oder die Genauigkeit zu verringern, ohne dass das Programm tatsächlich "falsch rechnet". Außerdem bietet die verbesserte Laufzeit bei zukünftigen Hardwareverbesserungen insgesamt die bessere Performance des Systems als eine Optimierung auf geringsten Platzbedarf.

Wie erreicht man eine effizientere Laufzeit?

Antwort: Durch Optimieren, und zwar auf verschiedenen Designebenen! Und durch häufiges Abschätzen der Laufzeit im aktuellen Entwicklungsstadium; dadurch zeigt sich, ob sich die Laufzeit in die richtige Richtung bewegt.

Der Begriff Designebenen soll weiter unten erläutert werden, doch zunächst...

Ein Fallbeispiel: Das N-Körper-Problem

Andrew Appel veröffentlichte 1985 "An efficient program for many-body simulations", also einen optimierten Algorithmus zur Lösung des physikalischen N-Körper-Problems.

Das N-Körper-Problem dreht sich um die Frage, wie sich Massekörper (mit gegebener Position im Raum und Initialgeschwindigkeit) in ihrem gemeinsamen Gravitationsfeld bewegen. Da die Lösung des Problems schon für n=3 Körper nicht mehr trivial ist, müssen die Flugbahnen der Körper approximiert werden.

Der Algorithmus

Der naive Lösungsansatz besteht zunächst darin, die Anziehungskraft zwischen je zwei Körpern zu bestimmen und damit die Änderung der Flugbahnen der Körper auszurechnen. Dies muss für jeden Körper zu jedem anderen Körper geschehen, also n² mal, somit resultiert eine Laufzeit von O(n²). Weiterhin handelt es sich bei den Berechnungen um Fließkommaoperationen, was bedeutet, dass jede dieser Berechnungen viele hundert Taktzyklen in Anspruch nimmt, was sich ebenso auf die Laufzeit auswirkt. Schließlich wird die Genauigkeit der Approximation durch die Länge der simulierten Zeitschritte bestimmt; je kürzer die Zeitschritte, umso genauer die Simulation - aber umso größer die Laufzeit. Zur Verwaltung der Daten in diesem ersten Algorithmus genügt ein eindimensionales Array, das für jeden Körper dessen Masse, Position und (vektorielle) Geschwindigkeit verwaltet.

Appel selbst schätze 1985 die Laufzeit dieses naiven O(n²)-Algorithmus für n=10.000 und 1.000 Zeitschritte auf über 1 Jahr!

[Hier gibt es mehrere Demonstrationsapplets, die den Algorithmus visuell darstellen und eindrucksvoll den Laufzeitzuwachs zeigen.]

Optimierungsmaßnahmen

Der O(n²)-Algorithmus konnte nicht die endgültige Lösung des Problems sein. Appel verringerte die Laufzeit des Programms drastisch und erreichte schließlich einen Speedup um den Faktor 400, und für n=10.000 und 1.000 Schritte betrug die Laufzeit schließlich nur noch einen Tag!

Diesen Speedup konnte Appel nur dadurch erreichen, dass er auf mehreren Designebenen optimierte:

1. Maßnahme: Organisation der Daten in einem Binärbaum
Das einfache Array zur Datenorganisation wird durch einen Binärbaum ersetzt, dessen Blätter einzelne Objekte repräsentieren. Innere Knoten repräsentieren entsprechend der Baumhierarchie Cluster mehrerer Objekte.
- resultierende Laufzeit: O(n log n)
- Clusterhierarchie ist Voraussetzung für weitere Maßnahmen
- Speedup-Faktor durch diese Maßnahme: 12

2. Maßnahme: Vergrößerung der Zeitschritte bei gleichbleibender Genauigkeit
Die Binärbaumstruktur erlaubt es nun, größere Zeitschritte bei der Simulation zu verwenden, wobei die Genauigkeit der Bahnapproximation nicht verringert wird. Dies führt natürlich zu einem Laufzeitvorteil.
- Speedup-Faktor durch diese Maßnahme: 2

3. Maßnahme: Rekonfiguration des Binärbaums nach jedem Berechnungsschritt
Nach einigen Berechnungszyklen ist die Konfguration des Binärbaums nicht mehr optimal. Die Neuordnung der Clusterhierarchie nach jedem Zeitschritt benötigt zwar zusätzliche Laufzeit, doch durch diese Rekonfiguration verkleinert sich der Binärbaum sukzessive, wodurch sich insgesamt ein größerer Laufzeitvorteil ergibt.
- Speedup-Faktor durch diese Maßnahme: 2

4. Maßnahme: Verwenden von 32 Bit- statt 64 Bit-Fließkommazahlen
Die Einführung des Binärbaums erlaubt auch die Verringerung der Genauigkeit in der Fließkommadarstellung, ohne die Genauigkeit der Simulation signifikant zu verschlechtern. Dies bringt nicht nur einen Geschwindigkeitsvorteil, sondern auch eine Verringerung des benötigten Speicherplatzes um 50%!
- Speedup-Faktor durch diese Maßnahme: 2

5. Maßnahme: Implementation der Berechnungsfunktionen in Assembler
Die Umsetzung des Bahnberechnungsalgorithmus direkt in Assemblercode bringt einen größeren Laufzeitgewinn, da diese Funktionalität den größten Teil der Laufzeit ausmacht.
-Speedup-Faktor durch diese Maßnahme: 2,5

6. Maßnahme: Ausrüsten des Computersystems mit einer Fließkomma-Recheneinheit
Da ein Großteil der Operationen des N-Körper-Algorithmus Fließkommaberechnungen sind, bringt der Einsatz einer FPU eine größere Verbesserung in der Laufzeit. Aufwendige Berechnungen werden durch schnelle Spezialhardware erledigt, evtl. können sogar mehrere Berechnungen parallel ausgeführt werden.
- Speedup-Faktor durch diese Maßnahme: 2

Fazit:
Die einzeln erreichten Speedups multiplizieren sich nahezu zu einem Gesamtspeedup-Faktor von etwa 400 (d.h. es ergibt sich durch den optimierten Algorithmus eine 400fach geringere Laufzeit, z.B. 1 Tag statt 1 Jahr).
Der neue Algorithmus erlaubt also schnellere, häufigere und genauere Simulationen. Außerdem ergeben sich bei zukünftigen Hardware-Upgrades wesentlich kürzere Laufzeiten dank der O(n log n)-Laufzeit im Vergleich zu früher. Schließlich ist ein so optimiertes Programm natürlich auch wirtschaftlicher, denn es verbraucht weniger Ressourcen bei gleicher Leistung.

Designebenen

An dieser Stelle soll nun erläutert werden, was man unter Designebenen versteht. Zunächst eine Definition des Begriffs Computersystem:

Computersystem

Ein Computersystem besteht aus

• der Anwendungssoftware (dem eigentlichen "Programm"),

• der Systemsoftware (neben Betriebssystem auch Compiler u.a.),

• der Hardware.

Dieses Modell liefert schon eine grobe Strukturierung der möglichen Designebenen:

Designebenen im Einzelnen

1. Problemspezifikation

2. Modularisierung

3. Algorithmen & Datenstrukturen

4. Codeoptimierung

5. Systemsoftware

6. Hardwareumgebung

Designebenen sind konkrete Gebiete, auf denen optimiert wird, um die Laufzeit zu verbessern. Die Punkte 1. bis 4. sind Designebenen auf Anwendungsebene, während die Punkte 5. und 6. auf der Ebene der Systemsoftware bzw. der Hardware beheimatet sind.

Einzelne Speedups auf den verschiedenen Designebenen multiplizieren sich i.A. zu einem großen Gesamtspeedup. Daher kann man die Höhe des Gesamtspeedup durch die Auswahl der zu optimierenden Ebenen kontrollieren.

1. Problemspezifikation
Das gegebene Problem wird oft zu grob beschrieben, als dass daraus direkt ein guter Algorithmus entstehen könnte. Eine genauere Analyse liefert daher wichtige Details, die als Ausgangspunkt der Optimierungen dienen. Einige eindrucksvolle Beispiele dafür:
- MaxSummen-Problem: von O(n³) auf O(n)
- N-Körper-Problem: von O(n²) auf O(n log n) bzw. Speedup-Faktor 100 durch Binärbaum

2. Modularisierung
Der modulare Aufbau von Softwaresystemen erleichtert
- die Entwicklung und das Verstehen des ganzen Programms
- die Laufzeitabschätzung,
- die Laufzeitoptimierung und
- den Austausch langsamer Komponenten, wenn ihre Laufzeit zu schlecht ist.

3. Algorithmen und Datenstrukturen
Die Optimierung der Algorithmen und Datenstrukturen ist essentiell:
- Das Anpassen der A. und D. an das Problem liefert den wichtigsten Speedup und
- liefert beim Einsatz schnellerer Hardware weiteren Geschwindigkeitsschub durch besseres O-Laufzeitverhalten.

4. Codeoptimierung
Hier bedeutet Codeoptimierung die Optimierung auf Maschinenebene, ist also vom Rechnersystem abhängig. Zur Codeoptimierung zählen z.B.
- Implementieren von Hochsprache-Funktionen direkt in Assembler
- Verringerung der Genauigkeit der Fließkomma-Zahldarstellung
Ein moderner Compiler kann diese Aufgaben oft selbst übernehmen, so dass Codeoptimierung von Hand keine so große Bedeutung mehr hat. 

5. Systemsoftware
Um auf dieser Ebene zu schnelleren System zu gelangen bieten sich viele Möglichkeiten zur Optimierung, die jedoch selten große Einzelspeedups bringen; z.B.:
- Wechsel auf ein Betriebssystem, das besser auf das Problem zugeschnitten ist
- Einsatz besserer Compiler, die den Code stärker optimieren
- nach Hardware-Upgrade neue Systemsoftware, um diese neue Hardware zu unterstützen
- Wechsel auf ein anderes Datenbanksystem, das schnellere Zugriffe erlaubt

6. Hardwareumgebung
Ein Speedup des Systems durch schnellere Hardware bringt in Verbindung mit "guten" Algorithmen immer den größten Laufzeitvorteil.
- Spezialhardware (z.B. FPU oder Grafikbeschleuniger) entlastet den Prozessor und beschleunigt (und parallelisiert) die Programmabarbeitung
- schnelle Prozessoren steigern Performance des gesamten Systems

The Back Of The Envelope

...oder "Intuitive Überschlagsrechnungen und Abschätzungen"

Ein Beispiel für eine solche Back Of The Envelope-Rechnung ist

Das Mississippi-Problem

Frage: "Wieviel Wasser fließt pro Tag aus dem Mississippi in das Meer?"
Antwort: ("Hey, woher soll ich das denn wissen???")

Bei diesem Problem könnte man vielleicht auf drei verschiedene Arten zu einer brauchbaren Lösung gelangen:

Lösung 1: "Mal sehen..." (der direkte Zugang)
Durch Abschätzen kommt man auf Folgendes:
Breite der Mündung: etwa 1 Meile
Tiefe der Mündung: etwa 20 Fuß, also etwa ¹/₂₅₀ Meile
Fließgeschwindigkeit: etwa 120 Meilen/Tag
Daraus errechnet sich leicht die Antwort:
1 Meile * ¹/₂₅₀ Meile * 120 Meilen/Tag = ¹/₂ Meile³/Tag!

Lösung 2: "Genauso viel wie reinfließt!"
Abschätzen liefert:
Größe des Mississippi-Basin: etwa 1000 x 1000 Meilen
Regenmenge: etwa 1 Fuß/Jahr, also etwa ¹/₅₀₀₀ Meile/Jahr
Daraus errechnet sich leicht die Antwort:
1000 Meilen * 1000 Meilen * ¹/₅₀₀₀ Meile = 200 Meilen³/Tag
200 Meilen³/Tag ÷ 400 Tage/Jahr = ¹/₂ Meile³/Tag!

Lösung 3: "Hier steht drin..." (für Perfektionisten)
Aus einem Almanach z.B. erfährt man:
Wasserausfluss: 640.000 Fuß³/Sekunde
Rechnung:
640.000 Fuß³/Sekunde * 86.400 Sekunden/Tag = 6*10¹⁰ Fuß³/Tag
6*10¹⁰ Fuß³/Tag ÷ (5000 Fuß/Meile)³ = 60*10⁹ Fuß³/Tag ÷ 125*10⁹ Fuß³/Meile³
= ⁶⁰/₁₂₅ Meile³/Tag = ¹/₂ Meile³/Tag! 

Nützliche Daumenregeln

Hier werden kurz ein paar Daumenregeln behandelt, die den Umgang mit Back Of The Envelope-Kalkulationen vereinfachen.

Die Dimensionen müssen passen!

Das Beispiel des Mississippi-Problems veranschaulicht folgende Regeln (ohne Anspruch auf Vollständigkeit) für den Umgang mit Dimensionen, die zudem recht intuitiv sind:

• addiert (und subtrahiert) werden können nur gleiche Einheiten, z.B. "2 Meilen + 3 Meilen = 5 Meilen", nicht aber z.B. "1 Meile + 1 Tag" (dies macht ja auch gar keinen Sinn...)

• das Ergebnis der Rechnung muss eine sinnvolle Einheit haben (z.B. ist ¹/₂ Meile³/Tag eine Volumenmenge pro Zeit, also sinnvoll, um den Ausfluss anzugeben

• wenn das Ergebnis eine sinnvolle Einheit hat, kann man davon ausgehen, dass die Idee, die der Rechnung zugrunde liegt, korrekt ist und ein sinnvolles Ergebnis liefert

oder "Modulo 9-Regel":
Diese Regel besagt, dass das Ergebnis mod 9 einer schriftlichen Addition gleich dem Ergebnis der Ziffernaddition mod 9 ist.

Beispiel:   3142 -> 3+1=4 +4=8 +2=10 mod 9 =1
            2718 -> 2+7=9 mod 9 =0 +1=1 +8=9 mod 9 =0
           +1123 -> 1+1=2 +2=4 +3=7; Gesamtsumme: 1+0+7=8
            6973 -> 6+9=15 mod 9 =6 +7=13 mod 9 =4 +3=7
Wie man sieht, ist das Ergebnis der Ziffernaddition mod 9 der drei Summanden (8)
ungleich dem Ergebnis der Ziffernaddition mod 9 des Ergebnis (7).
Also ist das Ergebis falsch! (vorausgesetzt, die mod 9-Rechnungen sind korrekt...)

72er-Regel / Verdopplungsregel

Diese Regel besagt einfach, dass sich eine Menge M verdoppelt, wenn die Vermehrungsrate r multipliziert mit der Zeit t den Wert 72 ergibt.

Beispiele: 1000 DM verdoppeln sich bei 6% p.a. nach 12 Jahren zu 2012 DM, 6*12=72!
           Eine Bakterienkolonie, die 3% pro Stunde wächst, verdoppelt sich pro Tag, 3*24=72!

10 Verdopplungen sind ein Faktor von 1.000, 20 Verdopplungen ein Faktor von 1.000.000! (denn 2¹⁰=1024 usw...)

"Pi Sekunden sind ein Nano-Jahrhundert"!

Genaugenommen hat ein Jahr 3,155*10⁷ Sekunden. Das sind ungefähr Pi*10⁷ Sekunden; die Abweichung ist kleiner als ein halbes Prozent. Andere Formulierung:

"Pi mal 10 Millionen Sekunden sind ein Jahr."

Sicherheitsfaktoren

Sicherheitsfaktoren sind ein Mittel zur einfachen Berücksichtigung des worst case bei der Laufzeitabschätzung. Evtl. kennt man zwar das mögliche Laufzeitintervall einer Systemkomponenten, nicht jedoch, wann welche Laufzeit auftritt. Man nimmt also den schlimmsten Fall an und sorgt dann dafür, dass das System auch im schlimmsten Fall immer reibungslos funktioniert. Dann ist man auf der sicheren Seite.

Nehmen wir als Beispiel Dateizugriffe:
Als Programmierer weiß man vielleicht, wie schnell ein Dateizugriff auf dem eigenen System ist, auf dem man entwickelt. Hier betrachtet man schon den schlimmsten Fall bei der Dauer eines Dateizugriffes. Weiterhin muss man davon ausgehen, dass nicht sämtliche Systeme, auf denen das entwickelte Programm später einmal läuft, mindestens so schnell sind wie das eigene. Also nimmt man noch einen Sicherheitsfaktor von vielleicht 3-6 hinzu und stellt damit sicher, dass das Programm auf den allermeisten Systemen läuft.

Auf ähnliche Weise sollte man z.B. davon ausgehen, dass ein 100MBit-Ethernet höchstens 80% oder auch nur 50% Durchsatz hat, also höchstens 9 MByte/Sekunde fließen.

Little's Law

Little's Law ist eine Bezeichnung für eine einfache Gesetzmäßigkeit, die für dynamische Systeme gilt, bei denen es einen Zufluss und Abfluss von Objekten in und aus dem System gibt und bei denen sich zu einem Zeitpunkt eine bestimmte Zahl von Objekten im System befinden. Dieses Gesetz ist universell anwendbar, wie die folgenden Beispiele zeigen werden.

		<N> = D * <T>

<N>: mittlere Zahl von Objekten in einem System
  D: Durchsatz (Zufluss oder Abfluss)
<T>: mittlere Verweildauer eines Objektes

Beispiele:

• Man betrachte ein Multi-User-System: Das System verarbeitet pro Zeiteinheit 3 Anfragen. Es befinden sich momentan 12 Anfragen in der Queue. Daraus folgt: Die Antwort auf eine neue Anfrage wird nach etwa 4 Zeiteinheit geliefert.
• Buffer Underrun beim CD-Brenner: Pro Sekunde werden 172 kByte (bei einfacher Geschwindigkeit) gebrannt. Ein Puffer von 1 MByte "hält" also bei 8facher Brenngeschwindigkeit nur eine ³/₄ Sekunde!
• Einkauf bei ALDI ;-) Alle zwei Minuten wird ein neuer Kunde abgefertigt; vor mir stehen noch 5 Kunden, ich muss also etwa 10 Minuten warten...

Aufgabe

Am Ende des Vortrags wurde folgende Aufgabe gestellt:

"Bis zu welcher Distanz ist ein Fahrradkurier schneller als eine Rechnerverbindung über ISDN?"

Für eine sinnvolle Lösung dieser Aufgabe muss man natürlich einige (plausible) Annahmen machen:

Wir nehmen an, die Übertragungsgeschwindigkeit der ISDN-Leitung sei 128.000 kBps. Es soll eine Datenmenge von 200 MB übertragen werden. ISDN schafft dies im Idealfall in 13.108 Sekunden, das sind gut 3½ Stunden. In dieser Zeit kommt ein Fahradkurier mit den 200 MB auf einer CDROM bei 10 km/h etwa 35 km weit! Ist die Entfernung der beiden Rechner also wesentlich geringer, ist der Fahrradkurier deutlich schneller!

zurück zum Anfang