Pourquoi la vectorisation, plus rapide en général, que les boucles?
Pourquoi, au niveau le plus bas du matériel effectuant des opérations et des opérations sous-jacentes générales impliquées (c'est-à-dire: choses générales aux implémentations réelles de tous les langages de programmation lors de l'exécution du code), la vectorisation est-elle généralement plus rapide que la boucle?
Que fait l'ordinateur lors de la boucle qu'il ne fait pas lors de l'utilisation de la vectorisation (je parle des calculs réels que l'ordinateur effectue, pas de ce que le programmeur écrit), ou que fait-il différemment?
J'ai été incapable de me convaincre pourquoi la différence devrait être si importante. Je pourrais probablement être persuadé que le code vectorisé rase un peu de surcharge en boucle quelque part, mais l'ordinateur doit toujours effectuer le même nombre d'opérations, n'est-ce pas? Par exemple, si nous multiplions un vecteur de taille N par un scalaire, nous aurons N multiplications à effectuer de toute façon, n'est-ce pas?
3 réponses
La vectorisation (comme le terme est normalement utilisé) fait référence à L'opération SIMD (single instruction, multiple data).
, ce Qui signifie, en substance, qu'une instruction effectue la même opération sur un certain nombre d'opérandes en parallèle. Par exemple, pour multiplier un vecteur de taille N par un scalaire, appelons M le nombre d'opérandes de cette taille sur lesquels il peut fonctionner simultanément. Si c'est le cas, alors le nombre d'instructions qu'il doit exécuter est approximativement N / M, où (avec des opérations purement scalaires) il devrait effectuer N opérations.
Par exemple, le jeu D'instructions AVX 2 actuel D'Intel utilise des registres 256 bits. Ceux-ci peuvent être utilisés à tenir (et exploiter) un ensemble de 4 opérandes de 64 bits chacun, ou 8 opérandes de 32 bits chacun.
Donc, en supposant que vous ayez affaire à des nombres réels à une seule précision de 32 bits, cela signifie qu'une seule instruction peut effectuer 8 opérations (multiplications, dans votre cas) à la fois, donc (au moins en théorie) vous pouvez terminer n multiplications en utilisant seulement N / 8 instructions de multiplication. Au moins, en théorie, cela devrait permettre à l'opération de finition d'environ 8 fois plus rapide que l'exécution d'une instruction à la fois le permettrait.
Bien sûr, l'avantage exact dépend du nombre d'opérandes que vous supportez par instruction. Les premières tentatives d'Intel ne prenaient en charge que les registres 64 bits, donc pour fonctionner sur 8 éléments à la fois, ces éléments ne pouvaient être que 8 bits chacun. Ils prennent actuellement en charge les registres 256 bits, et ils ont annoncé le support de 512 bits (et ils peuvent avoir même livré que dans quelques processeurs haut de gamme, mais pas dans les processeurs de consommation normale, au moins encore). Faire bon usage de cette capacité peut également être non trivial, pour le moins. Les instructions de planification de sorte que vous avez réellement n opérandes disponibles et aux bons endroits au bon moment ne sont pas nécessairement une tâche facile (du tout).
Pour mettre les choses en perspective, le (maintenant ancien) Cray 1 a gagné beaucoup de sa vitesse exactement de cette façon. Son unité vectorielle fonctionnait sur des ensembles de 64 registres de 64 bits chacun, ainsi il pourrait faire 64 opérations de double-précision par cycle d'horloge. Sur le code vectorisé de manière optimale, il était beaucoup plus proche de la vitesse d'un processeur actuel que ce à quoi vous pourriez vous attendre en fonction uniquement de sa vitesse d'horloge (beaucoup plus faible). Profiter pleinement de ce n'était pas toujours facile (et ne l'est toujours pas).
Gardez à l'esprit, cependant, que la vectorisation est pas la seule façon dont un PROCESSEUR peut effectuer des opérations en parallèle. Il y a aussi la possibilité d'un parallélisme au niveau de l'instruction, qui permet à un seul processeur (ou le noyau unique D'un processeur) d'exécuter plus d'une instruction à la fois. La plupart des processeurs modernes incluent du matériel pour exécuter (théoriquement) jusqu'à environ 4 instructions par cycle d'horloge si les instructions sont un mélange de charges, de magasins et D'ALU. Ils peuvent exécuter assez régulièrement près de 2 instructions par horloge en moyenne, ou plus dans des boucles bien réglées lorsque la mémoire n'est pas un goulot d'étranglement.
Ensuite, bien sûr, il y a multi-threading-exécutant plusieurs flux de instructions sur (au moins logiquement) des processeurs/cœurs séparés.
Ainsi, un processeur moderne peut avoir, disons, 4 cœurs, chacun pouvant exécuter 2 multiplications vectorielles par horloge, et chacune de ces instructions peut fonctionner sur 8 opérandes. Donc, au moins en théorie, il peut être effectué 4 * 2 * 8 = 64 opérations par horloge.
Certaines instructions ont un débit meilleur ou pire. Par exemple, FP ajoute un débit inférieur à FMA ou multiplie sur Intel avant Skylake (1 Vecteur par horloge au lieu de 2). Mais la logique booléenne comme AND or XOR a 3 vecteurs par débit d'horloge; il ne faut pas beaucoup de transistors pour construire une unité D'exécution AND/XOR/OR, donc les processeurs les répliquent. Les goulots d'étranglement sur la largeur totale du pipeline (le frontal qui décode et émet dans la partie hors service du noyau) sont courants lors de l'utilisation d'instructions à haut débit, plutôt que les goulots d'étranglement sur une unité d'exécution spécifique.
La vectorisation a deux avantages principaux.
Le principal avantage est que le matériel conçu pour prendre en charge les instructions vectorielles dispose généralement d'un matériel capable d'effectuer plusieurs opérations ALU en général lorsque des instructions vectorielles sont utilisées. Par exemple, si vous lui demandez d'effectuer 16 ajouts avec une instruction vectorielle de 16 éléments, il peut avoir 16 additionneurs parallèles qui peuvent faire tous les ajouts à la fois. Le moyen seulement d'accéder à tous ces adders1 c'est fini vectorisation. Avec des instructions scalaires, vous obtenez juste le 1 additionneur Solitaire.
Il y a généralement des frais généraux enregistrés en utilisant des instructions vectorielles. Vous chargez et stockez des données en gros morceaux (jusqu'à 512 bits à la fois sur certains processeurs Intel récents) et chaque itération de boucle fait plus de travail, de sorte que la surcharge de la boucle est généralement plus faible dans un sens relatif2, et vous avez besoin de moins d'instructions pour faire le même travail afin que la surcharge frontale du processeur soit inférieure, etc.
Enfin, votre dichotomie entre boucles et vectorisation est impair. Lorsque vous prenez du code non vectoriel et que vous le vectorisez, vous allez généralement vous retrouver avec une boucle s'il y en avait une avant, ou pas s'il n'y en avait pas. la comparaison est vraiment entre scalar (non-vector) instructions et instructions vectorielles.
1 Ou au moins 15 des 16, peut-être l'un est également utilisé pour faire scalaire des opérations.
2 Vous pourriez probablement obtenir un semblable boucle de frais généraux l'avantage dans le cas scalaire, au prix de beaucoup de déroulement de la boucle.
La vectorisation est un type de traitement parallèle. Il permet de consacrer plus de matériel informatique à l'exécution du calcul, de sorte que le calcul se fait plus rapidement.
De nombreux problèmes numériques, en particulier la solution d'équations aux Dérivées Partielles, nécessitent le même calcul pour un grand nombre de cellules, d'éléments ou de nœuds. La vectorisation effectue le calcul pour de nombreuses cellules/éléments/nœuds en parallèle.
La vectorisation utilise du matériel spécial. Contrairement à un CPU multicœur, pour laquelle chacune des unités de traitement parallèles est un cœur de CPU entièrement fonctionnel, les unités de traitement vectoriel ne peuvent effectuer que des opérations simples, et toutes les unités effectuent la même opération en même temps, fonctionnant simultanément sur une séquence de valeurs de données (un vecteur).