Ich habe ein Problem mit einem Algorithmus, um Werte parallel aufzuaddieren.
pardo heißt, dass das folgende nicht in einer Schleife abläuft, sondern in unterschiedlichen Prozessen (in diesem Fall Threads). Pi steht für den i-ten Prozess. Die Ausgangsdaten liegen im A-Array.
Der Ablauf schaut folgendermaßen aus (von links nach rechts und von unten nach oben):
Das Problem ist, dass sich die Threads in die Quere kommen können. Dass es B(2,1) vielleicht schon gibt, B(1,2) jedoch noch nicht. Irgendwie muss ich vielleicht mit join arbeiten. Dass B(2,1) und B(2,2) erst dann berechnet werden dürfen, wenn B(1,x) berechnet wurden. D. h. man muss das immer schichtweise von unten nach oben berechnen.
Aber ich habe keine Ahnung, wie ich hier mit join arbeiten könnte. Denn z B der Prozess 1 ist erst dann fertig, wenn er bei B(3,1) angekommen ist. Er müsste aber auf dem Weg dorthin schon mehrmals auf andere Prozesse warten.
PHP-Code:
for Pi, 1 <= i <= n pardo
B(0,i) := A(i)
for h := 1 to log(n) do
if i <= n/(2^h)
then B(h,i) := B(h-1,2*i-1) + B(h-1,2*i)
else stay idle // mache nichts
Der Ablauf schaut folgendermaßen aus (von links nach rechts und von unten nach oben):
Code:
B(3,1) / \ B(2,1) B(2,2) / \ / \ B(1,1) B(1,2) B(1,3) B(1,4) / \ / \ / \ / \ B(0,1)=A(1) B(0,2)=A(2) B(0,3)=A(3) B(0,4)=A(4) B(0,5)=A(5) B(0,6)=A(6) B(0,8)=A(7) B(0,8)=A(8)
Aber ich habe keine Ahnung, wie ich hier mit join arbeiten könnte. Denn z B der Prozess 1 ist erst dann fertig, wenn er bei B(3,1) angekommen ist. Er müsste aber auf dem Weg dorthin schon mehrmals auf andere Prozesse warten.
Kommentar