Qu'est-ce que la «vectorisation»?

201

Plusieurs fois maintenant, j'ai rencontré ce terme dans matlab, fortran ... un autre ... mais je n'ai jamais trouvé d'explication qu'est-ce que cela signifie, et qu'est-ce que cela signifie? Je demande donc ici, qu'est-ce que la vectorisation, et que signifie par exemple «une boucle est vectorisée»?

Thomas Geritzma
la source
1
@geoffspear Le lien semble avoir été déplacé vers en.wikipedia.org/wiki/Array_programming
J'aime

Réponses:

238

De nombreuses CPU ont des jeux d'instructions "vectoriels" ou "SIMD" qui appliquent la même opération simultanément à deux, quatre ou plus de données. Les puces x86 modernes ont les instructions SSE, de nombreuses puces PPC ont les instructions "Altivec", et même certaines puces ARM ont un jeu d'instructions vectorielles, appelé NEON.

La "vectorisation" (simplifiée) est le processus de réécriture d'une boucle de sorte qu'au lieu de traiter un seul élément d'un tableau N fois, il traite (disons) 4 éléments du tableau simultanément N / 4 fois.

(J'ai choisi 4 parce que c'est ce que le matériel moderne est le plus susceptible de prendre directement en charge; le terme «vectorisation» est également utilisé pour décrire une transformation logicielle de plus haut niveau où vous pourriez simplement résumer complètement la boucle et décrire simplement le fonctionnement sur des tableaux au lieu des éléments qui les composent)


La différence entre la vectorisation et le déroulement de boucle: considérez la boucle très simple suivante qui ajoute les éléments de deux tableaux et stocke les résultats dans un troisième tableau.

for (int i=0; i<16; ++i)
    C[i] = A[i] + B[i];

Le déroulement de cette boucle la transformerait en quelque chose comme ceci:

for (int i=0; i<16; i+=4) {
    C[i]   = A[i]   + B[i];
    C[i+1] = A[i+1] + B[i+1];
    C[i+2] = A[i+2] + B[i+2];
    C[i+3] = A[i+3] + B[i+3];
}

Le vectoriser, en revanche, produit quelque chose comme ceci:

for (int i=0; i<16; i+=4)
    addFourThingsAtOnceAndStoreResult(&C[i], &A[i], &B[i]);

Où «addFourThingsAtOnceAndStoreResult» est un espace réservé pour tout élément (s) intrinsèque (s) utilisé par votre compilateur pour spécifier des instructions vectorielles. Notez que certains compilateurs sont capables de vectoriser automatiquement des boucles très simples comme celle-ci, qui peut souvent être activée via une option de compilation. Des algorithmes plus complexes nécessitent toujours l'aide du programmeur pour générer un bon code vectoriel.

Stephen Canon
la source
13
Quelle est la différence entre cela et le déroulement / déroulement de la boucle?
Jeremy Powell le
3
N'est-il pas vrai qu'un compilateur aurait un travail plus facile de vectoriser automatiquement la boucle déroulée?
Nikos Athanasiou
2
@StephenCanon comment vérifier si certaines lignes ont été vectorisées ou non? Si l'on utilisait objdump, que rechercherait-on dans la sortie de objdump?
user1823664
4
@Shuklaswag: la vectorisation est quelque chose que les compilateurs peuvent faire pour vous, mais c'est aussi quelque chose que les programmeurs font eux-mêmes explicitement. Le système d'exploitation n'est pas impliqué.
Stephen Canon
1
@ user1823664 Les instructions et registres SIMD doivent être présents dans l'objdump. Exemple d'assemblage d'addition vectorisée.
rcode
35

La vectorisation est le terme utilisé pour convertir un programme scalaire en programme vectoriel. Les programmes vectorisés peuvent exécuter plusieurs opérations à partir d'une seule instruction, tandis que le scalaire ne peut fonctionner que sur des paires d'opérandes à la fois.

De wikipedia :

Approche scalaire:

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

Approche vectorisée:

for (i = 0; i < 1024; i+=4)
{
   C[i:i+3] = A[i:i+3]*B[i:i+3];
}
Anders
la source
N'est-ce pas essentiellement la même chose que l'approche scalaire? Votre syntaxe et votre progression en boucle sont différentes, mais en dessous, vous les multipliez encore 4 fois. Mais d'une manière ou d'une autre, ce sera probablement plus rapide que le CPU a des instructions qui font une astuce appelée Vectorisation.
mskw
On dirait que je vais répondre à ma propre question ici. La syntaxe dans l'approche de vectorisation lorsque le complieur verra cela, elle la traduira en instructions CPU optimisées qui multiplient les vecteurs. Comme SIMD.
mskw
11

Il fait référence à la capacité d'effectuer une seule opération mathématique sur une liste - ou «vecteur» - de nombres en une seule étape. Vous le voyez souvent avec Fortran parce que cela est associé au calcul scientifique, qui est associé au supercalcul, où l'arithmétique vectorisée est apparue pour la première fois. De nos jours, presque tous les processeurs de bureau offrent une forme d'arithmétique vectorisée, grâce à des technologies telles que le SSE d'Intel. Les GPU offrent également une forme d'arithmétique vectorisée.

Warren Young
la source
8

La vectorisation est largement utilisée dans le calcul scientifique où d'énormes morceaux de données doivent être traités efficacement.

Dans une vraie application de programmation, je sais qu'il est utilisé dans NUMPY (pas sûr d'autre).

Numpy (package pour le calcul scientifique en python), utilise la vectorisation pour une manipulation rapide d'un tableau à n dimensions, qui est généralement plus lent si cela est fait avec des options python intégrées pour la gestion des tableaux.

bien que des tonnes d'explications soient disponibles, VOICI CE QUE LA VECTORISATION EST DÉFINIE COMME DANS LA PAGE DE DOCUMENTATION NUMPY

La vectorisation décrit l'absence de boucle explicite, d'indexation, etc. dans le code - ces choses se déroulent, bien sûr, juste «en coulisse» dans un code C optimisé et précompilé. Le code vectorisé présente de nombreux avantages, parmi lesquels:

  1. le code vectorisé est plus concis et plus facile à lire

  2. moins de lignes de code signifie généralement moins de bogues

  3. le code ressemble plus étroitement à la notation mathématique standard (ce qui facilite généralement la codification correcte des constructions mathématiques)

  4. la vectorisation donne plus de code «pythonique». Sans vectorisation, notre code serait parsemé de boucles for inefficaces et difficiles à lire.

mauvais programmeur
la source
7

La vectorisation, en termes simples, signifie optimiser l'algorithme afin qu'il puisse utiliser les instructions SIMD dans les processeurs.

AVX, AVX2 et AVX512 sont les jeux d'instructions (Intel) qui effectuent la même opération sur plusieurs données en une seule instruction. par exemple. AVX512 signifie que vous pouvez utiliser 16 valeurs entières (4 octets) à la fois. Cela signifie que si vous avez un vecteur de 16 entiers et que vous voulez doubler cette valeur dans chaque entier, puis y ajouter 10. Vous pouvez soit charger des valeurs sur le registre général [a, b, c] 16 fois et effectuer la même opération, soit effectuer la même opération en chargeant les 16 valeurs sur les registres SIMD [xmm, ymm] et effectuer l'opération une fois. Cela permet d'accélérer le calcul des données vectorielles.

Dans la vectorisation, nous utilisons cela à notre avantage, en remodelant nos données afin que nous puissions effectuer des opérations SIMD dessus et accélérer le programme.

Le seul problème de vectorisation concerne les conditions de manipulation. Parce que les conditions branchent le flux de l'exécution. Cela peut être géré par masquage. En modélisant la condition en une opération arithmétique. par exemple. si nous voulons ajouter 10 à la valeur si elle est supérieure à 100. nous pouvons non plus.

if(x[i] > 100) x[i] += 10; // this will branch execution flow.

ou nous pouvons modéliser la condition en opération arithmétique créant un vecteur de condition c,

c[i] = x[i] > 100; // storing the condition on masking vector
x[i] = x[i] + (c[i] & 10) // using mask

c'est un exemple très trivial cependant ... ainsi, c est notre vecteur de masquage que nous utilisons pour effectuer une opération binaire basée sur sa valeur. Cela évite le branchement du flux d'exécution et permet la vectorisation.

La vectorisation est aussi importante que la parallélisation. Ainsi, nous devons en faire autant que possible. Tous les processeurs modernes ont des instructions SIMD pour les charges de travail de calcul lourdes. Nous pouvons optimiser notre code pour utiliser ces instructions SIMD en utilisant la vectorisation, cela revient à paralléliser notre code pour qu'il s'exécute sur plusieurs cœurs disponibles sur les processeurs modernes.

Je voudrais repartir avec la mention d'OpenMP, qui vous permet de vectoriser le code à l'aide de pragmas. Je considère cela comme un bon point de départ. On peut dire la même chose d'OpenACC.

File d'attente du marché
la source
3

Par les gens d'Intel, je pense que c'est facile à comprendre.

La vectorisation est le processus de conversion d'un algorithme opérant sur une seule valeur à la fois en opérant sur un ensemble de valeurs à la fois . Les processeurs modernes fournissent un support direct pour les opérations vectorielles où une seule instruction est appliquée à plusieurs données (SIMD).

Par exemple, une CPU avec un registre de 512 bits peut contenir 16 doubles à simple précision de 32 bits et effectuer un seul calcul.

16 fois plus rapide que d'exécuter une seule instruction à la fois. Combiner cela avec le threading et les processeurs multicœurs conduit à des gains de performances de l'ordre de grandeur.

Lien https://software.intel.com/en-us/articles/vectorization-a-key-tool-to-improve-performance-on-modern-cpus

En Java, il existe une option pour que cela soit inclus dans Jdk 15 de 2020 ou tardivement au JDK 16 à 2021.

https://bugs.openjdk.java.net/browse/JDK-8201271

L'API Vector est le premier JEP proposé pour cibler dans JDK 16. Proposé de cibler

https://bugs.openjdk.java.net/secure/Dashboard.jspa?selectPageId=19517

chiperortiz
la source
-4

Voir les deux réponses ci-dessus. Je voulais juste ajouter que la raison de vouloir faire de la vectorisation est que ces opérations peuvent facilement être effectuées en paraell par des supercalculateurs et des multi-processeurs, ce qui donne un gros gain de performances. Sur les ordinateurs à processeur unique, il n'y aura aucun gain de performances.

Larry Watanabe
la source
13
"Sur les ordinateurs à processeur unique, il n'y aura pas de gain de performances": faux. La plupart des processeurs modernes ont un support matériel (limité) pour la vectorisation (SSE, Altivec, etc. comme le nomme stephentyrone), ce qui peut donner une accélération significative lors de l'utilisation.
sleske le
merci, j'ai oublié que la parallélisation peut également être effectuée à ce niveau.
Larry Watanabe