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

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

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.

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 obtenus sur AMD Ryzen 5 5600G :

6.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.