Calcul parallèle et Distribué (CPD)
2019-2020
EXERCICE 1
On considère le nid parfait N suivant :
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.
2. En déduire le type de chaque boucle du nid N (séquentielle ou parallèle).
3. Etudier la validité des 5 permutations des boucles du nid N (notées IKJ, JIK, JKI, KIJ et
KJI) et donner pour chaque permutation valide la MDD correspondante. En déduire le type
de chaque boucle du nid correspondant.
4. Etudier, 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.
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.
EXERCICE 2
On considère le nid N suivant :
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
Publicité
1. Déterminer le nombre d'éléments de l'espace d'itérations E de N.
2. Représenter E pour n=4.
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).
4. Représenter, dans E, le graphe de dépendance pour n=4.
5. Etudier la validité de la permutation des boucles B1 et B2. Dans le cas où cette
transformation est valide, écrire le nouveau nid, noté 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).
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.
Remarque : on vérifiera à titre indicatif que les espaces d’itérations E de N et E’ de NP ont
le même nombre d’éléments pour n=4.
EXERCICE 3
On considère le nid parfait N suivant :
DO i=1,n1 / Boucle B1 /
DO j=1,n2 / Boucle B2 /
DO k=1,n3 / Boucle B3 /
S(i,j,k) / S(i,j,k) de coût 1/
ENDDO
ENDDO
ENDDO
L’analyse de dépendances au sein de N conduit à la matrice des signes des distances de
dépendances suivante :
0 1 1
M = 0 0 -1
1 1 -1
Publicité
1. Déterminer le type de chaque boucle du nid (séquentielle ou parallèle).
2. Etudier la validité des 5 permutations des boucles du nid et donner pour chaque
permutation valide le type de chaque boucle du nid correspondant.
3. Etudier 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.
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 (n1, n2 et n3
sont des entiers positifs quelconques).
EXERCICE 4
On considère le nid parfait N suivant :
DO i=1,n / Boucle B1 /
DO j=i,n / Boucle B2 /
DO k=i,n / Boucle B3 /
A(i,j,k) = E((A(i+d1,j+d2,k+d3)) / Ti,j,k) de coût 1 /
ENDDO
ENDDO
ENDDO
E est une expression arithmétique, d1, d2 et d3 sont des entiers relatifs appartenant à
l’ensemble {-1,0,1}.
2. Effectuer l’analyse de dépendances au sein du nid. En déduire le VDD (vecteur des
distances de dépendances). Vérifier vos résultats en prenant des valeurs
pour d1, d2 et d3.
3. Déterminer la nature (séquentielle ou parallèle) de chaque boucle du nid en discutant sur
les valeurs des trois coefficients d1, d2 et d3. On déterminera particulièrement à quelles
conditions (sur d1, d2 et d3) on a les configurations suivantes : PPP, PPS, SPP, PSP. Préciser
dans chaque cas des valeurs particulières des trois coefficients.
4. À quelle(s) conditions (sur d1, d2 et d3), les 5 permutations du nid N (notées JIK, IKJ,
JKI, KIJ et KJI) sont elles légales?
Publicité
5. On prend d1 = -1, d2 = 1 et d3 = 0.
5.1 Déterminer le VDD et en déduire type de chaque boucle deN .
5.2 Déterminer les permutations légales. Ecrire les nids correspondants. Déterminer pour
chacun de ces nids la nature de chacune de ses trois boucles.
5.3 L’inversion de boucles peut elle rendre légales les permutations non légales?
EXERCICE 5
On considère le nid parfait N (noté IJK) suivant :
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.
2. En déduire le type de chaque boucle du nid N (séquentielle ou parallèle).
3. Etudier la validité des 5 permutations des boucles du nid N (notées IKJ, JIK, JKI, KIJ et
KJI) et donner pour chaque permutation valide la MDD correspondante. En déduire le type
de chaque boucle du nid correspondant.
4. Etudier, 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.
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.