Hallo Stefan, Bernhard, ...
ich hatte nur wenig Zeit, daher die geringe Beteiligung meinerseits.
Zu SSE, damit habe bisher nur die negative Erfahrung gemacht, dass bei mir nur noch einfache statt doppelte Genauigkeit erzielt wurde, obwohl Hard- und Software angeblich SSE mit double Genauigkeit unterstützen sollten.
Zur Geschwindigkeit, bei mir kostet, wenn ich mich richtig entsinne, das Wurzelziehen beim Berechnen der Entfernungen ca. 40% der gesamten Rechenzeit. Daher speichere ich die Entfernungen in einer Matrix und berechne nur etwas weniger als die Hälfte, da die Entferungen symmetrisch sind.
Zur Parallelisierung gibt es mehrere Möglichkeiten:
Erstens kann man natürlich die Berechnung der Kräfte parallelisieren, da dies am längsten dauert. Dies sollte unabhängig vom algorithmus möglich sein. Der Nachteil ist natürlich, dass das nur für eine große Anzahl von Körpern günstig ist, da sonst der Overhead zu groß wird.
Zweitens kann man beim BS die Berechnungen für eine großen Zeitschritt mit den einzelnen Teilzeitschritten unabhängig von einander ausführen, das keine Ergebisse beim anderen benötigt werden.
Falls man den Kern bestimmen kann, auf welchen die jeweilen Teilprobleme gelöst werden kann eine optimale Beschleunigung erzielt werden.
Für 4 Kerne wäre die Aufteilung so:
Kern 0: 3 schritte + 4 Schritte
Kern 1: 2 Schritte + 5 Schritte
Kern 2: 1 Schritt+ 6 Schritte
Kern 3: 7 Schritte
Nach 7 Zeitschritten, d.h. nach 7 Berechnungen der Entfernungsmatrix ist jeder Kern fertig und die Extrapolation (nichtparallelisert, da im Vergleich zur Berechnung der Entfernungen/Kräfte schnell) kann beginnen.
Wenn man nur 3 Kerne hat, oder nutzen möchte damit man während der Rechnung noch was anderen machen kann, kann man die 7 Schritte weglassen und dadurch etwas weniger extrapolieren. Man wird etwas kürzere Zeitschritte nehmen müssen. Bei 2 Kernen legt man das, was bei 4 Kernen 2 tun zusammen.
Bei 4 Kernen hat man nun pro großem Schritt nur 7 Kraftberechnungen pro Kern statt 28. Bei 3 Kernen sind es 7 statt 21 und bei 2 Kernen sind es 14 statt 28, also optimal.
Wenn man den Kern nicht bestimmen kann, auf dem die Teilberechnungen ausgeführt werden, kann man nur hoffen, dass das Betriebssystem beim Verteilen keinen zu großen Blödsinn macht. Evtl. könnte man durch Veränderung der Reihenfolge der Starts der Berechnungen (z.b. 7 1 2 3 6 5 4 oder so) versuchen Einfluss zu nehmen.
Drittens gibt es natürlich noch die "poor man's" Parallelisierung. Wenn man ohnehin das Programm mehrmals mit verschiedenen Startwerten oder Parametern starten will, startet man das Programm mehrfach gleichzeitig mit diesen Werten.
Bei der Simmulation der Planetenentstehung gibt es den Trick, den Radius der Körper (die Sonne aber nicht, oder nicht so stark) zu vergrößern und so durch häufigere Kollisionen die notwendige Zeit zu verkürzen. In wie weit das da aber unrealisitsch wird, weiss ich nicht. Aber zum Testen oder erste, schnelle Ergebnisse könnte man das einsetzen. Vielleicht am Anfang um einen Faktor 100, (bei der Sonne nicht oder maximal Faktor 10). Das dürfte dann fast 10000mal schneller gehen.
Adaptive Zeitschritte sind bei BS sehr einfach und kosten keine Zeit, da mit dem Unterschied zwischen k und k-1 Extrapolationsschritten ein Fehlerschätzer gratis zur Verfügung steht. Ich denke, dass bei Kollisionen oder beinahe Kollisionen adaptive Zeitschritte notwendig sind.
Bei der adaptive Zeitschrittweite könnte man z.B. 3 Fehlerschranken angeben 0<f1<f2<f3.
Ist der Fehler kleiner als f1 wird der Schritt zwar akzeptiert, aber die Zeitschrittweite im nächsten Schritt etwas vergrößert. Zwischen f1 und f2 ist alles ok, schrittweite bleibt. Zwischen f2 und f3 wird ge eben gemachte Schritt zwar akzeptiert, aber die Zeitschrittweite im nächsten Schritt etwas verkleinert. Ist der Fehler größer als f3 muss der eben berechnet Zeitschritt verworfen und mit einer kleineren Schrittweite wiederholt werden (zur not mehrfach, bis der Fehler nicht mehr größer als f3 ist).
Durch den Zusatzterm wird ermöglicht nahe Vorbeigänge ohne Reduktion der Zeitschrittweite zu berechnen, ohne dass man bei der Kraftberechnung fast durch 0 teilt und im nächsten Schritt der Körper unter hohem unphysikalischem Energiegewinn davon schießt. Im Prinzip wird die Punktmasse dabei über ein größeres Gebiet "vermatscht". Das verhindert die grobe Verletzung des Enegieerhltungssatzes in der Simulation, aber der Stoßwinkel bleibt immer noch falsch. Er ist daher nur für statistische Betrachtungen bei Sternhaufen oder Galaxien geeignet, nicht aber wenn es auf individuelle Körper ankommt.
Sogenannte "Symplectic Integrators" werden verwendet, wenn sich die Bahnen gut durch ein Keplerproblem + kleine Störungen beschreiben lassen. Dann wird das Keplerproblem "exakt" gelöst und nur über die kleinen Störungen integiert. Das ist sehr gut, solange die kleinen Störungen wirklich klein sind. Bei näheren Begegnungen muss dann auf einen anderen Integrator z.B. BS umgeschaltet werden, weil es sonst zu ungenau wird.
BS ist dagegen universell einsetzbar und leichter zu implementieren.
Das BS so viel langsamer ist, kann ich mir nicht vorstellen, da beim BS die Zeitschrittweiten (großer Schritt) größer sind, als bei den "Symplectic Integrators".
Grüße UMa