Calcul parallèle et Distribué (CPD): Exercises on Loop Nestings and Dependency Analysis

Exercice 1 - Analyse d'un nid parfait à trois boucles

Question 1 - Détermination de la matrice des distances de dépendances (MDD)

Dans le nid N (I, J, K), l'instruction S contient une écriture vers A(i,j,k) et trois lectures : A(i,j+1,k), A(i+1,j+1,k) et A(i+1,j,k-1).

Pour trouver la distance de dépendance entre un accès source et un accès cible (distance = Itération cible - Itération source), nous devons d'abord identifier l'ordre temporel des accès à un même élément :

• Pour A(i,j+1,k) : L'itération (i, j-1, k) lit l'élément A(i,j,k). Ensuite, l'itération (i, j, k) écrit ce même élément A(i,j,k). L'opération de lecture a lieu avant l'écriture, il s'agit donc d'une anti-dépendance. La distance est (i, j, k) - (i, j-1, k) = (0, 1, 0).
• Pour A(i+1,j+1,k) : L'itération (i-1, j-1, k) lit A(i,j,k) avant que l'itération (i, j, k) ne l'écrive. C'est une anti-dépendance. La distance est (i, j, k) - (i-1, j-1, k) = (1, 1, 0).
• Pour A(i+1,j,k-1) : L'itération (i-1, j, k+1) lit A(i,j,k). Puisque i-1 < i, cette lecture se produit chronologiquement avant l'écriture à (i,j,k). C'est une anti-dépendance. La distance est (i, j, k) - (i-1, j, k+1) = (1, 0, -1).

La matrice des distances de dépendances, notée M, dont les colonnes sont les vecteurs de distances, est donc :

    | 0  1  1 |
M = | 1  1  0 |
    | 0  0 -1 |

Question 2 - Type de chaque boucle (séquentielle ou parallèle)

Une boucle est séquentielle si elle porte au moins une dépendance (c'est-à-dire si le vecteur distance a sa première composante non nulle strictement positive à la ligne correspondant à cette boucle).

• Boucle B1 (i) : La première ligne de M est (0, 1, 1). B1 porte les dépendances d2 = (1,1,0) et d3 = (1,0,-1). Elle est donc séquentielle.
• Boucle B2 (j) : La deuxième ligne de M intervient pour évaluer d1 = (0,1,0) car sa première composante (sur la ligne i) était nulle. Comme la composante j de d1 est 1 (>0), B2 porte la dépendance d1. Elle est séquentielle.
• Boucle B3 (k) : Toutes les dépendances ont déjà été portées par B1 et B2. La boucle B3 ne porte aucune dépendance. Elle est parallèle.

Question 3 - Validité des 5 permutations et types des boucles

Une permutation est valide si tous les vecteurs de la nouvelle matrice MDD (obtenue en permutant les lignes de M) restent lexicographiquement positifs (la première composante non nulle de chaque vecteur doit être strictement positive).

• IKJ : (Lignes 1, 3, 2). Nouvelle MDD = |0 1 1| ; |0 0 -1| ; |1 1 0|^T (soit les vecteurs (0,0,1)^T, (1,0,1)^T et (1,-1,0)^T). Tous les vecteurs sont lexicographiquement positifs. Valide. Types : B1(i) est Séquentielle (porte d2, d3). B2(k) est Séquentielle (porte d1). B3(j) est Parallèle (ne porte rien, car d3 est portée par B1).
• JIK : (Lignes 2, 1, 3). Nouvelle MDD = |1 1 0| ; |0 1 1| ; |0 0 -1|^T (vecteurs (1,0,0)^T, (1,1,0)^T et (0,1,-1)^T). Tous positifs. Valide. Types : B1(j) est Séquentielle (porte d1, d2). B2(i) est Séquentielle (porte d3). B3(k) est Parallèle.
• JKI : (Lignes 2, 3, 1). Le 3ème vecteur devient (0, -1, 1)^T. Sa première composante non nulle est négative. Non valide.
• KIJ : (Lignes 3, 1, 2). Le 3ème vecteur devient (-1, 1, 0)^T. Négatif. Non valide.
• KJI : (Lignes 3, 2, 1). Le 3ème vecteur devient (-1, 0, 1)^T. Négatif. Non valide.

Question 4 - Inversion des boucles pour les permutations non valides

L'inversion d'une boucle (ex: exécuter de n à 1 avec un pas de -1) multiplie la ligne correspondante de la MDD par -1.

• JKI : La dépendance problématique est d3 = (0, -1, 1)^T. Le problème vient de la ligne K (deuxième ligne de la nouvelle matrice) qui vaut -1. En inversant K (noté -K), on obtient le nid J, -K, I. Nouvelle MDD = |1 1 0| ; |0 0 1| ; |0 1 1|^T. Tous positifs. Valide. Types : B1(j) Séquentielle (porte d1, d2). B2(-k) Séquentielle (porte d3). B3(i) Parallèle.
• KIJ : La dépendance problématique est d3 = (-1, 1, 0)^T. Le -1 est sur la ligne K (première ligne). En inversant K, le nid devient -K, I, J. Nouvelle MDD = |0 0 1| ; |0 1 1| ; |1 1 0|^T. Tous positifs. Valide. Types : B1(-k) Séquentielle (porte d3). B2(i) Séquentielle (porte d2). B3(j) Séquentielle (porte d1).
• KJI : La dépendance problématique est d3 = (-1, 0, 1)^T. En inversant K, on obtient -K, J, I. Nouvelle MDD = |0 0 1| ; |1 1 0| ; |0 1 1|^T. Tous positifs. Valide. Types : B1(-k) Séquentielle (porte d3). B2(j) Séquentielle (porte d1, d2). B3(i) Parallèle.

Question 5 - Comparaison des nids obtenus et temps d'exécution

Le temps d'exécution parallèle (Tpar) s'évalue en considérant le produit du nombre d'itérations des boucles séquentielles (les boucles parallèles s'exécutent en temps 1 grâce à l'infinité de processeurs).

Nid	Boucles (S/P)	Position boucle //	Itérations parallèles	Tpar (coût 1 par itération séquentielle)
I, J, K (Original)	S, S, P	3ème (B3: k)	n3	n1 × n2
I, K, J	S, S, P	3ème (B3: j)	n2	n1 × n3
J, I, K	S, S, P	3ème (B3: k)	n3	n2 × n1
J, -K, I	S, S, P	3ème (B3: i)	n1	n2 × n3
-K, I, J	S, S, S	Aucune	1	n3 × n1 × n2
-K, J, I	S, S, P	3ème (B3: i)	n1	n3 × n2

Le choix optimal dépendra de la plus grande valeur parmi n1, n2 et n3, pour maximiser le parallélisme. Le nid -K, I, J est le pire car purement séquentiel.

Exercice 2 - Analyse et transformation d'un espace d'itérations triangulaire

Question 1 - Nombre d'éléments de l'espace d'itérations E

L'espace d'itérations est E = { (i,j) | 1 ≤ i ≤ n, 1 ≤ j ≤ 3i }. Pour un i donné, la boucle B2 exécute 3i itérations. Le nombre total d'éléments est la somme des 3i pour i allant de 1 à n : Σ (3i) = 3 × Σ i = 3 × (n × (n+1) / 2).

Question 2 - Représentation de E pour n=4

Pour n=4, le nombre total de points est 3 × 4 × 5 / 2 = 30 points. On peut représenter l'espace par une grille de coordonnées (i,j) :

• i=1 : j de 1 à 3 (3 points)
• i=2 : j de 1 à 6 (6 points)
• i=3 : j de 1 à 9 (9 points)
• i=4 : j de 1 à 12 (12 points)

Question 3 - Analyse de dépendance et MDD

L'instruction écrit dans A(i,j) et lit A(i+1,j+1) et A(i,j+1).

• Lecture de A(i+1, j+1) : L'élément est écrit à l'itération cible (i+1, j+1). La lecture à l'itération source (i,j) se produit chronologiquement avant l'écriture. C'est une anti-dépendance. Vecteur d1 = (i+1, j+1) - (i, j) = (1, 1).
• Lecture de A(i, j+1) : Anti-dépendance similaire. Vecteur d2 = (i, j+1) - (i, j) = (0, 1).

La matrice M est :

    | 1  0 |
M = | 1  1 |

• Type de B1 (i) : La première ligne de M contient un 1. B1 porte la dépendance d1 = (1,1). Elle est Séquentielle.
• Type de B2 (j) : La dépendance d2 = (0,1) n'est pas portée par B1. Sa première composante non nulle est sur la ligne de B2. B2 est donc Séquentielle.

Question 4 - Graphe de dépendance pour n=4

Dans l'espace triangulaire E représenté à la question 2 :

• Chaque point (i,j) est relié au point (i+1, j+1) par une flèche (diagonale bas-droite) représentant d1, à condition que ce point cible existe.
• Chaque point (i,j) est relié au point (i, j+1) par une flèche (horizontale droite) représentant d2, si la cible existe.

Question 5 - Validité de la permutation de B1 et B2 et nouveau nid NP

La MDD permutée devient :

     | 1  1 |
M' = | 1  0 |

Les vecteurs (1,1)^T et (1,0)^T sont tous les deux lexicographiquement positifs. La permutation est sur le plan des dépendances valide.

Géométriquement, l'espace d'origine est 1 ≤ i ≤ n et 1 ≤ j ≤ 3i. En inversant les bornes pour que j soit la boucle externe :

• j varie de 1 à la valeur maximale possible, soit 3n.
• Pour un j donné, i doit vérifier i ≤ n et 3i ≥ j (soit i ≥ j/3). Comme i est entier, i démarre à CEILING(j/3.0) (partie entière supérieure).

Le nouveau nid NP s'écrit (en utilisant la syntaxe Fortran DOSER pour séquentiel et DOPAR pour parallèle) :

      DOSER j=1, 3*n                             / Boucle B'1 /
             DOPAR i=CEILING(j/3.0), n           / Boucle B'2 /
                   A(i,j)=A(i+1,j+1)+A(i,j+1)
             ENDDO
      ENDDO

• Type des boucles : Avec la nouvelle matrice M', la première ligne contient uniquement des 1. La boucle externe B'1(j) porte toutes les dépendances. B'1 est donc Séquentielle et B'2(i) est Parallèle.

Question 6 - Analyse des performances parallèles de NP

Le nombre de processeurs np correspond au nombre maximal d'itérations de la boucle parallèle B'2. B'2 exécute n - CEILING(j/3.0) + 1 itérations. Cette valeur est maximale lorsque j=1 (où CEILING(1/3.0) = 1). Le maximum est donc n - 1 + 1 = n. np = n.

• Temps d'exécution parallèle (Tpar) : B'1 exécute 3n itérations séquentielles. À chaque étape, l'intérieur est entièrement parallélisé (temps 1 car on a n processeurs). Donc Tpar = 3n.
• Accélération (Sp) : Sp = Temps séquentiel / Tpar = (3 × n × (n+1) / 2) / (3n) = (n+1) / 2.
• Efficacité (Ep) : Ep = Sp / np = ((n+1)/2) / n = (n+1) / (2n).

(Vérification indicative : pour n=4, E de N compte 30 éléments. Pour NP, j va de 1 à 12. La somme des itérations de B'2 est 3×(4-1+1) + 3×(4-2+1) + 3×(4-3+1) + 3×(4-4+1) = 12 + 9 + 6 + 3 = 30 éléments. Les deux espaces sont identiques).

Exercice 3 - Analyse d'une matrice des signes

Question 1 - Type de chaque boucle du nid

La matrice M contient les signes :

    | 0  1  1 |
M = | 0  0 -1 |
    | 1  1 -1 |

Les vecteurs colonnes sont d1=(0,0,1)^T, d2=(1,0,1)^T, et d3=(1,-1,-1)^T.

• B1 (i) : La ligne 1 contient des 1 pour d2 et d3. B1 porte d2 et d3. B1 est Séquentielle.
• B2 (j) : Il ne reste que d1 qui n'est pas portée. Or, la composante de d1 sur la ligne 2 est 0. B2 ne porte aucune dépendance. B2 est Parallèle.
• B3 (k) : d1 a sa première composante non nulle (qui vaut 1) sur la ligne 3. B3 porte d1. B3 est Séquentielle.

Question 2 - Validité des 5 permutations et types des boucles

Vérifions les permutations de M :

• IKJ : (Lignes 1, 3, 2). Vecteurs : (0,1,0)^T, (1,1,0)^T, (1,-1,-1)^T. Tous positifs. Valide. Types : B1(i) Séquentielle (porte d2, d3). B2(k) Séquentielle (porte d1). B3(j) Parallèle.
• JIK : (Lignes 2, 1, 3). Le vecteur d3 devient (-1, 1, -1)^T (négatif). Non valide.
• JKI : (Lignes 2, 3, 1). Le vecteur d3 devient (-1, -1, 1)^T (négatif). Non valide.
• KIJ : (Lignes 3, 1, 2). Le vecteur d3 devient (-1, 1, -1)^T (négatif). Non valide.
• KJI : (Lignes 3, 2, 1). Le vecteur d3 devient (-1, -1, 1)^T (négatif). Non valide.

Question 3 - Inversion de boucle sur les permutations non valides

Les vecteurs problématiques proviennent tous de d3 original (1, -1, -1)^T.

• JIK : (d3 = -1, 1, -1). En inversant la première boucle J (qui porte le -1), on obtient le nid -J, I, K. d3 devient (1, 1, -1)^T. Tous les vecteurs sont positifs. Valide. Types : B1(-j) S (porte d3). B2(i) S (porte d2). B3(k) S (porte d1).
• JKI : (d3 = -1, -1, 1). En inversant J, on obtient -J, K, I. d3 devient (1, -1, 1)^T. Positif. Valide. Types : B1(-j) S (porte d3). B2(k) S (porte d1, d2). B3(i) Parallèle.
• KIJ : (d3 = -1, 1, -1). L'indice K (ligne 1 du nid permuté) est responsable du -1 pour d3, ce qui forcerait à inverser K pour valider d3. Mais si on inverse K, d1 (qui vaut (1,0,0)^T dans ce nid) deviendrait (-1,0,0)^T et rendrait d1 illégal. Il est donc impossible de rendre ce nid valide par simple inversion. Aucun nid valide.
• KJI : Même problème. d3 a un signe de -1 sur l'axe K, mais d1 a un signe de +1 sur ce même axe. Inverser K corrige l'un mais casse l'autre. Aucun nid valide.

Question 4 - Comparaison des nids obtenus

• I, J, K : 1 boucle parallèle B2 (j). n2 itérations parallèles.
• I, K, J : 1 boucle parallèle B3 (j). n2 itérations parallèles.
• -J, I, K : Aucune boucle parallèle (nid 100% séquentiel). 1 itération parallèle (exécution triviale).
• -J, K, I : 1 boucle parallèle B3 (i). n1 itérations parallèles.

Exercice 4 - Analyse générique paramétrée

Question 2 - Analyse de dépendances et VDD

L'instruction écrit dans A(i,j,k) (source de la dépendance) et lit A(i+d1, j+d2, k+d3). Deux cas de figure engendrent la dépendance :

1. Le flot d'exécution passe d'abord par l'écriture puis par la lecture (Dépendance vraie ou de Flot). Dans ce cas, la distance est Sink - Source = (i,j,k) - (i-d1, j-d2, k-d3) = (d1, d2, d3) ? Non, la lecture a lieu à (i+d1, j+d2, k+d3). Si l'itération source est (I, J, K) et l'itération puits est (I+d1, J+d2, K+d3), alors le vecteur est (-d1, -d2, -d3).
2. Le flot d'exécution passe d'abord par la lecture puis par l'écriture (Anti-dépendance). Le vecteur distance est (d1, d2, d3).

Puisqu'un vecteur de distance VDD doit, par définition, être lexicographiquement strictement positif, on détermine le VDD comme étant l'unique vecteur strictement positif parmi l'ensemble {(d1, d2, d3), (-d1, -d2, -d3)}. Pour l'exemple où d1=1, d2=0, d3=0, (1,0,0) > 0, c'est une anti-dépendance et le VDD est (1,0,0)^T.

Question 3 - Nature de chaque boucle et configurations

Soit V = (v1, v2, v3) le VDD déterminé ci-dessus (qui est lexicographiquement positif). Puisqu'il n'y a qu'une seule dépendance, une boucle est Séquentielle (S) si et seulement si elle est la première boucle à présenter une composante non nulle dans le VDD. Les autres boucles ne portant rien, elles sont Parallèles (P).

• SPP : La boucle 1 porte le VDD. Condition : v1 > 0, c'est-à-dire d1 ≠ 0. Exemple : d1 = 1, d2 = 0, d3 = 0.
• PSP : La boucle 1 ne porte rien (v1 = 0), la boucle 2 porte (v2 > 0). Condition : d1 = 0 et d2 ≠ 0. Exemple : d1 = 0, d2 = 1, d3 = 0.
• PPS : Les boucles 1 et 2 ne portent rien, la boucle 3 porte (v3 > 0). Condition : d1 = 0, d2 = 0 et d3 ≠ 0. Exemple : d1 = 0, d2 = 0, d3 = 1.
• PPP : Aucune dépendance. Condition : d1 = 0, d2 = 0, d3 = 0. Toutes les boucles sont parallèles. Exemple : d1 = 0, d2 = 0, d3 = 0.

Question 4 - Conditions de légalité des 5 permutations

Une permutation est légale géométriquement et sur le plan des dépendances si le nouveau VDD (après avoir permuté les lignes de v1, v2, v3 selon l'ordre des boucles) reste lexicographiquement positif. En posant le vecteur d'origine valide V = (v1, v2, v3) > 0 :

• JIK : Vecteur permuté (v2, v1, v3). Valide si v2 > 0 ou (v2 = 0 et v1 > 0). Donc condition: v2 ≥ 0.
• IKJ : Vecteur permuté (v1, v3, v2). Valide si v1 > 0 ou (v1 = 0 et v3 ≥ 0). Donc condition: v1 > 0 ou v3 ≥ 0.
• JKI : Vecteur permuté (v2, v3, v1). Valide si v2 > 0 ou (v2 = 0 et v3 ≥ 0).
• KIJ : Vecteur permuté (v3, v1, v2). Valide si v3 > 0 ou (v3 = 0 et v1 ≥ 0).
• KJI : Vecteur permuté (v3, v2, v1). Valide si v3 > 0 ou (v3 = 0 et v2 ≥ 0).

Question 5 - Application avec d1 = -1, d2 = 1, d3 = 0

5.1 VDD et type des boucles : Le vecteur (d1, d2, d3) = (-1, 1, 0) est lexicographiquement négatif. L'autre sens (-d1, -d2, -d3) = (1, -1, 0) est positif. VDD = (1, -1, 0). La composante de B1 n'est pas nulle (elle vaut 1). B1 est Séquentielle, B2 et B3 sont Parallèles. Type : SPP.

5.2 Permutations légales et nouveaux nids : On teste le VDD (1, -1, 0) avec les différentes permutations :

• JIK : (-1, 1, 0) -> Non légal.
• IKJ : (1, 0, -1) -> Légal. Type : B1 porte, B2, B3 non. SPP.
• JKI : (-1, 0, 1) -> Non légal.
• KIJ : (0, 1, -1) -> Légal. Type : B1 (valeur 0) ne porte pas, B2 porte, B3 non. PSP.
• KJI : (0, -1, 1) -> Non légal.

Les nids s'obtiennent en refaisant le calcul des bornes (intersection du domaine 1 ≤ i ≤ n ; i ≤ j ≤ n ; i ≤ k ≤ n) : Nid IKJ :

      DO i=1, n
             DO k=i, n
                   DO j=i, n
                         A(i,j,k) = E(A(i-1,j+1,k))
                   ENDDO
             ENDDO
      ENDDO

Nid KIJ :

      DO k=1, n
             DO i=1, k
                   DO j=i, n
                         A(i,j,k) = E(A(i-1,j+1,k))
                   ENDDO
             ENDDO
      ENDDO

5.3 L'inversion de boucles pour les permutations non légales : Les nids non légaux échouent tous à cause de la boucle J dont la composante permutée est -1. En appliquant l'inversion de boucle sur la boucle J (ce qui modifie le signe de sa coordonnée dans le vecteur), nous obtenons :

• JIK : avec inversion de J (-J, I, K), le vecteur devient (1, 1, 0). Légal.
• JKI : avec inversion de J (-J, K, I), le vecteur devient (1, 0, 1). Légal.
• KJI : avec inversion de J (K, -J, I), le vecteur devient (0, 1, 1). Légal. Oui, l'inversion de la boucle J permet systématiquement de rendre légales ces trois permutations, au prix d'un parcours décroissant pour l'indice J.

Exercice 5 - Analyse d'un nid parfait à trois boucles (Identique à l'Exercice 1)

(Le sujet tel qu'il a été restitué présente un "Exercice 5" dont l'énoncé et les questions sont rigoureusement identiques, caractère par caractère, à l'Exercice 1. Afin de ne négliger aucune question sans pour autant dupliquer sans valeur ajoutée, vous trouverez ci-dessous les conclusions directes).

Question 1 - MDD

Comme pour l'Exercice 1, les dépendances sont des anti-dépendances avec vecteurs de distance : (0,1,0)^T, (1,1,0)^T, (1,0,-1)^T.

Question 2 - Type de chaque boucle

La matrice M décrète la boucle B1(i) comme séquentielle (porte d2, d3), la boucle B2(j) comme séquentielle (porte d1) et la boucle B3(k) comme parallèle.

Question 3 - Validité des 5 permutations

Les permutations IKJ et JIK maintiennent des colonnes MDD lexicographiquement positives et sont valides (toutes deux donnent un schéma SPP pour les boucles résultantes). Les permutations JKI, KIJ et KJI produisent des vecteurs négatifs et sont invalides.

Question 4 - Utilisation de l'inversion de boucle

Les 3 permutations invalides (JKI, KIJ, KJI) peuvent être corrigées en inversant strictement la boucle problématique K. Elles deviennent respectivement (J, -K, I) (schéma SSP), (-K, I, J) (schéma SSS), et (-K, J, I) (schéma SSP).

Question 5 - Comparaison

Le nid originel (I,J,K) et ses variantes validées (comme J,I,K) offrent n3 et n1 itérations parallèles respectivement. Le temps d'exécution en parallèle massif est dominé par le produit des itérations des deux boucles séquentielles (ex: n1 × n2 pour le nid d'origine).

Méthode

Voici la méthode systématique pour analyser et transformer les nids de boucles, à appliquer lors des révisions :

1. Identification des dépendances : Pour chaque instruction, listez l'indice d'écriture puis tous les indices de lecture. Calculez les écarts entre l'indice qui exécute la source et celui qui exécute le puits de l'opération. (Rappel : on s'intéresse à l'ordre d'accès au niveau matériel).
2. Formation de la MDD : Le vecteur de distance D = Itération_Puits - Itération_Source doit toujours être lexicographiquement positif (la première valeur de la colonne non nulle doit être > 0). Assemblez-les en colonnes pour former la Matrice des Distances de Dépendances.
3. Qualification des boucles (S ou P) : On évalue chaque ligne de la MDD (de haut en bas). Si une ligne contient la première valeur non nulle d'une colonne de dépendance (nécessairement positive), cette boucle "porte" la dépendance et devient purement Séquentielle.
4. Transformation et validité : Permuter des boucles revient à permuter les lignes de la MDD. La condition stricte de validité d'une permutation est qu'aucun vecteur de la nouvelle MDD ne devienne lexicographiquement négatif.
5. Inversion : Si une permutation engendre un vecteur invalide à cause d'une composante négative sur sa ligne dominante, alors le remplacement de l'indice de cette boucle (parcours inverse, modélisé par -1) retourne le signe et résout potentiellement l'illégalité, sous réserve de ne pas invalider les dépendances adjacentes.