Optimieren durch GPU-Nutzung

[Gast]

Hallo,

kann mir jemand eine Seite mit Beispielen für Codeoptimierung durch GPU-Nutzung empfehlen? Besonders interessiert mich Integer-Arithmetik.

[Gast]

Hallo,

kann mir jemand eine Seite mit Beispielen für Codeoptimierung durch GPU-Nutzung empfehlen? Besonders interessiert mich Integer-Arithmetik.
Was meinst du? Wenn dein Problem parallelisierbar ist dann kannst du dein Programm quasi immer "optimieren" indem du es auf der GPU rechnest. Wenn das Probelm nicht parallelisierbar ist, bringt dir auch die GPU nichts bzw. dann ist es miestens schneller es auf der CPU zu machen.

Oder meinst du wie man optimalen Code für die GPU schreibt?

lg

[Gast]

Kann man z.B: sowas mit GPUnutzung beschleunigen:


for (size_t n = 0; n <= foo;)
{
array[n++] = 0;
array[n++] = 1;
}

[Gast]

oder sowas:

for (size_t n = 0; n <= foo;)
{
array[n += d1] = p1;
array[n += d2] = p2;
}


(array aus unsigned longs)

[Nasenbaer]

Also GPGPU wurde sicher nicht für die Berechnung von Integer-lastigen Algorithmen entwickelt und da die IHVs selbst keine Aussagen zur Integer-Leistung liefern, vermute ich, dass diese dafür auch längst nicht so gut geeignet sind wie für FP-lastige Aufgaben.

Und mir erschließt sich auch nicht der Hintergrund deiner Frage? Wenn du dir die Frage selbst nicht beantworten kannst ob man das unabhängige Beschreiben eines Arrays parallelisieren kann, dann solltest du auf GPGPU vorerst einmal verzichten. ;)
Im übrigen gibts zu simplen Array-Manipulationen genügend Beispiele in den entsprechenden SDKs (ATI Stream, CUDA und DirectX).

[Gnafoo]

Was meinst du? Wenn dein Problem parallelisierbar ist dann kannst du dein Programm quasi immer "optimieren" indem du es auf der GPU rechnest. Wenn das Probelm nicht parallelisierbar ist, bringt dir auch die GPU nichts bzw. dann ist es miestens schneller es auf der CPU zu machen.

„Immer“? Der Einsatz der GPU setzt schon sehr spezielle Probleme voraus.

Ich kenne mich zwar mit GPGPU auch nicht so sehr aus, aber die CPU kann vieles schneller als eine GPU. Verzweigungen sind auf der CPU viel günstiger, Speicherzugriffe auf der GPU sind höllisch teuer, der Datentransfer zwischen Host und GPU kann limitieren, das Problem muss wirklich massiv parallel sein, damit es überhaupt etwas bringt etc. Man braucht einfach genügend Threads, um die Speicherlatenzen zu verstecken und die GPU beschäftigt zu halten. Und ich rede hier nicht von 8 Threads oder so, sondern von mehreren Tausend.

Edit: für die Arrayfuchtelei da oben ist das natürlich unsinnig. Das ist O(n) und vermutlich braucht der Transfer auf die GPU und zurück länger, als die Aufgabe mit der CPU zu lösen.

[Coda]

Speicherzugriffe sind auf der GPU extrem billig, wenn das Problem parallel genug ist.

[Nasenbaer]

Speicherzugriffe sind auf der GPU extrem billig, wenn das Problem parallel genug ist.
Aber müssen die Zugriffe nicht zusätzlich "cache-freundlich" sein - also sind zufällige Speicherzugriffe nicht ziemlich ungeeignet?

[Gast]

„Immer“? Der Einsatz der GPU setzt schon sehr spezielle Probleme voraus.

Ja, die Voraussetzung ist dass das Problem parallelisierbar ist, das schrieb ich ja.

Ich kenne mich zwar mit GPGPU auch nicht so sehr aus, aber die CPU kann vieles schneller als eine GPU. Verzweigungen sind auf der CPU viel günstiger, Speicherzugriffe auf der GPU sind höllisch teuer, der Datentransfer zwischen Host und GPU kann limitieren, das Problem muss wirklich massiv parallel sein, damit es überhaupt etwas bringt etc. Man braucht einfach genügend Threads, um die Speicherlatenzen zu verstecken und die GPU beschäftigt zu halten. Und ich rede hier nicht von 8 Threads oder so, sondern von mehreren Tausend.

Natürlich meine ich wenn ich "parallelisierbares Problem" sage nicht dass man Physik und Sound auf 2 Threads aufteilt - das ist kein "parallelisierbares Problem". Insofern ist dann zwischen "paralleliserbares Problem" und "wirklich massiv parallel" kein Unterschied - das eine bedingt automatisch das andere.

Edit: für die Arrayfuchtelei da oben ist das natürlich unsinnig. Das ist O(n) und vermutlich braucht der Transfer auf die GPU und zurück länger, als die Aufgabe mit der CPU zu lösen.
Kommt ganz drauf an wie groß das Array ist... ;)
Wobei es in dem obigen Beispiel natürlich trotzdem unsinnig ist, das ganze ist ja nur sinnvoll wenn die Rechenleistung auf der CPU eine Rolle spielt, was hier (elemente 0/1 setzen) ja wohl nicht der Fall ist... ansonsten kann die GPU ihre stärke ja gar nicht ausspielen.

Aber müssen die Zugriffe nicht zusätzlich "cache-freundlich" sein - also sind zufällige Speicherzugriffe nicht ziemlich ungeeignet?
Nein, selbst ins global Memory (das langsamste was auf der GPU möglich ist) und bei "zufälligen" Zugriffen hast du Bandbreiten im Bereich von ~100GB/s, wenn Cache, local memory usw noch dazukommen gehts bis in die TB/s. (Wohlgemerkt, bei einem parallelen Problem, d.h. wenn die Cores genug ausgelastet sind - s. oben)

[Nasenbaer]

Nein, selbst ins global Memory (das langsamste was auf der GPU möglich ist) und bei "zufälligen" Zugriffen hast du Bandbreiten im Bereich von ~100GB/s, wenn Cache, local memory usw noch dazukommen gehts bis in die TB/s. (Wohlgemerkt, bei einem parallelen Problem, d.h. wenn die Cores genug ausgelastet sind - s. oben)
Ja die Bandbreite muss ja nicht zwangsweise mit geringer Latenz einhergehen.
Burst-Read und Random-Access unterscheiden sich bei einer HDD ja bspw. auch enorm.
AFAIK soll das bei GPUs auch nicht viel anders.

[Nighthawk13]

Schnelle rechenintensive Integer Arithmetik ist auch möglich auf GPUs.
Im Falle Nvidia, siehe Abschnitt 5.4.1 im Cuda-Programming-Guide:

http://developer.download.nvidia.com/compute/cuda/3_1/toolkit/docs/NVIDIA_CUDA_C_ProgrammingGuide_3.1.pdf

=> Die Integer-Operationen "add" und "logical operations"(and, or, ...) laufen so schnell wie float-FMA(1Op je Alu/Clock).
Alle anderen Integer-Ops(MAD, shift, ...) laufen nur auf der Hälfte der ALUs.

Da die "eingschränkte" Hälfte aber neben "add" und "logical operations" auch noch die "load/stores" ausführen kann, sollte die Auslastung auch bei Integer-Code ganz gut sein.

[Gast]

Ja die Bandbreite muss ja nicht zwangsweise mit geringer Latenz einhergehen.
Burst-Read und Random-Access unterscheiden sich bei einer HDD ja bspw. auch enorm.
AFAIK soll das bei GPUs auch nicht viel anders.
Doch, bei GPUs ist der Unterschied dass du eben parallel unterwegs bist. Der Performancevorteil der GPU ergibt sich ja nicht daraus dass einzelne Operationen um soviel schneller sind als auf der CPU (dass das nicht so ist wissen wir ja) sondern eben daraus dass du sehr viel gleichzeitig machen kannst. Und selbst wenn ein einzelner Speicherzugriff auf der GPU eine sagen wir mal 100 mal größere Latenz hat als auf der CPU - wenn du 10.000 davon gleichzeitig machen kannst bist du trotzdem viel schneller als die CPU wenn dein Problem auss 100.000 solcher Speicherzugriffe besteht und parallelisierbar ist.
(die Zahlen sind nur zur Verdeutlichung, ich weiß dass man auf der GPU nicht wirklich 10.000 Zugriffe parallel machen kann...)

[Gast]

Nachtrag:
Es ist so wie Nighthawk13 sagt, wenn es rechenintensiv (und natürlich parallelisierbar) ist dann zahlt es sich aus, egal ob Integer oder floating point Arithmetik.

[Coda]

Aber müssen die Zugriffe nicht zusätzlich "cache-freundlich" sein - also sind zufällige Speicherzugriffe nicht ziemlich ungeeignet?
Wenn du genügend Threads hast kannst du auch die Latenzen von Zugriffen direkt auf den RAM verstecken. Problematischer sind dabei eher Bank-Konflikte.

[Nasenbaer]

Ahh ok - wieder was gelernt.

[Nighthawk13]

Die pre-Fermi GPUs waren sehr auf "Bursts" angewiesen für schnellen Speicherzugriff(Jeder Threads liest ein DWORD, aufeinanderfolgende Threads jeweils 4 Bytes weiter, Anfangsadresse 128Byte aligned).

Bei Fermi ist es eigentlich wie auf einer CPU: Für jede (read/write-)Speicheradresse wird automatisch die zugehörige 128-Byte-Cacheline in den Cache reingeladen(mittels schnellem Burst), falls nicht schon passiert. Der eigentliche Speicherzugriff wird aus dem/in den Cache durchgeführt.

D.h. "wilde" Speicherzugriffe sind ok, solange alle Daten in den Cache passen(48KB wenn man wenig shared memory braucht).

[Yavion]

MS hatte mal ein Projekt namens Accelerator, womit man GPU Optimierungen recht leicht in .NET Programme einbauen kann. Das ist vielleicht nicht ganz so flexibel aber dafür weniger sperrig als CUDA.

Weiss aber nicht was draus geworden ist. Die URL ist gerade down aber Google hat ein trotzdem ein paar Treffer, Beispiele, z.B:
http://tomasp.net/blog/accelerator-life-game.aspx
Auch Download-Links sollten sich finden lassen.

[Gast]

oder sowas:

for (size_t n = 0; n <= foo;)
{
array[n += d1] = p1;
array[n += d2] = p2;
}


(array aus unsigned longs)

Das simple initialisieren eines Arrays ist als Benchmark vollkommen ungeeignet. Das hängt nur von der Compileroptimierung ab von "erhöhe des Feldindex jedes Mal um eins" bis zu "streiche die komplette for-Schleife, da die Ergebnisse nicht mehr verwendet werden". In jedem Fall wird das längste das Anfordern des RAMs sein.
Eine GPU bringt hier überhaupt nichts, außer, dass man den RAM sinnlos über den PCIExpress in die GPU und wieder zurück kopieren muss.

Abgesehen davon ist dieser Code selbst für eine CPU ziemlich performancefeindlich geschreiben, da hier nichts parallelisiert werden kann, da das n von der Ergebnissen der lezten Schleife abhängt. Wenn möglich sollte man das so schreiben:

for (size_t n = 0; n <= foo;n++)
{
array[n*(d1+d2)] = p1;
array[n*(d1+d2)+d1] = p2;
}

Ein guter Compiler wird d1 und d2 nicht in jeder Schleife neu berechnen, falls diese sich nicht ändern.
Falls d1 und d2 = sizeof(size_t), dann wird sogar weiter optimiert und gleich nur mehr ein Block kopiert.

Wenn man einen Performancetest machen will, dann sollte man etwas komplexere und praxisnahere Tests machen, da eine einzige Compileroption hier riesige Auswirkungen haben kann.