Liste des travaux pratiques / dirigés

Paralèlisme : cours

• 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

2. Réduction

2.1. Exercice 1

On s'intéresse à la paralèlisation liée à l'algorithme de réduction (cf cours). On se place dans le cadre de la réduction liée au calcul : $$ sum = ∑↙{i=1}↖{n} t_i $$

Ecrire un programme C++ appelé reduction_simple.cpp qui permet de réaliser la réduction d'un tableau de réels double précision $my\_array$ auquel on applique une fonction de traitement.

L'implantation choisie ainsi que la dimension du tableau (qui par défaut est de 1048576=$2^20$) seront passés en arguments du programme (penser à utiliser getopt).

Les métodes à implanter sont les suivantes :

• métode 1 : réduction classique sans optimisation
  
  1. typedef double real; 
  2. typedef real (*ReductionMethod)(real *t, size_t n);
  3.  
  4. real function(real v) {
  5.   for (int i = 0; i < 100; ++i) {
  6.     v = sin(v + 0.01);
  7.   }
  8.   return v;
  9. }
  10.  
  11. real reduction_serial(real *t, size_t n) {
  12.   real sum = 0;
  13.   for (size_t i = 0; i < n ; ++i) sum += function(t[i]);
  14.   return sum;
  15. }
  16.  
• métode 2 : réduction en utilisant les POSIX Threads avec 8 threads
• métode 3 : version utilisant la classe thread de C++11, par exemple 8 threads et répartition des indices
• métode 4 : version OpenMP avec 8 threads

Réaliser un script bash qui permet de calculer les temps de calculs avec les différentes versions et de les comparer. On génèrera des graphiques gnuplot pour comparer les méthodes avec différentes dimensions du tableau : $2^20$ à $2^25$. Les méthodes 2, 3 et 4 doivent donner les mêmes temps d'exécution.

2.2. Exercice 2

Ecrire un programme nommé amdhal qui permet d'afficher le gain théorique obtenu par le parallélisme pour un taux de parallélisation donné (compris entre 0 et 1) et qui si on fournit une liste de temps d'exécution pour k=1,2,4,8,16 threads donne également l'accélération obtenue ainsi que le gain en pourcentage et la métrique de Karp–Flatt .

Par exemple :

./amdhal -p 0.98 -v "11.10 5.66 2.83 1.80 0.97 0.67"
--------------------------
 Theoretical
--------------------------
 k  time  acc  %acc  %diff
--------------------------
 1  11.10
 2  5.66  1.96  0.49  0.49
 4  2.94  3.77  0.73  0.25
 8  1.58  7.02  0.86  0.12
16  0.90  12.31  0.92  0.06
32  0.56  19.75  0.95  0.03
-------------------------------
 Empirical
-------------------------------
 k  time  acc  %acc  %diff  K/F
-------------------------------
 1  11.10
 2  5.66  1.96  0.49  0.49  0.51
 4  2.83  3.92  0.75  0.25  0.25
 8  1.80  6.17  0.84  0.09  0.16
16  0.97  11.44  0.91  0.07  0.09
32  0.67  16.57  0.94  0.03  0.06

2.3. Exercice 3

Comparer les temps d'exécution de la version OpenMP en utilisant 2, 4, 8 puis 16 threads.

Voici également quelques résultats sur le cluster du LERIA (Intel E5-2670) pour un tableau de 8_388_608 ($2^{23}$ éléments) pour la méthode 4 (OpenMP) :

k time
1 20.72
2 10.56
4  5.42
6  4.14
8  2.73
10 2.23
12 1.92
14 1.71
16 1.50
18 1.43
20 1.31
22 1.53
24 1.44
26 1.39
28 1.36
30 1.33
32 1.35
34 1.36
36 1.28
38 1.31
40 1.35

2.4. Exercice 4

Reprendre le programme reduction_simple.cpp et en écrire une version plus complexe reduction_complex.cpp pour laquelle le nombre d'éléments du tableau n'est pas forcément une puissance de 2.

2.5. Exercice 5

Ecrire un framework (normalement qui se résume à une classe) basé sur MPI qui permet de réaliser la réduction d'un tableau de taille quelconque de valeurs (int, float ou double). On fera en sorte que +, *, min et max soient disponibles.