Transformer un algorithme séquentiel en un parallél
Résolu/Fermé
ra7ma7788
-
18 nov. 2012 à 18:25
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 18 nov. 2012 à 19:10
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 18 nov. 2012 à 19:10
A voir également:
- Transformer un algorithme séquentiel en un parallél
- Transformer majuscule en minuscule word - Guide
- Transformer image en icone - Guide
- Transformer un pdf en word gratuit - Guide
- Transformer epub en kindle - Guide
- Transformer un audio en texte gratuit - Guide
1 réponse
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
18 nov. 2012 à 19:10
18 nov. 2012 à 19:10
Déjà la parallélisation est faite pour gagner du temps sur l'exécution des algorithmes séquentiels, mais il faudrait déjà penser à optimiser ces algorithmes de bases, et le tri à bulles est l'un des plus mauvais algorithmes de tris !
Puisque c'est un exercice très scolaire on va garder ton tri à bulle, de complexité O(n²), et l'exécuter sur '2^k' machines en parallèles.
On peut découper le tableau 'a' en '2^k' morceaux de tailles n/2^k.
Chaque ordinateur exécute le tri à bulles sur son morceau de tableau, soit un temps O(n²/(2^k)²), afin d'obtenir le morceau de tableau trié. Tout ordinateur réunis on aura obtenus 2^k morceaux de tableaux de taille n/2^k triés.
Et là il y a une opération supplémentaire à effectuer c'est fusionner les tableaux triés, ce qui se fait deux par deux. Fusionner deux tableaux de taille 'm' se fait en O(2m).
À la première itération on prend par exemple les ordinateurs "pairs" qui envoient leur morceaux de tableau trié aux ordinateurs "impairs" qui en auront ainsi deux, et peuvent les fusionner. Après un temps O(2.n/2^k) on obtient ainsi 2^(k-1) morceaux triés de tableaux de taille n/2^(k-1).
Il faut bien sûr recommencer la fusion comme ça jusqu'aux deux derniers morceaux de tableaux de taille n/2, qui se fusionnent en un temps O(n).
Au final, la complexité temporelle O(n²) de l'algorithme séquentielle de départ devient une complexité de temporelle de O(n²/(2^k)² + n + n/2 + ... + n/2^(k-1)), ce qui se simplifie en O(n²/4^k + (2^k-1)n/2^(k-1))
Quelques exemples en remplaçant k par sa valeur :
Puisque c'est un exercice très scolaire on va garder ton tri à bulle, de complexité O(n²), et l'exécuter sur '2^k' machines en parallèles.
On peut découper le tableau 'a' en '2^k' morceaux de tailles n/2^k.
Chaque ordinateur exécute le tri à bulles sur son morceau de tableau, soit un temps O(n²/(2^k)²), afin d'obtenir le morceau de tableau trié. Tout ordinateur réunis on aura obtenus 2^k morceaux de tableaux de taille n/2^k triés.
Et là il y a une opération supplémentaire à effectuer c'est fusionner les tableaux triés, ce qui se fait deux par deux. Fusionner deux tableaux de taille 'm' se fait en O(2m).
À la première itération on prend par exemple les ordinateurs "pairs" qui envoient leur morceaux de tableau trié aux ordinateurs "impairs" qui en auront ainsi deux, et peuvent les fusionner. Après un temps O(2.n/2^k) on obtient ainsi 2^(k-1) morceaux triés de tableaux de taille n/2^(k-1).
Il faut bien sûr recommencer la fusion comme ça jusqu'aux deux derniers morceaux de tableaux de taille n/2, qui se fusionnent en un temps O(n).
Au final, la complexité temporelle O(n²) de l'algorithme séquentielle de départ devient une complexité de temporelle de O(n²/(2^k)² + n + n/2 + ... + n/2^(k-1)), ce qui se simplifie en O(n²/4^k + (2^k-1)n/2^(k-1))
Quelques exemples en remplaçant k par sa valeur :
Pour 1 ordinateur (k=0) : O(n²) Pour 2 ordinateurs (k=1) : O(n²/4+n) Pour 4 ordinateurs (k=2) : O(n²/16+3n/2) Pour 8 ordinateurs (k=3) : O(n²/64+7n/4) Pour n ordinateurs : O(1+2(2^k-1)(2^k)/2^(k-1)) = O(2n-1)
