parallelisieren Fibonacci-Sequenz-Generator

Ich lerne über Parallelisierung und in einer Übung bin ich ein paar Algorithmen gegeben, die ich in der Leistung verbessern sollte. Einer von ihnen ist ein Fibonacci-Sequenz-Generator:parallelisieren Fibonacci-Sequenz-Generator

array[0] = 0; 
array[1] = 1; 
for (q = 2; q < MAX; q++) { 
    array[q] = array[q−1] + array[q−2]; 
}

Mein Verdacht ist, dass dies nicht (durch Parallelisierung) optimiert werden, da jede Zahl auf den beiden vorhergehenden Zahlen abhängt (und damit indirekt auf alle vorhergehenden Zahlen). Wie könnte dies parallelisiert werden?

Quelle

2013-05-09 Jawap

Was haben Sie bisher in der Klasse zu tun? – devnull

Fibonacci ist eine schlechte Wahl für die Parallelisierung, glaube ich. Überprüfen Sie dies: http://trigonakis.com/blog/2011/02/27/parallelizing-simple-algorithms-fibonacci/ –

Sofern Sie benachbarte Fibonacci-Zahlen nicht rechtzeitig bestimmen können, ist es unwahrscheinlich, dass Sie es parallelisieren können . – devnull

wird die Fibonacci-Folge nur durch seine ersten beiden Elemente bestimmt wird; in der Tat könnte man es parallelisieren irgendwie, obwohl hässlich:

F(n + 2) = F(n + 1) + F(n) 
F(n + 3) = F(n + 1) + F(n + 2) = F(n + 1) * 2 + F(n) 
F(n + 4) = F(n + 2) + F(n + 3) = F(n + 1) * 3 + F(n) * 2 
F(n + 5) = F(n + 3) + F(n + 4) = F(n + 1) * 5 + F(n) * 3 
F(n + 6) = F(n + 4) + F(n + 5) = F(n + 1) * 8 + F(n) * 5

Hoffentlich jetzt können Sie sehen, dass:

F(n + k) = F(n + 1) * F(K) + F(n) * F(k - 1)

So nach der ersten k Zahlen Berechnen Sie diese Beziehung verwenden könnte zu berechnen Die nächsten k Elemente in der Sequenz werden parallelisiert.

Sie könnten auch die direkte Formel für Fibonacci-Zahlen verwenden, um sie parallel zu berechnen, aber das ist irgendwie zu uncool (könnte auch für Lernzwecke zu einfach sein, dass es dienen könnte).

Quelle

2013-05-09 14:58:18