Ein Compiler hat die Aufgabe eine höhere Programmiersprache in Maschinensprache zu übersetzen. Bei Großrechnern haben kompilierte Programme schon in den Sechzigern die Maschinensprache sukzessive verdrängt. Im PC Bereich war wegen der anfangs langsamen Prozessoren und dem geringen Speicher Assembler noch in den ersten Jahren wichtig, aber heute sicher nicht mehr.
Machen wir einen geschichtlichen Rückblick. Früher hat man auch evaluiert, wie effizient Compiler sind. Die Ergebnisse sind natürlich stark vom Quelltext abhängig. Die NASA hat für die Flugsoftware der Shuttle evaluiert wie schnell HAL als höhere Programmiersprache verglichen mit Assembler war. Und das Ergebnis war damals: 10-20% langsamer. Das Betriebssystem, das zeitkritisch war, wurde daraufhin in Assembler geschrieben, die „Anwendungen“ dann in HAL. Ein ähnliches Ergebnis gab es bei Tests der ersten Versionen von Turbo Pascal. Das ist erfreulich, denn das Programmieren ist doch erheblich leichter in einer Hochsprache.
Ich glaube in den letzten Jahren habe ich kaum noch was davon gelesen das jemand in Assembler programmiert, selbst wenn man nur Inline Code verwendet, also Assembler in eine höhere Programmiersprache einbettet. Die ct‘ hat als SSE eingeführt wurde das „Apfelmännchen“ also das Fractal mal in diesen Befehlen programmiert um zu sehen wie viel schneller es ist. Ich habe mal im ct Archiv gesucht: das letzte Mal war 2008. Damals war der C-Compiler meist schneller als der eingefügte Assembler.
Also alles in Ordnung? Nicht unbedingt. Es gibt zwei grundlegende Probleme für den Compiler
- Er hat keinerlei Kenntnis, wie der Prozessor intern arbeitet
- Das Ausnützen des Befehlssatzes wird immer schwieriger, je mehr Befehle es gibt und desto spezieller sie sind
- Er muss heute Befehle erzeugen, die ihre Daten von mehreren Quelltextzeilen bekommen, also den Bereich in dem er optimiert vergrößern oder es wird schwieriger den richtigen Befehl auswählen.
Es gibt durchaus Indizien, das hier noch einiges zu verbessern ist. Ich habe schon mal den Test der ct‘ der Matrixmultiplikation erwähnt. Der Benchmark ist nun extrem popelig, denn er besteht aus einer Zeile:
c[i][j] += a[i][k] * b[k][j];
Diese wird in drei Schleifen (i,J,k) für Spalten und Zeilen der beiden Matrizen durchlaufen. Nun gibt es einen Befehl, der genau diese Zeile durchführt: FMA – fused Add Multiply. Dieser Befehl kann sogar vier doppelt genaue und acht einfach genaue Zahlen in einem Takt addieren und multiplizieren. Das bedeutet pro Takt sollte er acht bzw. 16 Fließkommaoperationen durchführen, multipliziert man dies mit dem Takt und den acht Threads des Core i7- 4750HQ Prozessors so sind dies 180 GFlops bei 4 Kernen, Hyperthreading sollte weitere 30% erreichen.
Das Ergebnis: Microsofts C-Compiler erreicht 3,2 GFlops, wenn man AVX explizit nutzen will steigert sich das auf 6,5 GFlops – er nutzt aber nur einen Kern. Mit einer Erweiterung die Autoparallisierung nutzt klettert das dann auf 37 GFLOPS. Trotzdem – nur ein Viertel der theoretischen Leistung. Es zeigte sich auch, dass die Ergebnisse extrem sensitiv waren wie der Code aufgebaut war. Führte man die Initialisierung von C in einer vorgezogenen Schleife durch so war die Geschwindigkeit in der Rechenschleife eine andere als wenn dies in der Rechenschleife direkt erfolgte.
Intel als Prozessorhersteller sollte bessere Compiler liefern und sie sind auch besser. Sie kommen 5-8 GFlops bei einem Kern, auf 20 GFLOPS mit AVX Unterstützung und Nutzung aller Kerne, nimmt man die Erweiterung OpenMP hinzu kommt man auf 37 GFLOPS – ein vielfaches der Basisleistung. Doch programmiert man das nicht selbst sondern nutzt eine Bibliotheksfunktion, von der man annehmen kann, dass sie optimal programmiert ist, wahrscheinlich in Assembler, so erreicht man 140 GFLOPs.
Das bedeutet man kann ein und dasselbe Programm extrem beschleunigen und das, obwohl es sich nur um eine Programmzeile handelt. Es dürfte jedem klar sein, dass es nicht für jedes Problem eine Bibliotheksfunktion gibt, das Ergebnis ist also ernüchternd.
Es gibt noch ein zweites Faktum: das waren gescheiterte Prozessoren. 1989 lancierte Intel den i860 Prozessor, genannt „Cray on a Chip“, weil er die Leistung einer Cray 1 erreichte. Allerdings erzeugten Compiler Programme die nur ein Achtel der theoretischen Pearkperformance erreichten. Das lag nicht nur an den Compilern, der Chip galt als schwer zu programmieren und auch Assembler erreichte nur die Hälfte der Maximalleistung, aber immerhin noch viermal schneller als der Compiler.
Das zweite war das Scheitern des Itanienporzessors. Der hatte eine Philosophie die man VLIW nennt – very Long instruction Word. Dieser Ansatz soll zum einen die Abhängigkeit vom dem Speichersystem reduzieren, dass viel langsamer als der Prozessor ist – man überträgt nicht einen Befehl sondern mehrere, die man zu einem Superwort zusammenfasst. Das Konzept gibt es auch bei Signalverarbeitungsprozessoren und die Cyber Star setzte es auch ein. Das zweite ist das heute alle Prozessoren nicht nur mehrere Kerne haben, sondern jeder Kern auch mehrere Recheneinheiten. Während die Kerne aber nach außen hin sichtbar sind, sind es die Funktionseinheiten nicht. Die Prozessoren versuchen mit einigen Tricks diese Einheiten alle auszulasten sogar indem sie die Befehlsreihenfolge verändern. Der Itanium wollte diese aufwendige Logik einsparen und delegierte die Aufgabe an den Compiler. Einige Bits im Superwort enthielten die Informationen welche Befehle parallel ablaufen konnten und welche nicht. So richtig gelang dies nicht, denn die Performance war immer nur mittelmäßig. Folgerichtig stellte Intel auch diese Entwicklung ein.
Die Chancen, dass ein Compiler optimalen Code erzeugt sind um so besser, je weniger Befehle ein Prozessor hat. Untersuchungen von Kompiliertem Code bei den damals üblichen CISC Prozessoren ergab, dass vom gesamten Befehlssatz nur ein Bruchteil sehr häufig benutzt wurde, manche Befehle niemals. Das war damals der Startschuss für RISC – ein kleinerer Befehlssatz sollte schneller ausgeführt werden. Heute arbeiten die x86 und x64 Prozessoren intern auch mit RISC, sie machen einen Zwischenschritt und übersetzen den CISC Code in RISC. das zeigt schon die Problematik. Trotzdem führte Intel mit MMX, SSE 1-4 und AVX 1+2 immer neue Befehle ein, das mit wurde der Befehlssatz noch komplizierter und die Wahrscheinlichkeit, das der Compiler die beste Lösung findet schwindet, zumal er ja nur eine Vorschrift anwendet.
Was ist die Lösung? Nun OpenMP zeigt eine Lösung auf. Bei OpenMP, das bei Microsofts und Intels Compiler die Performance deutlich erhöhte, gibt der Programmierer an was parelellisierbar ist. Offenbar sind diese immer noch schlauer als die Compiler. Das zeigte auch der Code denn mein Compiler erzeugte. Dort wurde ich an eine Optimierung der Core 2 Architektur erinnert. Es handelt sich um den Befehl „Speichere Daten an Adresse X“ gefolgt wenige Befehle später von „Lade Daten von Adresse X“. Für einen Programmierer erscheint diese Sequenz dämlich, denn erst speichere ich einen Wert dann hole ich ihn, stattdessen kann ich ihn gleich in einem Register halten, das ist viel schneller. Obwohl nur vier der acht FPU Register genutzt wurden, fand sich genau diese Kombination im Code in dieser Zeile. Bei der Core 2 Mikroarchitektur hat man diese das Umsortieren der Befehle aufhaltende Kombination erkannt und sie blockiert nicht mehr das Umsortieren.
Das zeigt: Compiler sind heute noch strunz doof. Der Compiler hätte eigentlich so viel wie möglich in den Registern halten müssen denn der Speicherzugriff ist auch noch langsam. Was folgt daraus? Meine persönliche Ansicht nach sollte man das ursprüngliche Ziel von RISC beibehalten. Anstatt das Innenleben der CPU umzumodeln, damit sie das beste aus dem Code herauskitzeln, indem sie spekulative Sprünge vorhersagen, Register umbenennen, Befehle umsortieren oder Zugriffsmuster auf den Speicher vorhersagen sollte man wenige Befehle sehr schnell ausführen und das geht zum einen mit RISC zum andern mit Eingehen auf den Compiler. Beispielsweise übergeben die meisten Compiler Parameter an Funktionen über den Stack – nicht nur fehlerträchtig, sondern auch langsam.
Stattdessen sollte man für jede Routine eigene Register für die Parameterübergabe zur Verfügung stellen, die man als Fenster aus einem größeren Registerfile auswählt. Dieses Konzept des Registerfiles kennen einige RISC Architekturen. Anders als beim Cache kann der Compiler so viel besser kontrollieren wo die Daten gespeichert werden. Das gilt auch für das Laden von Routinen. Der Compiler weriß wie groß ein Unterprogramm ist und könnte es vorrausschauend in den Cache laden lassen. Auch das Konzept des VLIW ist nicht so dumm. Zumindest wäre es möglich in einem Statusbyte oder einigen Bits pro Befehl anzugeben welche Einheit man nutzt. Gleiche Werte erlauben es dem Prozessor zu erkennen: okay diese Befehle hängen voneinander ab. Man kann mit einem Befehl eine Einheit für eine Befehlssequenz reservieren und wieder freigeben.
Das sind nur einige Ideen, aber je mehr ich über Mikroarchitekturen schreibe, derzeit bin ich bei Nehalem, also der drittletzten Architektur die 2008n erschien, desto mehr wird mir klar, dass man eine ganze Menge Aufwand betreibt um im Prozessor die Performance zu steigern, ohne das der Anwender das heute groß mit dem Compiler beeinflussen könnte. Dabei kennt der den Quelltext er kennt Zugriffsmuster und er weiß wo Routinen sind die häufig gebraucht werden und welche wo langsam sind, bzw., welche als nächstes dran kommen (die man schon mal vom Speicher in den Cache geladen werden können). Man sollte also die Zusammenarbeit intensivieren anstatt neue CISD Befehle zu kreieren.
Es gäbe sogar eine noch weitergehende Möglichkeit: die des Profilings. Das gibt es heute als Tools für Entwicklungsstudios, aber es wurde auch bei PC’s eingesetzt die auf dem Alpha Prozessor basierten und für x86 geschriebene Programme als Emulation ausführten: Ein Programm wird zuerst einfach in Maschinensprache übersetzt und vom Anwender normal benutzt. Dabei führt ein mitgeliefertes Modul Buch wie oft welche Routine ausgeführt wird, auf welche Variablen zugegriffen wird etc. Das kann man ausbauen und auch zeitliche Zusammenhänge erkennen (eine Routine wird kurzzeitig sejr oft aufgerufen, dann wieder längere Zeit gar nicht). In einem zweiten Schritt wird das Programm neu übersetzt wobei die Informationen genutzt werden es zu optimieren. Ohne spezielle SIMD Befehle z.B. Variablen in Registern dauerhaft zu halten oder zumindest im Cache, Routinen vorbeugend laden wenn man weiß das sie oft nach anderen aufgerufen werden. Man kann es aber auch nutzen um CISC Befehle wie obigen FMA zu nehmen indem man beim lauf das Zugriffsmuster und die Operationen in einem Array erkennt.
