Odpowiedzi:
Istnieje wiele różnych algorytmów; Barnes Hut jest popularną metodą , a szybka metoda wielobiegunowa jest znacznie bardziej wyrafinowaną alternatywą 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 .
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.