Paralèlisme : cours
Liste des travaux pratiques / dirigés
- td 1 : Produit de matrices
- td 2 : Réduction
- td 3 : Scan
- td 4 : Tri
- td 5 : Jeu de la vie
- td 6 : Courbes de julia
- td 7 : Résolution d'équation
4. Tri
4.1. Exercice 1
Implanter un algorithme de tri (ordre croissant) pour les entiers de type merge sort en utilisant OpenMP (cf cours 2).
Le programme prendra en paramètres :
- -s taille : la taille du tableau
- -m method : la méthode de tri merge sort non parallèle, ou merge sort parallèle avec OpenMP
- -i method : la méthode d'initialisation du tableau soit valeurs décroissantes, soit aléatoires
Tester le temps d'exécution avec différentes tailles de tableaux.
4.2. Exercice 2
Ecrire un programme mpi_tri_merge_sort.cpp qui utilise MPI pour trier un tableau de $N$ entiers grâce à l'algorithme merge-sort.
Utiliser $2^k$ instances du même programme pour trier ce tableau qui peut être représenté sous forme d'un vector de la STL.
4.2.1. Phase 1 : séparation des données et tri
La première instance, de rang 0, est le maître : il crée le tableau initial de $N$ éléments (valeurs aléatoires) et le divise en $2^k$ parties. Il envoie une partie des données à trier aux $2^k - 1$ esclaves.
Par exemple si $k = 3$ et $N = 64$, chaque processeur/processus traitera initialement $64 / 2^3$ = 8 éléments.
- chaque esclave trie le sous tableau de 8 éléments qu'on lui a envoyé
- le maître trie le sous tableau qui comprend les 8 premiers éléments du tableau initial
4.2.2. Phase 2 : fusion
On passe ensuite par une phase de fusion des tableaux ainsi triés.
Par exemple, si on a $2^3$ processeurs et $N=64$:
- le processeur 1 transmet son tableau au processeur 0 qui réalise la fusion et possède à présent un tableau de 16 éléments
- le processeur 3 transmet son tableau au processeur 2 qui réalise la fusion
- le processeur 5 transmet son tableau au processeur 4 qui réalise la fusion
- le processeur 7 transmet son tableau au processeur 6 qui réalise la fusion
puis
- le processeur 2 transmet son tableau au processeur 0 qui réalise la fusion et possède à présent un tableau de 32 éléments
- le processeur 6 transmet son tableau au processeur 4 qui réalise la fusion
et enfin
- le processeur 4 transmet son tableau au processeur 0 qui réalise la fusion et obtient un tableau de 64 éléments
On a donc un fonctionnement en $log_2(2^k) = k$ étapes de fusion.