Rechnen per CUDA
Frank Buss
Grafikkarte ausgelagert und wollte mal kurz dar�ber berichten, da ja auch
andere in dieser Newsgroup teilweise viel Rechenleistung f�r elektronische
Aufgaben brauchen: Ein Test l�uft auf einem Intel Quad Core (allerdings nur
auf einem Core laufend) mit 2,4 GHz in ca. 230 Sekunden durch, auf einer
NVIDIA 8800 GTX braucht es rund 2 Sekunden und auf einer NVIDIA 8600 GT
rund 10 Sekunden, wobei der C-Source f�r die Grafikkarte fast identisch
ist, nur ein paar unn�tige Branches sind wegoptimiert (z.B. Division durch
0 wird nicht getestet, da die Grafikkarte das einfach ignoriert und
Infinity zur�ckgibt). Man kann da ganz normal in C programmieren, mit ein
paar wenigen Erweiterungen z.B. Threadsynchronisierung oder Abfrage der
Thread- und Block Id, um jeweils einen passenden Teilbereich eines Arrays
abzuarbeiten. Die Integration von CUDA in Visual Studio ist sehr gut, wenn
man erstmal der IDE per Registry-Key beibebracht hat, da� jetzt auch
.cu-Dateien wie C++ per Syntax-Highlighting dargestellt werden sollen :-)
Welche Aufgaben k�nnte man noch leicht paralellisieren? W�re das auch was
f�r Spice-Berechnungen oder Leiterbahnrouting? GNU Radio scheint ja bereits
einiges in dieser Richtung zu machen.
--
Frank Buss, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Oliver Bartels
wrote:
>Welche Aufgaben k�nnte man noch leicht paralellisieren? W�re das auch was
>f�r Spice-Berechnungen oder Leiterbahnrouting? GNU Radio scheint ja bereits
>einiges in dieser Richtung zu machen.
Simulationen mit Matrizen etc. lassen sich sehr gut parallelisieren,
auch der Design Rule Check bei uns im BAE High End ist bereits
parallelisiert (der merkt, wenn weitere Cores anwesend sind).
Signalverarbeitung schreit auch danach.
Hingegen wird man sich beim Autorouter sehr schwer tun, weil es
eine recht eklige Abh�ngigkeit der Daten voneinander gibt, die
allen Dijkstra-�hnlichen Algorithmen gemein ist:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Siehe z.B.:
http://ditwww.epfl.ch/SIC/SA/publications/SCR98/scr10-page3.html
"Local Dijkstra"
Die Synchronisierung ist - auch nach unserern ausgiebigen Tests -
das gro�e Problem. Bei handels�blichen n-Core Prozessoren f�r PC's
kostet die mehr Zeit als das Parallelisieren bringt, bei einer
Grafikkarte w�re das noch zu untersuchen.
Gru� Oliver
--
Oliver Bartels + Erding, Germany + obar...@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10
Matthias Weingart
> Ich habe meine Magnetfeldberechnung auf einen Auftrag hin per CUDA auf die
> Grafikkarte ausgelagert und wollte mal kurz dar�ber berichten, da ja auch
Klingt ja interessant. Was passiert eigentlich, wenn die Grafikkarte schon
vom Direct-X Treiber benutzt wird?
M.
Jens Frohberg
"Frank Buss" <f...@frank-buss.de> wrote
> Ich habe meine Magnetfeldberechnung auf einen Auftrag hin per CUDA auf die
> Grafikkarte ausgelagert und wollte mal kurz dar�ber berichten[...]
Sehr sch�n, ich wollte mich schon immer mal damit besch�ftigen.
Gibts dazu ein Tutorial/Buch?
alsdenn, Jens
Florian Stock
> Klingt ja interessant. Was passiert eigentlich, wenn die Grafikkarte schon
> vom Direct-X Treiber benutzt wird?
Sollte schon. Wenn die Grafikkarte auch tatsaechlich fuer Grafik benutzt
wird, gibt aber einen Watchdog (ich glaube 5 Sek. warens), so dass der
Bildschirm nicht von einem lange rechnenden Kernel geblockt werden kann.
Florian
Björn Franke
> Hingegen wird man sich beim Autorouter sehr schwer tun, weil es
> eine recht eklige Abh�ngigkeit der Daten voneinander gibt, die
> allen Dijkstra-�hnlichen Algorithmen gemein ist:
> http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Dieses Paper [1] koennte in diesem Zusammenhang ganz interessant sein.
Oder auch jenes hier [2].
Bjoern
[1] Katz, Gary J. and Kider,Jr, Joseph T.: All-pairs shortest-paths for
large graphs on the GPU. GH '08: Proceedings of the 23rd ACM
SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, 2008.
http://portal.acm.org/citation.cfm?id=1413966#
[2] Solka, J.L., Perry, J.C., Poellinger, B.R., Rogers, G.W.:
Autorouting using a parallel Dijkstra algorithm with embedded
constraints. International Joint Conference on Neural Networks (IJCNN),
1992.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=227001
Klaus Rotter
> [2] Solka, J.L., Perry, J.C., Poellinger, B.R., Rogers, G.W.:
> Autorouting using a parallel Dijkstra algorithm with embedded
> constraints. International Joint Conference on Neural Networks (IJCNN),
> 1992.
> http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=227001
Hat da jemand Zugriff auf das Paper und kann es mir evtl. zukommen
lassen? Herzlichen Dank!
--
Klaus Rotter * klaus at rotters dot de * www.rotters.de
Klaus Rotter
> Bj�rn Franke schrieb:
>> [2] Solka, J.L., Perry, J.C., Poellinger, B.R., Rogers, G.W.:
>> Autorouting using a parallel Dijkstra algorithm with embedded
>> constraints. International Joint Conference on Neural Networks
>> (IJCNN), 1992.
>> http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=227001
>
> Hat da jemand Zugriff auf das Paper und kann es mir evtl. zukommen
> lassen? Herzlichen Dank!
Danke, habe es erhalten!
Frank Buss
> Sehr sch�n, ich wollte mich schon immer mal damit besch�ftigen.
> Gibts dazu ein Tutorial/Buch?
Am besten erstmal CUDA Treiber, Toolkit und SDK installieren. Im Toolkit
gibt es zwei gute PDFs: Ein Programmers Guide, mit einer auf�hrlichen
Beschreibung und Beispielen, und eine API-Referenz (auch als CHM). Gibt
auch viele Beispiele, aber ich habe ein einfaches Hello-World, ohne
Abh�ngigkeiten zu den Beispiel-Commons, vermisst und daher das hier als
Basis verwendet:
http://llpanorama.wordpress.com/2008/05/21/my-first-cuda-program/
Der Library-Pfad ist absolut in den Project-Settings codiert, den ggf.
einfach durch $(CUDA_LIB_PATH) ersetzen, dann l�uft es und man kann das
leicht f�r eigene Experimente verwenden.
Frank Buss
> Klingt ja interessant. Was passiert eigentlich, wenn die Grafikkarte schon
> vom Direct-X Treiber benutzt wird?
Scheint keine Probleme zu geben, wenn man ein wenig sogf�ltig programmiert.
Ich habe hier Vista mit Aero und kann w�hrend der Berechnung ohne Probleme
z.B. Windows-Tab dr�cken, f�r die 3D-Ansicht der Fenster. Ruckelt w�hrend
der Berechnung allerdings recht stark. Die Berechnung ging �ber 12
Sekunden, waren allerdings immer einzelne kleine H�ppchen.
Ich habe eben mal ein "while (1);" eingebaut und scheint tats�chlich ein
Timeout von ca. 5 Sekunden zu geben: Die Abarbeitung bricht dann ab.
Scheint also wirklich so zu sein, da� alles stehen bleibt, was mit Grafik
zu tun hat, solange ein Programm per CUDA ausgef�hrt wird, denn w�hrend der
Endlosschleife kann man nur die Maus bewegen, aber sonst ist alles
eingefroren (CPU-Zeit ist nat�rlich immer noch vorhanden). Nach dem Abbruch
kommt eine Meldung, da� es einen Fehler im Displaytreiber gegeben hat, man
kann aber sonst danach weiterarbeiten.
Hier �brigens die Ausgabe f�r die 12 Sekunden Rechenzeit: 1000 gerade
stromdurchflossene Leiterst�cke, in einer komplexen Kurve angeordnet und
dann das Magnetfeld von 1600x1200 Punkten im Raum vektoriell berechnet, die
in einer passenden Ebene liegen und logarithmisch dargestellt werden, wobei
die x/y/z-Komponenten jedes Magnetfeldvektors jeweils f�r RGB (Modulo 256)
verwendet werden. Also nichts sinnvolles, aber sieht h�bsch aus :-)
http://www.frank-buss.de/tmp/magnetfeld.jpg
Frank Buss
> Die Synchronisierung ist - auch nach unserern ausgiebigen Tests -
> das gro�e Problem. Bei handels�blichen n-Core Prozessoren f�r PC's
> kostet die mehr Zeit als das Parallelisieren bringt, bei einer
> Grafikkarte w�re das noch zu untersuchen.
Die Synchronisierung soll laut dem Programming Guide sehr optimiert sein.
Auch das Scheduling ist recht ausgekl�gelt und soll so gut wie keinen
Overhead haben. Mu� es auch, bei hunderten von parallel laufenden Threads
und der dynamischen Verteilung je nach Blockanzahl und Auslastung, und je
nach Grafikkarte. Bleibt aber nat�rlich noch das Problem, da� man den
Algorithmus so schreiben mu�, da� die Threads nicht allzu lange Leerlauf
haben beim synchronisieren.
Allerdings gibt es einige sch�ne Hilfsmittel. Z.B. Matrixoperationen werden
bis zu 3 Dimensionen speziell von der Hardware unterst�tzt, soda� die
Implementierung des parallelen Algorithmus schon fast trivial wird. Werde
ich vielleicht mal bei Gelegenheit ausprobieren.
Das Jonglieren mit local-, global-, host-Memory und Threads, Bl�cken und
Registern (wobei letzteres der Compiler einem abnimmt),
Speicherzugriffsstrategien usw., ist allerdings nicht ganz trivial, wenn
man wirklich das letzte an Geschwindigkeit herausholen will.
Frank Buss
> Ich habe meine Magnetfeldberechnung auf einen Auftrag hin per CUDA auf die
> Grafikkarte ausgelagert
Der Auftraggeber hat auch diese Version freigegeben, hier ist die
aktualisierte Webseite:
http://www.frank-buss.de/magnetfeld/index.html
Kann man auch gut als Beispielprojekt f�r eigene Experimente mit CUDA
verwenden.