Jak można rozwiązać problem grawitacyjnego n-ciała równolegle?

25

Jak można rozwiązać problem grawitacyjnego n-ciała równolegle numerycznie?

Czy możliwy jest kompromis precyzji i złożoności?

Jak precyzja wpływa na jakość modelu?

Sklavit
źródło
W tym artykule opisano możliwe implementacje z OpenMP.
Geremia

Odpowiedzi:

27

Istnieje wiele różnych algorytmów; Barnes Hut jest popularną metodą , a szybka metoda wielobiegunowa jest znacznie bardziej wyrafinowaną alternatywą O ( N ) .O(N.logN.)O(N.)

Obie metody wykorzystują strukturę danych drzewa, w której węzły zasadniczo oddziałują tylko z najbliższymi sąsiadami na każdym poziomie drzewa; możesz pomyśleć o podzieleniu drzewa na zestaw procesów na wystarczającej głębokości, a następnie umożliwieniu im współpracy tylko na najwyższych poziomach.

Najnowszy artykuł omawiający FMM na maszynach petascale znajduje się tutaj .

Jack Poulson
źródło
2
BH, zwany także kodem drzewa, wydaje się być preferowany przy niskiej dokładności. Oto artykuł, w którym metody są łączone adaptacyjnie, ale nie widziałem jeszcze tej pracy w praktyce.
Matt Knepley,
8

Jako alternatywne źródło można również przyjrzeć się metodom typu Ewald opartym na siatce. Geneza metod „siatki cząstek” (takich jak PPPM i wygładzona siatka cząstek Ewald) polega na symulacji galaktyk dla astrofizyki; połączenie z opłatami było niezamierzonym efektem ubocznym (który akurat w końcu wyprzedził pierwotne użycie).

Niedawno pojawiła się również literatura na temat wielopoziomowych metod sumowania, które są podobne w duchu do szybkich metod wielobiegunowych i Barnes-Hut, ale mogą oferować zalety w różnych okolicznościach (bardziej ogólna i elastyczna geometria, pewne zwiększenie wydajności itp.).

eeismail
źródło
8

W przypadku klasycznego problemu grawitacyjnego n-ciała uważam, że następujące dwa artykuły dobrze się spisują w dyskusji na temat odwrotnej implementacji dla kroku oceny siły. Chociaż dokumenty omawiają implementację GPU, wykonują dobrą robotę, omawiając równoległość i podają szczegóły dotyczące algorytmów:

Ten artykuł autorstwa Nyland, Harris i Prins przedstawia algorytm bezpośredniego n-ciała w CUDA dla procesorów graficznych.

Ten drugi artykuł autorstwa Yokoty i Barby zawiera dobrą dyskusję na temat kodu treec i szybkiego algorytmu wielobiegunowego, również w kontekście obliczeń na GPU

Twoje pytania dotyczące dokładności symulacji numerycznych n-ciała są nieco bardziej zaangażowane i istnieje tak wiele ważnych szczegółów, że odpowiedź może zrodzić kilka książek. Myślę, że najlepiej pomyśleć o podaniu kilku odniesień do książek. Sugeruję:

Grawitacyjne symulacje N-ciała Sverre J. Aarseth

Symulacje komputerowe z wykorzystaniem cząstek Hockneya i Eastwooda. (Niestety brak wersji pdf)

fcruz
źródło
4

Jeśli potrzebujesz prostego podejścia do implementacji, które nie jest optymalne w sensie asymptotycznym, możesz rozważyć użycie operacji komunikacji typu all-gather. Ponieważ każde z ciał N musi znać działanie grawitacyjne innych ciał, każdy procesor musi znać cały zestaw danych. To właśnie robią operacje zbierania. Jest dobra książka: Programowanie równoległe w C z MPI i OPENMP autorstwa Michaela J. Quinna (2004), która dokładnie omawia ten temat na stronie 82. Warto zacząć od początku.

Paweł
źródło
3
O(n2))
To prawda. Chociaż, jak powiedziałem wcześniej, jest to łatwa implementacja, niekoniecznie wydajna.
Paweł
+1 w jakiś sposób wszystkie inne odpowiedzi zakładają, że PO szuka wydajności tera lub petascale. FMM i akin mają sens tylko w przeciwieństwie do bardziej naiwnych podejść.
Stefano M
1

Zobacz Google Scholar i poszukaj odniesień do HACC i GADGET, między innymi kodami.

Jeff
źródło
2
Czy możesz dodać trochę więcej szczegółów na temat tego, dlaczego polecasz HACC i GADŻET?
Paweł
1
Oba są głośnymi kodami kosmologicznymi, które obejmują solwery grawitacyjne.
Jeff