exp schnell berechnen
-
Ich wurde vor kurzem mal gefragt, ob ich einen guten Weg kenne,
exp() von einem komplexen Vektor schnell zu berechnen (komponentenweise, d.h. von jedem element des Vektors).Für lineare Algebra gibts ja mit verschiedenen ziemlich gute Implementierungen der BLAS. Kennt ihr für dieses Problem etwas vergleichbares? Ich hab beim googeln nichts gefunden (suche ich vielleicht nach dem falschen?)
Das einzige, was mir bisher eingefallen ist, das Problem auf mehrere Prozessoren zu verteilen. Das finde ich aber phantasielos - ausserdem kann man das auch machen, wenn man schon eine gute Einprozessorlösung hat.
Es geht um ein Simulationsprogramm, das wohl 90% der Zeit nichts anderes macht, ausser komplexe Exponentialfunktionen zu berechnen....
-
Von wievielen Dimensionen des Vektors sprechen wir hier ungefähr?
-
Und wofür werden die Exponentialfunktionen benötigt? Evtl. kann man zumindest teilweise ohne auskommen oder Ergebnisse cachen? Vielleicht reicht überhaupt eine Lookup-Table?
-
Hat mich ein wenig hieran erinnert:
http://de.wikipedia.org/wiki/Logarithmentafel
-
Genaue Informationen habe ich auch nicht... wie gesagt, ein Kollege hat gefragt, ich hatte keine gute Antwort parat, aber die Frage interessiert mich.
Ich vermute, der Vektor hat einige tausend oder zehntausend Einträge. Nach der Berechnung wird das Ergebnis genommen, damit ein neuer Vektor aufgestellt und wieder exponentiert. Ich vermute, das sind die berühmten 10% Code, die 90% der Rechenzeit verbrauchen.
Eine vernünftige Approximation wäre bestimmt auch gut. Wieviel Genauigkeit gebraucht wird, kann ich überhaupt nicht sagen. Lookup-tabellen selber basteln ist was feines, mein erster Gedanke war dann aber: Eigentlich muss es doch schon was fertiges geben.
Hübsch finde ich ja diese Approximation: http://schraudolph.org/bib2html/b2hd-Schraudolph99.html
Aber das ist nur was für die reelle Welt.
-
Einige zehntausend Einträge ist ja schon nichts mehr, das man effizient mit den SIMD-Fähigkeiten eines x86 angehen könnte*. Da bietet sich doch wirklich eher eine echte Parallelisierung an. Sei es auf mehreren CPU-Kernen oder mit einer GPU. Der Trick ist dann, die Daten zu verteilen und die Ergebnisse zurück zu bekommen. Das Schwierige an Parallelisierung ist daher meistens, sich ein Schema auszudenken, bei dem dies gar nicht (oder zumindest nicht so oft) nötig ist, weil jeder Prozessor für sich eine Weile mit den Daten rumrechnen kann.
Threadparallelität könnte hier sehr stark helfen, falls man ein System mit vielen Kernen und gemeinsamem Speicher hat. Dann entfällt nämlich das Verteilen und man muss sich auch kein neues Schema ausdenken. Wenn du also einen netten Rechner mit 4 oder 8 Kernen hast (Kernzahl << Zahl der Einträge), sollte das mit fast 100% Effizienz skalieren.
*: Aber es könnte natürlich trotzdem helfen. Kommt halt drauf an, wieviele Werte er gleichzeitig in die SSE-Einheit bekommt. Wenn die komplexe Zahl jedoch aus 2x double besteht dürfte das so ungefähr ein Wert sein, was natürlich wenig hilfreich wäre.
