Równolegle generatora sekwencji Fibonacci

Uczę się o równoległości i w jednym ćwiczeniu dostaję kilka algorytmów, które powinny poprawić wydajność. Jednym z nich jest generator sekwencji Fibonacciego:Równolegle generatora sekwencji Fibonacci

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

Podejrzewam, że to nie może być optymalizowane (przez parallelization), ponieważ każda liczba zależy od dwóch poprzednich liczb (a więc pośrednio na wszystkich poprzednich numerów). Jak można to zrównoleglić?

Źródło

2013-05-09 Jawap

Co robiłeś w swojej klasie do tej pory? – devnull

Fibonacci jest kiepskim wyborem do zrównoleglania, jak sądzę. Sprawdź to: http://trigonakis.com/blog/2011/02/27/parallelizing-simple-algorithms-fibonacci/ –

Jeśli nie możesz określić sąsiednich liczb Fibonacciego z wyprzedzeniem, jest mało prawdopodobne, że będziesz w stanie je zrównoleglić . – devnull

Sekwencja Fibonacciego jest określana właśnie przez jej pierwsze dwa elementy; w rzeczywistości, można jakoś parallelize, chociaż brzydki:

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

Mam nadzieję, że teraz można zobaczyć, że:

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

Więc po obliczeniowej pierwszych liczb k, można użyć tej relacji do obliczania następne k pozycji w sekwencji, w tym samym czasie, zrównoleglone.

Można również użyć bezpośredniej formuły dla liczb Fibonacciego, aby obliczyć je równolegle, ale to jest trochę zbyt niefajne (również może być zbyt proste do celów edukacyjnych, aby mogło służyć).

Źródło

2013-05-09 14:58:18