Wie kann das gravitative N-Körper-Problem parallel gelöst werden?

25

Wie kann das gravitative n-Körper-Problem numerisch parallel gelöst werden?

Ist ein Kompromiss zwischen Präzision und Komplexität möglich?

Wie beeinflusst Präzision die Qualität des Modells?

Sklavit
quelle
Dieses Dokument beschreibt mögliche Implementierungen mit OpenMP.
Geremia

Antworten:

27

Es gibt eine Vielzahl von Algorithmen; Barnes Hut ist eine beliebte -Methode, und die Fast Multipole-Methode ist eine viel ausgefeiltere O ( N ) -Alternative.O(NlogN)O(N)

Beide Methoden verwenden eine Baumdatenstruktur, bei der Knoten im Wesentlichen nur mit ihren nächsten Nachbarn auf jeder Ebene des Baums interagieren. Sie können sich vorstellen, den Baum in ausreichender Tiefe zwischen den Prozessen aufzuteilen und sie dann nur auf höchster Ebene zusammenarbeiten zu lassen.

Sie können ein aktuelles Papier diskutieren FMM auf Petascale Maschinen finden hier .

Jack Poulson
quelle
2
BH, auch Tree-Code genannt, scheint bei geringer Genauigkeit vorzuziehen zu sein. Hier ist ein Papier , wo die Methoden adaptiv kombiniert werden, aber ich habe nicht diese Arbeit in der Praxis noch nicht gesehen.
Matt Knepley
8

Als alternative Quelle können Sie sich auch mesh-basierte Ewald-ähnliche Methoden ansehen. Die Entstehung der "Particle Mesh" -Methoden (wie PPPM und Smoothed Particle Mesh Ewald) liegt in der Simulation von Galaxien für die Astrophysik; Die Verbindung zu Gebühren war eine unbeabsichtigte Nebenwirkung (die zufällig die ursprüngliche Verwendung überholte).

In jüngerer Zeit gab es auch Literatur zu mehrstufigen Summationsmethoden, die dem Geist nach den schnellen Multipolmethoden und der Barnes-Hut ähneln, jedoch unter verschiedenen Umständen Vorteile bieten können (allgemeinere und flexiblere Geometrien, einige Effizienzgewinne usw.).

Aeismail
quelle
8

Für das klassische Gravitations-n-Körper-Problem denke ich, dass die folgenden beiden Arbeiten gute Arbeit leisten, um den Mut der parallelen Implementierung für den Kraftbewertungsschritt zu diskutieren. Obwohl in den Beiträgen eine GPU-Implementierung erörtert wird, können sie die Parallelität gut diskutieren und Details zu den Algorithmen bereitstellen:

In diesem Artikel von Nyland, Harris und Prins wird der direkte N-Body-Algorithmus in CUDA für GPUs vorgestellt.

Diese andere Veröffentlichung von Yokota und Barba enthält eine gute Diskussion über den Treecode- und den schnellen Multipol-Algorithmus, auch im Zusammenhang mit GPU-Computing

Ihre Fragen zur Genauigkeit numerischer n-Körper-Simulationen sind etwas komplizierter und es gibt so viele wichtige Details, dass eine Antwort mehrere Bücher hervorbringen kann. Ich denke, das Beste, was Sie tun können, ist, Ihnen ein paar Buchreferenzen zu geben. Ich schlage vor:

Gravitations-N-Körpersimulationen von Sverre J. Aarseth

Computersimulationen mit Partikeln von Hockney und Eastwood. (Sorry, keine pdf-Version)

fcruz
quelle
4

Wenn Sie einen einfachen Implementierungsansatz benötigen, der im asymptotischen Sinne nicht optimal ist, sollten Sie die Verwendung von All-Gather-Kommunikationsoperationen in Betracht ziehen. Da jeder der N-Körper den Gravitationseffekt der anderen Körper kennen muss, ist es für jeden Prozessor wichtig, den gesamten Datensatz zu kennen. Dies ist die Aufgabe von All-Gather-Operationen. Es gibt ein gutes Buch: Parallel Programming in C mit MPI und OPENMP von Michael J. Quinn (2004), in dem genau dieses Thema auf Seite 82 behandelt wird.

Paul
quelle
3
O(n2)
Das ist richtig. Obwohl dies, wie bereits erwähnt, eine einfache und nicht unbedingt effiziente Implementierung ist.
Paul
+1 Irgendwie gehen alle anderen Antworten davon aus, dass das OP nach tera- oder petascale-Leistung sucht. FMM und Ähnliches sind nur sinnvoll, wenn sie eher naiven Ansätzen entgegenstehen.
Stefano M
1

Besuchen Sie Google Scholar und suchen Sie unter anderem nach Verweisen auf HACC und GADGET.

Jeff
quelle
2
Können Sie etwas näher erläutern, warum Sie HACC und GADGET empfehlen?
Paul
1
Sie sind beide hochkarätige Kosmologie-Codes, die Schwerkraftlöser enthalten.
Jeff