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 :
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; int b; // 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 manuelshttp://dl.acm.org/citation.cfm?id=2254108.
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] );