Vectorisation (informatique)

La vectorisation (dans le cadre du calcul parallèle), est un cas particulier de la parallélisation, dans lequel des logiciels qui effectuent par défaut une seule opération à la fois sur un seul thread sont modifiés pour effectuer plusieurs opérations simultanément.

La vectorisation est le processus de conversion d'un programme informatique à partir d'une implémentation scalaire, qui traite une seule paire d'opérandes à la fois, à une implémentation vectorielle qui traite une opération sur plusieurs paires d'opérandes à la fois. Le terme vient de la convention de mettre les opérandes dans des vecteurs ou des matrices.

Le calcul vectoriel est une caractéristique majeure concernant à la fois les ordinateurs classiques et les superordinateurs modernes, pouvant réaliser des opérations vectorielles qui effectuent simultanément des opérations telles que par exemple les quatre additions suivantes :

{\begin{aligned}c_{1}&=a_{1}+b_{1}\\c_{2}&=a_{2}+b_{2}\\c_{3}&=a_{3}+b_{3}\\c_{4}&=a_{4}+b_{4}\end{aligned}}

Cependant, dans la plupart des langages de programmation on écrit généralement des boucles qui effectuent séquentiellement des additions de grands nombres. Voici un exemple d'une telle boucle, en C :

for (i=0; i<n; i++)
    c[i] = a[i] + b[i];

La vectorisation automatique est un sujet de recherche majeur en informatique ; cela consiste à rechercher des méthodes qui permettent à un compilateur de convertir (sans assistance humaine) des programmes scalaires en programmes vectorisés.

Contexte

Les premiers ordinateurs avaient généralement une unité logique qui exécutait séquentiellement une instruction sur une paire d'opérandes à la fois. Les programmes informatiques et les langages de programmation ont donc été conçus pour exécuter des instructions de façon séquentielle. Les ordinateurs modernes peuvent faire beaucoup de choses à la fois. Un grand nombre de compilateurs optimisants réalisent une vectorisation automatique du code : c'est une fonctionnalité du compilateur qui permet à certaines parties des programmes séquentiels d'être transformés en programmes parallèles équivalents afin de produire du code qui sera bien utilisé par un processeur vectoriel.

Garanties

La vectorisation automatique, tout comme l'optimisation de boucle ou une quelconque autre optimisation de compilation, doit préserver exactement le comportement du programme.

Dépendances de données

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.

Précision des donné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.

Théorie

Pour vectoriser un programme, l'optimiseur du compilateur doit d'abord comprendre les dépendances entre les déclarations et les réaligner si nécessaire. Une fois les dépendances mappées, l'optimiseur doit organiser correctement les implémentations d'instructions des candidats appropriés aux vecteurs instructions qui fonctionnent sur plusieurs éléments de données.

Construire le graphe de dépendances

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
}

Clustering

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

Détection des idiomes

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.

Cadre général

Le cadre général de la vectorisation de boucles est divisé en quatre étapes :

Prélude : lorsque les variables de boucle indépendantes sont prêtes à être utilisées à l'intérieur de la boucle. Ceci implique normalement de les déplacer dans des registres vectoriels avec des motifs spécifiques qui seront utilisés dans des instructions vectorielles. C'est aussi l'endroit pour insérer le contrôle de dépendance d'exécution. Si le contrôle décide que la vectorisation n'est pas possible, passage à l'étape de nettoyage.
Boucle(s) : toutes les boucles vectorisées (ou non), séparées par clusters CSSC par ordre d'apparition dans le code original.
Postlude : retourne toutes les variables de boucles indépendantes, inductions et réductions.
Nettoyage : implémente tout simplement les boucles (non-vectorisées) pour les itérations à l'extrémité d'une boucle qui ne sont pas un multiple de la taille de vecteur ou pour quand les contrôles d'exécution interdisent le traitement de vecteur.

Runtime vs compilation

Certaines vectorisations ne peuvent pas être entièrement vérifiées au moment de la compilation. L'optimisation au moment de la compilation exige un index explicite d’array. Les fonctions de bibliothèque peuvent également défaire l'optimisation si les données qu'elles traitent sont fournies par des paramètres externes. Même dans ces cas, l'optimisation d'exécution peut encore vectoriser des boucles en fonctionnement.

Ce contrôle d'exécution est fait dans l'étape de prélude et dirige le flux vers des instructions vectorisées si possible, autrement on revient au traitement standard, selon les variables qui sont passées sur les registres ou les variables scalaires.

Le code suivant peut facilement être vectorisé au moment de la compilation, car il ne possède pas de fonctions faisant appel ou dépendant de paramètres externes. En outre, le langage garantit qu'il n'occupera la même allocation mémoire que toute autre variable, étant des variables locales et ne vivant que dans la pile d'exécution.

int a[128];
int b[128];
// initialise b

for (i = 0; i<128; i++)
  a[i] = b[i] + 5;

D'autre part, le code ci-dessous n'a pas d'information sur les positions de mémoire car les références sont des pointeurs et la mémoire dans laquelle elles sont allouées est dynamique.

int *a = malloc(128*sizeof(int));
int *b = malloc(128*sizeof(int));
// initialise b

for (i = 0; i<128; i++, a++, b++)
  *a = *b + 5;
// ... 
// ...
// ...
free(b);
free(a);

Une vérification rapide d'exécution sur l'adresse de a et b, ainsi que l'espace boucle d'itération (128) est suffisant pour dire si les arrays se chevauchent ou non, révélant ainsi toutes les dépendances.

Il existe des outils pour analyser dynamiquement les applications existantes afin d'évaluer le potentiel latent inhérent à parallélisme SIMD, exploitable grâce à l'évolution du compilateur et/ou par des changements de code manuels^[1].

Techniques

Un exemple serait un programme multipliant deux vecteurs de données numériques. Une approche scalaire serait quelque chose comme :

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

Il pourrait être vectorisé pour ressembler à ceci :

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

Ici, C [i: i + 3] représente les quatre indices de tableau de C[i] à C[i + 3] et le processeur vectoriel peut effectuer quatre opérations pour une seule instruction vectorielle. Du fait que les quatre opérations vectorielles sont complétées en même temps à peu près qu'une instruction scalaire, l'approche par vecteur peut exécuter jusqu'à quatre fois plus rapide que le code original.

Il existe deux approches distinctes de compilation : l'une basée sur la technique de vectorisation classique et l'autre sur la base de déroulage de boucle.

Vectorisation automatique au niveau boucle

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.

Trouver une boucle interne qui peut être vectorisée ;
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] );
  }

Vectorisation automatique au niveau bloc de base

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 :

La boucle la plus interne est déroulée par un facteur de la longueur du vecteur pour former un grand corps de boucle.
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.

En présence de flux de contrôle

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];
  }

Réduction du surcoût de la vectorisation en présence de flux de contrôle

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.

Voir aussi

Processeur vectoriel#Chaining

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Vectorization_(parallel_computing) » (voir la liste des auteurs).

↑ http://dl.acm.org/citation.cfm?id=2254108
↑ S. Larsen et S. Amarasinghe, « Proceedings of the ACM SIGPLAN conference on Programming language design and implementation », ACM SIGPLAN Notices, vol. 35, n^o 5,‎ 2000, p. 145–156 (DOI 10.1145/358438.349320)
↑ « Code Optimization with IBM XL Compilers », juin 2004 (consulté en mai 2010)
↑ J. Shin, M. W. Hall et J. Chame, « Proceedings of the international symposium on Code generation and optimization », Superword-Level Parallelism in the Presence of Control Flow,‎ 2005, p. 165–175 (ISBN 0-7695-2298-X, DOI 10.1109/CGO.2005.33)
↑ J. Shin, « Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques », Introducing Control Flow into Vectorized Code,‎ 2007, p. 280–291 (DOI 10.1109/PACT.2007.41)

[1] ttp://dl.acm.org/citation.cfm?id=2254108

[2] S. Larsen et S. Amarasinghe, « Proceedings of the ACM SIGPLAN conference on Programming language design and implementation », ACM SIGPLAN Notices, vol. 35, n^o 5,‎ 2000, p. 145–156 (DOI 10.1145/358438.349320)

[ibm-3] « Code Optimization with IBM XL Compilers », juin 2004 (consulté en mai 2010)

[4] J. Shin, M. W. Hall et J. Chame, « Proceedings of the international symposium on Code generation and optimization », Superword-Level Parallelism in the Presence of Control Flow,‎ 2005, p. 165–175 (ISBN 0-7695-2298-X, DOI 10.1109/CGO.2005.33)

[5] J. Shin, « Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques », Introducing Control Flow into Vectorized Code,‎ 2007, p. 280–291 (DOI 10.1109/PACT.2007.41)

[1]

[2]

[3]

[4]

[5]