[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ >]
Bei einer Vielzahl von Technischen Problemen besteht die Notwendigkeit, mehr oder weniger umfangreiche numerische Aufgaben zu lösen. Da in der Wirtschaft und Industrie nach dem Grundsatz "Zeit ist Geld" gearbeitet wird, müssen immer neue Techniken entwickelt werden, um die Rechenzeit für sehr große oder oftmals durchzuführende Berechnungen auf ein Mindestmaß zu beschränken. Dabei spielt die Auswahl des Algorithmus sehr oft eine entscheidende Rolle, da nur so die zu bewältigende Arbeitsmenge reduziert werden kann. Jedoch ist nicht nur die Anzahl der erforderlichen Operationen maßgebend, sondern auch die möglichst optimale Auslastung der vorhandenen Hardware. Um dieses Ziel zu erreichen, können numerische Algorithmen natürlich in Assembler geschrieben und manuell für eine spezielle Rechnerarchitektur optimiert werden, jedoch ist dieses Vorgehen zumeist zu arbeitsintensiv und fehleranfällig. Überdies sind solche Programme meist nicht auf andere Hardware portierbar, ohne sie vollkommen neu zu entwickeln. Aus diesem Grund sind hochoptimierende Compiler (für z.B.: FORTRAN oder C) ein unerläßliches Hilfsmittel zur Entwicklung von numerischen Programmen und Software. Bei Einsatz eines optimierenden Compilers sollte auf alle Fälle überprüft werden, ob sich die angewendeten Optimierungen auch wirklich effizienzsteigernd auswirken und die Korrektheit des Programms dadurch nicht beeinträchtigt wurde. Speziell bei aggressivem Optimieren entstehen oft unerwartete Übersetzungsfehler, die zu einem späteren Zeitpunkt nur schwer nachzuvollziehen sind. Zusätzlich ist anzumerken, daß auch bei stark optimierenden Compilern die Effizienz einfacher Algorithmen und Datenstrukturen zu wünschen übrig läßt. Auch gestaltet sich die Messung von Leistungsdaten oft schwierig, da Faktoren wie Daten und Code im Cache enthalten bzw. nicht enthalten oder Scheduling-Strategien nicht simuliert bzw. beeinflußt werden können.
Die meisten der heute verwendeten Computer beziehen ihre Geschwindigkeit nicht nur aus der Steigerung der Taktfrequenz und der Anzahl der Instruktionen, die in jedem Taktzyklus abgearbeitet werden können, sondern basieren vorwiegend auf Parallelismus (durch Superskalararchitekturen, Vektorprozessoren und Pipelining). Um solche Computer möglichst gut auszulasten, muß die Befehlsreihenfolge so umgestellt werden, daß sich zwar das Ergebnis der Berechnungen nicht verändert, jedoch möglichst viele Instruktionen parallel ausgeführt werden können. Wird von der Rechnerarchitektur Pipelining unterstützt, so darf die Befehlspipeline nach Möglichkeit nicht unterbrochen werden, d.h. möglichst wenige Verzweigungen des Programmablaufes, etc., da sonst der Vorteil des Pipelinings nicht ausgenützt werden kann. In einigen Fällen entstehen dadurch sogar Verzögerungen, da das Löschen, Füllen und Verwalten der Befehlspipeline zusätzlichen Aufwand benötigt.
Die Fähigkeit der Compiler, die optimale Reihenfolge zu finden, wird durch eine Anzahl von Faktoren beeinträchtigt. Darunter hauptsächlich Abhängigkeiten der einzelnen Programmteile untereinander. Die einzelnen Abhängigkeiten lassen sich in zwei Gruppen unterteilen: in Datenabhängigkeiten bzw. Steuerabhängigkeiten.
Man spricht von Datenabhängigkeit, wenn zwei Anweisungen beide die selben Daten benötigen, wobei bei mindestens einer der beiden Anweisungen schreibend auf die Daten zugegriffen wird. Steuerabhängigkeiten hingegen entstehen, z.B. durch logische Verzweigungen und Schleifen.
Beispiel (Steuerabhängigkeit):
IF (errsum<=errb) THEN
result = result+area12-aream
END IF
In dieser Sequenz ist die Steuerabhängigkeit dadurch gegeben, daß die Zuweisung eines neuen Wertes an die Variable result nur dann erfolgt, wenn der Ausdruck (errsum<=errb) erfüllt ist.
Beispiel (Steuerabhängigkeit):
DO i = 1, n
a(i) = a(i)+b(i)
END DO
Hier entsteht die Steuerabhängigkeit durch die Abhängigkeit der Zuweisung an a(i) vom Schleifenzähler.
Liegt ein Fall von Datenabhängigkeit vor, so kann man diesen weiter differenzieren (hier sind nur die Abhängigkeiten angegeben, die bei numerischen Programmen eine Rolle spielen):
Die Anweisungssequenz B heißt von A flußabhängig (oder auch echt abhängig) bezüglich einer Variablen v, wenn v in A geschrieben und in B gelesen wird.
Beispiel:
area = area+area12-aream errb = MAX(epsabs, epsrel*ABS(area))
Hier ist die zweite Anweisung von der ersten abhängig, da die Variable area in der ersten Anweisung geschrieben und in der zweiten Anweisung gelesen wird.
Die Anweisungssequenz B heißt von A antiabhängig bezüglich einer Variablen v, wenn v in A gelesen und in B geschrieben wird.
Beispiel:
errb = MAX(epsabs, epsrel*ABS(area)) area = area+area12-aream
Hier können die Operationen der ersten Anweisung zwar gleichzeitig mit den Operationen der zweiten durchgeführt werden, jedoch muß mit der Zuweisung an die Variable area gewartet werden, bis der Wert von area in der ersten Anweisung nicht mehr benötigt wird.
Die Anweisungssequenz B heißt von A ausgabeabhängig bezüglich einer Variablen v, wenn v sowohl in A als auch in B geschrieben wird.
Beispiel:
FOR i = 2, n-1
a(i-1) = 2*b(i)
a(i+1) = c(i)+1
END DO
Hier sind die Iterationen i=k und i=k+2 ausgabeabhängig, da in beiden die Variable a(k+1) geschrieben wird.
Die oben angesprochene Einschränkung optimierender Compiler besteht unter anderem darin, daß überall dort, wo eine Datenabhängigkeit nicht ausgeschlossen werden kann, ebendiese angenommen werden muß. Ist dies nicht der Fall und wird vom Compiler eine "Optimierung" vorgenommen, so führt dies unter Umständen zu einem falschen Ergebnis. Unterprogrammaufrufe und Steuerkonstrukte sind prädestiniert dafür, potentielle Datenabhängigkeiten zu erzeugen.
Beispiel:
x = a/2
IF (c<=0) THEN
a = d+e
ELSE
b = d+e
END IF
Die offensichtliche Antiabhängigkeit zwischen der Zuweisung an die Variable x und dem folgenden IF-Block besteht nur dann, wenn der Wert der Variablen c kleiner oder gleich 0 ist. Kann der Wert von c zur Übersetzungszeit nicht bestimmt werden, so ist nur eine potentielle Abhängigkeit gegeben.
Beispiel:
CALL prozedur (indikator, x) x = y+z
Hier ist die Art der Abhängigkeit unbestimmt, da nicht bekannt ist, in welcher Weise (und ob überhaupt) im Unterprogramm auf die Variable x zugegriffen wird. Dies kann z.B. durch die Variable indikator gesteuert sein.
Da die Prozessoren immer schneller werden, vermindern sich auch die Zugriffszeiten auf die Daten. Um den steigenden Anforderungen gerecht zu werden, ist der verfügbare Speicher in mehrere Ebenen gegliedert, die unterschiedlich schnell sind (z.B. Prozessorregister, Cache-Speicher, RAM, Harddisks, Bandlaufwerke, ...). Oft benötigte Daten sollten sich nach Möglichkeit weit oben in der Hierarchie befinden, da sie dort sehr schnell verfügbar sind (auf Daten in niedrigeren Ebenen kann oft nur mit einer Geschwindigkeit zugegriffen werden, die um einige Zehnerpotenzen langsamer ist). Werden Daten angesprochen, die sich nicht im Cache bzw. im Hauptspeicher befinden, so spricht man von einem Cache-miss bzw. Page-fault. Die Daten müssen dann von einem langsameren Medium geholt werden, was eine enorme Verzögerung mit sich bringt. Das Halten der Daten im Cache bzw. Hauptspeicher gestaltet sich umso schwieriger je verteilter die Zugriffe auf die Daten sind. Man spricht dann von mangelnder Lokalität von Speicherzugriffen. Dies hat einen starken Einfluß auf die Programmleistung, da der Compiler Fakten wie Größe des verfügbaren freien Hauptspeichers, Dimension eines (dynamischen) Feldes, etc. zur Übersetzungszeit nicht kennen kann und daher auch keine Möglichkeit hat, die Zugriffe geeignet zu optimieren. Die automatische Bestimmung von Programmtransformationen, welche die Referenzlokalität verbessern, ist daher derzeit nicht möglich.
Ein weiteres Problem ist ein schlechtes Referenzmuster bei Speicherzugriffen (schlechte Referenzlokalität), d.h. eine oder mehrere Speichereinheiten werden wesentlich stärker belastet als die anderen. Dies tritt insbesondere bei Caches mit blockzyklischen Verfahren zur Abbildung des Hauptspeichers auf: bei dieser Methode wird der Hauptspeicher in lauter gleich große Bereiche aufgeteilt, die dann in zyklischer Weise auf den Cache abgebildet werden. Wird nun eine Speicherzelle angesprochen, die zwar im Speicher in einem anderen Block liegt, aber im Cache der selben Adresse zugeordnet wird, so muß der Cache erst an der entsprechenden Stelle geleert und anschließend der Wert aus dem Hauptspeicher geladen bzw. dorthin geschrieben werden. Dies kann bei ungünstigen Zugriffsmustern sogar zu einer enormen Verschlechterung der Leistung führen.
Beispiel (inneres Produkt):
summe = 0.
DO i = 1, n
summe = summe + a(i*k)*b(i)
END DO
Bei diesem Beispiel wurde die Berechnung für eine große Anzahl von Vektorlängen ausgeführt (10<=n<=4000), wobei die Berechnung mit drei verschiedenen Werten für k durchgeführt wurde (k=1, 32, 50). Dabei ergaben sich folgende Leistungsdaten (auf einer HP-Workstation):
| n = 500 | n = 1000 | n = 1500 | n = 2000 | n = 2500 | n = 3000 | n = 4000 | |
| k = 1 | 80% | 86% | 87% | 88% | 90% | 90% | 90% |
| k = 32 | 64% | 48% | 48% | 48% | 18% | 12% | 8% |
| k = 50 | 52% | 50% | 50% | 30% | 28% | 26% | 24% |
Aus den Leistungsdaten läßt sich ablesen, daß nur bei optimaler Referenzlokalität (k=1) eine gute Gleitpunktleistung erreicht werden kann. Auffallend ist auch, daß die Leistung des Algorithmus bei k=32 (ab n>=2100) geringer ausfällt, als jene mit k=50. Dieser Effekt kann durch das bei k=32 besonders schlechte Referenzmuster bei Speicherzugriffen erklärt werden. Hierzu sei zu bemerken, daß der Cache der HP-Workstation ein einfach assoziativer Cache (direct mapped) mit 256KByte Kapazität und einer Cachezeilen-Länge von 32 Byte. Wird nun nur auf jedes 32. Speicherwort zugegriffen, so reduziert sich die Cachegröße auf 1/32 (=8KByte, =2048 Speicherworte). Aufgrund dieser Tatsache nimmt die Gleitpunktleistung ab einer Vektorlänge von n=2048 stark ab.
Als Overhead werden Programmteile bezeichnet, die nicht direkt zur Ermittlung des Resultats benötigt werden. Es lassen sich zwei Arten von Overhead unterscheiden: mehr oder minder unvermeidbare Operationen, wie z.B. Unterprogrammaufrufe, garbage-collection, Indexberechnungen, etc. und tatsächlich unnötige Operationen.
Die Laufzeit des Overheads kann bei einmaliger Ausführung oftmals vernachlässigt werden, bei mehrmaliger Ausführung (z.B. innerhalb einer Schleife) kann der Aufwand jedoch beträchtliche Ausmaße annehmen. Hier sind insbesondere Unterprogrammaufrufe, Mehrfachberechnungen, logische Verzweigungen und Typumwandelungen relevant. Solche Konstrukte sind innerhalb von Schleifen nur dann zu verwenden, wenn keine andere Möglichkeit (mit weniger Overhead) zum Ziel führt. Der Overhead bei Indexberechnungen in Schleifen kann etwa durch Schleifenaufrollen vermindert werden. Auch Vektorprozessoren ermöglichen oftmals eine Steigerung der Leistung, da Operationen auf ganze Vektoren von Daten gleichzeitig ausgeführt werden können und somit weniger Indexberechnungen, etc. durchgeführt werden müssen. Solche Verfahren eignen sich jedoch nur bedingt, da gegebene Abhängigkeiten berücksichtigt werden müssen und daher viele Operationen nicht parallel ausgeführt werden können.
Beispiel (logische Verzweigungen):
DO i = 1, n
IF (indikator > 0) THEN
a(i) = b(i)
ELSE
a(i) = 0
END IF
END DO
In diesem Beispiel verursacht die logische Verzweigung innerhalb der Schleife beträchtlichen, jedoch vermeidbaren Overhead. Da die Variable indikator innerhalb der Schleife ihren Wert nicht verändert, ist das Ergebnis des logischen Ausdrucks bei allen Durchläufen identisch. Diese n Auswertungen sind daher Overhead. Dem kann entgegengewirkt werden, indem die logische Verzweigung aus der Schleife herausgenommen wird und statdessen zwei Schleifen (für jeden Fall eine) in den THEN- bzw. ELSE-Zweig der logischen Verzweigung eingefügt werden. Das Beispiel liest sich dann in folgender Form:
IF (indikator > 0) THEN
DO i = 1, n
a(i) = b(i)
END DO
ELSE
DO i = 1, n
a(i) = 0
END DO
END IF
Beispiel (logische Verzweigungen):
DO i = 1, n
IF (MOD(i,2) == 0) THEN
a(i) = b(i)
ELSE
a(i) = 0
END IF
END DO
Hier ist leicht zu ersehen, daß das Ergebnis der logischen Auswertung zwar nicht bei jeder Iteration gleich ist, jedoch das Ergebnis für gerade i wahr und für ungerade i falsch ist. Es kann daher eine ähnliche Transformation wie bem vorangegangenen Beispiel angewandt werden:
DO i = 2, n, 2
a(i) = b(i)
END DO
DO i = 1, n, 2
a(i) = 0
END DO
Anstelle der logischen Verzweigung in der Schleife wurden zwei Schleifen ohne logische Verzweigungen eingeführt. In der ersten Schleife werden alle geraden Indizes behandelt, die zweite ist für alle ungeraden Schleifenindizes zuständig. Durch diese Transformation wurde der Overhead beträchtlich vermindert, da (für große n) sehr viele logische Auswertungen und Sprünge eliminiert werden konnten.