Bearbeiten : Da die Partikel in Gitterzellen segmentiert sind (zB 16^3 grid), ist es besser, eine Arbeitsgruppe für jede Gitterzelle und so viele Elemente in einer Arbeitsgruppe, da es maximale Anzahl von Partikeln pro Gitterzelle geben kann?
In diesem Fall könnte ich alle Partikel aus benachbarten Zellen in den lokalen Speicher laden und durch sie einige Eigenschaften berechnen. Dann könnte ich einen bestimmten Wert in jedes Partikel in der aktuellen Gitterzelle schreiben.
Wäre dieser Ansatz von Vorteil gegenüber dem Ausführen des Kernels für alle Partikel und für jedes Iterieren über (meistens die gleichen) Nachbarn?
Was ist das ideale Verhältnis von number of particles/number of grid cells ?
Ich versuche, CUDA Particles neu zu implementieren (und zu modifizieren) OpenCL und verwenden Sie es, um die nächsten Nachbarn für jedes Partikel abzufragen. Ich habe die folgenden Strukturen erstellt:
P enthält die 3D-Positionen aller Partikel ( float3 ) Puffer Sp speichert int2 Paare von Partikel-IDs und ihre räumlichen Hashwerte. Sp wird nach dem Hash sortiert. (Der Hash ist nur eine einfache lineare Zuordnung von 3D zu 1D - noch keine Z-Indizierung.)
Puffer L speichert int2 Paare von Anfangs- und Endpositionen bestimmter räumlicher Hashwerte im Puffer Sp . Beispiel: L[12] = (int2)(0, 50) .
L[12].x ist der Index (in Sp ) des ersten Partikels mit dem räumlichen Hash 12 . L[12].y ist der Index (in Sp ) des letzten Partikels mit dem räumlichen Hash 12 . Nun, da ich all diese Puffer habe, möchte ich alle Partikel in P durchlaufen und für jedes Partikel durch seine nächsten Nachbarn iterieren. Momentan habe ich einen Kernel, der so aussieht (Pseudocode):
Das Problem mit diesem Code ist, dass er langsam ist. Ich vermute, dass der nichtlineare GPU-Speicherzugriff (insbesondere P[Sp[p].y] in der innersten for -Schleife) die Langsamkeit verursacht.
Was ich tun möchte, ist Z-Auftragskurve als räumlicher Hashwert. Auf diese Weise konnte ich nur 1 for Schleife haben, die bei der Abfrage von Nachbarn durch einen kontinuierlichen Speicherbereich iteriert. Das einzige Problem ist, dass ich nicht weiß, was die Z-Index-Werte starten und stoppen soll.
Der heilige Gral, den ich erreichen möchte:
%Vor%Sie sollten die Morton-Code-Algorithmen genau studieren. Ericsons Echtzeit-Kollisionserkennung erklärt das sehr gut.
Ericson - Echtzeit-Kollisionserkennung
Hier ist eine weitere nette Erklärung, die einige Tests enthält:
Morton-Codierung / Decodierung durch Bit-Interleaving: Implementierungen
Z-Order-Algorithmen definieren nur die Pfade der Koordinaten, in denen Sie von 2 oder 3D-Koordinaten zu einer Ganzzahl hashen können. Obwohl der Algorithmus für jede Iteration tiefer geht, müssen Sie die Grenzwerte selbst festlegen. Normalerweise wird der Stop-Index durch ein Sentinel angegeben. Lassen Sie den Sentinel stoppen, wird Ihnen sagen, auf welcher Ebene das Partikel platziert ist. Die maximale Ebene, die Sie definieren möchten, gibt Ihnen die Anzahl der Zellen pro Dimension an. Zum Beispiel mit maximaler Stufe bei 6 haben Sie 2 ^ 6 = 64. Sie haben 64x64x64 Zellen in Ihrem System (3D). Das bedeutet auch, dass Sie ganzzahlige Koordinaten verwenden müssen. Wenn Sie Floats verwenden, müssen Sie konvertieren wie coord.x = 64*float_x und so weiter.
Wenn Sie wissen, wie viele Zellen Sie in Ihrem System haben, können Sie Ihre Grenzen definieren. Versuchen Sie, einen binären Octree zu verwenden?
Da Teilchen in Bewegung sind (in diesem CUDA-Beispiel), sollten Sie versuchen, über die Anzahl der Teilchen anstelle von Zellen zu parallelisieren.
Wenn Sie Listen der nächsten Nachbarn erstellen möchten, müssen Sie die Partikel Zellen zuordnen. Dies geschieht durch eine Tabelle, die anschließend von Zellen nach Partikeln sortiert wird. Trotzdem sollten Sie die Partikel durchlaufen und auf ihre Nachbarn zugreifen.
Über Ihren Code:
Das Problem mit diesem Code ist, dass er langsam ist. Ich vermute, dass der nichtlineare GPU-Speicherzugriff (insbesondere P [Sp [p] .y) in der innersten for-Schleife) die Langsamkeit verursacht.
Denken Sie daran, Donald Knuth. Sie sollten messen, wo der Flaschenhals ist. Sie können den NVCC Profiler verwenden und nach Engpässen suchen. Nicht sicher, was OpenCL als Profiler hat.
%Vor%
Ich denke, Sie sollten es nicht auf diese Weise abzweigen. Wie wäre es mit einer Null, wenn Sie heavy_computation aufrufen? Nicht sicher, aber vielleicht hast du hier eine Art Verzweigungsprognose. Versuchen Sie das irgendwie zu entfernen.
Parallel über die Zellen zu laufen ist nur dann sinnvoll, wenn Sie keine Schreibzugriffe auf die Partikeldaten haben, sonst müssen Sie Atomics verwenden. Wenn Sie stattdessen über den Partikelbereich gehen, lesen Sie Zugriffe auf die Zellen und Nachbarn, aber Sie erstellen Ihre Summe parallel, und Sie sind nicht gezwungen, ein bestimmtes Race-Condition-Paradigma zu wählen.
Was ist auch das ideale Verhältnis von Anzahl der Partikel / Anzahl der Gitterzellen?
Das hängt wirklich von Ihren Algorithmen und der Partikelpackung in Ihrer Domäne ab, aber in Ihrem Fall würde ich die Zellengröße entsprechend dem Partikeldurchmesser definieren und einfach die Anzahl der Zellen verwenden, die Sie erhalten.
Wenn Sie also die Z-Reihenfolge verwenden und Ihren heiligen Gral erreichen wollen, versuchen Sie, ganzzahlige Koordinaten zu verwenden und sie zu hashen.
Versuchen Sie auch, größere Mengen an Partikeln zu verwenden. Ungefähr 65000 Partikel wie CUDA-Beispiele sollten verwendet werden, da auf diese Weise die Parallelisierung meist effizient ist; die laufenden Verarbeitungseinheiten werden ausgenutzt (weniger Leerlaufthreads).
Tags und Links algorithm physics opencl nearest-neighbor simulation