Parallele N-Körper Simulation

Ulf

Hallo,

ich bin dabei eine N-Körper Simulation zu schreiben und würde sie gerne parallelisieren. Doch egal, ob ich den einfachen Euler- oder den Bernes-Hut Algorithmus nehme, sehe ich nicht, wie ich das ganze effektiv parallelisieren kann.

Ich habe jeweils einen Container (vector), der die Pointer auf die zu simulierenden Objekte enthält. Wenn ich die Berechnung der Wechselwirkungen auf ein paar Threads aufteile, dann hätte ich zwei Möglichkeiten: Ich erstelle für jeden Thread eine Kopie aller Objekte und lasse sie dann rechnen, oder ich lasse alle Threads mit den gleichen Objekten arbeiten und sichere mich dann mit Mutex ab, dass die nicht zeitgleich auf die Objekte zugreifen.

Ersteres würde einen wahnsinnigen Kopieraufwand bedeuten (das mag beim Euler vielleicht noch gehen, beim viel schnelleren Bernes-Hut Algo müsste ich aber jeweils noch die ganze Baumstruktur erzeugen), letzteres wäre durch die zahlreichen Mutex-Verwendung tatsächlich noch viel langsamer.

Habt ihr eine Idee, wie man das effektiv gestalten kann?

nevermore

Witzig, genau darüber hab ich morgen eine Prüfung. Vielleicht hilft dir mein Lernmaterial: http://people.inf.ethz.ch/iyves/pnc12/slides/11.pdf (ab Folie 38)

Ulf schrieb:

Ersteres würde einen wahnsinnigen Kopieraufwand bedeuten (das mag beim Euler vielleicht noch gehen, beim viel schnelleren Bernes-Hut Algo müsste ich aber jeweils noch die ganze Baumstruktur erzeugen), letzteres wäre durch die zahlreichen Mutex-Verwendung tatsächlich noch viel langsamer.

Habt ihr eine Idee, wie man das effektiv gestalten kann?

Die Idee, die auch oben in den verlinkten Folien beschrieben ist, ist dass du beim Barnes-Hut nicht immer den kompletten Baum kopieren musst. Du musst nur jedem Prozessor einen Teilbaum des kompletten Baumes geben (Locally Essential Tree, LET). Nur so viel, wie du eben brauchst. Damit das funktioniert, musst du die Partikel so auf die Prozessoren verteilen, dass räumlich nahe Partikel auf dem gleichen Prozessor landen.

nevermore

Ne Blödsinn. Du willst ja mit Threads arbeiten. Das was ich geschrieben haben würde man auf einem Distributed Memory System machen.

Auf einem Shared Memory System gibst du einfach jedem Thread N/p Partikel und lässt sie die Wechselwirkungen parallel berechnen. Du musst überhaupt nichts kopieren. Auf den Baum greifst du ja nur read-only zu. Und den Vektor musst du nicht mit einem Mutex schützen, weil jeder Thread greift ja nur auf seine eigenen Partikel zu.

Ulf

Ich danke dir schonmal.

Ich dachte, ich benötige Mutex unabhängig von der Art des Zugriffs. Passiert da nichts bei read only? Das wäre natürlich toll.

und was passiert, wenn ein Thread sein Teilchen gerade ändert und ein anderer Thread will gleichzeitig darauf (read only) zugreifen?
Notfalls könnte man auch nur das Schreiben mit Mutex sichern, das wäre natürlich auch schon ein gewaltiger Fortschritt.

knivil

Dir fehlen Grundlagen. Schon mal "Game of Life" programmiert? Wie wuerdest du das parallelisieren? Oder schon mal eine Grafikanwendung programmiert? Der Trick ist Double Buffering. Man liest aus dem einen und schreibt Ergebnisse in den anderen. Fuer den darauffolgenden Schritt liest man nur aus dem anderen und schreibt in den einen.

nevermore

Ulf schrieb:

Ich danke dir schonmal.

Ich dachte, ich benötige Mutex unabhängig von der Art des Zugriffs. Passiert da nichts bei read only? Das wäre natürlich toll.

Von mehreren Threads lesen ist kein Problem.

Ulf schrieb:

und was passiert, wenn ein Thread sein Teilchen gerade ändert und ein anderer Thread will gleichzeitig darauf (read only) zugreifen?

Das geht nicht! Das ist besonders gefährlich weil es manchmal tatsächlich funktionieren könnte und du dann den Fehler nicht bemerkst -- bei der nächsten Ausführung fragst du dich dann, woher der Fehler kam.

Am einfachsten ist dein Problem in zwei Schritten zu lösen:

Parallel für alle Partikel die einwirkende Kraft berechnen und in einem Kraft-Vektor forces speichern. Dabei greifst du nur lesend auf den Tree/die Partikel zu.
Im zweiten Schritt dann dann parallel den forces Vektor lesen und die Partikel gemäß der Kraft bewegen. Also forces lesen, positions schreiben.

Wenn du z.B. OpenMP verwendest, ist das ziemlich trivial.

Ulf

Ich danke euch, es klappt nun wunderbar.