Hallo,

hatte bisher nur Hashmaps auf CPU verwendet, z.b. eine 2-Dimensionale Hashmap, für die X-Achse eine und pro X-Achse eine für die Y-Achse und dann für jede Y-Achse eine ArrayList für Einträge.

Wie macht man das auf der GPU? Vor allem wie löst man sowas parallel? Also mein Szenario sieht wie gefolgt aus, ich benötige ein Uniform Grid um Partikel darin einzusortieren um für jede Zelle eine Liste der Partikel zu bekommen, damit ich um einen Partikel herum alle Nachbaren herausbekommen kann. Leider habe ich absolut keinen Schimmer wie ich das auf der GPU umsetzten kann. Auf der CPU ist das sehr einfach: Map<Integer, Map<Integer, List<ParticleIndex>>> gridMap; // Dynamic 2D uniform hashmap for particle buckets

Das Grid kann übrigens fix sein, dynamisch wie die Hashmaps wäre zwar besser aber ich denke mal das ist auch langsamer...

Danke,
Final

Also was du demonstrierst scheint mir keine Hashmap zu sein, es ist einfach ein Array mit den Partikeln und auch ohne Hash.

Zu deiner CPU Implementierung:
Ich möchte Anmerken dass deine CPU-Implementierung grauenvoll ist.
Warum, das? Du hast einen dreifach Pointer mit mindestens dreifacher Indirektion. Du hast sehr schlechte Cache Density. Eine Map besitzt außerdem keine konstante Zugriffszeit und es müssen mehrere Zugriffe stattfinden um einen Eintrag zu finden. Somit hast du auch aus Sicht eines theoretischen Informatikers gar keine konstante Laufzeit des Containers erreicht, was das Hauptargument einer Hash Map oder Grids(was du eigentlich willst)wäre!

Und genau so würde ich es auch auf der GPU umsetzen. Allerdings ist es da noch stärker hilfreich, wenn du für die Anzahl Partikel pro Zelle ein Maximum finden kannst. Die Datenstruktur ist dann einfach als 3 dimensionales Array organisierbar. (X, Y, Partikel in Zelle).

Naja über Hashmaps hat man den Vorteil, dass das Grid in jede Richtung wachsen kann. Aber nen Statisches Uniform Grid ist natürlich deutlich schneller.
Versteh ich das Richtig das man es aufbaut, das man sagt es gibt z.b. max. 4 Partikel pro Zelle und dann im grunde das 3 Dimensional in einem 1D Array/VBO abbildet?
So z.b. [X, Y, PI1, Pi5, Pi7, -1],[X, Y, PI21, Pi25, Pi17, P22]

Ich denke es gibt Möglichkeiten "beliebiges" Wachstum schonender und GPU fähiger zu Implementieren. Ich sehe zum Beispiel die Möglichkeit eines nicht tief verschachtelten Baumes. In OpenGL "möglicherweise" umsetzbar mit einer Extension wie "ARB_sparse_buffer". Allerdings vermute ich, dass dynamisches Wachstum in OpenGL auf der GPU sehr schwierig umzusetzen ist.

Ja das verstehst du wahrscheinlich richtig. Dein Beispiel verstehe ich ehrlich gesagt nicht.
Du könntest aber auf der GPU auch eine Textur verwenden. Unter anderem besteht auch die Möglichkeit, nur eine 2 dimensionale Textur zu verwenden und dann die bis zu vier Farbkomponenten für die bis zu 4 Partikel pro Zelle zu nutzen. Es sieht mir allerdings etwas unflexibler aus. (Und nicht unbedingt schneller) Je nachdem könnte es auch sinnvoll sein zusätzlich noch eine 2 dimensionale Dastenstruktur anzulegen, die dann angibt wieviele Partikel in jeder Zelle zu finden sind. So machen wir es in unserer Partikelsimulation auf der CPU und das erspart das Nachschlagen von vielen Partikeln, den häufig gibt es gar keine in einer Zelle, dann müssen nicht 3 Indices geladen werden. (Das ist bei uns momentan das Partikelmaximum pro Zelle)

Hallo,

für mich sieht die doppelt verschachtelte Hashmap etwas umständlich aus. Ich würde die Partikel in einer doppelt verketteten Liste (oder noch besser: ein AVL-Baum) nach x sortieren. Um für einen Partikel die nächsten Nachbarn zu finden, suchst du einmal in einem bestimmten Radius in der x-Liste und filterst die Ergebnisse dann nach dem y-Radius.

Verkettete Listen lassen sich in GLSL mit 1D-Texturen realisieren, man benötigt lediglich eine Zweikanaltextur mit 8Bit (16Bit falls dein Suchradius größer 255 ist) pro Kanal, also GL_LUMINANCE_ALPHA als Format. In einem Kanal speicherst du den Sprungwert (zur nächsten Textur-Koordinate) zum nächsten linken, in dem anderen den zum nächsten rechten Nachbarn. So kannst du dann über mehrere Lookups immer die nächsten Nachbarn bestimmen. Dasselbe machst du dann nochmal für die y-Werte, allerdings in einer 2D-Textur abhängig vom x-Wert. In einer weiteren 2D- oder gar 3D-Textur kannst du dann die Partikel-Indizes abspeichern.

Der Shader-Algorithmus für die Suche würde dann folgendermaßen aussehen:


Keine Garantie, dass der Algorithmus wirklich funktioniert Die Texturen mit den Sprungwerten zu erstellen dürfte eigentlich kein Problem sein, wenn du schon die Hashmap hast.

Viele Grüße
dj3hut1

P.S. wenn du einen richtigen Suchradius (euklidischer Abstand) willst, musst du durch ersetzen.

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University

Es ist dir aber hoffentlich klar, dass eine so umgesetzte Linked List sowohl auf der CPU als auch auf der GPU vergleichsweise ziemlich langsam ist. Linked Lists sind zurecht in optimierter Software auf modernen Plattformen ziemlich unbeliebt(Cache). Ich habe schon in letzter Zeit ziemlich viel dazu im Forum geschrieben. Bäume führen viele Zugriffe auf dem Speicher verteilt aus, um die Zielposition zu finden. Und jedesmal hohe Wahrscheinlichkeit eines Cachemiss. Bei Linked Lists ist es kaum anders. Die Speicherverschwendung durch die Pointer, die gespeichert werden müssen, ist groß.
Ich habe nie eine derartige Datenstruktur auf der GPU ausprobiert, aber alles was ich von der Arbeitsweise der GPUs weiß, ist es dort vielleicht sogar dafür noch schlechtere Bedingungen herschen. Texturen werden speziell so verwaltet, dass lokale Zugriffe besonders schnell sind: Bei Linked Lists und Bäumen die quer durch den Speicher gehen, weniger hilfreich. Außerdem können GPUs sehr schlecht mit vielen Kontrollstrukturen umgehen, was meiner Erfahrung mit anderen Szenarien nach leicht die Hauptbremse eine GPU-Portierung werden kann. Und zuletzt ist auf der GPU noch Bandbreite ein wichtiges Thema. Wieviele Texturzugriffe bei dir stattfinden müssen, um einen Wert zu erhalten, muss ich wohl nicht weiter erläutern.

Anstatt "GL_LUMINANCE_ALPHA" würde ich übrigens die nicht veraltete Alternative "GL_RG?​​" empfehlen.

Hallo OpenglerF,

leider kann ich deine Kritik nicht ganz verstehen. Speicherzugriffe, ob nun gecached oder nicht, sollten generell langsamer sein, selbst wenn man Kontrollstrukturen benutzt. Die Performance von meinem Algorithmus hängt auch stark vom Suchradius und der Partikeldichte ab. Bei einem sehr kleinen Suchradius oder einer sehr hohen Partikeldichte dürfte die Performance aufgrund der zusätzlichen Texturzugriffe im Unterschied zur Brute-Force-Methode schlechter sein. Bei einer kleineren Partikeldichte wird aber der Speicherzugriff deutlich minimiert, da man immer sofort zum nächsten Partikel "springt" und keine unnötigen Texturzugriffe mehr hat.

Mal als Beispielrechnung: nimm einen Suchradius von 5 (100 Felder) und 10 Partikel, die sich darauf verteilen (Worst-Case: mit jeweils unterschiedlichen x-Koordinaten). Die Brute-Force-Methode würde 100 Texturzugriffe benötigen. Bei meinem Algorithmus wären das etwa 10 Zugriffe auf die erste, 20 Zugriffe auf die zweite und 10 Zugriffe auf die dritte Textur (um auf die Partikel-Indizes) zuzugreifen (plus der Schleifenoverhead). Das wären also nur 40% der Texturzugriffe. Bei weniger Partikeln sinkt sogar die Rate, während die Zugriffszahl bei der ersten Methode immer konstant bleibt.

Viele Grüße
dj3hut1

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University

Viele Texturzugriffe direkt beieinander können durch die Cache Locality viel schneller beantwortet werden, als gleich viele verteilt über den gesamten Speicher. Dieser Effekt hat starke Auswirkungen haben. (Siehe zum Beispiel hier) Texturen werden deshalb zum Beispiel im Speicher extra für erhöhte räumliche Lokalität im Speicher gefaltet abgelegt.


Ja das stimmt. Allerdings ist in vielen Partikelsystemen zwecks der Einfachheit der Suchradius einfach konstant und das Grid muss einfach entsprechend ausgelegt sein, damit nur eine optimale Anzahl Zugriffe erledigt werden müssen. (Zum Beispiel so dass nur noch 3² Felder durchsucht werden, wie bei unserer Implementierung) In dem Fall vom Suchradius fünf, den du oben beschreibst, ist das Grid für diese Art Suchanfrage einfach zu eng gelegt und damit falsch dimensioniert.

Ich würde vorschlagen du schaust dir mal Histogram Pyramid als indexing Struktur an. Eingesetzt werden diese meist für point-cloud und n-body Probleme.
Sind leider nicht ganz trivial in der implementierung hoffe das hier hilft dir weiter.

mfg FrenK