Discussion :

[nicolas66]

Bonjour,

Pour les besoins d'un projet, je dois trouver un algorithme pour paralléliser la suite de Fibonacci sur plusieurs ordinateurs. J'ai déjà réfléchi sur le sujet sans succès . Est-ce que quelqu'un aurait une idée, un lien ou autre là-dessus ? Merci d'avance à ceux qui pourront m'aider.


Nico.

[gangsoleil]

Bonjour,

De mémoire, la suite de Fibonacci ne peut s'exprimer que en fonction de ses termes précédents :
F(n) = 0 si n=0,
F(n) = 1 si n=1,
F(n) = F(n-1) + F(n-2) dans tous les autres cas.

C'est à dire que, si je te donne le nombre 7632, il n'existe pas d'algorithme permettant de calculer le résulat sans calculer tous les termes intermédiaires entre 1 et 7632.
Donc au mieux, ce que tu pourrais faire, c'est utiliser un pipeline, mais cela ne permet d'utiliser que 3 processeurs, ce qui n'est pas énorme...

[Sivrît]

http://fr.wikipedia.org/wiki/Suite_de_Fibonacci et http://en.wikipedia.org/wiki/Fibonacci_number sont très intéressant. On y retrouve par exemple la formule de Binet.

[nicolas66]

Merci d'abord pour vos réponses. La formule de Binet a l'air très aléchante mais je pense que l'on doit s'en passer pour cet exercice. Juste pour info, voici l'énoncé exact de mon exo :



En fait, j'arrive pas à imaginer à un algorithme parallèle à partir de l'égalité donnée

Note : EREW -> Exclusive Reading & Exclusive Writing

[millie]

Avec deux ordinateurs :

Tu as :

(F_{n+1} F_n) = Q² (F_{n-1} F_{n-2})

Avec Q² = ((2 1) (1 1))

Donc on peut calculer F_{n+1} indépendamment de F_{n} et F_{n} indépendemment de F_{n+1}. Donc un ordi calcule F_{n+1} et l'autre F_{n} et se partage les résultats en récrivant au ancienne position de F_{n-1} et F_{n-2}.

Mais bon, c'est bof bof Parce qu'avec plus d'ordinateurs, ça va plus.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Au début, A et B valent a et b
 
Boucler sur les instructions suivantes :
 
P1 lit en A et P2 lit en B
P1 lit en B et P2 lit en A
P1 calcule 2A + B et P2 calcule A+B
P1 écrit le résultat dans A et P2 le résultat dans B

Si tu considères que P1 fait une instruction de plus lors du calcul (à cause du 2*), tu peux faire incrémenter le compteur de boucle par P2 pendant ce temps.

[Sivrît]

Ces formules ramènent le problème au calcul de Q^n (ou phi^n)... Mais on retombe sur un problème du même genre : Comment paralléliser ça ? L'exponentiation doit être un cas d'école mais je ne vois rien d'évident. En théorie on calcule Q^(n/2) mais ça donne deux partie identique donc inutile de répartir

J'ai peut-être une idée qui serait peut-être EREW (vue la signification, mais ce n'est pas mon domaine) pour répartir tout ça en deux. On part sur l'exponentiation rapide qui va au final nous faire multiplier des éléments de la forme Q^(2^k). Un process peut calculer tous les Q^(2^k) pour 2^k<n, et un autre les assemble au fur et à mesure de leur disponibilité suivant l'écriture binaire de n pour obtenir Q^n.

[méphistopheles]

soit A la matrice Q-Id (a11=1, les autres termes valent 0) (Id est l'indentité)
A^n= A
Id^n=Id
Q^2= Id + 3A
Q^3= Id + 7A
Q^4= Id + 15A

on suppose la propriété Q^n=Id+(2^n)A-A vraie

Q^n+1=(Id+(2^n)A-A)(Id+A)=Id+A+(2^n)A +(2^nA) -A -A= Id+ (2^(n+1))A -A

la propriété est vérifiée. tu à donc ton Q^n (1 sur la diagonale, 2^(n+1) -1 en haut à gauche, 0 en bas à droite)

ensuite, tu n'a plus qu'a calculer, par exemple que les termes de rang pair/ impair ou bien avec un pas de 3, en fonction de ton nombre d'ordinateurs.

Salut.