Durch Benutzung des CONVEX performance analyzer cxpa bin ich darauf gestoßen, daß in meinem Simulationsprogramm die meiste Rechenzeit für ein Unterprogramm benötigt wird, in dem ein lineares Gleichungssystem mit dem Gauß'schen Eliminationsverfahren gelöst wird (s.vorherigen Artikel).
Ich verwende dabei ein selbst geschriebenes Programm gauss, das für beliebige Systeme gemacht ist, aber immer nur für 3x3-Systeme gebraucht wird (Source-Code des Unterprogramms s.u.).
Überraschend war nun die Beobachtung, daß mein Programm auf hydra deutlich schneller läuft, wenn ich den HP-Fortran-Compiler mit Optimierung -O verwende statt des Convex-Fortran-Compilers fc mit der Optimierung -O2.
Deshalb haben wir (Peter Junglas und ich) eine kleine Testumgebung geschrieben, die 1.000.000 mal das Unterprogramm aufruft, und haben dann die CPU-Zeiten gemessen. Dabei ergaben sich folgende Ergebnisse:
auf hydra mit subroutine gauss:
fc, -O0: | |
real | 14.3 |
user | 12.7 |
sys | 0.4 |
fc, -O1: | |
real | 0m7.98s |
user | 0m6.68s |
sys 0m0.22s | |
fc, -O2: | |
real | 0m24.53s |
user | 0m23.21s |
sys | 0m0.20s |
Man sieht an der User-Zeit, daß die O2-Optimierung keineswegs den schnellsten Code liefert.
Zum Vergleich gibt's auf hydra aber ja noch den Application-Compiler apc und den HP-Compiler fort77:
apc, -O2: | |
real | 0m20.60s |
user | 0m19.31s |
sys | 0m0.20s |
fort77, -O: | |
real | 0m7.26s |
user | 0m6.11s |
sys | 0m0.23s |
Der HP-Compiler ist also immer noch einen Tick schneller als der Convex-Compiler mit -O1, aber immerhin. Nun lag's natürlich nahe, auch mal zu schauen, wie lange denn ein Rechner des HP-Clusters für das Testbeispiel benötigt:
auf HP-CLUSTER mit subroutine gauss:
f77, -O: | |||
6.13u | 0.05s | 0:08.31 | 74.3% |
6.13u gegen 0m6.11s, Convex und HP-Cluster sind also tatsächlich gleich schnell, wenn man auf der Convex den HP-Compiler verwendet - und wenn das Problem vollständig in den Cache paßt!
Schließlich gab's noch den Versuch, das selbst geschriebene Unterprogramm durch den Aufruf der veclib-Routinen dgefa und dgesl zu ersetzen:
auf hydra mit veclib (dgefa, dgesl):
fc, -O2 | |
real | 2:25.1 |
user | 2:23.9 |
sys | 0.7 |
auf HP-CLUSTER mit veclib (dgefa, dgesl):
229.86u | 0.08s | 5:15.63 | 72.8% |
Hier schneidet also der HP-Cluster deutlich schlechter ab als die Convex - allerdings sind beide Ergebnisse unakzeptabel im Vergleich zu der selbstgeschriebenen Routine. Dieses schlechte Resultat ist darauf zurückzuführen, daß die Veclib-Routinen auf der hydra parallelisiert sind, was bei großen Matrizen auch zu großen Beschleunigungen führen kann, aber bei N=3 vor allem einen riesigen Overhead erzeugt.
Um nun den großen Zeitunterschied zwischen -O1 und -O2 in diesem Beispiel zu verstehen, muß man sich den Optimierungsreport ansehen, der bei Optimierungen mit -O2 standardmäßig ausgegeben wird:
Optimization for GAUSS
Line | Id | Iter. | Reordering | New | Optimizing / Special |
Num. | Num. | Var. | Transformation | Loops | Transformation |
16 | 1 | I | *Dist | (2-3) | No Strip |
16-1 | 2 | I | *Interchange | (4) | (I J) -> (J I) |
17-1 | 4 | J | Serial | ||
16 | 5 | I | Serial | Unroll | |
16-2 | 3 | I | Serial | Unroll | |
23 | 6 | I | Serial | ||
28 | 7 | J | Serial | Unroll | |
38 | 8 | J | Serial | Unroll | |
46 | 9 | J | *Dist | (10-11) | StripMine |
46-1 | 10 | J | Serial | StripMine Unroll | |
46-2 | 11 | J | *Interchange | (12) | (J J K) -> (J K J) |
StripMine Blocked | |||||
46 | 12 | J | Serial | StripMine Unroll | |
48-2 | 13 | K | Serial | ||
57 | 14 | I | Serial | ||
59 | 15 | J | Serial | Unroll |
Line | Id | Iter. | Analysis |
Num. | Num. | Var. | |
46 | 12 | J | Loop blocked by 160 iterations |
16-2 | 3 | I | Replicated: partially unrolled with factor of 6 |
16 | 5 | I | Replicated: partially unrolled with factor of 6 |
23 | 6 | I | Inner loop has varying trip count |
28 | 7 | J | Replicated: partially unrolled with factor of 6 |
38 | 8 | J | Replicated: partially unrolled with factor of 6 |
46-1 | 10 | J | Replicated: partially unrolled with factor of 5 |
46 | 12 | J | Replicated: partially unrolled with factor of 6 |
57 | 14 | I | Inner loop has varying trip count |
59 | 15 | J | Replicated: partially unrolled with factor of 4 |
Man sieht, der Compiler hat eine Menge aus unseren Loops gemacht. Wir wollen jetzt nicht in die Details gehen , sondern nur zwei Basis-Optimierungen kurz ansprechen, die hier verwendet wurden: das Loop-Unrolling und das Loop-Blocking.
Beim Unrolling wird der Body einer Schleife mehrfach wiederholt und die Schleifenparameter entsprechend angepaßt. Dadurch können Register und Instruktionsreihenfolgen optimiert werden, allerdings wird auch ein - normalerweise geringer - Overhead erzeugt. In unserem Fall allerdings werden Schleifen um Faktoren 4 - 6 entrollt, die selbst nur 3 Iterationen beinhalten!
Das Loop-Blocking zerlegt eine große Schleife in eine äußere Schleife über Blöcke - hier der Größe 160 - und eine innere Schleife, die jeweils einen Block bearbeitet. Damit soll bei großen Matrizen der Cache besser ausgenutzt werden. Man kann sich aber vielleicht vorstellen, was für ein riesiger Overhead entsteht, wenn man eine Schleife mit drei Iterationen solcherart zerlegt.
Zusätzlich zu diesem durch ungünstige Optimierung entstandenen Overhead kam noch der Effekt eines speziellen Bugs hinzu: Bei -O1 wird eine sehr trickreiche Optimierung eingesetzt, die man bei -O2 nicht mehr verwendet. Dies macht sich normalerweise nicht bemerkbar, weil sie nur den normalerweise als Overhead betrachteten Anteil zerhackter Schleifen betrifft. Aber in unserem Fall bestehen die Schleifen nach der Optimierung ja nur noch aus ``Overhead''! Dieses Verhalten wurde inzwischen als Compiler-Bug an Convex gemeldet.
Was soll man nun tun? Nicht auf höhere Optimierungen verzichten, sondern auf jeden Fall Laufzeiten vergleichen, wenn man optimiert. Und bei seinen Tests daran denken, daß sich bei verschieden großen Problemen ein völlig verschiedenes Verhalten ergeben kann. Dies und die generelle Nützlichkeit von -O2 zeigt zum Abschluß die folgende Tabelle:
n | Zeit(-O1) | Zeit(-O2) |
in s | in s | |
3 | 7.39 | 25.29 |
30 | 9.23 | 13.12 |
300 | 114.79 | 59.28 |
3000 | 8932.01 | 3405.99 |