Parallélisation des programmes polyédriques –Partie 2
Dans cette deuxième partie du cours, nous s’intéressons à la détection et extraction du
parallélisme au sein des nids de boucles dits polyédriques. Nous explicitons d’abord la détection
des boucles parallèles puis nous définissons certaines transformations de boucles permettant
d’améliorer le parallélisme du nid.
4. Détection de parallélisme
Comme déjà mentionné, à partir des niveaux de dépendances d’un programme, nous pouvons
détecter le parallélisme et déterminer ainsi la nature des boucles du nid, c’est-à-dire lesquelles
sont parallèles (p) et lesquelles sont séquentielles (s).
Rappelons que le niveau de dépendance (appelé aussi profondeur de dépendance) correspond à
la position du premier coefficient non nul qui est strictement positif dans le vecteur des
distances ou des signes de dépendance (voir partie 1, section 3.2). Ce niveau de dépendance
détermine la boucle qui doit rester séquentielle pour conserver la lexico-positivité des
dépendances. Cette notion permet de définir le type de chaque boucle du nid i.e. séquentielle
ou parallèle. Si dans un nid parfait de profondeur n, il y a un niveau de dépendance k (1≤ k ≤
n), nous dirons qu’il y a une dépendance portée par la boucle de profondeur k. Cette boucle sera
considérée comme séquentielle. Par conséquent, l’absence d’une dépendance de niveau k
implique que la boucle de profondeur k est parallèle. De ce fait, la connaissance de la MSDD
permet de déterminer le type de chacune des n boucles (séquentielle ou parallèle).
Exemple 4.1
Soit le nid parfait de deux boucles N suivant :
N
DO 𝑖1 = 1, 𝑛 // Boucle B1 //
DO 𝑖2 = 1, 𝑛 // Boucle B2 //
𝐴(𝑖1, 𝑖2) = 𝐴(𝑖1, 𝑖2 − 1) // corps H
ENDDO
ENDDO
1
𝑉𝐷𝐷 = 𝑉𝑆𝐷𝐷 = (
0
1
)
Il y a une seule dépendance de niveau 2. Donc la deuxième boucle B2 est séquentielle et la
première boucle B1 est parallèle. Le nid est dit (p,s).
Exemple 4.2
Soit le nid parfait de deux boucles N suivant :
N
DO 𝑖1 = 1, 𝑛 // Boucle B1 //
DO 𝑖2 = 1, 𝑛 // Boucle B2 //
DO 𝑖3 = 1, 𝑛 // Boucle B3 //
𝐴(𝑖1, 𝑖2) = 𝐴(𝑖1 + 1, 𝑖2 − 1, 𝑖3 + 1)
ENDDO
ENDDO
ENDDO
+𝐴(𝑖1, 𝑖2, 𝑖3 − 1) // corps H
𝑀𝐷𝐷 = 𝑀𝑆𝐷𝐷 = (
1
−1
1
)
0
0
1
Il y a une dépendance de niveau 1. Donc la première boucle B1 est séquentielle.
Il y a une dépendance de niveau 3. Donc la première boucle B3 est séquentielle.
La deuxième boucle B2 est parallèle car il n’y a aucune dépendance de niveau 2.
Le nid est dit (s,p,s).
5. Extraction du parallélisme : Transformation de programmes
Lors de la parallélisation des nids de boucles, nous pouvons utiliser diverses transformations
qui, partant d’un programme initial, génèrent un programme sémantiquement équivalent mais
exhibant plus de parallélisme. Il se trouve souvent qu’un nid de boucles renferme des
dépendances explicites mais comporte un parallélisme implicite qu’on peut extraire en
appliquant une transformation du programme. Même dans le cas extrême où l’analyse de
dépendance permet de détecter que toutes les boucles d’un nid sont séquentielles, il est possible,
sous certaines conditions, de concevoir une transformation spécifique permettant d’extraire un
2
certain parallélisme. Un autre cas intéressant a lieu lorsqu’un nid de boucles est tel que la boucle
interne est parallèle alors que la plus externe ne l’est pas. Il est alors préférable de le transformer
en un autre nid où c’est la boucle externe qui est parallèle.
Toutefois, dans tous les cas, une étape primordiale avant d’appliquer la transformation
choisie est de vérifier sa légalité (ou validité) pour conserver l’équivalence de la
sémantique du nouveau programme avec l’initial. La transformation doit alors préserver les
relations de dépendance dans le premier nid.
Précisons qu’il y a deux classes de transformations : les transformations unimodulaires
(élémentaires et générales) et les transformations non unimodulaires. Nous présentons ici deux
transformations unimodulaires élémentaires à savoir l’inversion et la permutation et une
transformation non unimodulaire à savoir la distribution des boucles.
Considérons un nid parfait N de profondeur 𝑛. Soit 𝑈 une matrice unimodulaire de taille n i.e.
les coefficients de U appartiennent à ℤ et son déterminant est égal à ±1. Si on applique au nid
une transformation unimodulaire (notée TU) définie par la matrice U, on obtient un nouveau
nid parfait N’. Les espaces d’itération ainsi que les vecteurs d’itération des deux nids sont
homologues.
Publicité
Pour que le nouveau N’ nid soit sémantiquement équivalent à N, les nouveaux VDD (colonnes
de la MDD) doivent être lexicographiquement positifs (le premier élément non nul de
chaque colonne est positif). Dans le cas contraire, la transformation est dite non valide.
Exemple : si un VDD= (
0
1
) devient après transformation (
0
−1
), la transformation est non légale
et elle ne peut être appliquée.
Nous présentons ici deux transformations élémentaires à savoir l’inversion et la permutation
des boucles. Nous montrons ensuite leur éventuel rôle dans l’extraction du parallélisme.
Inversion de boucle
L’inversion d’une boucle (en Anglais Loop reversal) consiste à inverser le compteur de la
boucle en question. Considérons une boucle Bk (1≤ k ≤ n) d’un nid parfait N de profondeur n.
Le compteur ik ayant pour bornes lk et uk et comme pas pk =1 est transformé en un compteur
i’k = -ik dont les bornes sont -lk et -uk le pas restant égal à 1. Ceci est en fait équivalent à inverser
les itérations i.e. ik varie de uk à lk avec un pas -1. Nous avons ce qui suit :
3
Nid original N
DO 𝑖1 = 𝑙1, 𝑢1
…
DO 𝑖𝑘 = 𝑙𝑘, 𝑢𝑘
…
DO 𝑖𝑛 = 𝑙𝑛, 𝑢𝑛
H (𝑖1, … , 𝑖𝑘, … , 𝑖𝑛)
ENDDO
…
ENDDO
…
ENDDO
Nid après inversion de 𝐵𝑘
DO 𝑖1 = 𝑙1, 𝑢1
…
DO 𝑖′𝑘 = −𝑙𝑘, −𝑢𝑘
…
DO 𝑖𝑛 = 𝑙𝑛, 𝑢𝑛
H (𝑖1, … , −𝑖′𝑘, … , 𝑖𝑛)
ENDDO
…
ENDDO
…
ENDDO
⟺
DO 𝑖1 = 𝑙1, 𝑢1
…
DO 𝑖𝑘 = 𝑢𝑘, 𝑙𝑘, −1
…
DO 𝑖𝑛 = 𝑙𝑛, 𝑢𝑛
H (𝑖1, … , 𝑖𝑘, … , 𝑖𝑛)
ENDDO
…
ENDDO
…
ENDDO
La matrice unimodulaire U correspondante est tout simplement la matrice identité où l’élément
1 à la ligne k est replacé par -1.
1
⋮
⋯
⋱
−1
(
0
⋯
⋱
0
⋮
1)
𝑖1
⋮
𝑖𝑘
⋮
𝑖𝑛
Cette transformation n’est valide que si la nouvelle MDD est lexicographiquement positive.
Nous illustrons cela par l’exemple suivant.
Exemple 4.3
Considérons le nid de boucle de l’Exemple 4.1 où le VDD est égal à (
première boucle i.e. U=(−1 0
0 1
) conduit à un VDD égal à (−1 0
Publicité
0 1
) (0
1
0
1
). Une inversion de la
) = (
). L’inversion est
0
1
donc valide puisque le nouveau vecteur est lexicographiquement positif. Par contre si on inverse
la seconde boucle i.e. U=(1 0
0 −1
), le nouveau VDD est égal à (1 0
0 −1
). L’inversion
) = ( 0
−1
) (
0
1
est donc non valide.
Permutation de boucle
Soit un nid parfait N de profondeur n. On appelle permutation de boucles ou encore échange
de boucles (en Anglais loop interchange) la transformation qui consiste à échanger l’ordre des
différentes boucles. La matrice U correspondant à cette transformation est obtenue à partir de
la matrice identité d’ordre n en permutant ses lignes conformément à la permutation. Si M est
la MDD du nid N, la nouvelle MDD égale à M’=UM doit être lexicographiquement positive
pour que la permutation soit valide.
Remarquons que pour un nid parfait de profondeur n, on peut définir n! permutations.
4
Exemple 4.4
Si nous reprenons l’Exemple 4.1 précédent, la permutation des deux boucles se ramène à prendre
𝑈 = (0 1
1 0
) et le nouveau VDD est alors égal à (1
0
). Elle est donc valide. Le nouveau nid est
alors le suivant :
Nid après permutation de boucles
DO 𝑖2 = 1, 5
DO 𝑖1 = 1, 5
𝐴(𝑖1, 𝑖2) = 𝐴(𝑖1, 𝑖2 − 1)
ENDDO
ENDDO
// H
i1
i2
Figure 1-4 : GDEI du nid après permutation
La permutation des boucles modifie l’ordre d’exécution des itérations dans le nid, mais respecte
toujours les dépendances :
Figure 1-5 : Ordre d'exécution des itérations avant et après permutation de boucles
Dans cet exemple où les bornes des boucles sont constantes, l’écriture du nouveau nid est
immédiate. Toutefois, lorsque les bornes des boucles sont des expressions affines des bornes
des boucles englobantes, on doit appliquer une procédure spécifique de détermination des
nouvelles bornes qui conduit, en général, à des bornes inférieures (resp. supérieures) qui sont
des maximums (resp. minimums) d’expressions affines des bornes des boucles englobantes.
Cette procédure consiste à réécrire, par déductions successives, les inéquations vérifiées par les
compteurs des boucles. Nous introduisons ci-dessous un exemple illustratif.
5
Exemple 4.5 :
Soit le nid parfait N suivant où l’on a un VDD égal à (0
1
).
Nid parfait N
DO 𝑖1 = 1, 5
DO 𝑖2 = 𝑖1 + 1, 𝑖1 + 5
𝐴(𝑖1, 𝑖2) = 𝐴(𝑖1, 𝑖2 − 1)
ENDDO
ENDDO
Nid N’ après permutation de boucles
DO 𝑖2 = 2, 10
DO 𝑖1 = 𝑚𝑎𝑥(1, 𝑖2 − 5), 𝑚𝑖𝑛(5, 𝑖2 − 1)
𝐴(𝑖1, 𝑖2) = 𝐴(𝑖1, 𝑖2 − 1)
ENDDO
ENDDO
Les inéquations vérifiées par les compteurs sont réécrites afin que les nouvelles bornes de la
seconde soient constantes. Nous avons alors :
{
1 ≤ 𝑖1 ≤ 5
𝑖1 + 1 ≤ 𝑖2 ≤ 𝑖1 + 5
⇒ {
Publicité
2 ≤ 𝑖2 ≤ 10
1 ≤ 𝑖1 ≤ 5
𝑖1 ≥ 𝑖2 − 5
𝑖1 ≤ 𝑖2 − 1
Les espaces d’itération sont comme suit :
i2
⇒ {
2 ≤ 𝑖2 ≤ 10
𝑚𝑎𝑥 (1, 𝑖2 − 5) ≤ 𝑖1 ≤ 𝑚𝑖𝑛 (5, 𝑖2 − 1)
i1
Nid original
Nid après permutation de boucles
i1
i2
Figure 1-6 : Espaces d'itération et graphes de dépendances de l'exemple 4.5
Remarquons enfin que dans le nouveau nid obtenu après inversion ou bien permutation de
boucle, le corps est identique à celui du nid initial.
Amélioration du parallélisme avec permutation et/ou inversion de boucles :
Dans notre contexte d’amélioration du parallélisme d’un nid de boucles :
6
- L’inversion sert à rendre valide une transformation qui ne l’était pas, particulièrement
une permutation. En effet, si après permutation, la MDD devienne lexicographiquement
négative et si elle renferme une ligne où les éléments sont tous négatifs ou nuls, on peut
alors inverser la boucle correspondante à cette ligne et rendre ainsi la MDD
lexicographiquement positive. La transformation permutation-inversion sera dans ce cas
valide.
- La permutation sert à (i) augmenter le nombre de boucles parallèles, ou (ii) augmenter
le nombre d’itération parallèles en remplaçant une boucle parallèle par une autre ayant
plus d’itération, ou (iii) améliorer le mode de parallélisme en remontant les boucles
parallèles à l’extérieur pour générer moins d’overhead de synchronisations. Par exemple
avec 3 boucles imbiquées, la configuration (p,s,s) est meilleure que (s,p,s) qui est à son
tour meilleure que (s,s,p).
Exemple 4.6
Reprenons l’exemple 4.2 où la MDD est la suivante :
𝑀𝐷𝐷 = (
1
−1
1
0
0
1
). Le nid est alors (s,p,s).
- Une permutation valide est celle de la boucle j et k, dite (i,k,j). La MDD correspondante
est (
0
1
1
1
−1 0
) qui est lexicographiquement positive. Le nid tansformé devient
(s,s,p). Donc même parallélisme mais on a détérioré le mode de parallélisme.
- Les deux permutations (i,j,k) et (i,k,j) sont valides aussi car les MDD correspondantes
commencent par la ligne (1 1) et sont donc lexicographiquement positives. Le nid
devient (s,p,p). On a donc amélioré le parallélisme en augmentant le nombre de boucles
parallèles.
- Les deux permutations commençant par la boucle j i.e. (j,i,k) et (j,k ,i) sont non valides
car la première ligne de la MDD est (-1 0). Mais ces permutations peuvent devenir
valides en inversant la boucle j.
7
On aura alors (j-1,i,k) dont la MDD est (
1
1
1
) et le nid transformé est donc
0
0
1
(s,p,s). La boucle parallèle est i au lieu de j dans la version (i,j,k). Donc on améliore le
parallélisme en augmentant le nombre d’itérations parallèles au cas où la boucle i a plus
d’itérations que la boucle j.
La version (j-1,k,i) a une MDD = (
1
1
1
0
1
0
) et le nid transformé est donc (s,s,p)
donc n préfre le mode de parallélisme du précédent.
8