Mittwoch, 18. Mai 2011

Mathematiker: Das Ende der Nahrungskette?

Da werden sich die Leser wundern: Mathematiker, Herrscherinnen des Wissenschaftskosmos, Könige der Abstraktion, Heldinnen der Grundlagenforschung irgendetwas anderem Unteran als den eigenen Launen oder dem Drittmittelgeber? Ich weiß, ich weiß, man mag es kaum glauben.

Und streng genommen stimmt es auch nicht, da des bedauerlichen Umstandes von dem ich schreiben möchte, wohl nur die Numeriker etwas wissen, während die Zahlentheoretiker im obersten Stock des Elfenbeinturms einfach nie aus dem Fenster schauen. Es geht um Hardware. Die numerische Mathematik bedient sich Computer, um mathematische Probleme zu lösen. Dabei sind auch beachtliche Erfolge erzielt worden. Hardwaremässig wurde seit 1950 eine Beschleunigung um einen Faktor von 10^9 erzielt (gemeint sind ähnliche Investitionskosten). Dazu kommen für mathematische Probleme noch die Verbesserungen der zugrundeliegenden numerischen Verfahren, was für viele relevante Problemklassen ein Faktorvon 10^5 bis 10^7 ist. Die beiden Sachen multiplizieren sich und so kann ich die Laplace-Gleichung heute 10^16 mal schneller lösen als früher oder, was heute eine Sekunde braucht, hätte 1950 300 Millionen Jahre gebraucht.

Die Hardwareverbesserung wird empirisch durch Moore's Law beschrieben. Und dies kommt nun an eine physikalische Grenze, weil die Dimensionen, auf denen gearbeitet wird, Molekülbreite erreichen. Und auch wenn Intel derzeit einige Stunts macht, wird es keine 20 Jahre mehr dauern, bis die Verbesserungen einzelner Mikroprozessoren das Ende der Fahnenstange erreicht haben. Das wissen natürlich auch die Hardwarehersteller und deswegen gibt es den Trend zur Parallelisierung, also verschiedene Prozessoren in derselben Maschine zu haben, die beispielsweise einen gemeinsamen Arbeitsspeicher haben. Im Supercomputingbereich ist das nichts neues, sondern ganz normal. Auf dem PC-Markt ist das mittlerweile angekommen, jeder Computer den man heutzutage kauft, hat einen Multicore-Prozessor.


NVidia-GeForce-GPU. Wir hams immer gewusst:
Computerspiele führen zu nix gutem!
Bild: Tors via Wikimedia Commons

Neu ist dagegen der Trend, im Scientific Computing Grafikprozessoren (GPUs für Graphical Processor Units) zu nutzen. Und zwar hat sich dank der vielen fleissigen Computerspieler ein riesiger Bedarf nach Grafikhardware entwickelt. Denn was macht Standard-Computergrafik-Software? Sie rechnet aus, ob Teile der Spielfigur vielleicht gerade in einer Wand stecken, sie rechnet aus, was der Spieler jetzt gerade sehen kann und berechnet die entsprechende Grafik, alles basierend auf analytischer Geometrie. Vielleicht löst sie nebenbei noch die Flachwassergleichungen, weil bei denen nettaussehende Oberfächenwellen rauskommen, vor denen sich Spielerinnen versonnen den berechneten Sonnenuntergang betrachten können. Anders gesagt: Im Gegensatz zu einer CPU ist eine GPU für einen einzigen Zweck konzeptioniert: Numbercrunching. Oder nochmal anders gesagt: Für Numerik.

Das wurde Numerikern klar, sie probierten ihre Verfahren auf GPUs auf und berichteten von atemberaubenden Beschleunigungsfaktoren von 1000. Und durch den wachsenden Markt im Bereich der numerischen Strömungsmechanik wurde Nvidia klar, dass sie ihr Geld nicht nur von Computerspielern beziehen müssen, sondern dass da ein komplett neuer Kundenkreis wartet. Und als Nebenbemerkung: Der Gründer und Geschäftsführer Jen-Hsun Huang ist Stanford-Absolvent und aufgrund einer großzügigen Spende ist das neue Ingenieurwissenschaften-Gebäude, in dem auch mein Institut sitzt, nach ihm benannt. Und eines Tages Ende 2010 stand er vor der Tür des Instituts, betrachtete das beschreibende Poster, sagte "Das ist genau das, was ich unterstützen will" und spendete einen GPU-Cluster.

Wie auch immer, Tatsache ist, dass die Beschleunigungsfaktoren von 1000 nur auf zwei Dingen beruhen: Einem Vergleich von Äpfeln und Birnen und dem Nutzen schlechter Codes, die nie für die CPU optimiert wurden. Schaut man genauer hin, was vergleichbare CPUs und GPUs leisten, kommt man auf einen Faktor von 5, wobei die GPU mehr kostet und auch mehr Strom verbraucht. Auch das ist aber nicht der Punkt, an dem Mathematiker wie ich anfangen, doof zu gucken.

Der Punkt ist: Eine handelsübliche CPU ist inhärent sequentiell, es wird also brav ein Befehl nach dem anderen abgearbeitet, in Spezialfällen können die CPUs zwei Dinge gleichzeitig erledigen. Eine GPU ist dagegen inhärent parallel, die macht so genanntes Multithreading und macht einfach mal 1000 Multiplikationen parallel. Und da fangen die Konsequenzen für den Mathematiker an.

Nehmen wir an, ich habe ein Verfahren, bei dem ich warten muss, bis ein Ergebnis da ist, bevor ich das nächste ausrechnen kann. Das klassische Beispiel ist hier das Gauß-Seidel-Verfahren. Dieses liefert näherungsweise Lösungen linearer Gleichungssysteme, indem es mit einer Lösung anfängt, in der ersten Gleichung alle bis auf die erste Unbekannte festhält und dann die erste Unbekannte so wählt, dass die Gleichung stimmt. Dann geht es weiter zur zweiten Gleichung, hält alle Unbekannten bis auf die zweite fest, wobei es für die erste Unbekannte den eben errechneten neuen Wert nimmt und bestimmt die zweite Unbekannte so, dass die zweite Gleichung erfüllt ist. Dadurch ist die erste Gleichung nicht mehr erfüllt! Führt man das bis zur letzten Gleichung durch, hat man einen Näherungsvektor, der unter gewissen Voraussetzungen näher an der Lösung ist als der ursprüngliche. Dieser Zyklus wird nun wiederholt. Klar ist aber: auf der GPU wäre das Verfahren nicht schneller als auf der CPU, weil ich eine Gleichung nach der anderen abarbeiten muss.

Eine Alternative ist das Jacobi-Verfahren. Das macht dasselbe wie Gauß-Seidel, nur werden in jeder Gleichung die Werte der alten Näherung genommen. Dadurch kann ich in jeder Gleichung die neue Iteration gleichzeitig ausrechnen. Wie geschaffen für eine GPU, bzw. im allgemeinem für parallele Rechnungen, im Gegensatz zu Gauß-Seidel.

Und das ist dann das Ende des lamentierens: Elektrotechniker basteln neue Hardware. Informatiker basteln dafür Compiler. Numeriker schauen sich das an, stellen fest dass ihre Verfahren auf der neuen Hardware mit den neuen Compilern nicht mehr funktionieren und fragen sich, ob das die Rache der Informatiker und Elektrotechniker dafür ist, dass sie im Studium Mathe hören mussten.


Und sonst:
Creative Commons Lizenzvertrag
Birchlog von P. Birken steht unter einer Creative Commons Namensnennung-Weitergabe unter gleichen Bedingungen 3.0 Deutschland Lizenz.
Beruht auf einem Inhalt unter birchlog.blogspot.com.