Die Sache mit den Gigaflops

Da ich gerade in loser Reihe mich mit den Supercomputern von Cray beschäftige und dann in der letzten ct‘ noch der Artikel „Matrix reloaded“ erschien möchte ich an dieser Stelle mal was zu der realen und theortischen Geschwindigkeit auf sich hat. Bei Supercomputern aber auch Großrechnern hat sich da die Angabe der Fließkommaoperationen pro Sekunde eingebürgert. Früher meist Megaflops, heute pro Prozessor Gigaflops und pro Rechner können es schon Teraflops sein. Das Maß ist auch für den Laien gut verständlich: Ein „FLOP“ so die Abkürzung ist eine Rechnung pro Sekunde, entspricht also im täglichen Leben einem Druck auf die Taschenrechnertasten + – * / oder einer längeren Anstrengung des Kopfes. Das F steht für Fließkommazahlen, denn es gibt auch die Ganzzahlrechnungen, die man zweckentfremden zur Festpunktarithmetrik nutzen kann. So wird aus einer 20 Stelligen Ganzzahl eben dann eine 16 Stellige mit 4 Stellen hinter dem Komma. Nachteil dieses Verfahrens ist, dass man nicht sehr große oder sehr kleine Zahlen verarbeiten kann. Bei allen Rechnern wird die Geschwindigkeit in FLOPS leicht angegeben: Wie viele dieser, kann man maximal zu einem Zeitpunkt ausführen. Als Beispiel greife ich auf eine Cray 1 zurück, weil es bei der noch sehr einfach war und es keine Caches oder andere Features gab die das Ergebnis verfälschen. Die Cray 1 konnte in Vektoroperationen gleichzeitig eine Addition und Multiplikation durchführen und erreichte so 2 Flops pro Takt. Das war bei 80 Millionen Takten pro Sekunde dann 160 MFlops. Doch das Beispiel zeigt auch schon wo der Hase im Pfeffer ist. Denn es gilt nur für Vektoroperationen, sprich dass man für ganze Felder von Zahlen die gleiche Operation durchführt. In FORTRAN wäre das bei diesem Codebeispiel der Fall:

COMMON A(64),B(64),C(64),D(64)
    DO10,I=1,64
    D(I)=A(I)*B(I)+C(I)
10CONTINUE

Dieses Beispiel ist in FORTAN, weil Cray Research einen FORTRAN Compiler mit „Autovektorisierer“ bereitstellte, der bei solchen Schleifen die Vektoroperationen automatisch durchführte. In diesem Falle werden die Daten in die Vektorregister geladen, die Multiplikation läuft mit A(1) und B(1) an und im nächsten Takt kommt dann die Addition von C(1) und dem Ergebnis hinzu während parallel A(2= * B(2) berechnet wird. Für i=2 bis 63 arbeiten so beide Recheneinheiten parallel. Diese Technik nennt man Chaining. Das ist aber nicht die reale Geschwindigkeit dieses Benchmarks. Denn zum einen haben die Operationen eine Vorlaufzeit: Sie müssen dekodiert und die Ausgangswerte an die Funktionseinheiten übergeben werden. Die letzte Operation hat auch noch eine Nachlaufzeit in der das letzte Ergebnis ins Zielregister geschrieben wird. Dies addiert 5 Takte bei der Addition und 6 bei der Multiplikation. Für 64 werte (das Maximum was die Register fassen) braucht man so 70 Takte. Doch die werte müssen erst in das Register kommen und vom Register die Ergebnisse auch wieder in den Hauptspeicher kommen. Das Laden eines Vektorregisters dauert 81 Takte. Hier haben wir 4 Lade- und einen Speichervorgang, dass addiert, wenn man die Zahlen nicht für andere Operationen braucht 5 x 81 Takte. Dagegen entfallen auf die Schleife keine weiteren Operationen, denn die wird beim Vektorisieren gar nicht ausgeführt. Es muss aber in einem Befehl noch angegeben werden wie viele Vektoroperationen durchgeführt werden, das addiert noch ein paar Takte. Im Worst Case würden die 128 Flop hier also 480 Takte brauchen, das wären dann nur noch 21,3 MFlops.

So was beobachtet man auch in Wirklichkeit. Im Livermoore Forschungslabor hat man genau untersucht, wie schnell die Rechner sind und hat aus existierenden Programmen zwischen 6 und 73 MFlops herausgebracht. Das obige Beispiel ergab in Übereinstimmung mit den theoretischen Werten 22 MFLOP. Der LINPACK Benchmark der heute Standard für Tests ist ergab bei n=300 rund 34 MFLOPs. Noch schlechter sieht es aus, wenn nicht Vektoroperationen durchgeführt werden, sondern einzelne Zahlen also keine ganzen Arrays bearbeitet werden. Dann braucht eine Cray 1 rund sechsmal so lange, auch ist ein Skalarregister erst in 14 Takten geladen. Es handelt sich also um eine typische Peakperformanceangabe. Nun ein Sprung zu heute. Im obigen Artikel stellte Andreas Stiller einen Laufzeitunterschied in einem Benchmark vom Faktor 1000 fest – da ist die Geschwindigkeitseinbuße der Cray 1 oben vom Faktor 10 doch ein Pappenstiel. Dabei handelte es sich nicht um einen Uralt-Compiler verglichen mit dem neuesten Exemplar, sondern um den aktuellen von Visual Studio mit Intels C++ Compiler. Kernstück ist folgendes Codestück, dem obigen Forttran Code recht ähnliches:

#define DIM 1024
typedefdouble mat[DIM][DIM];

mat a,b,c;

void clear()

{
   for (int i=0; i < DIM; i++)
   for (int j=0; j < DIM; j++)
   {
	c[i][j] = 0.0;
	b[i][j] = i*1.2;
	a[i][j] = j*1.1;
   }
}



int _tmain(int argc, _TCHAR* argv[])
{
   clear();
   for (int k=0; k < DIM; k++)
   for (int j=0; j < DIM; j++)
   for (int i=0; i < DIM; i++)
   {
	c[i][j]+= a[i][k] * b[k][j];
   }

Nur vom letzte Teil nach Clear (der Initialisierung) wird für die GFLOP Berechnung benutzt und auf einem schnellen iCore i7-4750 HQ Prozessor (3,2 GHz, 4 Kerne, Hyperthreading) kam beim Microsoft Compiler 0,126 GFlops und beim Intel Compiler 138 GFlops – als Extremwerte. Diese eine Zeile in drei Schleifen hat es in sich. Bei den Compilern, die verwendet wurden, ist die Schleifenanordnung k-j-i so angelegt, dass sie die optimale Anordnung der Compiler für die Arrayelemente umgeht. Diese legen die Elemente einer Spalte hintereinander an, die innerste Schleife läuft bei zwei der drei Matrizen aber über die Zeilen. Dadurch sind Caches weitgehend unwirksam. Der Hauptspeicher ist aber um Längen langsamer als die Caches. Ändert man die Reihenfolge auf i-j-k ab, so steigt die Performance von 0,126 auf 3,2 GFLOPS. Das ist übrigens compilerabhängig, denn bei meinem Borland war eine andere Reihenfolge die schnellste.

Das ist die Performance pro Kern mit skalaren Operationen. Nun gibt es die Erweiterung AVX2. Die kann vier Werte gleichzeitig bearbeiten. Das ergibt die vierfache Performance. Beim „Autovektorisieren“ ist mit Microsofts Compiler aber nur eine Steigerung um 25 bis 50% drin. Über einen Compilerschalter nutzt der Compiler alle vier Prozessoren ohne das der Programmierer seinen Code ändern muss ihn z.b. in parallellaufende Threads aufteilt. Beim Microsofts Compiler kommt man so auf maximal 28,9 GFLOPS, bei Intel sogar auf 62 GFLOPS. Der Prozessor hat vier Kerne die sogar 8 Threads parallel verarbeiten können. Das letzte ist dann noch die Benutzung des Fused AddMultiply Befehls, der in einem Rutsch die Multiplikation und Addition durchführt und so die Performance nochmals verdoppelt. Den Maximalwert von 138 GFlops erhielt man durch den Aufruf einer Bibliotheksfunktion für Matrixmultiplikation welche alle Tricks implementierte, also nicht mit eigenem Code. Theoretisch sollte der Prozessor 204,8 GFLOP erreichen. Der Artikel ist lesenswert, auch weil er zeigt, das viele Compilerflags nicht den Code schneller achten und schon kleine Änderungen an vorgeschlagenen Geschwindigkeitsoptimierungen die Performance wieder ins Bodenlose fallen lassen Und das alles bei einer Programmzeile, in drei einfachen Schleifen. Man kann sich dann mal vorstellen, was dann erst passiert wenn der Code etwas komplexer ist. Man wird wohl nicht erwarten dass Programmierer füpr jede Codezeile im kopf haben wie man sie am besten formuliert, damit der Compiler den schnellsten Code erzeugt Es verwundert daher nicht wenn man im Supercomputerbereich das uralte FORTRAN nimmt, bei denen man nicht so vieles einstellen kann, viel weniger Optionen bei der Variablendeklaration und Parameterübergabe gibt. Weiterhin gibt es für die Supercomputer oft auch FORTRAN Compiler mit proprietären Erweiterungen um die Parallelisierung zu unterstützen.

Der Endverbraucher hat vond en Optimierungen nichts. erst rechts nichts von Erweiterungen wie AVX, die im obigen Beispiel erst den Perfromanceboost um den Faktor 4-7 brachte. Denn damit würde der Code dann nicht mehr unter älteren Rechnern oder neuen CPU ohne dieses Features (Celerons oder Atoms) laufen. Softwarehersteller verzichten daher darauf. Die sehr schlechten Fähigkeiten von Compilern schnellen Code zu erzeugen führten auch zum Aus von zwei Intel Prozessoren: dem i860 und Itanium. Beide setzten die VLIW Technologie ein, bei der der Compiler befehle so umgruppiert, dass sie unabhängig voneinander ausgeführt werden können und so alle Recheneinheiten optimal auslasten. Das war jedoch nur selten der Fall. Aus dieser Sicht wäre es am besten man würde zurückgehen zu einem einfachen Instruktionssatz, vielen Registern, damit man bei den vielen heutigen kurzen Funktionsaufrufen möglichst viele Parametern in den Registern halten kann und dann vielleicht mehr Kernen die parallel arbeiten können. RISC ist nichts neues, es gab schon immer Rechner mit einfachen Instruktionen ohne Spezialregister und ohne Spezialbefehle. Aber der Begriff kam erst in den Achtzigern auf, als eine Auswertung von Compilercode zeigte, das bei den üblichen CISC Architekturen die Compiler 80% des Codes mit 20% der Befehle erzeugten. Die vielen Spezialbefehle (die restlichen 80%) wurden also selten benutzt und so sollte RISC Code Compiler freundlich sein. Leider konnte sich keine RISC Architektur auf lange Zeit gegen Intels Marktmacht durchsetzen – wenn man Stückzahlen im dreistelligen Millionenbereich hat, dann kann man sich komplexere Architekturen leisten die aufwendiger zu Produzieren sind, weil man über die Stückzahl die Investitionen in die Herstellung wieder hereinbekommt und Chip Herstellung ist eben im Prinzip wie Zeitung drucken – hat man einmal die Vorlage erstellt so (bei Chips: den Fertigungsprozess im Griff) so ist es egal ob man einen 8 Bit Mikrocontroller produziert oder einen 32 Bit Atom, nur die jeweils neueste Technologie die den teuersten Chips vorbehalten ist kostet mehr.