[OpenCL] AI Projekt auf OCL/GPU - Portierung möglich?

Hi,

ich arbeite gerade an einer “Artificial Intelligence” (Spieleniveau) und Pathfinding-Algorithmus der auf der GPU arbeiten kann.

Im Moment läuft das ganze noch seriel auf der CPU und das mit überraschend guter Performance bei 100-tausenden Aktoren. Eigentlich ist ja auch der hohe RAM Verbrauch das unlösbare Problem aber das ganze System ist für GPUs einfach prädestiniert.

Im Grunde muss wie bei OpenGL, in einem Fragment Shader, ein riesiges Array (Textur) in ein anderes Array (Rendertarget/Framebuffer) geschrieben werden.
Theoretisch ist das auch mit OpenGL compute&Fragment shadern umsetzbar aber natürlich mit dem ganzen Render Pipeline Overhead drumherum.

In OpenCL scheint es aber keine 3D Arrays, und dann auch noch in dieser Größe, zu geben.
Man kann zwar auf Texturen im OpenGL Kontext zugreifen und manipulieren…

Im Grunde muss ich ein 1D Array mit unbegrenzter Größe an OpenCL Streamen können und ein 3D Array (gerne auch 4D) als Ergebniss mit unbegrenzter Größe zurückbekommen.
Jeder Eintrag in den 1D/2D/3D/4D arrays sollte dabei optimalerweise seinen eigenen “Thread” bekommen oder wie man das auch immer auf GPUs nennt.

Mal so allgemein gefragt: Kann das OpenCL?
Google sagt mir eher nein. Aber ich kenne mich mit OCL auch nicht aus.

hust hust @Marco13 hust hust hust

Naive Websuchen nach „Pathfinding GPU“ bringen zwar einige Ergebnisse (wo ich ggf. morgen nochmal genauer drüberschaue). Aber die Beschreibungen mit den 100000en Aktoren und den Arrays klingen sowohl speziell als auch spezifisch. Also, was genau mit

Im Grunde muss ich ein 1D Array mit unbegrenzter Größe an OpenCL Streamen können und ein 3D Array (gerne auch 4D) als Ergebniss mit unbegrenzter Größe zurückbekommen.
Jeder Eintrag in den 1D/2D/3D/4D arrays sollte dabei optimalerweise seinen eigenen „Thread“ bekommen oder wie man das auch immer auf GPUs nennt.

gemeint ist, erschließt sich mir gerade nicht. Gerade was Speicherallokationen angeht sind GPUs recht „starr“. (Und OpenCL noch etwas mehr als CUDA. Bei letzterem baut NVIDIA alles ein, was ihre GPUs irgendwie hinkriegen, und da kann man seit neuerem auch Speicher IN einem Kernel allokieren). Auch die Frage nach der Dimensionalität ist nicht ganz klar: Was SIND denn diese 4 Dimensionen? (Es gibt zwar sowas wie mem clCreateFromGLTexture3D, aber zugegeben: Damit hab ich noch nicht wirklich was gemacht…). Oft bildet man eben n-D-Arrays einfach auf 1D ab - außer, wenn sich die Verwendung von (GL) Texturen „aufdrängt“. Aber auch dann ist „random access“ ziemlich schwierig. Ich wüßte nicht, was bei einem A* oder so viel „gerechnet“ werden sollte - und wenn das Problem „memory bound“ ist, ist es schwierig, einen guten Speedup rauszuholen. (Ich erinnere mich zumindest auch, dass @Fancy und ich mal einen Conway implementiert hatten, und der https://github.com/mschorn/net.mschorn.sandbox/tree/master/src/main/resources/net/mschorn/sandbox/lwjgl/gpgpu/samples/conway war am Ende IIRC deutlich schneller)

Ich verwende keinen A*, es gibt viele Algorithmen die nicht darauf basieren, leider wird über Google nur A* propagiert - nicht zu Unrecht, ist halt der im „generellen“ Fall anpassbarste Algorithmus.
Mein Algorithmus erweitert den Collaboration Diffusion Algorithmus, darüber will ich hier bei Zeit aber auch noch einen detaillierten Blogeintrag schreiben.
Ich hab nurnoch keinen Namen dafür :smiley:

Conway ist aber ein gutes Stichwort. Funktioniert hier sehr ähnlich. Jede Zelle im Array repräsentiert einen Graphen dessen Gewichtung sich aus den Nachbarzellen ergibt.

Nehmen wir Conway, weil das Prinzip simpel ist und fast 1zu1 übertragen werden kann.

Diese Textur in die ihr im Fragment Shader schreibt, die müsst ihr ja jedes mal zurück streamen an die CPU.
Und dann ist da noch dieser ganze OGL Render Pipeline Overhead.
Klar kann ich die AI auch auf OGL laufen lassen aber was ihr mit Conway gemacht habt, könnte man das auch auf OCL umsetzen?

Wie ich auch (etwas ausführlicher) in Using Java with Nvidia GPU’s (cuda) - Stack Overflow geschrieben habe: Man KANN alles mögliche auf der GPU rechnen.
Eine spzifischere Websuche führte nun zu Ramblings of a Game Dev Student: Pathfinding Using Collaborative Diffusion , was beim Überfliegen ja recht überschaubar aussieht. Ich vermute, das, was dann parallel von tausenden Aktoren ausgeführt werden sollte, wäre die Rückwärtssuche entlang des steilsten Gradienten…?

Mal etwas Grundsätzliches…

Ich würde stets davon absehen riesige Arrays zu kopieren. Ich würde zwei Speicherbereiche alloziieren und darauf über eine Struktur zugreifen, in welcher Adresse, DatenPointer, Größe und Schrittweite steht. Wenn der benötigte Speicherbereich stets die selbe größe hat, genügt es, den doppelten Speicher fest zu belegen und die Pointerstrukturen zwischen Schreib- und Lesethreads auszutauschen und deren Datenpointer zu resettieren. Ist er nicht immer der selbe, muss der Schreibthread stets den benötigten Speicher neu anfordern und der Lesethread nach getaner Arbeit ihn wieder freigeben. Eine längerdauernde Kopie ist hier nicht mehr notwendig, sondern nur die Weitergabe der Adresse des gerade bearbeiteten Buffers. Ich bin zwar nicht firm in CL-Geschichten, aber ich denke mal, das sollte dort auch gehen - würde mich wundern, wenn nicht. In Java wird das Ganze btw. mit „java.nio“ (".duplicate()") realisiert. :wink:

Das war eine interessante Antwort auf Stack Overflow.

Nebenläufig: Von Projekt Sumatra höre ich das erste mal, dabei ging mir, und vielen anderen scheinbar auch, der Gedanke bereits mehr als einmal im Kopf herum. AMD arbeitete bereits 2010 an einem ähnlichen Projekt „Aparapi“, die Meldungen über Sumatra hören aber 2014 komplett auf.
Gibt es da irgendwie andere Neuigkeiten oder wurde das Projekt eingestellt?

Noch hab ich OpenCL nicht richtig zum laufen gebracht, zu viele Probleme, deshalb kann ich noch nicht rumprobieren. Dachte erst gelesen zu haben ein array in OpenCL könnte nur eine Größe von 4 haben. Float4, int4, etc…
Jetzt sehe ich aber in einem Beispielsprogramm ein array von 10.000 Einträgen, das hatte ich dann wohl missverstanden. clCreateFromGLTexture hätte man sicherlich auch irgendwie verwenden können.

Exakt und natürlich die vorangehende Diffusionsberechnung, jeder Aktor auf der CPU müsste dann eine Ziel-Koordinate zurück erhalten von der GPU.
Wie oft die Berechnung durchgeführt wird spielt eigentlich auch keine Rolle, je öfter desto genauer, irgendwann frägt der Aktor auf der CPU halt mal nach was denn im Moment so das beste Ziel wäre sich als nächstes zu bewegen.
Die aktuellste Position und Wert jedes Aktors muss dabei natürlich vorher auf die GPU gestreamt werden, am besten in Form einer primitiven Liste/Arrays und die Ergebnisse müssen zurück an die GPU gestreamt werden, wiederum in Form einer primitiven Liste/Array.
Im Moment macht mir das noch sorgen, weil ich nicht weiß wie ich da am besten heran gehe und wie gesagt ich noch nie mit OCL gearbeitet habe. Entsprechend kenne ich die Möglichkeiten nicht auswendig.

Naja ich probier das einfach mal irgendwie.

@Spacerat
Ich vergesse immer wieder das wir hier über eine C-ähnliche Sprache reden. Das wäre möglich, wenn das in OpenCL denn erlaubt ist.
Eklig wäre es natürlich wenn der Zugriff auf den GPU Speicher synchronisiert ist und die CPU warten müsste.

Also wenn, dann müsste höchstens due GPU warten, oder nicht? Ich denke mal, der Speicherzugriff wird über DMA-Kanäle geregelt, wobei nur Schreib- und Lesezyklen voneinander getrennt werden müssen (sicher schon per Hardware gegeben). Eine Speicherzelle kann auf die Art von mehreren Threads gleichzeitig - solange sie nicht beschrieben wird - gelesen aber nur von einem geschrieben werden. Wenn man nur komplette Buffer lesbar machen will, müssen die Lesethreads halt warten, bis sich die Leseadresse des aktuellen Buffers ändert. In diesem Fall muss auf jedem Fall auf den Schreibthread gewartet werden, egal ob dieser auf der CPU oder der GPU läuft - Schreibvorgänge dauern nunmal länger (ist afaik immer so).
In Java (LWJGL) zumindest kann man Speicherbuffer auf der Graka mit einem Attribut (irgendwas mit STREAM_WRITE oder ähnlich) versehen und dann kann auch die CPU darin direkt schreiben. Das muss aber nicht sein, wenn man das, was die CPU machen soll einem GPU-Kern per OpenCL (oder GLSL oder ähnlichem) beibringen kann.

Ja, Sumatra ist leider „praktisch tot“ - oder hoffen wir mal: „Nur im Winterschlaf“. Selbst wenn das nicht 1:1 in der nächsten Java-Version kommt, kann man doch hoffen, dass die Erkenntnisse, die man dort (in, wenn man das dann so sehen will, einer Art „Sandkasten“) gewonnen hat, Einfluß auf Panama & Co nehmen.

„Zum Laufen bringen“. Hm. Eigentlich sollte es bei jedem aktuellen Graka-Treiber dabei sein, und es müßte dann eigentlich nichts installiert werden oder so. Zumindest sowas wie http://jocl.org/samples/JOCLDeviceQuery.java sollte „immer“ gehen…

Ähm. Die „float4“ usw. haben mit der Arraygröße nichts zu tun. Die sind nur für die Bequemlichkeit, bzw. um dem ganzen mehr „Semantik“ zu geben - oder auch ein Erbe aus dem „G“ vor dem „PU“. Ein „float4“ ist eben ein 3D-Vektor (homogene Koordinaten), und dient z.B. dazu, in einem Kernel

void kernel(float4* data) {
    // Coordinates: 
    float x = data**.x;
    float y = data**.y;
    float z = data**.z;
}

statt

void kernel(float* data) {
    // Coordinates: 
    float x = data[i*4+0];
    float y = data[i*4+1];
    float z = data[i*4+2];
}

schreiben zu können. Die C-Welt hat es da recht leicht: Da gibt’s auf der Host-Seite die passende struct, und man kann dort einfach einen

cl_float4 array[24];

erstellen. In Java geht das nicht so direkt… :frowning:

Mal etwas konkreter on topic:

und natürlich die vorangehende Diffusionsberechnung

Das dachte ich mir schon. Da bin ich mir nicht ganz sicher: Das ist ja ein inhärent sequentieller Prozess. Man kann nicht für eine beliebige Zelle (x,y) den Wert ausrechnen, wenn man nicht vorher den Wert für alle Nachbarzellen ausgerechnet hat. Und wenn man eine (1D) Diffusion hat wie


Step 0: |   |   |   |1.0|   |   |   |
Step 1: |   |   |0.5|...|0.5|   |   |
Step 2: |   |0.2|...|...|...|0.2|   |

ist das ja noch der einfachste Fall. Spätestens bei


Step 0: |   |1.0|   |   |   |1.0|   |
Step 1: |0.5|   |0.5|   |0.5|   |0.5|
Step 2: |...|...|...|XXX|...|...|...|

kommen bei „XXX“ ja Informationen von zwei Seiten zusammen. Andererseits ist das ähnlich (bzw. praktisch das gleiche) wie eine Faltung mit einem Gaußfilter, und da gibt’s natürlich einige Tricks (da es auch eine „Seperable Convolution“ ist).

Ansonsten klingt es, als wäre (oder sollte das sein) schon ein recht „getakteter“ Prozess. Also, zu beliebigen Zeitpunkten mal irgendeine Abfrage machen, ist schwierig. Es gibt noch ein paar weitere Stolpersteine. Ich habe Spacerats Beschreibung nicht genau nachvollziehen können, aber … „Pointer“ bzw. „Adressen“ speichern geht in OpenCL definitiv NICHT - es sei denn, man versteht darunter lediglich einen index in eine eigene Struktur (d.h. in einen eigenen Array).

Was mir nicht ganz klar ist, ist, wie die „Pfade“ gespeichert werden sollen. Angenommen, man hat den 2D-Array mit den diffundierten Zielen. Und man hat 1000 Aktoren. Jetzt könnte in einem Kernel (Pseudocode) sowas stehen wie

void kernel(float map[][]) {
  
    for (each actor in parallel) {
    
        while (!reachedGoal(actor))
        {
            int x = actor.x;
            int y = actor.y;
            int2 t = findSteepestGradient(map, x, y);

            // So the actor should go to map[t.x][t.y] in the next
            // step - WHERE will this be stored?
        }
    }
}

EDIT: Natürlich könnte man einfach einen
int2 path[numberOfActors][maximumPathLength]
an den Kernel übergeben, aber das „maximumPathLength“ ist etwas kritisch. Das KANN eben schon SEHR groß sein - praktisch die komplette Karte!

Für den Fall, dass das von anderen Bereichen benötigte Ergebnis nur Pixel in einem gewissen Radius benötigt, bietet es sich an, die Bereiche für die parallele Verteilung entsprechend breit überlappen zu lassen, so dass überall genug benötigte Pixel von anderen Bereichen zur Verfügung stehen.

Zumindest wurde es so etwa für einen Medianfilter gemacht, als ich (vor langer Zeit) mal mit parallel C an einer TU mit soetwas Geld verdient habe.

@Marco13
Die Rückgabe ist kein Weg wie beim klassischen A*, die AI liefert eine “bestmögliche Richtung” zurück.
Jeder Aktor übergibt seine Position (2D/3D Punkt) -> der Algorithmus berechnet für jeden Aktor eine Richtung (2D/3D Vektor).
Aber weder Algorithmus noch Aktor wissen zu irgendeinem Zeitpunkt, wohin irgendwer eigentlich gerade läuft.
Die Information ist im Array der CollDiff zwar vorhanden aber die frägt niemand ab weil sie sich ständig verändert, also auch die heuristisch berechnete “beste Richtung”.

@Crian
Kann dir leider nicht folgen.
Jede Zelle benötigt die Werte ihrer 4 oder 8 Nachbarn, ja. Du sagst jetzt man soll den Wertebereich überlappen… In OpenGL also per texelFetch();
:ka:

Hier ist mal eine grafische Darstellung der OGL AI Umsetzung bis jetzt. Sieht ganz okay aus. Das Ziel ist Rechts-Mittig.

Mit höherer Auflösung

OCL kriege ich nicht auf Android zum laufen, deshalb muss OGL erst einmal reichen.
Zur Not gäbe es noch RenderScript, das Google Konkurrenzprodukt zu OCL.

Ahja, auf Android ist OpenCL noch so eine Sache. Obwohl JOCL auch schonmal auf Android lief. (Vorcompilierte Binaries hab’ ich aber leider nicht mehr. Ich hatte nur mal ein Android-Handy von so einer Firma bekommen, aber das flackt jetzt nur noch hier rum, und anscheinend funktioniert das Touch-Display nicht mehr).

Ehrlich gesagt erschiließt sich mir jetzt aber noch etwas weniger, WAS da denn eigentlich mit 1000 Thread parallel gerechnet werden soll. Die Abfrage der 1000 Richtungen für die Aktoren wäre, wenn diese “Steigungskarte” berechnet wurde, ja einfach nur
dir = directionBetween(currentField, fieldWithLargestValue(eightNeighbors));
und da wird man auf der GPU nicht glücklich.

Und die Diffusion selbst ist zwar (wie gesagt) vermutlich recht ähnlich zu einem Gaußfilter/Convolution, aber da der Kernel (hier der Filterkernel!) so groß sein muss, wie das Spielfeld, muss man auch überlegen, ob das dann noch was bringt (und Wände muss man nachträglich als “Bereiche mit Wert 0” einzeichnen)

[QUOTE=TMII]@Crian
Kann dir leider nicht folgen.
Jede Zelle benötigt die Werte ihrer 4 oder 8 Nachbarn, ja. Du sagst jetzt man soll den Wertebereich überlappen… In OpenGL also per texelFetch();
:ka:
[/QUOTE]

Acht Nachbarn heißt vermutlich, links oben, oben, rechts oben, rechts, rechts unten, unten, links unten und links? Dann machst du alle vorher exakt geteilten Bereiche des zu berechnenden Feldes um einen Pixel breiter und brauchst keine Informationen von anderen Teilen, mit denen du dich austauschen musst.

Aber vielleicht reden wir auch schlicht aneinander vorbei, von OpenGL habe ich keine Ahnung.

[QUOTE=Crian]Acht Nachbarn heißt vermutlich, links oben, oben, rechts oben, rechts, rechts unten, unten, links unten und links? Dann machst du alle vorher exakt geteilten Bereiche des zu berechnenden Feldes um einen Pixel breiter und brauchst keine Informationen von anderen Teilen, mit denen du dich austauschen musst.

Aber vielleicht reden wir auch schlicht aneinander vorbei, von OpenGL habe ich keine Ahnung.[/QUOTE]

Ahja ich verstehe. In einem Fragment Shader jetzt nicht direkt, aber in einem Compute Shader sollte das tatsächlich in etwa umsetzbar sein, aber nicht komplett parallel soweit ich weiß.
Würde auch nicht der wissenschaftlichen Arbeit von Repenning (2006) ganz gerecht werden, aber vielleicht wird das Ergebnis sogar besser* :smiley:

*Gerade getestet noch vor dem Abschicken der Antwort, das Ergebnis bleibt ungefähr gleich. :slight_smile:

@Marco13
Ich hab mich da mal eurem Conway Shader bedient, nur etwas umgeschrieben.

/*
 * Copyright 2012, Michael Schorn (me@mschorn.net). All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification, are permitted
 * provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright notice, this list of
 *      conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright notice, this list of
 *      conditions and the following disclaimer in the documentation and/or other materials
 *      provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/*
 * 'Modified
 * Copyright 2016, TMGroup©
 */

#version 310

precision mediump float;

uniform sampler2D texture;
uniform sampler2D collision_map;

void main() {
    float c = texelFetch(collision_map, ivec2(gl_FragCoord.x, gl_FragCoord.y), 0).r;

    if( c == 0 ) {
        float n = texelFetch(texture, ivec2(gl_FragCoord.x  - 1, gl_FragCoord.y - 1), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x - 0, gl_FragCoord.y - 1), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x + 1, gl_FragCoord.y - 1), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x - 1, gl_FragCoord.y - 0), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x + 1, gl_FragCoord.y - 0), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x - 1, gl_FragCoord.y + 1), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x - 0, gl_FragCoord.y + 1), 0).r;
        n += texelFetch(texture, ivec2(gl_FragCoord.x + 1, gl_FragCoord.y + 1), 0).r;

        gl_FragColor = vec4( n * 0.125, 0, 0, 0 );
    }
    else {
        gl_FragColor = vec4( 0, 0, 0, 0 );
    }
}

Die Textur des Framebuffers wird dann per glGetTexImage zurück zur CPU beordert und „texture“ wird mit „framebufferTexture“ vertauscht und wieder gestartet.

  • Fehlt nur noch das vorher über eine 1D Textur gearbeitet wird mit den Positionen der Aktoren die dann in den Framebuffer geschrieben werden.

texelFetch(texture, ivec2(positionX, positionY), 0).r = 0;

  • Dann wird der Code oben ausgeführt über die gesamte 2D Textur.
  • Und im letzten Schritt wird dann wieder über die 1D Textur im ersten Schritt gelaufen und in einen 1D Framebuffer die Ergebnisse geschrieben und an die CPU zurückgegeben.

ivec2 neighbourIndex = getHighestNeighbour(x, y);
vec2 direction = calcDirection( x, y, neighbourIndex.x, neighbourIndex.y );
gl_FragColor.xy = direction;

  • Und im allerletzten Schritt wird dann framebuffer mit texture auf der GPU (und nicht auf der CPU) vertauscht

Der Shader stammte ausschließlich von @Fancy . Der Thread dazu ist im “falschen Forum”, da verlinke ich mal “aus Prinzip” nicht drauf.