Parallélisation des programmes polyédriques – Partie 2
Parallélisation des programmes polyédriques – Partie 2
Programming, Math · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document traite de la détection et de l'extraction du parallélisme dans les programmes polyédriques, en particulier au sein des nids de boucles. Il s'adresse aux étudiants et chercheurs en informatique et en optimisation de programmes, souhaitant comprendre comment analyser et transformer des boucles imbriquées pour améliorer le parallélisme d'exécution.
La détection du parallélisme dans un nid de boucles polyédriques repose sur l'analyse des niveaux de dépendances, aussi appelés profondeurs de dépendance. Le niveau de dépendance correspond à la position du premier coefficient strictement positif dans le vecteur des distances ou des signes de dépendance. Ce niveau indique la boucle qui doit rester séquentielle pour préserver la lexico-positivité des dépendances.
Dans un nid parfait de profondeur n, si une dépendance est portée par la boucle de profondeur k (1 ≤ k ≤ n), cette boucle est séquentielle. En l'absence de dépendance de niveau k, la boucle k est parallèle. Ainsi, la connaissance de la Matrice des Distances de Dépendance (MDD) permet de déterminer le type (séquentielle ou parallèle) de chacune des n boucles.
DO i1 = 1, n // Boucle B1 //
DO i2 = 1, n // Boucle B2 //
A(i1, i2) = A(i1, i2 - 1) // corps H
ENDDO
ENDDO
VDD = VSDD = (
0
1
)
Il y a une seule dépendance de niveau 2. La boucle B2 est donc séquentielle, tandis que la boucle B1 est parallèle. Le nid est noté (p,s).
DO i1 = 1, n // Boucle B1 //
DO i2 = 1, n // Boucle B2 //
DO i3 = 1, n // Boucle B3 //
A(i1, i2) = A(i1 + 1, i2 - 1, i3 + 1) + A(i1, i2, i3 - 1) // corps H
ENDDO
ENDDO
ENDDO
MDD = MSDD = (
1
-1
1
0
0
1
)
Il y a une dépendance de niveau 1 (B1 séquentielle) et une de niveau 3 (B3 séquentielle). La boucle B2 est parallèle car aucune dépendance de niveau 2 n'existe. Le nid est noté (s,p,s).
Pour extraire le parallélisme implicite dans un nid de boucles, on applique des transformations qui produisent un programme sémantiquement équivalent mais avec plus de parallélisme. Ces transformations doivent être validées pour préserver la sémantique, en conservant la lexico-positivité des vecteurs de dépendance (VDD) dans la MDD.
Deux classes de transformations existent :
Nous présentons ici deux transformations unimodulaires élémentaires : l'inversion et la permutation des boucles, ainsi qu'une transformation non unimodulaire : la distribution des boucles.
Soit un nid parfait N de profondeur n. Une matrice unimodulaire U est une matrice carrée d'ordre n avec des coefficients entiers et un déterminant égal à ±1. Appliquer la transformation unimodulaire TU définie par U sur N donne un nouveau nid parfait N'. Les espaces d'itération et vecteurs d'itération des deux nids sont homologues.
La transformation est valide si les nouveaux vecteurs de dépendance (colonnes de la MDD) restent lexicographiquement positifs (premier élément non nul positif). Sinon, la transformation est non valide.
L'inversion d'une boucle Bk (1 ≤ k ≤ n) consiste à inverser son compteur ik, de bornes lk à uk avec pas 1, en un compteur i'k = -ik avec bornes -lk à -uk et pas 1, équivalent à faire varier ik de uk à lk avec pas -1.
Nid original N
DO i1 = l1, u1
...
DO ik = lk, uk
...
DO in = ln, un
H(i1, ..., ik, ..., in)
ENDDO
...
ENDDO
...
ENDDO
Nid après inversion de Bk
DO i1 = l1, u1
...
DO i'k = -lk, -uk
...
DO in = ln, un
H(i1, ..., -i'k, ..., in)
ENDDO
...
ENDDO
...
ENDDO
Equivalent à
DO i1 = l1, u1
...
DO ik = uk, lk, -1
...
DO in = ln, un
H(i1, ..., ik, ..., in)
ENDDO
...
ENDDO
...
ENDDO
La matrice unimodulaire U correspondante est la matrice identité où l'élément 1 à la ligne k est remplacé par -1.
Pour le nid de l'Exemple 4.1 avec VDD = (0, 1), l'inversion de la première boucle (U = (-1 0; 0 1)) donne un nouveau VDD = (0, 1), toujours lexicographiquement positif, donc la transformation est valide.
En revanche, l'inversion de la seconde boucle (U = (1 0; 0 -1)) donne un VDD = (0, -1), non lexicographiquement positif, donc non valide.
La permutation de boucles (ou échange de boucles) consiste à échanger l'ordre d'exécution des boucles imbriquées. La matrice U est obtenue en permutant les lignes de la matrice identité selon la permutation souhaitée. La transformation est valide si la nouvelle MDD M' = U × M est lexicographiquement positive.
Pour un nid parfait de profondeur n, il existe n! permutations possibles.
En reprenant l'Exemple 4.1, la permutation des deux boucles correspond à :
U = (0 1
1 0)
Le nouveau VDD est alors (1, 0), lexicographiquement positif, donc la permutation est valide. Le nid transformé est :
DO i2 = 1, 5
DO i1 = 1, 5
A(i1, i2) = A(i1, i2 - 1)
ENDDO
ENDDO
Cette permutation modifie l'ordre d'exécution des itérations tout en respectant les dépendances.
Lorsque les bornes des boucles sont des expressions affines des compteurs des boucles englobantes, la permutation nécessite de recalculer les nouvelles bornes. Cette procédure réécrit les inéquations vérifiées par les compteurs pour exprimer les nouvelles bornes en fonction des anciennes, souvent sous forme de maximums et minimums d'expressions affines.
Nid parfait N
DO i1 = 1, 5
DO i2 = i1 + 1, i1 + 5
A(i1, i2) = A(i1, i2 - 1)
ENDDO
ENDDO
Nid N' après permutation des boucles
DO i2 = 2, 10
DO i1 = max(1, i2 - 5), min(5, i2 - 1)
A(i1, i2) = A(i1, i2 - 1)
ENDDO
ENDDO
Les inéquations initiales :
se réécrivent en :
Les espaces d'itération et graphes de dépendances sont ainsi adaptés au nouveau nid.
Par exemple, avec trois boucles imbriquées, la configuration (p,s,s) est préférable à (s,p,s), elle-même préférable à (s,s,p).
MDD = (
1
-1
1
0
0
1
)
Nid initial : (s,p,s)
MDD (j-1,i,k) = (
1
1
1
0
0
1
)
Nid transformé : (s,p,s)
La boucle parallèle est i au lieu de j, ce qui peut améliorer le parallélisme si la boucle i a plus d'itérations.
MDD (j-1,k,i) = (
1
1
1
0
1
0
)
Nid transformé : (s,s,p)
Cette version est moins favorable que la précédente en termes de mode de parallélisme.