Calcul parallèle et Distribué (CPD)

Ce sujet de Calcul parallèle et Distribué (CPD) est un ensemble d'exercices d'analyse de dépendances dans des nids de boucles parfaits. Il teste la capacité à déterminer les dépendances, à analyser la parallélisation possible, à étudier la validité des permutations de boucles, et à évaluer les gains en temps d'exécution parallèle.

EXERCICE 1

On considère le nid parfait N :

DO i=1,n1               / Boucle B1 /
   DO j=1,n2             / Boucle B2 /
      DO k=1,n3          / Boucle B3 /
         A(i,j,k)= A(i,j+1,k)+A(i+1,j+1,k)/A(i+1,j,k-1)
      ENDDO
   ENDDO
ENDDO

1. Déterminer la matrice des distances de dépendances (MDD), notée M, du nid N.

La dépendance vient des indices des accès aux éléments de A :

• Lecture de A(i,j+1,k) : dépendance sur (0, +1, 0)
• Lecture de A(i+1,j+1,k) : dépendance sur (+1, +1, 0)
• Lecture de A(i+1,j,k-1) : dépendance sur (+1, 0, -1)

Les dépendances sont donc les vecteurs de distance :

(0, 1, 0), (1, 1, 0), (1, 0, -1)

La matrice des distances de dépendances M est donc :

i	j	k
0	1	0
1	1	0
1	0	-1

Réponse : M = [[0,1,0], [1,1,0], [1,0,-1]]

2. En déduire le type de chaque boucle du nid N (séquentielle ou parallèle).

Une boucle est parallèle si toutes les distances de dépendances sur son indice sont nulles ou positives. Ici :

• Boucle B1 (indice i) : distances 0, 1, 1 → présence de dépendances positives → la boucle B1 est séquentielle.
• Boucle B2 (indice j) : distances 1, 1, 0 → toutes ≥ 0 → B2 est parallèle.
• Boucle B3 (indice k) : distances 0, 0, -1 → présence de -1 → B3 est séquentielle.

Réponse : B1 séquentielle, B2 parallèle, B3 séquentielle.

3. Étudier la validité des 5 permutations des boucles du nid N (IKJ, JIK, JKI, KIJ, KJI) et donner pour chaque permutation valide la MDD correspondante. En déduire le type de chaque boucle du nid correspondant.

Les permutations sont :

• IKJ : i, k, j
• JIK : j, i, k
• JKI : j, k, i
• KIJ : k, i, j
• KJI : k, j, i

Pour chaque permutation, on réordonne les colonnes de la matrice M selon l'ordre des indices.

Permutation IKJ (i,k,j) :

i	k	j
0	0	1
1	0	1
1	-1	0

La distance négative (-1) sur k (deuxième colonne) indique une dépendance négative sur la boucle k, donc la permutation IKJ n'est pas valide.

Permutation JIK (j,i,k) :

j	i	k
1	0	0
1	1	0
0	1	-1

Présence de -1 sur k (troisième colonne), donc non valide.

Permutation JKI (j,k,i) :

j	k	i
1	0	0
1	0	1
0	-1	1

Présence de -1 sur k (deuxième colonne), donc non valide.

Permutation KIJ (k,i,j) :

k	i	j
0	0	1
0	1	1
-1	1	0

Présence de -1 sur k (première colonne), donc non valide.

Permutation KJI (k,j,i) :

k	j	i
0	1	0
0	1	1
-1	0	1

Présence de -1 sur k (première colonne), donc non valide.

Conclusion : Aucune des permutations n'est valide sans transformation.

4. Étudier, pour les permutations non valides, l’utilisation de l’inversion de boucle. En déduire les nids correspondants qui sont alors valides et déterminer pour chacun le type de chacune de ses boucles.

L'inversion de boucle consiste à inverser l'ordre d'une boucle pour rendre les dépendances positives.

Par exemple, pour la permutation IKJ, on peut inverser la boucle k :

DO i=1,n1
   DO k=n3,1,-1
      DO j=1,n2
         ...

Cette inversion change la direction des dépendances sur k, rendant la distance -1 en +1.

De même, pour les autres permutations non valides, on peut inverser la boucle qui présente une dépendance négative.

Après inversion, la MDD devient positive sur toutes les boucles, rendant la permutation valide.

Le type des boucles après inversion est :

• La boucle inversée devient séquentielle (car dépendances strictes dans un sens).
• Les autres boucles restent parallèles ou séquentielles selon leurs distances.

Réponse : En inversant la boucle présentant une dépendance négative dans chaque permutation non valide, on obtient un nid valide. Le type des boucles est alors :

• Pour IKJ avec inversion de k : B1 séquentielle, B3 séquentielle (inversée), B2 parallèle.
• Pour JIK avec inversion de k : B2 parallèle, B1 séquentielle, B3 séquentielle (inversée).
• Pour JKI avec inversion de k : B2 parallèle, B3 séquentielle (inversée), B1 séquentielle.
• Pour KIJ avec inversion de k : B3 séquentielle (inversée), B1 séquentielle, B2 parallèle.
• Pour KJI avec inversion de k : B3 séquentielle (inversée), B2 parallèle, B1 séquentielle.

5. Comparer tous les nids ainsi obtenus, en discutant sur le nombre et les positions des boucles parallèles ainsi que sur le nombre d’itérations parallèles. On donnera pour chaque nid le temps d’exécution parallèle lorsqu’on dispose d’autant de processeurs que nécessaire.

Le nid initial a une seule boucle parallèle (B2). Les permutations valides avec inversion conservent une seule boucle parallèle, mais sa position varie.

Le nombre d'itérations parallèles correspond au nombre d'itérations de la boucle parallèle :

• Dans le nid initial, B2 est la boucle du milieu, avec n2 itérations parallèles.
• Dans les permutations, la boucle parallèle peut être en première ou troisième position, ce qui peut influencer la granularité de parallélisme.

Le temps d'exécution parallèle Tpar avec autant de processeurs que nécessaire est donné par le produit des tailles des boucles séquentielles, car la boucle parallèle est entièrement parallélisée :

Tpar = (nombre d'itérations séquentielles) × (coût unitaire)

Soit :

• Si B1 et B3 sont séquentielles, Tpar = n1 × n3 × 1 (coût unitaire de l'instruction)
• La boucle parallèle n2 est divisée entre processeurs.

Réponse : Tous les nids ont une seule boucle parallèle (n2 itérations), les autres boucles sont séquentielles. Le temps parallèle est Tpar = n1 × n3.

EXERCICE 2

On considère le nid N :

DO i=1,n               / Boucle B1 /
   DO j=1,3i             / Boucle B2 /
      A(i,j)=A(i+1,j+1)+A(i,j+1)   / Instruction S(i,j) de coût 1 /
   ENDDO
ENDDO

1. Déterminer le nombre d'éléments de l'espace d'itérations E de N.

L'espace d'itérations E est l'ensemble des couples (i,j) tels que :

• 1 ≤ i ≤ n
• 1 ≤ j ≤ 3i

Le nombre d'éléments est donc :

S = Σ_{i=1}^n (3i) = 3 Σ_{i=1}^n i = 3 × n(n+1)/2 = (3n(n+1))/2

Réponse : Le nombre d'éléments de E est (3n(n+1))/2.

2. Représenter E pour n=4.

Pour n=4, on a :

• i=1 : j=1..3
• i=2 : j=1..6
• i=3 : j=1..9
• i=4 : j=1..12

Le graphe d'itérations est donc un triangle avec des lignes de plus en plus longues :

i=1: (1,1) (1,2) (1,3)
i=2: (2,1) ... (2,6)
i=3: (3,1) ... (3,9)
i=4: (4,1) ... (4,12)

Ce dessin représente un espace triangulaire croissant en j selon i.

Réponse : E est un triangle avec i de 1 à 4 et j de 1 à 3i.

3. Effectuer l'analyse de dépendance au sein de N. Donner la matrice des distances de dépendance M. En déduire le type de chacune des boucles B1 et B2 (séquentielle ou parallèle).

Les accès dans l'instruction sont :

• Lecture de A(i+1,j+1) → dépendance sur (1,1)
• Lecture de A(i,j+1) → dépendance sur (0,1)

Les distances de dépendance sont donc :

M = [[1, 0], [1, 1]]

Explication :

• Pour i : dépendances de 1 (i+1) et 0 (i)
• Pour j : dépendances de 1 (j+1) et 1 (j+1)

On peut écrire la matrice M comme :

B1 (i)	B2 (j)
1	1
0	1

La boucle B1 a une dépendance positive (1) → séquentielle.

La boucle B2 a une dépendance positive (1) → séquentielle.

Réponse : B1 séquentielle, B2 séquentielle.

4. Représenter, dans E, le graphe de dépendance pour n=4.

Le graphe de dépendance relie chaque itération (i,j) à :

• (i+1, j+1) si dans E
• (i, j+1) si dans E

Pour n=4, on a les arcs :

• De (1,1) vers (2,2) et (1,2)
• De (1,2) vers (2,3) et (1,3)
• ...
• De (3,9) vers (4,10) et (3,10) (si dans E)

Ce graphe montre des dépendances diagonales et horizontales vers des itérations plus grandes.

Réponse : Le graphe de dépendance est un réseau orienté dans E reliant chaque (i,j) aux itérations (i+1,j+1) et (i,j+1) si elles existent.

5. Étudier la validité de la permutation des boucles B1 et B2. Dans le cas où cette transformation est valide, écrire le nouveau nid NP (utiliser DOSER et DOPAR), après avoir calculé les nouvelles bornes des compte-tours. Donner le type de chacune des deux boucles de NP, notées B’1 et B’2 (séquentielle ou parallèle).

Permutation des boucles : on échange B1 et B2, donc :

DO j=1,?
   DO i=?
      ...

Les bornes doivent être recalculées pour que l'espace d'itérations soit le même :

• Initialement : i=1..n, j=1..3i
• Après permutation : j varie de 1 à 3n (car j max = 3n)
• Pour chaque j, i varie de 1 à floor(j/3) (car j ≤ 3i → i ≥ j/3)

Donc :

DO j=1,3n
   DO i=1,floor(j/3)
      A(i,j)=A(i+1,j+1)+A(i,j+1)
   ENDDO
ENDDO

Analyse des dépendances dans NP :

• Lecture de A(i+1,j+1) : dépendance sur (1,1) → sur i et j
• Lecture de A(i,j+1) : dépendance sur (0,1)

Dans NP, B’1 = i, B’2 = j.

La boucle i (B’1) a une dépendance positive sur i → séquentielle.

La boucle j (B’2) a une dépendance positive sur j → séquentielle.

Réponse : La permutation est valide avec les bornes ajustées. NP :

DO j=1,3n
   DO i=1,floor(j/3)
      A(i,j)=A(i+1,j+1)+A(i,j+1)
   ENDDO
ENDDO

Les deux boucles B’1 et B’2 sont séquentielles.

6. Pour exécuter NP, on dispose d'un nombre de processeurs np égal au nombre maximal d'itérations de la boucle parallèle de NP. Donner np. Déterminer le temps parallèle Tpar correspondant ainsi que l’accélération et l’efficacité correspondantes.

Dans NP, aucune boucle n'est parallèle (les deux sont séquentielles), donc np = 1.

Le temps parallèle Tpar est alors égal au temps séquentiel Tseq = nombre total d'itérations × coût unitaire = (3n(n+1))/2 × 1.

L'accélération est :

Accélération = Tseq / Tpar = 1

L'efficacité est :

Efficacité = Accélération / np = 1/1 = 1

Réponse : np = 1, Tpar = Tseq = (3n(n+1))/2, accélération = 1, efficacité = 1.

EXERCICE 3

On considère le nid parfait N :

DO i=1,n1             / Boucle B1 /
   DO j=1,n2           / Boucle B2 /
      DO k=1,n3        / Boucle B3 /
         S(i,j,k)       / coût 1 /
      ENDDO
   ENDDO
ENDDO

L’analyse de dépendances conduit à la matrice des signes des distances :

i	j	k
0	1	1
0	0	-1
1	1	-1

1. Déterminer le type de chaque boucle du nid (séquentielle ou parallèle).

On analyse les signes des distances :

• Boucle i : distances 0, 0, 1 → pas de dépendance négative → i est parallèle.
• Boucle j : distances 1, 0, 1 → pas de dépendance négative → j est parallèle.
• Boucle k : distances 1, -1, -1 → présence de -1 → k est séquentielle.

Réponse : B1 (i) parallèle, B2 (j) parallèle, B3 (k) séquentielle.

2. Étudier la validité des 5 permutations des boucles du nid et donner pour chaque permutation valide le type de chaque boucle du nid correspondant.

Les permutations possibles sont IKJ, JIK, JKI, KIJ, KJI. On vérifie la présence de dépendances négatives sur la première boucle :

• IKJ : première boucle i (parallèle) → valide.
• JIK : première boucle j (parallèle) → valide.
• JKI : première boucle j (parallèle) → valide.
• KIJ : première boucle k (séquentielle) → dépendance négative → non valide.
• KJI : première boucle k (séquentielle) → non valide.

Pour les permutations valides :

• IKJ : B1 parallèle, B2 séquentielle, B3 séquentielle (car k en deuxième ou troisième position).
• JIK : B1 parallèle, B2 séquentielle, B3 séquentielle.
• JKI : B1 parallèle, B2 séquentielle, B3 séquentielle.

Réponse : Les permutations IKJ, JIK, JKI sont valides avec les boucles parallèles en première position et les autres séquentielles. KIJ et KJI ne sont pas valides.

3. Étudier pour les permutations non valides l’utilisation de l’inversion de boucle. En déduire les nids correspondants qui sont alors valides et déterminer pour chacun le type de chacune de ses boucles.

Pour KIJ et KJI, on peut inverser la boucle k pour rendre les dépendances positives :

• Inversion de k dans KIJ et KJI rend la distance négative positive.
• Après inversion, k devient séquentielle (car dépendance stricte).
• Les autres boucles gardent leur nature.

Réponse : En inversant la boucle k, KIJ et KJI deviennent valides avec k séquentielle, i et j parallèles.

4. Comparer tous les nids ainsi obtenus, en discutant sur le nombre et les positions des boucles parallèles ainsi que sur les nombres d’itérations de chaque boucle.

Les permutations valides ont toujours deux boucles parallèles (i et j) et une séquentielle (k). La position des boucles parallèles varie :

• IKJ, JIK, JKI : deux boucles parallèles en première et deuxième position.
• KIJ, KJI (après inversion) : deux boucles parallèles en deuxième et troisième position.

Le nombre d'itérations parallèles est le produit des tailles des boucles parallèles (n1 × n2).

Réponse : Tous les nids ont deux boucles parallèles (i et j) et une séquentielle (k). La position des boucles parallèles varie selon la permutation.

Méthode

Ce sujet récompense la maîtrise de l’analyse des dépendances dans des nids de boucles parfaits, notamment :

• Identifier précisément les vecteurs de dépendance à partir des indices des accès mémoire.
• Construire la matrice des distances de dépendance (MDD) en respectant l’ordre des boucles.
• Déterminer la nature séquentielle ou parallèle d’une boucle en analysant les signes des distances.
• Étudier la validité des permutations de boucles en vérifiant la positivité des distances sur la première boucle.
• Utiliser l’inversion de boucle pour rendre valides les permutations non valides.
• Calculer les bornes des boucles après permutation lorsque les limites dépendent des indices.
• Évaluer les gains en temps parallèle en fonction du nombre de boucles parallèles et de leurs tailles.

Les erreurs pénalisées sont :

• Confondre les indices des dépendances ou oublier un vecteur.
• Ne pas respecter l’ordre des indices dans la matrice MDD.
• Omettre la vérification des signes pour la validité des permutations.
• Ne pas recalculer correctement les bornes des boucles après permutation.
• Ne pas justifier les conclusions sur la parallélisation.