[ < ][ Globale Übersicht ][ Kapitelübersicht ][ Stichwortsuche ][ > ]
Dieses Kapitel beschreibt die verschiedenen Möglichkeiten, die Leistung von Software zu messen, um zu erkennen, ob es sinnvoll ist die Software zu optimieren. Da Leistung mit den Komponenten Arbeit und Zeit berechnet wird, kann man Leistung messen, indem man die verrichtete Arbeit durch die benötigte Zeit dividiert.
Die Messung der Arbeit gestaltet sich in den meisten Fällen zu
einem schwierigen, komplexen Unterfangen. Um die verrichtete Arbeit abschätzen
zu können ist zunächst Kenntnis über die Anzahl der Gleitpunktoperationen
erforderlich. Eine genaue Aussage ist bei den meisten Programmen gar nicht
möglich, da sie schon bald sehr komplex werden. Nur besonders einfache
Beispiele aus dem Bereich der linearen Algebra lassen sich auf diese Weise
exakt abzählen.
Ein weiterer Punkt der bei der Messung der Arbeit beachtet werden muß
ist der Speicherbedarf der Arbeit. Eine Analyse des Speicherbedarfs ist
ohne Hilfsmittel sehr ungenau und mühsam. Jedoch stehen unter
UNIX
beispielsweise verschiedene Möglichkeiten zur Verfügung um den
genauen Speicherbedarf der Software zu ermitteln. Mittels der Anweisung
SIZE liefert UNIX den genauen Speicherbedarf des Programms in allen Einzelheiten.
Dazu gehört der Speicherbedarf der Maschineninstruktionen, der Speicherbedarf
der zur Übersetzungszeit bereits initialisierten Daten sowie der nicht
initialisierten Daten. Die Anweisung SIZE vermittelt allerdings einen etwas
verfälschten Eindruck. Bei der Verwendung von statischen Feldern fällt
die Deklaration des Feldes oft als zu hoch aus, um sicher genug zu haben.
In diesem Fall liefert Size einen Wert, der die tatsächliche Arbeit
der Software nicht wiederspiegeln kann.
Für Abschätzung des Verwendeten dynamischen Speichers kann SIZE
nicht mehr verwendet werden. Stattdessen findet das UNIX-Kommando ps Anwendung.
Mit ps werden wiederum verschiedene Speicherdaten erarbeitet. Die momentane
Größe des für den jeweiligen Prozeß allokierten Hauptspeichers
(RSS - Resident Set Size) wird dynamisch gemessen.Dieser Wert ist bei einer
bruchstückhaften Verwendung des Feldes einiges kleiner als der statisch
berechnete Wert. RSS liefert nicht den dynamischen Speicherbedarf sondern
nur die dynamische Größe des allokierten Hauptspeicherbereichs.
Neben der Anzahl der Gleitpunktoperationen und dem Speicherbedarf spielt bei Programmen
die aktiv mit dem sekundären und tertiären Speicher (Festplatte, ..) arbeiten
die Anzahl der Ein/Ausgabeoperationen eine wichtige Rolle in der Messung der
Arbeit. Diese läßt sich mit dem UNIX-Kommando Time sowie mit der UNIX-Shell
csh
und tcsh messen.
Die Messung der Laufzeit eines ganzen Progamms bedeutet im Normalfall
kein Problem. Unter UNIX läßt sich dieser Wert ganz einfach
mit dem Kommando time ermitteln. Um die Laufzeit für einzelne Programmteile
berechnen zu können, ist es dagegen schon nötig dem Programm
Zeitabfragen zuzufügen. In UNIX-Systemen steht dem Benutzer dafür
das vordefinierte C-Unterprogramm times zu Verfügung. Times liefert
einen Wert zurück, der der Prozeßzeit entspricht. Daher wird
times unmittelbar vor und nach dem zu analysierenden Programmteil aufgerufen.
Die Differenz dieser beiden Werte bildet dann die Laufzeit des Programmteils.
Allerdings sind gerade Ergebnisse von Zeitmessungen am Computer mit größter
Vorsicht zu genießen. Durch die verschiedensten Techniken, die angewandt
werden um den Computer zu beschleunigen (Multi-Tasking, Cashe ...) kann
es bei der mehrmaligen Messung des gleichen Programmteils zu großen
Streuungen kommen.
Cashe :
Die eigentliche Vorteile des Cashe-Speichers sind ein echtes
Problem für eine korrekte zuverlässige Zeitmessung. Beim Cashe ist zwischen
zwei Extremfällen zu unterscheiden :
Keine wichtigen Daten im Cashe, bzw. Cashe leer : In diesem Zustand müßte auf den Cashe zumindest im Anfangsstadium des Programms keine Rücksicht genommen werden.
Die wichtigen Daten und Code im Cashe.
Durch den Einfluß, den der Cashe auf die Rechenzeit ausübt, ist es notwendig, daß dem Experimentator der Zustand des Cashe zumindest zu Beginn der Messung bekannt ist.
Translation Lookaside Buffer :
Beim TLB ist wie beim Cashe der Anfangszustand
in Erfahrung zu bringen, da es durch Fehlzugriffe bei sehr große Datenmengen
zu erhöhten Rechenzeiten kommen kann.
Hauptspeicher :
Page faults (Fehlzugriffe auf den Hauptspeicher) sind ein
besonderes Problem für die Zeitmessung, da sie eine dermaßen gravierende Streuung
verursachen, daß die verschiedenen Meßzeiten überhaupt nicht mehr miteinander
vergleichbar sind. Aus diesem Grunde sollte das Auftreten von Page faults während
einer Zeitmessung, durch das Referenzieren aller Daten auf alle Fälle vermieden
werden.
Context-Switches :
Auch Context-Switches, also der Umschaltvorgang der
verschiedenen Tasks beim Multi-Tasking, verursachen eine erhöhte Rechnerzeit
durch die Ausführung der dafür benötigten Routinen und der Abwicklung der
"parallel" ablaufenden Tasks. Um hier eine zusätzliche Streuung zu vermeiden, sollte
man versuchen, andere rechenintensive Tasks zu eliminieren.
Interrupts :
Interrupts verursachen eine Unterbrechung und somit eine Verzögerung
des Programmablaufs. Die Unberechenbarkeit des Auftretens der Interrupts
erschwert dabei das Einkalkulieren dieses Faktors.
Compiler-Optimierung :
Bei der Compiler-Optimierung kann es durch die Wahl der Compileroption zu
starken Schwankungen der Rechenzeit kommen. Aus diesem Grund sollten sowohl
die Wahl des Compilers und der Compileroptionen stets mitdokumentiert werden.
Im Normalfall wird man mit der höchsten Optimierungsstufe arbeiten.
Die Streuung ist kein verläßliches Maß für die Zeitmessung. Zwar kann man bei einer starken Streuung sehr wohl davon ausgehen, daß beeinflussende Faktoren existieren. Eine schwache Streuung gibt allerdings absolut keine Garantie, daß das Meßergebnis korrekt ist.
Da die Auflösung der Prozeßzeit lediglich um die 10 ms beträgt,
kommt es gelegentlich vor, daß die zu messende Laufzeit unter der
Auflösung der Prozeßzeit liegt. Diese Programmteile sind mit
der vorhin angesprochenen Methode nicht meßbar. Eine Möglichkeit
dieses Problem zu lösen wäre, den zu messenden Programmteil in
einer Schleife so oft zu wiederholen, bis die Laufzeit groß genug
für die Auflösung der Prozeßzeit ist. Der Einfluß
des Cache verursacht dabei allerdings eine Verfälschung des Ergebnisses.
Da die gleiche Operation immer wieder wiederholt wird erreicht der Cache
unter Umständen nach wenigen Durchläufen eine optimale Trefferrate,
was die Laufzeit deutlich verkürzt. Diese Ergebnisschwankungen können
nicht durch ermitteln des Mittelwertes behoben werden, da die Auswirkungen
des Cache bei jedem Durchlauf auftreten.
Um nun auch kurze Zeitintervalle korrekt messen zu können, kann die "Real-time"
herangezogen werden. Die Real-Time, also die wirkliche Uhrzeit, hat mit
1 Mikrosekunde eine weit bessere Auflösung als die Systemzeit.
Profiling wird angewandt um jene Programmteile aufzuspüren, die am meisten
Rechenzeit benötigen. Dabei wird das Programm in nicht überlappende Abschnitte
eingeteilt, und die Rechenzeit dieser Abschnitte separat gemessen. In den meisten
Fällen sind diese Abschnitte und die Unterprogramme des Programms identisch,
wodurch der Benutzer die Testergebnisse einfacher auswerten kann.
Wenn aber die Rechenzeitverteilung innerhalb eines Unterprogramms analysiert
werden soll, reicht der Unterprogramm-Profiler (= das Hilfsprogramm, das die
Einteilung vornimmt) nicht mehr aus. In diesem Fall wird das Programm von
einem Basisblock-Profiler in Basisblöcke eingeteilt, d.h. in eine Folge von
Programmanweisungen, die vom Eintritt bis zum Austritt aus dem Abschnitt
genau einmal und in sequentieller Reihenfolge durchlaufen wird.
Unterprogrammprofiler unter UNIX
In den meisten UNIX-Betriebssystemen sind verschiedene Profiler enthalten. Die
am meisten verwendeten sind prof und die Erweiterung dazu gprof.
Bei diesen Profilern wird in regelmäßigen Abständen überprüft welches Unterprogramm
aktiv ist. Durch dieses Stichprobenverfahren kann auf die Rechenzeitverteilung
geschlossen werden. Das ganze Verfahren ist allerdings von einem Zufallsfaktor
abhängig, da nicht bekannt ist, was zwischen den Stichproben vorgeht. Dadurch
muß bei diesem Verfahren mit einer gewissen Ungenauigkeit gerechnet werden.
Weiters muß beachtet werden, daß das Profiling selbst unter Umständen die Rechenzeit und die
Rechenzeitverteilung beeinflußt, da er zum Beispiel den Cashe-Inhalt verändern
kann.
Basisblockprofiler
Bei den Basisblock-Profiler gibt es keine Standardprogramme. Von System zu
System arbeiten die Profiler unterschiedlich. Während tcov von SUN-Systemen
und lprof von UNIX einander noch sehr ähnlich sind, unterscheidet sich pixie
von MIPS-basierenden Systemen, völlig von den vorher genannten.
Pixie geht sogar über ein Basisblock-Profiling hinaus. Es analysiert die
Rechenzeitverteilung auf jede einzelne Programmzeile. Es arbeitet allerdings
unter der Annahme, daß der Cashe immer optimal arbeitet, also daß immer sämtliche
Daten im Cashe enthalten sind. Verzögerungen beim Speicherzugriff werden nicht
berücksichtigt.
Während die Leistung selbst wie oben beschrieben sehr wohl meßbar ist, ist die Analyse des Leistungsverhaltens und die Bestimmung der leistungshemmende Faktoren in vielen Fällen auf Grund fehlender Diagnoseinstrumente nicht möglich. Ähnliche Schwierigkeiten stellen sich bei der Analyse von Speicherzugriffsverzögerungen, die durch eine mangelnde Referenzlokalität verursacht werden können. Diese Problemen stellen die größten Hindernisse bei der Optimierung numerischer Programme dar; und solange keine Diagnoseinstrumente verfügbar sind, ist ein gezieltes Eliminieren der leistungshemmenden Faktoren nicht möglich.
Wenn die Leistung eines numerischen Programms unter den Erwartungen liegt und die Möglichkeit der Anschaffung neuer Hardware nicht akzeptabel ist, müssen leistungssteigernde Veränderungen am Programm durchgeführt werden. Dabei besteht zum Einen die Möglichkeit, das mathematische Modell zu verändern. Diese Aufgabe fällt in den Bereich der Angewandten Mathematik und wird in diesem Buch nicht behandelt. Neben dem mathematischen Modell kann auch der verwendete Algorithmus entweder verbessert oder komplett ausgetauscht werden. Die Methoden zur Optimierung des bestehenden Algorithmus werden nun in den folgenden Kapiteln behandelt.