Worldlex Wiki La vectorisation automatique , en calcul parallèle , est un cas particulier de parallélisation automatique . Elle consiste à convertir un programme informatique 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 d'opérandes simultanément. Par exemple, les ordinateurs classiques modernes, y compris les supercalculateurs spécialisés , disposent généralement d'opérations vectorielles qui effectuent simultanément des opérations telles que les quatre additions suivantes (via du matériel SIMD ou SPMD ) :
Cependant, dans la plupart des langages de programmation, on écrit généralement des boucles qui effectuent séquentiellement des additions de plusieurs nombres. Voici un exemple d'une telle boucle, écrite en C :
Un compilateur vectorisant transforme ces boucles en séquences d'opérations vectorielles. Ces opérations vectorielles effectuent des additions sur des blocs d'éléments des tableaux aet b. cLa vectorisation automatique est un sujet de recherche majeur en informatique.
Arrière-plan
Les premiers ordinateurs possédaient généralement une seule unité logique, qui exécutait une instruction sur une paire d'opérandes à la fois. Les langages et les programmes informatiques étaient donc conçus pour s'exécuter séquentiellement. Les ordinateurs modernes, en revanche, peuvent effectuer plusieurs tâches simultanément. C'est pourquoi de nombreux compilateurs optimisants procèdent à une vectorisation automatique, transformant ainsi des parties de programmes séquentiels en opérations parallèles.
La vectorisation des boucles transforme les boucles procédurales en assignant une unité de traitement à chaque paire d'opérandes. Les programmes passent la majeure partie de leur temps à l'intérieur de ces boucles. Par conséquent, la vectorisation peut les accélérer considérablement, notamment sur de grands ensembles de données. La vectorisation des boucles est implémentée dans les architectures Intel MMX , SSE et AVX , dans l' architecture Power ISA AltiVec , dans les architectures ARM NEON , SVE et SVE2 , et dans les jeux d'instructions Vector Extension de RISC-V .
De nombreuses contraintes empêchent ou entravent la vectorisation. Celle-ci peut parfois ralentir l'exécution, notamment en raison de la synchronisation du pipeline ou du temps de transfert des données. L'analyse des dépendances de boucles permet d'identifier les boucles vectorisables, en s'appuyant sur la dépendance des instructions à l'égard des données qu'elles contiennent.
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 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 dépendances invariantes de boucle et les dépendances lexicales en avant peuvent être facilement vectorisées, et les dépendances lexicales en arrière peuvent être transformées en dépendances lexicales en avant. Cependant, ces transformations doivent être effectuées avec précaution afin de garantir que la dépendance entre toutes les instructions reste conforme à l'original.
Les dépendances cycliques doivent être traitées indépendamment des instructions vectorisées.
Il arrive que le compilateur suppose une dépendance avec trop de prudence. Certains compilateurs proposent une directive nommée ivdep pour indiquer au compilateur d'ignorer les dépendances. Une application incorrecte de cette directive entraînerait des résultats incorrects.
Précision des données
La précision des entiers (taille en bits) doit être préservée lors de l'exécution d'instructions vectorielles. Le choix de l'instruction vectorielle appropriée dépend de la taille et du comportement des entiers internes. De plus, en présence de types entiers mixtes, une attention particulière doit être portée à leur promotion/rétrogradation afin de garantir une précision optimale. Une vigilance accrue est requise lors de l'extension de signe (car plusieurs entiers sont stockés dans un même registre), des décalages temporels et des opérations avec retenue .
Virgule flottante
Par défaut, la sémantique des nombres à virgule flottante de la norme IEEE-754 est conservée, ce qui empêche souvent toute vectorisation. Prenons l'exemple d'une boucle triviale qui calcule la somme d'un tableau :
Comme les opérations en virgule flottante ne sont pas associatives (modifier l'ordre de la somme modifie le résultat), le compilateur ne peut pas vectoriser la boucle. Ce n'est que lorsque le compilateur est explicitement autorisé à réassocier (réordonner les opérations comme si elles étaient associatives) qu'il peut compiler en un code ressemblant à :
Dans ce cas, les résultats différeront légèrement des résultats originaux, mais l' erreur d'arrondi asymptotique sera similaire. Il s'agit d'un exemple de réduction .
Des variations importantes, même en faisant abstraction de la norme IEEE-754, indiquent généralement une erreur de programmation. Une cause fréquente est que la réassociation complète peut rendre inefficaces les algorithmes de sommation compensée . Des commandes plus restreintes, telles que la clause de réduction d' OpenMP, permettent un paramétrage plus précis.
Théorie
Pour vectoriser un programme, l'optimiseur du compilateur doit d'abord identifier les dépendances entre les instructions et les réorganiser si nécessaire. Une fois ces dépendances identifiées, l'optimiseur doit ensuite agencer correctement les instructions d'implémentation en transformant les instructions candidates appropriées en instructions vectorielles, qui opèrent sur plusieurs éléments de données.
Construction du graphe de dépendance
La première étape consiste à construire le graphe de dépendances , en identifiant les instructions qui dépendent les unes des autres. Cela implique d'examiner chaque instruction et d'identifier chaque donnée à laquelle elle accède, d'associer les modificateurs d'accès aux tableaux à des fonctions et de vérifier la dépendance de chaque accès à tous les autres dans toutes les instructions. L'analyse des alias permet de vérifier que les différentes variables accèdent bien à la même zone mémoire (ou la partagent).
Le graphe de dépendances contient toutes les dépendances locales dont la distance n'excède pas la taille du vecteur. Ainsi, si le registre vectoriel est de 128 bits et le type tableau de 32 bits, la taille du vecteur est de 128/32 = 4. Toutes les autres dépendances non cycliques ne devraient pas invalider la vectorisation, puisqu'il n'y aura pas d'accès concurrents dans la même instruction vectorielle.
Supposons que la taille du vecteur soit la même que celle de 4 entiers :
Clustering
À partir du graphe, l'optimiseur peut alors regrouper les composantes fortement connexes (SCC) et séparer les instructions vectorisables du reste.
Prenons l'exemple d'un fragment de programme contenant trois groupes d'instructions à l'intérieur d'une boucle : (SCC1+SCC2), SCC3 et SCC4, dans cet ordre. Seul le deuxième groupe (SCC3) peut être vectorisé. Le programme final contiendra alors trois boucles, une pour chaque groupe, seule la boucle centrale étant vectorisée. L'optimiseur ne peut pas joindre la première à la dernière sans enfreindre l'ordre d'exécution des instructions, ce qui invaliderait les garanties nécessaires.
Détection des expressions idiomatiques
Certaines dépendances non évidentes peuvent être optimisées davantage grâce à des idiomes spécifiques.
Par exemple, les autodépendances de données suivantes peuvent être vectorisées car la valeur des valeurs de droite ( RHS ) est récupérée puis stockée dans la valeur de gauche, de sorte qu'il n'y a aucun moyen que les données changent au sein de l'affectation.
L'autodépendance par 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 : Préparation des variables indépendantes de la boucle. Cela implique généralement leur déplacement vers des registres vectoriels avec des motifs spécifiques utilisés dans les instructions vectorielles. C’est également ici qu’est insérée la vérification des dépendances à l’exécution. Si cette vérification conclut à l’impossibilité de la vectorisation, l’exécution passe à la phase de nettoyage .
- Boucle(s) : Toutes les boucles vectorisées (ou non), séparées par des clusters SCC dans l'ordre d'apparition dans le code d'origine.
- Postlude : Retournez toutes les variables indépendantes de la boucle, les inductions et les réductions.
- Nettoyage : Implémenter 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 d'exécution interdisent le traitement vectoriel.
Exécution vs. compilation
Certaines vectorisations ne peuvent être entièrement vérifiées à la compilation. Par exemple, les fonctions de bibliothèque peuvent contourner l'optimisation si les données qu'elles traitent sont fournies par l'appelant. Même dans ces cas, l'optimisation à l'exécution peut vectoriser les boucles à la volée.
Cette vérification d'exécution est effectuée dans la phase préliminaire et oriente le flux vers des instructions vectorisées si possible, sinon elle revient au traitement standard, en fonction des variables transmises sur les registres ou des variables scalaires.
Le code suivant peut facilement être vectorisé à la compilation, car il ne dépend d'aucun paramètre externe. De plus, le langage garantit qu'aucune variable n'occupera la même zone mémoire qu'une autre variable, puisqu'il s'agit de variables locales résidant uniquement dans la pile d'exécution .
En revanche, le code ci-dessous ne contient 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.
Une vérification rapide à l'exécution des adresses de ` a` et ` b` , ainsi que de l'espace d'itération de la boucle (128), suffit à déterminer si les tableaux se chevauchent ou non, révélant ainsi d'éventuelles dépendances. (À noter qu'à partir de C99, la qualification des paramètres avec le mot-clé `restrict` – ici : int *restrict a, int *restrict b`a` – indique au compilateur que les plages mémoire pointées par `a` et `b` ne se chevauchent pas, ce qui conduit au même résultat que dans l'exemple précédent.)
Il existe des outils permettant d'analyser dynamiquement les applications existantes afin d'évaluer le potentiel latent inhérent de parallélisme SIMD, exploitable grâce à de nouvelles améliorations du compilateur et/ou via des modifications manuelles du code.
Techniques
Par exemple, un programme pourrait multiplier deux vecteurs de données numériques. Une approche scalaire ressemblerait à ceci :
Cela pourrait être vectorisé pour ressembler à ceci :
Ici, c[i:i+3] représente les quatre éléments du tableau allant de c[i] à c[i+3], et le processeur vectoriel peut effectuer quatre opérations avec une seule instruction vectorielle. Comme ces quatre opérations vectorielles s'exécutent en un temps sensiblement équivalent à celui d'une instruction scalaire, l'approche vectorielle peut être jusqu'à quatre fois plus rapide que le code d'origine.
Il existe deux approches de compilation distinctes : l’une basée sur la technique de vectorisation conventionnelle et l’autre sur le déroulement de boucle .
vectorisation automatique au niveau des boucles
Cette technique, utilisée pour les machines vectorielles classiques, vise à identifier et exploiter le parallélisme SIMD au niveau des boucles. Elle se compose de deux étapes principales, décrites ci-après.
- Trouver une boucle interne qui peut être vectorisée
- Transformez la boucle et générez des codes vectoriels
Dans un premier temps, le compilateur recherche les obstacles à la vectorisation. Un obstacle majeur est la présence de dépendances de données plus courtes que la longueur du vecteur. Parmi les autres obstacles figurent les appels de fonction et les nombres d'itérations trop faibles.
Une fois la boucle vectorisable, elle est optimisée en fonction de sa longueur vectorielle : chaque instruction scalaire est remplacée par son équivalent vectoriel. Les transformations nécessaires à cette étape sont illustrées ci-dessous à l’aide de l’exemple précédent.
- Après l'exploitation minière à ciel ouvert
- Après la distribution de la boucle à l'aide de tableaux temporaires
- Après remplacement par des codes vectoriels
vectorisation automatique au niveau des blocs de base
Cette technique relativement récente cible spécifiquement les architectures SIMD modernes à vecteurs courts. Bien que le déroulement des boucles permette d'accroître le parallélisme SIMD dans les blocs de base, cette technique exploite le parallélisme SIMD au sein même des blocs de base plutôt que dans les boucles. Les deux principales étapes sont les suivantes.
- La boucle la plus intérieure est déroulée d'un facteur égal à la longueur du vecteur pour former un grand corps de boucle.
- Les instructions scalaires isomorphes (qui effectuent la même opération) sont regroupées dans une instruction vectorielle si les dépendances ne l'empêchent pas.
Pour illustrer les transformations étape par étape de cette approche, le même exemple est réutilisé.
- Après déroulement de la boucle (par la longueur du vecteur, supposée être de 4 dans ce cas)
- Après avoir emballé
- Après la génération du code
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 des boucles, à l'exception du compilateur IBM XL, qui utilise les deux.
En présence d'un flux de contrôle
La présence d'instructions « if » dans le corps de la boucle exige l'exécution d'instructions dans tous les chemins de contrôle afin de fusionner les valeurs multiples d'une variable. Une approche générale consiste à effectuer une séquence de transformations de code : prédication → vectorisation (à l'aide de l'une des méthodes ci-dessus) → suppression des prédicats vectoriels → suppression des prédicats scalaires. Le code suivant sert d'exemple pour illustrer ces transformations ;
- Après la prédiction
où (P) désigne un prédicat protégeant l'énoncé.
- Après vectorisation
- Après la suppression des prédicats vectoriels
- Après suppression des prédicats scalaires
Réduction de la surcharge de vectorisation en présence de flux de contrôle
L'exécution des instructions sur tous les chemins de contrôle du code vectoriel constitue l'un des principaux facteurs de ralentissement par rapport au code scalaire. Plus le flux de contrôle est complexe et plus le nombre d'instructions ignorées dans le code scalaire est élevé, plus la surcharge de vectorisation est importante. Pour réduire cette surcharge, des branchements vectoriels peuvent être insérés afin d'ignorer les instructions vectorielles, de la même manière que les branchements scalaires ignorent les instructions scalaires. Les prédicats AltiVec sont utilisés ci-dessous pour illustrer comment y parvenir.
- Ligne de base scalaire (code original)
- Après vectorisation en présence de flux de contrôle
- Après l'insertion des branches vectorielles
Deux points sont à noter dans le code final comportant des branches vectorielles : premièrement, l’instruction définissant le prédicat pour vPA est également incluse dans le corps de la branche vectorielle externe grâce à vec_any_gt ; deuxièmement, la rentabilité de la branche vectorielle interne pour vPB dépend de la probabilité conditionnelle que vPB ait des valeurs fausses dans tous ses champs, sachant que vPA a des valeurs fausses dans tous ses champs.
Prenons l'exemple où la branche externe du code scalaire de base est systématiquement exécutée, court-circuitant ainsi la plupart des instructions du corps de la boucle. Le cas intermédiaire présenté ci-dessus, sans branchement vectoriel, exécute toutes les instructions vectorielles. Le code final, avec branchement vectoriel, exécute à la fois la comparaison et le branchement en mode vectoriel, ce qui peut potentiellement améliorer les performances par rapport au code scalaire de base.
Vectorisation manuelle
Dans la plupart des compilateurs C et C++ , il est possible d'utiliser des fonctions intrinsèques pour implémenter manuellement SIMD , au détriment de l'effort du programmeur, de la maintenabilité et de la portabilité. Certains langages (par exemple GNU C, C++ std::experimental::simd, Rust std::simd) incluent des types de données vectorielles qui se compilent en instructions SIMD appropriées, améliorant ainsi la portabilité et réduisant l'effort requis.
Une autre approche consiste à utiliser SPMD : écrire un programme qui semble ne manipuler qu’un seul élément à la fois, puis le compilateur l’élargit pour qu’il corresponde à la largeur d’un vecteur SIMD. C’est l’approche utilisée par les shaders graphiques et plus récemment adoptée par des outils orientés CPU tels qu’Intel IPSC. Contrairement à la vectorisation automatique, qui peut échouer et revenir à du code scalaire (par exemple, lors d’un appel à une fonction externe dans une boucle), production de code vectoriel lorsque cela est possible, tout comme l’utilisation manuelle de fonctions intrinsèques ou de types de données vectoriels.