Vectorisation automatique - Automatic vectorization

La vectorisation automatique , en calcul parallèle , est un cas particulier de parallélisation automatique , où un programme informatique est converti d'une implémentation scalaire , qui traite une seule paire d' opérandes à la fois, en une implémentation vectorielle , qui traite une opération sur plusieurs paires de opérandes à la fois. Par exemple, les ordinateurs conventionnels modernes, y compris les superordinateurs spécialisés , ont généralement des opérations vectorielles qui effectuent simultanément des opérations telles que les quatre ajouts suivants (via le matériel SIMD ou SPMD ) :

{\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 nombreux nombres. Voici un exemple d'une telle boucle, écrite en C :

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

Un compilateur de vectorisation transforme ces boucles en séquences d'opérations vectorielles. Ces opérations vectorielles effectuent des ajouts sur des blocs d'éléments des tableaux a, bet c. La vectorisation automatique est un sujet de recherche majeur en informatique.

Fond

Les premiers ordinateurs avaient généralement une unité logique, qui exécutait une instruction sur une paire d'opérandes à la fois. Les langages et programmes informatiques ont donc été conçus pour s'exécuter en séquence. Les ordinateurs modernes, cependant, peuvent faire beaucoup de choses à la fois. Ainsi, de nombreux compilateurs d'optimisation effectuent une vectorisation automatique, où des parties de programmes séquentiels sont transformées en opérations parallèles.

La vectorisation de boucle transforme les boucles procédurales en affectant une unité de traitement à chaque couple d'opérandes. Les programmes passent la plupart de leur temps dans de telles boucles. Par conséquent, la vectorisation peut considérablement les accélérer, en particulier sur de grands ensembles de données. Boucle vectorisation est mis en œuvre dans Intel 's MMX , SSE et AVX , en puissance ISA est AltiVec , et ARM de NEON , SVE jeux d'instructions et SVE2.

De nombreuses contraintes empêchent ou gênent la vectorisation. Parfois, la vectorisation peut ralentir l'exécution, par exemple en raison de la synchronisation du pipeline ou de la synchronisation des mouvements de données. L'analyse de dépendance de boucle identifie les boucles qui peuvent être vectorisées, en s'appuyant sur la dépendance des données des instructions à l'intérieur des boucles.

Garanties

La vectorisation automatique, comme toute optimisation de boucle ou autre optimisation au moment de la compilation, doit préserver exactement le comportement du programme.

Dépendances des données

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

En général, les dépendances invariantes de boucle et les dépendances lexicalement avancées peuvent être facilement vectorisées, et les dépendances lexicalement arrière peuvent être transformées en dépendances lexicalement avancées. Cependant, ces transformations doivent être effectuées en toute sécurité, afin de garantir que la dépendance entre toutes les déclarations reste fidèle à l'original.

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

Précision des données

La précision de l' entier (taille du bit) doit être conservée pendant l'exécution de l'instruction vectorielle. L'instruction vectorielle correcte doit être choisie en fonction de la taille et du comportement des entiers internes. De plus, avec des types entiers mixtes, des précautions supplémentaires doivent être prises pour les promouvoir/rétrograder correctement sans perdre en précision. Des précautions particulières doivent être prises avec l' extension de signe (car plusieurs entiers sont emballés dans le même registre) et pendant les opérations de décalage, ou les opérations avec des bits de retenue qui seraient autrement pris en compte.

La précision en virgule flottante doit également être conservée, sauf si la conformité IEEE-754 est désactivée, auquel cas les opérations seront plus rapides mais les résultats peuvent varier légèrement. De grandes variations, même en ignorant IEEE-754, signifient généralement une erreur du programmeur.

Théorie

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

Construire le graphe de dépendance

La première étape consiste à construire le graphe de dépendance , en identifiant quelles instructions dépendent de quelles autres instructions. Cela implique d'examiner chaque instruction et d'identifier chaque élément de données auquel l'instruction accède, de mapper les modificateurs d'accès de tableau aux fonctions et de vérifier la dépendance de chaque accès à tous les autres dans toutes les instructions. L'analyse d'alias peut être utilisée pour certifier que les différentes variables accèdent (ou se croisent) à la même région en mémoire.

Le graphique de dépendance contient toutes les dépendances locales dont la distance n'est pas supérieure à la taille du vecteur. Ainsi, si le registre vectoriel est de 128 bits et que le type de tableau est de 32 bits, la taille du vecteur est de 128/32 = 4. Toutes les autres dépendances non cycliques ne doivent pas invalider la vectorisation, car il n'y aura pas d'accès concurrent dans le même instruction vectorielle.

Supposons que la taille du vecteur soit la même que 4 ints :

for (i = 0; i < 128; i++) {
    a[i] = a[i-16]; // 16 > 4, safe to ignore
    a[i] = a[i-1]; // 1 < 4, stays on dependency graph
}

Regroupement

En utilisant le graphique, l'optimiseur peut ensuite regrouper les composants fortement connectés (SCC) et séparer les instructions vectorisables du reste.

Par exemple, considérons un fragment de programme contenant trois groupes d'instructions à l'intérieur d'une boucle : (SCC1+SCC2), SCC3 et SCC4, dans cet ordre, dans lequel seul le deuxième groupe (SCC3) peut être vectorisé. Le programme final contiendra alors trois boucles, une pour chaque groupe, avec seulement celle du milieu vectorisée. L'optimiseur ne peut pas joindre le premier avec le dernier sans violer l'ordre d'exécution des instructions, ce qui invaliderait les garanties nécessaires.

Détecter les idiomes

Certaines dépendances non évidentes peuvent être optimisées davantage en fonction d'idiomes spécifiques.

Par exemple, les auto-dépendances suivantes peuvent être vectorisées car la valeur des valeurs de droite ( RHS ) est récupérée puis stockée sur la valeur de gauche, il n'y a donc aucun moyen que les données changent dans l'affectation.

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

L'autodépendance par les scalaires peut être vectorisée par élimination de variables .

Cadre général

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

Prélude : où les variables indépendantes de la boucle sont préparées pour être utilisées à l'intérieur de la boucle. Cela implique normalement de les déplacer vers des registres vectoriels avec des motifs spécifiques qui seront utilisés dans les instructions vectorielles. C'est aussi l'endroit où insérer le contrôle de dépendance à l'exécution. Si la vérification décide que la vectorisation n'est pas possible, passez à Cleanup .
Boucle(s) : Ensemble des boucles vectorisées (ou non), séparées par des clusters SCC par ordre d'apparition dans le code d'origine.
Postlude : Renvoie toutes les variables indépendantes de la boucle, inductions et réductions.
Nettoyage : implémentez des boucles simples (non vectorisées) pour les itérations à la fin d'une boucle qui ne sont pas un multiple de la taille du vecteur ou lorsque les vérifications à l'exécution interdisent le traitement vectoriel.

Temps d'exécution vs temps de compilation

Certaines vectorisations ne peuvent pas être entièrement vérifiées au moment de la compilation. Par exemple, les fonctions de bibliothèque peuvent empêcher l'optimisation si les données qu'elles traitent sont fournies par l'appelant. Même dans ces cas, l'optimisation de l'exécution peut toujours vectoriser les boucles à la volée.

Ce contrôle d'exécution est effectué dans l' étape de prélude et oriente le flux vers des instructions vectorisées si possible, sinon 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 dépend pas de paramètres externes. De plus, le langage garantit qu'aucune n'occupera la même région en mémoire que n'importe quelle autre variable, car ce sont des variables locales et ne vivent que dans la pile d' exécution .

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

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

En revanche, le code ci-dessous n'a aucune information sur les positions mémoire, car les références sont des pointeurs et la mémoire vers laquelle elles pointent peut se chevaucher.

void compute(int *a, int *b)
{
    int i;
    for (i = 0; i < 128; i++, a++, b++)
        *a = *b + 5;
}

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

Il existe des outils pour analyser dynamiquement les applications existantes afin d'évaluer le potentiel latent inhérent au parallélisme SIMD, exploitable grâce à de nouvelles avancées du compilateur et/ou via des modifications de code manuelles.

Technique

Un exemple serait un programme pour multiplier 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];

Cela pourrait être vectorisé pour ressembler à quelque chose comme :

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 éléments du tableau de c[i] à c[i+3] et le processeur vectoriel peut effectuer quatre opérations pour une seule instruction vectorielle. Étant donné que les quatre opérations vectorielles se terminent à peu près en même temps qu'une instruction scalaire, l'approche vectorielle peut s'exécuter jusqu'à quatre fois plus rapidement que le code d'origine.

Il existe deux approches distinctes du compilateur : l'une basée sur la technique de vectorisation classique et l'autre basée sur le déroulement de boucle .

Vectorisation automatique au niveau de la boucle

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

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

Dans un premier temps, le compilateur recherche les obstacles pouvant empêcher la vectorisation. Un obstacle majeur à la vectorisation est la vraie dépendance aux données plus courte que la longueur du vecteur. D'autres obstacles incluent les appels de fonction et le nombre d'itérations courtes.

Une fois que la boucle est déterminée comme étant vectorisable, la boucle est supprimée par la longueur du vecteur et chaque instruction scalaire dans le corps de la boucle est remplacée par l'instruction vectorielle correspondante. Ci-dessous, les transformations de composants pour cette étape sont illustrées à l'aide de l'exemple ci-dessus.

Après le décapage

for (i = 0; i < 1024; i += 4)
    for (j = 0; j < 4; j++)
        c[i+j] = a[i+j] * b[i+j];

Distribution après boucle à l'aide de tableaux temporaires

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

Après remplacement par des 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 du bloc de base

Cette technique relativement nouvelle cible spécifiquement les architectures SIMD modernes avec des longueurs vectorielles courtes. Bien que les boucles puissent être déroulées pour augmenter la quantité de parallélisme SIMD dans les blocs de base, cette technique exploite le parallélisme SIMD dans les blocs de base plutôt que les boucles. Les deux étapes principales sont les suivantes.

La boucle la plus interne est déroulée d'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 compressées dans une instruction vectorielle si les dépendances ne l'empêchent pas de le faire.

Pour montrer les transformations étape par étape pour cette approche, le même exemple est à nouveau utilisé.

Après le déroulement de la boucle (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'emballage

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 génération de 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.

La plupart des compilateurs commerciaux à vectorisation automatique utilisent l'approche conventionnelle au niveau de la boucle, à l'exception du compilateur IBM XL, qui utilise les deux.

En présence de flux de contrôle

La présence d'instructions if dans le corps de la boucle nécessite l'exécution d'instructions dans tous les chemins de contrôle pour fusionner les multiples valeurs d'une variable. Une approche générale consiste à passer par une séquence de transformations de code : prédication → vectorisation (en utilisant l'une des méthodes ci-dessus) → suppression des prédicats vectoriels → suppression des prédicats scalaires. Si le code suivant est utilisé comme exemple pour montrer ces transformations ;

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

Après 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 protégeant l'instruction.

Après 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 avoir supprimé les prédicats vectoriels

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 avoir supprimé les 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 des frais généraux de 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é l'un des principaux facteurs qui ralentissent le code vectoriel par rapport à la ligne de base scalaire. Plus le flux de contrôle devient complexe et plus les instructions sont contournées dans le code scalaire, plus le surcoût de vectorisation devient important. Pour réduire cette surcharge de vectorisation, des branches vectorielles peuvent être insérées pour contourner les instructions vectorielles de la même manière que les branches scalaires contournent les instructions scalaires. Ci-dessous, les prédicats AltiVec sont utilisés pour montrer comment cela peut être réalisé.

Ligne de base scalaire (code d'origine)

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

Après 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 avoir inséré des branches vectorielles

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 branches vectorielles ; Premièrement, l'instruction de définition de prédicat pour vPA est également incluse dans le corps de la branche vectorielle externe en utilisant vec_any_gt. Deuxièmement, la rentabilité de la branche vectorielle interne pour vPB dépend de la probabilité conditionnelle que vPB ait de fausses valeurs dans tous les champs étant donné que vPA a de fausses valeurs dans tous les champs.

Prenons un exemple où la branche externe de la ligne de base scalaire est toujours prise, en contournant la plupart des instructions du corps de la boucle. Le cas intermédiaire ci-dessus, sans branches vectorielles, exécute toutes les instructions vectorielles. Le code final, avec des branches vectorielles, exécute à la fois la comparaison et la branche en mode vectoriel, améliorant potentiellement les performances par rapport à la ligne de base scalaire.

Vectorisation manuelle

Dans la plupart des compilateurs C et C++ , il est possible d'utiliser des fonctions intrinsèques pour vectoriser manuellement, au détriment de l'effort et de la maintenabilité du programmeur.

Languages

In other projects