Liste des travaux pratiques / dirigés

Paralèlisme : cours

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 :

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.

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
------------------------
 1  11.10
 2  5.66  1.96  0.49  0.49
 4  2.83  3.92  0.75  0.25
 8  1.80  6.17  0.84  0.09
16  0.97  11.44  0.91  0.07
32  0.67  16.57  0.94  0.03

2.3. Exercice 3

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

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.

  1. // TYPE = int, float or double
  2. int size = 1022345;
  3. TYPE *tab;
  4. MPIReductor<TYPE> reductor(...);
  5.  
  6. // creation of global array on Master only
  7. if (reductor.is_master()) {
  8.   // initialize array
  9.   tab = new TYPE [ size ];
  10.   size_t index = 0;
  11.   for (int cpu = 0; cpu < reductor.max_cpus(); ++cpu) {
  12.     for (size_t i = 0; i < reductor.local_sizes()[cpu]; ++i) {
  13.       tab[index++] = (cpu+1);
  14.     }
  15.   }
  16.  
  17.   cout << "GLOBAL_ARRAY=";
  18.   for (int i=0;i<size;++i) cout << tab[i] << " ";
  19.   cout << endl;
  20. }
  21.  
  22. // all CPUs do the job
  23. reductor.process_and_print(tab, ...);
  24.