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
• td 8 : easy MPI
• td 9 : Problème du cavalier

3. Scan

On s'intéresse à la paralèlisation de l'algorithme de scan (cf cours). On se place dans le cadre du scan lié à la somme d'un tableau.

Ecrire un programme C++ qui permet de réaliser le scan inclusif ou exclusif d'un tableau de double $array$ . L'implantation choisie ainsi que la dimension du tableau (qui par défaut est de 1048576) seront passés en arguments du programme (penser à utiliser getopt).

Les métodes à implanter sont les suivantes :

• métode 1 : scan séquentiel
  
• métode 2 : parallèle naïf
• métode 3 : version paralèlle avec phase de up/down sweep

Dans un premier temps, comparer les temps d'exécution de ces methodes pour une taille de tableau de $2^20$ éléments en répétant le calcul 5000 fois. La version séquentielle (mono-thread) doit être la plus rapide car cet algorithme (scan) n'est pas adapté au parallèlisme.

Réaliser un script bash qui permet de calculer les temps de calculs avec les différentes versions et de les comparer, notemment la version séquentielle (mono-thread), up and down sweep mono-thread, up and down sweep parallèle. On génèrera des graphiques avec gnuplot pour comparer les méthodes avec différentes dimensions du tableau allant de $2^20$ à $2^25$.

Voici un exemple pour 200 répétitions du calcul sur AMD Ryzen 5 9500X :