Wie könnten Sie eine 2D-Boids-Simulation parallelisieren?

Wie könnte man eine 2D-Boids-Simulation so programmieren, dass sie Rechenleistung aus verschiedenen Quellen (Cluster, GPU) nutzt?

Im obigen Beispiel bewegen sich die nicht gefärbten Partikel, bis sie sich sammeln (gelb) und aufhören, sich zu bewegen.

Das Problem ist, dass alle Entitäten möglicherweise miteinander interagieren können, obwohl es unwahrscheinlich ist, dass eine Entität oben links mit einer Entität unten rechts interagiert. Wenn die Domain in verschiedene Segmente aufgeteilt wurde, kann dies das Ganze beschleunigen. Wenn eine Entität jedoch in ein anderes Segment wechseln möchte, kann dies zu Problemen führen.

Im Moment funktioniert diese Simulation mit 5000 Objekten mit einer guten Bildrate, ich würde dies gerne mit Millionen versuchen, wenn möglich.

Wäre es möglich, Quad-Bäume zu verwenden, um dies weiter zu optimieren? Irgendwelche anderen Vorschläge?

Die Masterarbeit Parallel Simulation of Particle Fluids von Mattias Linde bietet möglicherweise einen Einblick in die Datenaufteilung und die Algorithmen für die Großsimulation.

Sein Beitrag ist auf die Hydrodynamik geglätteter Partikel ausgerichtet , bei der für die naive Lösung in der Regel das räumliche Hashing mit einer Schaufelgröße verwendet wird, die der Größe des Kernabdrucks der Partikel in der Simulation entspricht.

Da die Interaktionsentfernung in typischen SPH-Kerneln stark eingeschränkt ist, sind solche Partitionierungsoptimierungen für die Skalierung des Systems fast unerlässlich.

Der Begriff, den ich vor langer Zeit gelernt habe, war die Informationsgeschwindigkeit eines Spiels.

Wenn die Geschwindigkeit Ihrer Boids 1 ist und sie sich nur um ihre Nachbarn kümmern, dann ist die Informationsgeschwindigkeit 3, dh ein Boid, das zwei Quadrate von Ihnen entfernt ist, könnte sich innerhalb des Bereichs befinden, den Sie innerhalb eines Frames interessieren:

1 Quadratbewegung pro Feld in der Interaktion (1 + 1) plus die Entfernung, über die Sie Dinge bemerken können (1), entspricht 3.

Ausgehend davon lernen wir, dass wir eine Karte in Stücke zerlegen können, die so klein sind, wie wir möchten, aber mit dieser Informationsgeschwindigkeit in alle benachbarten Stücke überlappen.

Ich gehe davon aus, dass Sie Ihren Boids erlauben, sich nur um ein Feld zu bewegen, aber sie können drei sehen

Wenn Sie eine massive Parallelsimulation ausführen möchten, teilen Sie diese in 10x10-Gitter auf, überlappen sich jedoch an jeder Kante mit 5 Quadraten. Immer wenn sich einer von Ihnen in der Informationsentfernung vom Rand des lokalen Chunks befindet, sollten Sie den Nachbarn aktualisieren. Sobald er die Grenze überschreitet, gehört er Ihnen nicht mehr. Wenn ein Nachbar sagt, dass ein Boid, das er kontrolliert, in Ihren Block eingezogen ist, müssen Sie dessen KI übernehmen.

Dies bedeutet, dass die Kommunikation zu den benachbarten Chunk-Managern lokalisiert wird und der Datenverkehr auf ein Minimum reduziert wird. Je mehr Jobs Sie ausführen, desto mehr CPUs können Sie für die Simulation verwenden. Je mehr Jobs Sie jedoch ausführen, desto mehr Überlappungen treten auf und desto mehr Informationen werden im Verlauf der Simulation zwischen Jobs / Chunks übertragen. Hier müssen Sie hartnäckig werden und die Blockgröße basierend auf der KI-Komplexität und der verfügbaren Hardware anpassen.

Wenn Sie Ihre Frage lesen, können Sie anscheinend Quad-Bäume nutzen, einen Quad-Baum erstellen und die Simulation für jedes Segment auf einer anderen Verarbeitungseinheit ausführen. Dies führt dazu, dass nur Objekte überprüft werden, die sich in der Nähe befinden. Sie müssen jedoch Ihre Threads in jedem Zyklus synchronisieren. Das bedeutet, dass einige dieser Boids von einer Verarbeitungsgruppe auf eine andere übertragen werden. Im Allgemeinen besteht jeder Zyklus aus 3 Schritten:

1. Bewegen Sie alle Boids um eine Einheit. (die leicht mit mehreren Threads verarbeitet werden können)
2. Zuweisen von Boids zu Gruppen *. Dies bedeutet, dass Sie mit einem Algorithmus von O (n) auswählen müssen, welche Boids am wahrscheinlichsten kollidieren. Dies kann auch mit mehreren Threads erledigt werden.
3. Am Ende muss geprüft werden, ob zwei Boids einer Gruppe kollidieren.

* Um Gruppen zu erstellen, können Sie das folgende Muster verwenden:

Beachten Sie, dass einige Boids Teil mehrerer Gruppen sein können, dieses Muster jedoch genauere Ergebnisse liefert. Sie können auch so viele Gruppen erstellen, wie Sie möchten. Mit diesem Muster müssen Sie nur eine Zahl ermitteln, um wie viele Boids und welche Bildschirmgröße und wie viele Gruppen Sie am besten erstellen müssen.

--bearbeiten--

Es gibt eine andere Idee zur Segmentierung, die in dem Artikel @LarsViklund sugested beschrieben wird. Auf diese Weise gibt es viel weniger doppelte Überprüfungen und es ist nicht erforderlich, die Anzahl der Threads zwischen den Schritten zu erhöhen / zu verringern:

Beachten Sie, dass einige Bereiche immer noch Teil von zwei Gruppen sind. und flächenbreite beider gruppenbedeckung ist genau 2*maximum speed. In Ihrem Fall, wenn Boids sich pro Simulationsschritt um ein Pixel bewegen, müssen Sie nur die 2 Pixel breite Fläche zwischen jeweils 2 Gruppen teilen. und es gibt einen kleinen Bereich, der Teil von 4 Gruppen ist. Im Allgemeinen ist diese Methode jedoch einfacher zu implementieren und bei richtiger Implementierung um ein Vielfaches schneller. Übrigens gibt es auf diese Weise keine Rückwärtsbewegung. Wenn sich ein Objekt bewegen kann, ist keine weitere Überprüfung erforderlich.

Ich habe dieses Problem kürzlich angesprochen, indem ich einige dieser Antworten als Ausgangspunkt genommen habe. Das Hilfreichste ist, dass Boids eine Art einfache N-Körper-Simulation sind: Jedes Boid ist ein Partikel, das eine Kraft auf seine Nachbarn ausübt.

Ich fand das Linde-Papier schwer zu lesen; Ich schlage stattdessen vor, SJ Plimptons "Fast Parallel Algorithms for Short-Range Molecular Dynamics" zu betrachten , auf die sich Linde bezieht. Plimptons Artikel ist weitaus lesbarer und detaillierter mit besseren Zahlen:

Kurz gesagt, ordnen Atomzerlegungsmethoden jedem Prozessor permanent eine Untergruppe von Atomen zu, Zwangszerlegungsmethoden ordnen jedem Prozess eine Untergruppe von paarweisen Kraftberechnungen zu, und räumliche Zerlegungsmethoden ordnen jedem Prozess einen Unterbereich der Simulationsbox zu .

Ich empfehle Ihnen, AD zu versuchen. Es ist am einfachsten zu verstehen und umzusetzen. FD ist sehr ähnlich. Hier ist die n-Body-Simulation von nVidia mit CUDA unter Verwendung von FD, die Ihnen eine ungefähre Vorstellung davon geben soll, wie durch Kacheln und Reduzieren die Serienleistung drastisch gesteigert werden kann.

SD-Implementierungen sind im Allgemeinen Optimierungstechniken und erfordern ein gewisses Maß an Choreografie, um sie zu implementieren. Sie sind fast immer schneller und skalieren besser.

Dies liegt daran, dass AD / FD das Erstellen einer "Nachbarliste" für jedes Boid erfordert. Wenn alle boid Bedarf die Position seiner Nachbarn wissen, ist die Kommunikation zwischen ihnen O ( n ²). Sie können Verlet Nachbarlisten verwenden , um die Größe der Fläche , die jeweils boid Kontrollen zu reduzieren, was die Liste alle paar Zeitschritte statt jedem Schritt wieder aufbauen können, aber es ist immer noch O ( n ²). In SD hat jede Zelle eine Nachbarliste, während in AD / FD jede Zelle eine Nachbarliste hat. Anstatt also jedes Boid miteinander zu kommunizieren, kommuniziert jede Zelle miteinander. Diese Reduzierung der Kommunikation ist der Grund für die Geschwindigkeitssteigerung.

Leider sabotiert das Boids-Problem die SD etwas. Es ist am vorteilhaftesten, wenn jeder Prozessor den Überblick über eine Zelle behält, wenn die Boids über die gesamte Region verteilt sind. Aber Sie möchten, dass sich Boids zusammenballen! Wenn sich Ihre Herde richtig verhält, tickt die überwiegende Mehrheit Ihrer Prozessoren ab und tauscht leere Listen miteinander aus. Eine kleine Gruppe von Zellen führt dann dieselben Berechnungen wie AD oder FD durch.

Um dies zu bewältigen, können Sie entweder die Größe der Zellen (die konstant ist) mathematisch anpassen, um die Anzahl der leeren Zellen zu einem bestimmten Zeitpunkt zu minimieren, oder den Barnes-Hut-Algorithmus für Quad-Bäume verwenden. Der BH-Algorithmus ist unglaublich leistungsfähig. Paradoxerweise ist die Implementierung auf parallelen Architekturen äußerst schwierig. Dies liegt daran, dass ein BH-Baum unregelmäßig ist und daher von parallelen Threads mit sehr unterschiedlichen Geschwindigkeiten durchlaufen wird, was zu einer Thread-Divergenz führt. Salmon und Dubinski haben orthogonale rekursive Bisektionsalgorithmen vorgestellt, um die Quadtrees gleichmäßig auf die Prozessoren zu verteilen. Diese müssen für die meisten parallelen Architekturen iterativ angepasst werden.

Wie Sie sehen, befinden wir uns an dieser Stelle eindeutig im Bereich der Optimierung und der schwarzen Magie. Versuchen Sie erneut, Plimptons Zeitung zu lesen, und prüfen Sie, ob dies sinnvoll ist.

Ich gehe davon aus, dass es sich bei Ihrem System um ein toroidales System handelt. Sie können es in den Raum unterteilen, sodass jede Einheit ihren Unterbereich hat.

Bei jedem Schritt werden die Partikel bewegt, und die Partikel, die den Unterbereich verlassen, werden an den entsprechenden Prozessor gesendet. In einem Kommunikationsschritt werden die Prozessoren synchronisiert und in einem letzten Schritt die Position der Fremdpartikel (falls vorhanden) ermittelt.

Hier gibt es drei Probleme:

• 1) die Form des Unterbereichs:

Man kann sich für Rechtecke entscheiden, aber die zeigen ein kleines Verhältnis von Fläche zu Umfang im Vergleich zu Rillen. Je größer die Grenze, desto mehr Partikel werden austreten. Während die Cicles das beste A / P-Verhältnis aufweisen, können sie nicht für die Tessellation verwendet werden. Sie sollten sich daher für eine (möglicherweise halb regelmäßige) Tessellation mit einem guten durchschnittlichen A / P-Verhältnis entscheiden. Offensichtlich sollte es einfach sein, den Quastenindex nach Zellkoordinaten zu berechnen. Überlegen Sie sich dies, bevor Sie eine sehr exotische Quaste versuchen.

• 2) das Kommunikationsprotokoll:

Je nachdem, über welche Kommunikationsinfrastruktur Sie verfügen, können Sie überlegen, wie Sie die grenzüberschreitenden Informationen auf die Prozessoren verteilen. Broadcasting vs. Peer-to-Peer-Rekonstruktion vs. Peer-to-Peer-Kommunikation sind alle Optionen.

• 3) die Untergebietszuordnung:

Sie sollten Ihre Ausarbeitung im Gleichgewicht halten, da bei jedem Schritt eine Synchronisation stattfindet. Sie können festlegen, ob den Prozessoren Bereiche statisch oder dynamisch zugewiesen werden sollen. Dies ist kein großes Problem, wenn Ihr Raum gleichmäßig von aktiven Partikeln bedeckt ist. Ich glaube jedoch, dass dies in diesem Fall unwahr sein kann, da Kollisionen die Partikel deaktivieren. Das Ändern der Zuordnung erfordert einen schwereren Kommunikationsschritt. Einige Verknüpfungen können verwendet werden, wenn alle Prozessoren die grenzüberschreitenden Informationen gemeinsam nutzen, Sie dies jedoch berücksichtigen müssen

Probieren Sie meine Simulation für Hinweise https://github.com/wahabjawed/Boids-Simulation

Ich habe das auf XNA entwickelt