Parallélisation des programmes polyédriques – Partie 2

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.

Détection de parallélisme

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.

Exemple 4.1

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).

Exemple 4.2

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).

Extraction du parallélisme : Transformations de programmes

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 :

• Transformations unimodulaires (élémentaires et générales)
• Transformations non unimodulaires

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.

Transformation unimodulaire

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.

Inversion de boucle

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.

Exemple 4.3

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.

Permutation de boucle

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.

Exemple 4.4

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.

Permutation avec bornes affines

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.

Exemple 4.5

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 :

• 1 ≤ i1 ≤ 5
• i1 + 1 ≤ i2 ≤ i1 + 5

se réécrivent en :

• 2 ≤ i2 ≤ 10
• max(1, i2 - 5) ≤ i1 ≤ min(5, i2 - 1)

Les espaces d'itération et graphes de dépendances sont ainsi adaptés au nouveau nid.

Amélioration du parallélisme avec permutation et inversion

• Inversion : Permet de rendre valide une transformation non valide, notamment une permutation. Si la MDD devient lexicographiquement négative et contient une ligne avec tous éléments négatifs ou nuls, on peut inverser la boucle correspondante pour restaurer la validité.
• Permutation : Sert à augmenter le nombre de boucles parallèles, augmenter le nombre d'itérations parallèles en remplaçant une boucle parallèle par une autre avec plus d'itérations, ou améliorer le mode de parallélisme en remontant les boucles parallèles vers l'extérieur afin de réduire l'overhead de synchronisation.

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).

Exemple 4.6

MDD = (
 1
-1
 1

 0
 0
 1
)

Nid initial : (s,p,s)

• Permutation valide des boucles j et k (ordre (i,k,j)) donne une MDD lexicographiquement positive, transformant le nid en (s,s,p). Le parallélisme est conservé mais le mode est moins bon.
• Permutations (i,j,k) et (i,k,j) sont aussi valides, donnant (s,p,p), améliorant le parallélisme en augmentant le nombre de boucles parallèles.
• Permutations commençant par j (j,i,k) et (j,k,i) sont non valides car la première ligne de la MDD est (-1,0). Cependant, en inversant la boucle j, ces permutations deviennent valides :

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.

Glossaire des termes clés

• Nid parfait de boucles : Ensemble de boucles imbriquées sans instructions entre elles, formant une structure régulière.
• Niveau de dépendance : Position du premier coefficient strictement positif dans le vecteur des distances ou signes de dépendance, indiquant la boucle séquentielle.
• Vecteur de dépendance (VDD) : Vecteur représentant les distances de dépendance entre itérations.
• Matrice des distances de dépendance (MDD) : Matrice dont les colonnes sont les vecteurs de dépendance, utilisée pour analyser les dépendances dans un nid de boucles.
• Lexicographiquement positif : Propriété d'un vecteur ou d'une matrice où le premier élément non nul est strictement positif.
• Transformation unimodulaire : Transformation linéaire définie par une matrice entière de déterminant ±1, préservant la structure discrète des itérations.
• Inversion de boucle : Transformation qui inverse l'ordre d'itération d'une boucle en changeant le sens du compteur.
• Permutation de boucles : Échange de l'ordre d'imbrication des boucles dans un nid.
• Distribution des boucles : Transformation non unimodulaire qui répartit le corps d'une boucle en plusieurs boucles distinctes.
• Parallélisme implicite : Parallélisme non directement visible dans le code initial mais pouvant être extrait par transformation.

Points clés à retenir

• Le parallélisme dans un nid de boucles est déterminé par l'analyse des niveaux de dépendance via la MDD.
• Une boucle est séquentielle si une dépendance de son niveau existe, sinon elle est parallèle.
• Les transformations de boucles doivent préserver la lexicographiquement positivité des vecteurs de dépendance pour être valides.
• L'inversion de boucle permet d'inverser l'ordre d'itération et peut rendre valide une transformation non valide.
• La permutation de boucles modifie l'ordre d'exécution et peut améliorer le parallélisme en augmentant le nombre de boucles parallèles ou en optimisant leur position.
• Les transformations combinées inversion-permutation sont souvent utilisées pour extraire un parallélisme maximal.
• Le recalcul des bornes des boucles est nécessaire lors de permutations lorsque les bornes sont affines.
• Le choix du mode de parallélisme (ex. (p,s,s) vs (s,p,s)) impacte la performance en termes de synchronisation et exploitation des ressources.