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

6. Courbes de Julia

On s'intéresse à la parallèlisation du calcul des courbes (ou ensembles) de Julia. Il s'agit d'un exemple classique où chaque calcul lié à un point est indépendant des autres.

6.1. L'implantation mono thread

Récupérez l'archive jula_cpu_etudiants.tgz qui contient le code de base qui devra être modifié par la suite.

L'implantation de base utilise une fenêtre par défaut entre $x ∊ [-1.4, +1.4]$ et $y ∊ [-1.5, +1.5]$

Dans ces intervalles on place par défaut 1024 pixels ce qui va nous permettre de constituer une image de $1024 × 1024$ pixels. Cette image sera affichée si on utilise l'option en ligne de commande -v, sinon on effectuera un test de performance du calcul de l'image pendant 200 itérations.

Chaque point de l'image est identifié par un nombre complexe $z_1 = x + y {\text i}$ et pour lequel on calcule la suite :

$$ z_{n+1} = z_n^2 + z_0 $$

où la constante par défaut $z_0 = 0.3 + 0.5 {\text i}$.

On cherche à savoir si la suite converge grâce à la fonction julia(...). Celle-ci calcule la norme de $z_{n+1}$ pour $n$ variant de 1 à 400. Si elle devient supérieure à $4.0$ on s'arrête en considérant que la suite ne convergera pas.

Effectuez un premier test de performance et noter le temps de calcul en monothread :

/usr/bin/time -f "time=%U" bin/julia_cpu.exe
image_width=1024
image_height=1024
max_images=200
max_terms=400
constant_real=0.3
constant_imag=0.5
timer.computation.ms=30156
time=30.14
cat /proc/cpuinfo | grep "model name" | uniq
model name	: AMD Ryzen 5 5600G with Radeon Graphics

Dans l'exemple précédent le test s'est exécuté en $30,14$ secondes sur un AMD Ryzen 5 5600G.

6.2. Partie OpenMP

6.2.1. Améliorations

Parallélisez le code de l'archive. Comparer les temps d'exécution des différentes méthodes qui suivent.

• méthode 1 : sans parallélisation, mono thread c'est la méthode par défaut qui utilise la fonction appelée kernel()
• méthode 2 : en utilisant OpenMP sur la première boucle (y) de la fonction kernel
• méthode 3 : en utilisant OpenMP sur la deuxième boucle (x) de la fonction kernel
• méthode 4 : en utilisant OpenMP sur les deux boucles de la fonction kernel en utilisant collapse

On effectuera les tests avec les paramètres par défaut.

On pourra éventuellement modifier les paramètres -a si le nombre de générations donne des temps de calcul trop importants sur PC portable.

6.2.2. Résultats

Remplir le tableau suivant avec les temps de calcul des différentes méthodes en modifiant le nombre de threads. On écrira un script bash afin d'automatiser les calculs.

Voici les temps de calcul et des graphiques obtenus pour différentes architectures :

6.2.2.a  Ryzen 9 7950X3D (Mathis SAUVAGE)

On obtient un temps minimal de 1,65s pour $k=70$ ou $72$.

6.2.3. Analyse

Que remarque t-on ?

• comparez les méthodes entre elles
• que peut-on dire quant au nombre de threads sachant qu'un AMD Ryzen 5 5600G possède 6 coeurs dotés de l'hyperthreading

Analyser les résultats de la méthode 2 par rapport à la loi de Amdahl en considérant que le temps de calcul passé en parallèle est de 98%, soit $Par = 0,98$.

• dans un premier temps on calcule pour $K (= 2, 4, 6, ..., 32)$ qui est le nombre de coeurs de calcul, l'accélération théorique (acc_K) donnée par : $$ {\text acc}_K = 1 / {1 - Par + {Par}/ K} $$
• comparez l'accélération théorique et le temps que l'on devrait obtenir par rapport au temps obtenu.
• calculez l'accélération réelle (acc_R)
• calculez la métrique de Karp-Flatt sur l'accélération réelle afin de déterminer quel est le nombre de coeurs de calcul pour lesquels la parallélisation est la meilleure en prenant en compte l'accélération réelle.

On ne considère que les valeurs positives et dans ce cas c'est pour $k = 16$ que l'on obtient le meilleur résultat.

Pour $k = 2$, l'accélération théorique (${\text acc}_K$) est sensiblement égale à l'accélération réelle (${\text acc}_R$)

Par contre, à partir de $k = 4$, on note une différence importante entre ces valeurs.

6.3. Partie MPI

Modifiez le programme précédent pour en donner une version MPI pour laquelle chaque CPU / thread se voit attribuer un nombre de lignes à traiter et renvoie le résultat au processus maître.

Il se peut que le compilateur mpic++ affiche des erreurs liées au type Status défini pour MPI sous forme d'une classe mais également pour OpenGL sous forme d'un entier. Pour supprimer le problème introduire les lignes suivantes avant d'inclure la librairie MPI :

#ifdef Status
#undef Status
#endif
#include <mpi.h>

Donner les temps d'exécution pour $k$ (nombre de CPU) variant de 2 à 8 par exemple soit sur la même machine soit sur plusieurs machines différentes.