Jak można równolegle przeprowadzić symulację boidów 2D

Jak można zaprogramować symulację boidów 2D w taki sposób, aby mogła ona wykorzystywać moc obliczeniową z różnych źródeł (klastry, GPU).

W powyższym przykładzie bezbarwne cząstki poruszają się, aż skupią się (żółte) i przestaną się poruszać.

Problem polega na tym, że wszystkie byty mogłyby potencjalnie oddziaływać na siebie, chociaż jest mało prawdopodobne, aby istota w lewym górnym rogu współdziałała z jedną w prawym dolnym rogu. Jeśli domena została podzielona na różne segmenty, może to wszystko przyspieszyć, ale jeśli jednostka chciała przejść do innego segmentu, mogą wystąpić problemy.

W tej chwili ta symulacja działa z 5000 jednostek z dobrą częstotliwością klatek, chciałbym spróbować z milionami, jeśli to możliwe.

Czy byłoby możliwe wykorzystanie drzew quadów do dalszej optymalizacji? Jakieś inne sugestie?

Praca magisterska Parallel Simulation of Particle Fluids autorstwa Mattiasa Linde może dać pewien wgląd w partycjonowanie danych i algorytmy do symulacji na dużą skalę.

Jego praca jest skierowana do hydrodynamikę cząstek wygładzonych , która w naiwnym rozwiązaniu ma tendencję do używania funkcji Hashing przestrzenny z wielkością wiadra mniej więcej wielkości śladu jądra cząstek w symulacji.

Ponieważ odległość interakcji jest mocno ograniczona w typowych jądrach SPH, takie optymalizacje partycjonowania są prawie niezbędne w skalowaniu systemu.

Termin, którego nauczyłem się dawno temu, był szybkością informacji w grze.

Jeśli prędkość twoich boidów wynosi 1 i troszczą się tylko o swoich sąsiadów, wtedy prędkość informacji wynosi 3, to znaczy boid, który jest dwa kwadraty od ciebie, może znajdować się w zasięgu, na którym ci zależy w obrębie jednej klatki:

1 ruch kwadratowy na boid w interakcji (1 + 1) plus odległość, którą możesz zauważyć (1), wynosi 3.

Biorąc to pod uwagę, dowiadujemy się, że możemy podzielić mapę na kawałki, tak małe, jak nam się podoba, ale z tą prędkością informacji nakładają się na sąsiednie fragmenty.

Zakładam, że pozwalasz swoim boidom poruszać się tylko o jedno pole, ale widzą trzy

Jeśli chcesz uruchomić masywną równoległą kartę SIM, podziel się na 10x10 siatek, ale nakładaj się na 5 kwadratów na każdej krawędzi. Ilekroć jeden z twoich ludzi znajdzie się w odległości informacyjnej od krawędzi lokalnego fragmentu, powinieneś zaktualizować sąsiada, a gdy przekroczy on granicę, nie należy do ciebie. Jeśli sąsiad twierdzi, że kontrolowany przez niego boid przeniósł się do twojej części, musisz przejąć jego sztuczną inteligencję.

Oznacza to, że komunikacja jest zlokalizowana dla sąsiednich menedżerów porcji, a ruch jest ograniczony do minimum. Im więcej uruchomionych zadań, tym więcej procesorów można użyć do zasilania symulacji, ale im więcej uruchomionych zadań, tym bardziej się one pokrywają, a zatem im więcej informacji przechodzi między zadaniami / porcjami w miarę postępu symulacji. W tym miejscu musisz ciężko pracować i dostroić rozmiar porcji na podstawie złożoności sztucznej inteligencji i dostępnego sprzętu.

Po przeczytaniu swojego quesitonu wydaje się, że możesz skorzystać z drzewa quad, stworzyć drzewo quad i uruchomić symulację dla każdego segmentu na innym urządzeniu przetwarzającym. Spowoduje to, że sprawdzanie nastąpi tylko w przypadku obiektów blisko siebie. ale musisz synchronizować wątki w każdym cyklu. Co oznacza przeniesienie niektórych z tych boidów z jednej grupy przetwarzania do drugiej. ogólnie każdy cykl składa się z 3 kroków:

1. Przenieś wszystkie pociski o jedną jednostkę. (które można łatwo przetwarzać za pomocą wielu wątków)
2. Przypisywanie każdego boid do grupy *. Oznacza to, że używając algorytmu O (n) musisz wybrać, które boidy najprawdopodobniej spowodują kolizję. Można to również obsłużyć za pomocą wielu wątków.
3. Na koniec musisz sprawdzić, czy dwa boidy w tej samej grupie zderzyły się.

* Aby utworzyć grupy, możesz użyć poniższego wzoru:

zwróć uwagę, że niektóre boidy mogą należeć do więcej niż jednej grupy, ale ten wzór daje dokładniejsze wyniki. możesz również utworzyć tyle grup, ile chcesz, używając tego wzorca. Jest to tylko liczba, którą musisz znaleźć dla ilu boidów i ekranu, jaki rozmiar ekranu, jaka jest najlepsza liczba grup, którą musisz utworzyć.

--edytować--

istnieje inny pomysł na segmentację, który jest opisany w artykule @LarsViklund sugerowanym, w ten sposób jest o wiele mniej podwójnych kontroli i nie ma potrzeby zwiększania / zmniejszania liczby wątków między krokami:

zwróć uwagę, że niektóre obszary są nadal częścią dwóch grup. i szerokość obszaru, który obejmuje obie grupy 2*maximum speed. W twoim przypadku, jeśli pociski poruszają się o jeden piksel na krok symulacji, musisz tylko podzielić obszar o szerokości 2 pikseli między każdą 2 grupę. i jest mały obszar, który jest częścią 4 grup. ale ogólnie rzecz biorąc, ta metoda jest łatwiejsza do wdrożenia i zdecydowanie szybsza, jeśli jest poprawnie wdrożona. a przy okazji, nie ma ruchu wstecznego w ten sposób, jeśli jakiś obiekt może się poruszać, może się poruszać, nie jest już wymagane sprawdzanie.

Ostatnio rozwiązałem ten problem, wykorzystując niektóre z tych odpowiedzi jako punkt wyjścia. Najbardziej pomocną rzeczą, o której należy pamiętać, jest to, że boidy są rodzajem prostej symulacji n-ciała: każda boid jest cząsteczką, która wywiera siłę na sąsiadów.

Trudno mi było przeczytać artykuł Linde; Zamiast tego sugeruję spojrzenie na „Szybkie równoległe algorytmy SJ Plimpton dla dynamiki molekularnej bliskiego zasięgu” , do których nawiązał Linde. Artykuł Plimpton jest o wiele bardziej czytelny i szczegółowy z lepszymi danymi:

W skrócie, metody dekompozycji atomów przypisują na stałe podzbiór atomów do każdego procesora, metody dekompozycji sił przypisują podzbiór par obliczeń siły do ​​każdego proc, a metody dekompozycji przestrzennej przypisują podregion pola symulacji do każdego proc .

Polecam spróbować AD. Jest najłatwiejszy do zrozumienia i wdrożenia. FD jest bardzo podobny. Oto symulacja n-ciała nVidii z CUDA przy użyciu FD, która powinna dać ogólny obraz tego, w jaki sposób kafelkowanie i redukcja mogą znacznie przewyższyć wydajność szeregową.

Implementacje SD są ogólnie technikami optymalizacji i wymagają pewnego stopnia choreografii do wdrożenia. Są prawie zawsze szybsze i lepiej skalowalne.

Wynika to z faktu, że AD / FD wymaga zbudowania „listy sąsiadów” dla każdego boid. Jeśli każdy boid musi znać pozycję swoich sąsiadów, komunikacja między nimi to O ( n ²). Możesz użyć list sąsiadów Verlet, aby zmniejszyć rozmiar obszaru, który sprawdza każdy boid, co pozwala przebudowywać listę co kilka kroków czasowych zamiast każdego kroku, ale nadal jest to O ( n ²). W SD każda komórka utrzymuje listę sąsiadów, podczas gdy w AD / FD każdy boid ma listę sąsiadów. Więc zamiast każdego boidu komunikującego się ze sobą, każda komórka komunikuje się ze sobą. To zmniejszenie komunikacji jest przyczyną wzrostu prędkości.

Niestety problem boidów nieznacznie sabotuje SD. Śledzenie komórki przez każdy procesor jest najbardziej korzystne, gdy boidy są nieco równomiernie rozmieszczone w całym regionie. Ale chcesz, aby klastry łączyły się razem! Jeśli twoje stado zachowuje się prawidłowo, znaczna większość twoich procesorów będzie tykała, wymieniając między sobą puste listy, a mała grupa komórek zakończy te same obliczenia, które wykonałyby AD lub FD.

Aby sobie z tym poradzić, możesz albo matematycznie dostroić rozmiar komórek (który jest stały), aby zminimalizować liczbę pustych komórek w danym momencie, lub użyć algorytmu Barnes-Hut dla quadów. Algorytm BH jest niezwykle potężny. Paradoksalnie niezwykle trudne jest wdrożenie na architekturach równoległych. Wynika to z faktu, że drzewo BH jest nieregularne, więc równoległe wątki będą je przechodzić z bardzo różnymi prędkościami, powodując rozbieżność nici. Salmon i Dubiński przedstawili ortogonalne rekurencyjne algorytmy bisekcji, aby równomiernie rozdzielić kwadraty między procesory, które muszą być powtórzone iteracyjnie dla większości równoległych architektur.

Jak widać, w tym momencie jesteśmy wyraźnie w dziedzinie optymalizacji i czarnej magii. Ponownie spróbuj przeczytać artykuł Plimptona i sprawdź, czy ma to jakiś sens.

Zakładam, że twój jest systemem toroidalnym, możesz podzielić na przestrzeń, aby każda jednostka miała swój obszar podrzędny.

Na każdym etapie cząstki są przenoszone, cząstki wychodzące z podobszaru są wysyłane do odpowiedniego procesora; krok komunikacji zsynchronizuje procesory i podejmowany jest ostatni krok po kroku w celu opracowania pozycji obcych cząstek (jeśli występują).

Tutaj są trzy problemy:

• 1) kształt podobszaru:

Można wybrać prostokąty, ale pokazują mały stosunek powierzchni do obwodu w porównaniu do cirlces. Im większa granica, tym więcej cząstek opuści. Podczas gdy cykle wykazują najlepszy stosunek A / p, nie można ich używać do teselacji, więc powinieneś przebadać niektóre (prawdopodobnie częściowo regularne) teselacje z dobrym średnim współczynnikiem A / p. Oczywiście obliczenie wskaźnika pomponu na podstawie współrzędnych komórki powinno być proste, więc zastanów się nad tym przed wypróbowaniem bardzo egzotycznego pompowania.

• 2) protokół komunikacyjny:

W zależności od posiadanej infrastruktury komunikacyjnej możesz zastanowić się, jak rozproszyć informacje o przekraczaniu granicy między procesorami. Nadawanie i rekonstrukcja peer-to-peer vs. komunikacja peer-to-peer to wszystkie opcje.

• 3) Przydział podobszarów:

Powinieneś zachować równowagę swojego opracowania, ponieważ na każdym kroku występuje synchronizacja. Możesz wybrać statyczne lub dynamiczne przydzielanie obszarów procesorom. Nie jest to duży problem, jeśli twoja przestrzeń jest jednorodnie pokryta przez aktywne cząstki, ale wierzę, że w tym przypadku może to być nieprawda, ponieważ kolizje dezaktywują cząstki. Zmiana alokacji wymaga cięższego kroku komunikacji; niektóre skróty można zastosować, jeśli wszystkie procesory współużytkują informacje transgraniczne, ale trzeba o tym pomyśleć

Wypróbuj moją symulację, aby uzyskać wskazówki https://github.com/wahabjawed/Boids-Simulation

Opracowałem to na XNA