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

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?

Istnieje wiele różnych algorytmów; Barnes Hut jest popularną metodą , a szybka metoda wielobiegunowa jest znacznie bardziej wyrafinowaną alternatywą O ( N ) .$\mathcal{O}(N \log N)$$\mathcal{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 .

Spójrz na szybką metodę wielobiegunową . Jest wysoce skalowalny i . Pozwala na kompromis między precyzją a kosztami. Oto przykład, w którym jest uruchamiany przy 42 Tflops w klastrze GPU .$O(n)$

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.).

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)

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.

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