Ein sehr häufiges Problem bei einem N-Körper-Problem ist die Verwendung eines Doppelzyklus, um die Wechselwirkungen zwischen den Teilchen zu berechnen. Betrachtet man ein N-Körper-Problem mit n Teilchen, kann der Zyklus geschrieben werden
%Vor%Meine Frage ist, wie dieser Zyklus mit verschiedenen Threads parallelisiert werden kann. Das Ziel ist, dass jeder Thread "idealerweise" die gleiche Anzahl von Interaktionen berechnen muss.
Meine Idee war, den äußeren Zyklus, den i-Zyklus, in verschiedenen Intervallen zu trennen, sagen wir a_k = a (k), wobei k = 1,2, ..., p ist, wobei p die Anzahl der gewünschten Fäden ist das Problem in teilen.
So könnte der Zyklus als
geschrieben werden %Vor%Wo der äußerste Zyklus, der k-Zyklus, derjenige ist, der parallelisiert werden soll.
Da die Anzahl der Interaktionen des innersten Zyklus, des j-Zyklus, n- (i + 1) ist, ist die Anzahl der Interaktionen, die von jedem Thread berechnet werden,
\ sum_ {i = a (k)} ^ {a (k + 1)} n - (i + 1)
Dies bedeutet, dass man die diskrete Funktion a_k so finden möchte, dass das funktionale
f [a_k] = \ sum_ {i = a (k)} ^ {a (k + 1)} n - (i + 1)
mit den Randbedingungen a (1) = 0 und a (p) = n ist eine konstante Funktion, so dass die Anzahl der Interaktionen in jedem Thread gleich ist.
Ich habe versucht, verschiedene "Heuristiken" zu verwenden (z. B. a_k Polynom, exponentiell, log), und bisher hat mir keiner eine befriedigende Antwort gegeben. Eine direkte Lösung dieses Problems ist mir nicht ersichtlich.
Für kleines p kann dieses Problem auf die "Minimierungs-Sack-Probleme" gelegt werden, wo grundsätzlich jedes a_k eine Variable ist, um die Funktion zu minimieren
f (a_1, a_2, a_3, ...) = Summe (| f [a_k] - n / p | ^ 2)
Aber Sie könnten vermuten, dass dies für höhere Werte von p nicht effizient ist (oder sogar konvergiert).
Hat jemand eine Vorstellung davon, wie dieses Problem angegangen werden könnte?
(Tut mir leid, wenn das nicht klar ausgedrückt wird, es macht Sinn in meinem Kopf).
Wenn Sie alle Zahlen von 1 bis N addieren, können Sie feststellen, dass N + 1 = (N - 1) + 2 = (N - 2) + 3 usw.
Also, was ist, wenn jeder Thread ein kleines i und ein großes i verwendet, so dass die Summen immer addiert werden?
Oder sagen Sie, Sie wollten immer 5 Threads verwenden. Thread 1 würde die ersten 10% und die letzten 10% tun, Thread 2 würde die zweiten 10% und die zweitletzten 10% tun, und so weiter. Jede Paarung eines "frühen" und eines "späten" Abschnitts würde sich zu der gleichen Gesamtanzahl von Interaktionen addieren.
BEARBEITEN:
Ein Diagramm von einem anderen Beitrag stehlen ...
%Vor%Zeigt das deutlicher, was ich meine?
Sie können Ihre Objekte in k groups von ungefähr N/k bodies aufteilen und dieses verwenden, um das ursprüngliche Dreieck von Interaktionen in k*(k + 1)/2 pieces zu zerlegen:
Diese Ansicht wird durch die Tatsache kompliziert, dass es zwei Arten von Stücken gibt: jene entlang der Diagonalen (welche Dreiecke mit (N/k)*(N/k - 1)/2 -Elementen sind) und jene, welche nicht sind (welche Quadrate mit (N/k)*(N/k) -Elementen sind). Da die diagonalen Teile jedoch ungefähr halb so groß wie die quadratischen Teile sind, können Sie jedem Thread zwei zuweisen, um die Last auszugleichen - insgesamt also% gleichwertige Aufgaben.
Ein Vorteil dieser Methode besteht darin, dass jede Aufgabe nur auf die Daten für k*k/2 bodies zugreifen muss, wodurch sie wesentlich Cache-freundlicher wird.
Heute habe ich die Lösung gefunden. Ich akzeptiere es nicht, bis jemand es bestätigt.
Damit f [a_k] eine konstante Funktion in Bezug auf k ist, dann
f [a_ {k + 1}] - f [a_k] = 0
muss für k = 1,2,3, ..., p-1 wahr sein.
Wir können diese Gleichung erweitern, indem wir die Definitionen verwenden, die ich zu der Frage geschrieben habe, und wir kommen zu einem System von algebraischen Gleichungen "p" 2º-Ordnung in Bezug auf a_k, k = 1,2,3, ..., p. Ich sehe keine geschlossene Lösung für ein beliebiges p, aber es kann für jedes p analytisch gelöst werden.
Ich habe das bestätigt:
die Summe, wenn ich das a_k verwende, das ich berechnet habe, war n (n-1) / 2, die Gesamtzahl der Interaktionen dieses Problems.
Die Anzahl der Wechselwirkungen pro Faden ist in der Tat konstant für p = 2,3,4,5 und 10 (wobei p = 10 einige Zeit brauchte, um auf der mathematica® zu rechnen).
BEARBEITEN
Nach eingehender Prüfung der Lösungen für verschiedene Werte von p, habe ich die allgemeine geschlossene Lösung erreicht
a_k = 1 / (2p) (-p + 2pn - sqrt [p ^ 2 + 4p (p + 1 - k) (n - 1) n])
welches für jedes p & gt; = 2, n & gt; 1 gilt.
Damit ist die Antwort abgeschlossen.
Tags und Links optimization math parallel-processing