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.