Vectorisation (informatique)

Toutes les dépendances doivent être respectées lors de l'exécution afin d'éviter des résultats incorrects.

En général, les invariants de boucle et les dépendances à portées lexicale peuvent être facilement vectorisées et les dépendances qui ne sont pas à portées peuvent l'être également, bien que plus difficilement. Mais ces transformations doivent être effectuées en toute sécurité, afin d'assurer la dépendance entre toutes les déclarations en restant fidèle au code original.

Les dépendances cycliques doivent être traitées indépendamment des instructions vectorisées.

La précision d'entier (taille binaire) doit être maintenue pendant l'exécution de l'instruction vectorielle. Cette dernière doit être choisie correctement en fonction de la taille et du comportement des entiers internes. En outre, avec les types d'entiers mixtes, des précautions supplémentaires doivent être prises pour promouvoir/rétrograder correctement sans perte de précision. Un soin particulier doit être pris avec extension de signe (plusieurs entiers étant emballés dans le même registre) et pendant les opérations de transformation, ou des opérations de carry bit qui auraient été pris en compte.

La précision en virgule flottante doit aussi être conservée, à moins que la conformité à la norme IEEE-754 ne soit pas en vigueur, auquel cas les opérations seront plus rapides mais les résultats varier légèrement. De grandes variations, ignorant même IEEE-754 signifient généralement des erreurs de programmation. Le programmeur peut aussi forcer les constantes et les variables de boucle en simple précision (par défaut deux normalement) pour exécuter deux fois plus d'opérations par instruction.

La première étape est de construire le graphe de dépendances, en identifiant les déclarations dépendant des autres déclarations. Il s'agit d'examiner chaque déclaration et l'identification en autre de chaque élément de données que la déclaration accède. L'analyse d'alias peut être utilisée pour certifier que les différentes variables accèdent à la même allocation mémoire.

Le graphe de dépendance contient toutes les dépendances locales avec une distance inférieure à la taille du vecteur. Donc, si le registre vectoriel est de 128 bits, et le type de tableau est de 32 bits, la taille du vecteur est 128/32 = 4. Toutes les autres dépendances non-cycliques ne devraient pas invalider la vectorisation, car il n'y aura pas un accès simultané à la même instruction vectorielle.

Supposons que la taille du vecteur est le même que 4 entiers (ints) :

for (i = 0; i < 128; i++) {
  a[i] = a[i-16]; // 16 > 4, ignoré
  a[i] = a[i-1]; // 1 < 4, reste sur le graphe de dépendances
}

À l'aide du graphe, l'optimiseur peut alors regrouper les composantes fortement connexes (SCC) et les déclarations vectorisables séparées du reste.

Par exemple, considérons un fragment de programme contenant trois clusters d'instructions à l'intérieur d'une boucle : (SCC1 + SCC2), SCC3 et SCC4, dans cet ordre, dans lequel seul le deuxième cluster (SCC3) peut être vectorisé. Le programme définitif contiendra trois boucles, une pour chaque cluster, avec seulement celui du milieu vectorisé. L'optimiseur ne peut pas rejoindre la première à la dernière sans violer l'ordre d'exécution de l'instruction, qui invaliderait les garanties nécessaires.

Certaines dépendances non-évidentes peuvent être optimisées davantage en se basant sur des expressions idiomatiques spécifiques.

Par exemple, les auto-dépendances de données suivantes peuvent être vectorisées du fait que la valeur des valeurs de droite (RHS) sont récupérées, puis stockées sur la valeur de gauche, de sorte qu'il est impossible que les données changent au sein de l'assignation.

a[i] = a[i] + a[i+1];

L'auto-dépendance par scalaires peut être vectorisée par l'élimination de variables.

Cette technique, utilisée pour les machines à vecteurs classiques, essaie de trouver et d'exploiter le parallélisme SIMD au niveau de la boucle. Il se compose de deux grandes étapes, comme suit.

1. Trouver une boucle interne qui peut être vectorisée ;
2. Transformer la boucle et générer des codes vectoriels ;

Dans la première étape, le compilateur recherche les obstacles qui peuvent empêcher vectorisation. Un obstacle majeur pour la vectorisation est une vraie dépendance de données plus courte que la longueur du vecteur. D'autres obstacles incluent les appels de fonction et les courts nombre d'itérations.

Une fois que la boucle est déterminée comme étant vectorisable, la boucle est strip-minée par la longueur du vecteur et chaque instruction scalaire à l'intérieur du corps de la boucle est remplacée par l'instruction vectorielle correspondante. Ci-dessous, les transformations des composants de cette étape sont présentés en utilisant l'exemple ci-dessus.

• Après strip-mining

for (i = 0; i < 1024; i+=4)
    for (ii = 0; ii < 4; ii++)
       C[i+ii] = A[i+ii]*B[i+ii];

• Après la distribution de boucles à l'aide de tableaux temporaires

  for (i = 0; i < 1024; i+=4)
  {
    for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii];
    for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii];
    for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii];
    for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii];
  }

• Après le remplacement à l'aide de codes vectoriels

for (i = 0; i < 1024; i+=4)
  {
    vA = vec_ld( &A[i] );
    vB = vec_ld( &B[i] );
    vC = vec_mul( vA, vB );
    vec_st( vC, &C[i] );
  }

Cette technique relativement nouvelle cible spécifiquement les architectures SIMD modernes avec de courtes longueurs de vecteur[2]. Bien que les boucles peuvent être déroulées pour augmenter la quantité de parallélisme SIMD en blocs de base, cette technique exploite le parallélisme SIMD à l'intérieur des blocs de base plutôt que des boucles. Les deux principales étapes sont les suivantes :

1. La boucle la plus interne est déroulée par un facteur de la longueur du vecteur pour former un grand corps de boucle.
2. Les instructions scalaires isomorphes (qui effectuent la même opération) sont empaquetées dans une instruction vectorielle si les dépendances ne l'empêchent pas de le faire.

Pour afficher les transformations étape-par-étape de cette approche, le même exemple que ci-dessus est utilisé à nouveau.

• Après déroulage des boucles (par la longueur du vecteur, supposée être 4 dans ce cas)

for (i = 0; i < 1024; i+=4)
  {
     sA0 = ld( &A[i+0] );
     sB0 = ld( &B[i+0] );
     sC0 = sA0 * sB0;
     st( sC0, &C[i+0] );
           ...
     sA3 = ld( &A[i+3] );
     sB3 = ld( &B[i+3] );
     sC3 = sA3 * sB3;
     st( sC3, &C[i+3] );
  }

• Après l'empaquetage

for (i = 0; i < 1024; i+=4)
  {
     (sA0,sA1,sA2,sA3) = ld( &A[i+0:i+3] );
     (sB0,sB1,sB2,sB3) = ld( &B[i+0:i+3] );
     (sC0,sC1,sC2,sC3) = (sA0,sA1,sA2,sA3) * (sB0,sB1,sB2,sB3);
     st( (sC0,sC1,sC2,sC3), &C[i+0:i+3] );
  }

• Après la génération du code

for (i = 0; i < 1024; i+=4)
  {
    vA = vec_ld( &A[i] );
    vB = vec_ld( &B[i] );
    vC = vec_mul( vA, vB );
    vec_st( vC, &C[i] );
  }

Ici, sA1, SB1, ... représentent des variables scalaires et VA, VB, et Vc représentent des variables vectorielles.

Les compilateurs commerciaux de vectorisation automatique emploient pour la plupart l'approche au niveau de la boucle conventionnelle excepté le compilateur d'IBM XL[3], qui emploient chacun des deux.

La présence de if dans le corps de la boucle nécessite l'exécution d'instructions dans tous les chemins de commande pour fusionner les multiples valeurs d'une variable. Une approche générale est de passer par une séquence de transformations de code : Prédication → vectorisation (en utilisant l'une des méthodes ci-dessus) → retirer les prédicats des vecteurs → supprimer les prédicats scalaires.

Le code suivant est utilisé comme un exemple pour montrer ces transformations[4] :

for (i = 0; i < 1024; i++)
     if (A[i] > 0)
       C[i] = B[i];
     else
       D[i] = D[i-1];

• Après la prédication

for (i = 0; i < 1024; i++)
  {
     P = A[i] > 0;
     NP = !P;
     C[i] = B[i];     (P)
     D[i] = D[i-1];   (NP)
  }

où (P) désigne un prédicat gardant la déclaration.

• Après la vectorisation

for (i = 0; i < 1024; i+=4)
  {
     vP  = A[i:i+3] > (0,0,0,0);
     vNP = vec_not(vP);
     C[i:i+3] = B[i:i+3];     (vP)
     (NP1,NP2,NP3,NP4) = vNP;
     D[i+3] = D[i+2];         (NP4)
     D[i+2] = D[i+1];         (NP3)
     D[i+1] = D[i];           (NP2)
     D[i]     = D[i-1];         (NP1)
  }

• Après la suppression des prédicats de vecteurs

for (i = 0; i < 1024; i+=4)
  {
     vP  = A[i:i+3] > (0,0,0,0);
     vNP = vec_not(vP);
     C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP);
     (NP1,NP2,NP3,NP4) = vNP;
     D[i+3] = D[i+2];         (NP4)
     D[i+2] = D[i+1];         (NP3)
     D[i+1] = D[i];           (NP2)
     D[i]     = D[i-1];         (NP1)
  }

• Après la suppression des prédicats scalaires

for (i = 0; i < 1024; i+=4)
  {
     vP  = A[i:i+3] > (0,0,0,0);
     vNP = vec_not(vP);
     C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP);
     (NP1,NP2,NP3,NP4) = vNP;
     if (NP4) D[i+3] = D[i+2];
     if (NP3) D[i+2] = D[i+1];
     if (NP2) D[i+1] = D[i];
     if (NP1) D[i]   = D[i-1];
  }

Devoir exécuter les instructions dans tous les chemins de contrôle en code vectoriel a été un des principaux facteurs ralentissant le code vectoriel en ce qui concerne la base scalaire. Plus le flux de commande devient complexe et plus d'instructions sont déviés dans le code scalaire plus la vectorisation devient difficile. Pour réduire son surcoût, des branchements vectoriels peuvent être insérés pour contourner les vecteur d'instructions similaires à la façon dont les branchements scalaires contournent les instructions scalaires[5]. Ci-dessous, les prédicats AltiVec sont utilisés pour montrer comment cela peut être réalisé.

• Base scalaire (code original)

for (i = 0; i < 1024; i++)
  {
     if (A[i] > 0)
     {
       C[i] = B[i];
       if (B[i] < 0)
         D[i] = E[i];
     }
  }

• Après la vectorisation en présence de flux de contrôle

for (i = 0; i < 1024; i+=4)
  {
     vPA = A[i:i+3] > (0,0,0,0);
     C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA);
     vT = B[i:i+3] < (0,0,0,0);
     vPB = vec_sel((0,0,0,0), vT, vPA);
     D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB);
  }

• Après l'insertion dans des branchements vectoriels

for (i = 0; i < 1024; i+=4)
     if (vec_any_gt(A[i:i+3],(0,0,0,0)))
     {
        vPA = A[i:i+3] > (0,0,0,0);
        C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA);
        vT = B[i:i+3] < (0,0,0,0);
        vPB = vec_sel((0,0,0,0), vT, vPA);
        if (vec_any_ne(vPB,(0,0,0,0)))
           D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB);
     }

Il y a deux choses à noter dans le code final avec des branchements vectoriels. D'une part, le prédicat définissant l'instruction pour vPA est également inclus dans le corps du branchement vectoriel externe en utilisant vec_any_gt. D'autre part, la rentabilité du branchement vectoriel intérieure pour vPB dépend de la probabilité conditionnelle de vPB ayant de fausses valeurs dans tous les champs étant donné que vPA a de fausses valeurs dans tous les champs de bits.

Prenons un exemple où le branchement externe dans la base scalaire est toujours prise en contournant la plupart des instructions dans le corps de la boucle. Le cas intermédiaire ci-dessus, sans branchements vectoriels, exécute toutes les instructions vectorielles. Le code final, avec des branchements vectoriels, exécute à la fois la comparaison et le branchement en mode vectoriel, gagnant potentiellement en performance par rapport à la base scalaire.