Calcul parallèle et Distribué (CPD): Exercises on Loop Nestings and Dependency Analysis
Calcul parallèle et Distribué (CPD): Exercises on Loop Nestings and Dependency Analysis
Parallel Computing · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
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 :
(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).(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).(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 |
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).
(0, 1, 1). B1 porte les dépendances d2 = (1,1,0) et d3 = (1,0,-1). Elle est donc séquentielle.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.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).
|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).|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.(0, -1, 1)^T. Sa première composante non nulle est négative. Non valide.(-1, 1, 0)^T. Négatif. Non valide.(-1, 0, 1)^T. Négatif. Non valide.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.
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.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).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.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.
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).
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) :
L'instruction écrit dans A(i,j) et lit A(i+1,j+1) et A(i,j+1).
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).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 |
d1 = (1,1). Elle est Séquentielle.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.Dans l'espace triangulaire E représenté à la question 2 :
d1, à condition que ce point cible existe.d2, si la cible existe.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.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
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.
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.(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).
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.
Vérifions les permutations de M :
(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.(-1, 1, -1)^T (négatif). Non valide.(-1, -1, 1)^T (négatif). Non valide.(-1, 1, -1)^T (négatif). Non valide.(-1, -1, 1)^T (négatif). Non valide.Les vecteurs problématiques proviennent tous de d3 original (1, -1, -1)^T.
-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).-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.-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.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 :
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).(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.
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).
v1 > 0, c'est-à-dire d1 ≠ 0.
Exemple : d1 = 1, d2 = 0, d3 = 0.d1 = 0 et d2 ≠ 0.
Exemple : d1 = 0, d2 = 1, d3 = 0.d1 = 0, d2 = 0 et d3 ≠ 0.
Exemple : d1 = 0, d2 = 0, d3 = 1.d1 = 0, d2 = 0, d3 = 0. Toutes les boucles sont parallèles.
Exemple : d1 = 0, d2 = 0, d3 = 0.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 :
(v2, v1, v3). Valide si v2 > 0 ou (v2 = 0 et v1 > 0). Donc condition: v2 ≥ 0.(v1, v3, v2). Valide si v1 > 0 ou (v1 = 0 et v3 ≥ 0). Donc condition: v1 > 0 ou v3 ≥ 0.(v2, v3, v1). Valide si v2 > 0 ou (v2 = 0 et v3 ≥ 0).(v3, v1, v2). Valide si v3 > 0 ou (v3 = 0 et v1 ≥ 0).(v3, v2, v1). Valide si v3 > 0 ou (v3 = 0 et v2 ≥ 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 :
(-1, 1, 0) -> Non légal.(1, 0, -1) -> Légal. Type : B1 porte, B2, B3 non. SPP.(-1, 0, 1) -> Non légal.(0, 1, -1) -> Légal. Type : B1 (valeur 0) ne porte pas, B2 porte, B3 non. PSP.(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 :
(-J, I, K), le vecteur devient (1, 1, 0). Légal.(-J, K, I), le vecteur devient (1, 0, 1). Légal.(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.(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).
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.
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.
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.
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).
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).
Voici la méthode systématique pour analyser et transformer les nids de boucles, à appliquer lors des révisions :
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.