Calcul parallèle et Distribué (CPD)
Calcul parallèle et Distribué (CPD)
Programming, Math, etc. · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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
La dépendance vient des indices des accès aux éléments de A :
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]]
Une boucle est parallèle si toutes les distances de dépendances sur son indice sont nulles ou positives. Ici :
Réponse : B1 séquentielle, B2 parallèle, B3 séquentielle.
Les permutations sont :
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.
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 :
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 :
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 :
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 :
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.
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
L'espace d'itérations E est l'ensemble des couples (i,j) tels que :
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.
Pour n=4, on a :
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.
Les accès dans l'instruction sont :
Les distances de dépendance sont donc :
M = [[1, 0], [1, 1]]
Explication :
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.
Le graphe de dépendance relie chaque itération (i,j) à :
Pour n=4, on a les arcs :
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.
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 :
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 :
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.
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.
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 |
On analyse les signes des distances :
Réponse : B1 (i) parallèle, B2 (j) parallèle, B3 (k) séquentielle.
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 :
Pour les permutations valides :
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.
Pour KIJ et KJI, on peut inverser la boucle k pour rendre les dépendances positives :
Réponse : En inversant la boucle k, KIJ et KJI deviennent valides avec k séquentielle, i et j parallèles.
Les permutations valides ont toujours deux boucles parallèles (i et j) et une séquentielle (k). La position des boucles parallèles varie :
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.
Ce sujet récompense la maîtrise de l’analyse des dépendances dans des nids de boucles parfaits, notamment :
Les erreurs pénalisées sont :