« Fonctionnement d'un ordinateur/Les architectures à parallélisme de données » : différence entre les versions

 

 

 

Certains processeurs fournissent des instructions capables de traiter plusieurs éléments en parallèle. Ces instructions sont appelées des '''instructions vectorielles'''. Ces instructions vectorielles travaillent sur un plusieurs nombres entiers ou flottants placés les uns à coté des autres, qui forment ce qu'on appelle un vecteur. Quand on exécute une instruction sur un vecteur, celle-ci traite ces entiers ou flottants en parallèle, simultanément.

 

 

Les instructions SIMD peuvent être rassemblées en deux grands groupes : les horizontales et les verticales. Les instructions horizontales travaillent en parallèle sur les éléments qui sont "à la même place" dans deux vecteurs. Les instructions verticales vont réduire un vecteur en un simple nombre. Elle peuvent calculer la somme des éléments d'un vecteur, calculer le produit de tous les éléments d'un vecteur, renvoyer le nombre d’éléments nuls dans un vecteur, etc. Une instruction de calcul vectoriel va traiter chacune des données du vecteur indépendamment des autres. Par exemple, une instruction d'addition vectorielle va additionner ensemble les données qui sont à la même place dans deux vecteurs, et placer le résultat dans un autre vecteur, à la même place.

 

 

Les instructions SIMD sont difficilement utilisables dans des langages de haut niveau et c'est donc au compilateur de traduire un programme avec des instructions vectorielles. Les transformations qui permettent de traduire des morceaux de programmes en instructions vectorielles (déroulage de boucles, strip-mining) portent le nom de vectorisation.

 

 

Nos processeurs contiennent des registres spécialisés pouvant chacun contenir un paquet. Pour traiter un paquet, il suffira alors de le charger dans un de ces registres, et éxecuter une ou plusieurs instructions dessus. Cela a une conséquence : les registres ayant tous une taille fixe, la taille d'un paquet est fixée une fois pour toute par le jeu d'instruction. Cela implique que suivant la taille des données à manipuler, on pourra en placer plus ou moins dans un paquet.

 

 

On devra utiliser des instructions différentes suivant ce qu'on met dans le paquet : suivant la taille des données, et le type de celle-si, on devra effecteur des manipulations différentes. Par exemple, on devra utiliser deux instructions différente suivant le type des données présentes dans le vecteur (flottant, entier, booléens, etc). Il faudra aussi gérer la taille des données : il faudra bien savoir comment découper le paquet en données à traiter en parallèle. Et pour cela, on utilise différentes instructions suivant ce que contient le paquet : l'instruction pour manipuler des paquets contenant des entiers de 16 bits sera différente de celle manipulant des entiers de 32 bits.

Un processeur vectoriel peut aussi incorporer d'autres registres pour faciliter le traitement des diverses instructions. Ces registres vont permettre au compilateur de mieux utiliser les instructions vectorielles pour compiler certaines structures logicielles. Parmi ces registres, nous aborderons ultérieurement le Vector Length Register, et le Vector Mask Register.

 

 

La première technique permet de gérer les tableaux dont la taille n'est pas un multiple d'un vecteur, en ajoutant un registre spécial : le '''Vector Length Register'''. Celui-ci indique combien d’éléments on doit traiter dans un vecteur. On peut ainsi dire au processeur : je veux que tu ne traite que les 40 premiers éléments présents d'un paquet. Quand on arrive à la fin d'un tableau, il suffit de configurer le Vector Length Register pour ne traiter que ce qu'il faut.

 

 

Ce registre facilite l'usage d'une optimisation appelée le '''déroulage de boucle'''. Il s'agit d'une optimisation qui vise à réduire le nombre d'itérations d'une boucle en dupliquant son corps en plusieurs exemplaires. Elle est utilisée pour réduire le cout d’exécution des branchements et des autres opérations de comparaison de la boucle. Sur les processeurs SIMD, elle peut s'utiliser afin de réduire le temps d’exécution de boucles qui agissent sur des tableaux. D'ordinaire, les programmeurs utilisent une boucle pour répéter un traitement sur tous les éléments d'un tableau, la boucle traitant un élément à la fois. Nos instructions vectorielles permettent de traiter plusieurs éléments à la fois, ce qui fait que plusieurs tours de boucles peuvent être rassemblés en une seule instruction SIMD. Mais cela ne fonctionne que si les éléments du tableau sont traités indépendamment, ou d'une façon assez simple, auquel cas la boucle peut être vectorisée. Pour cela, le compilateur va répliquer le corps de la boucle (les instructions à répéter) en plusieurs exemplaires dans cette boucle.

Les processeurs vectoriels utilisent le Vector Length Register pou éviter d'utiliser le strip-mining. Pour rappel ce registre stocke le nombre d’éléments que notre instruction doit traiter. Avec ce registre, il est possible de demander aux instructions vectorielles de ne traiter que les n premiers éléments d'un vecteur : il suffit de placer la valeur n dans le Vector Length Register. Évidemment, n doit être inférieur ou égal au nombre d’éléments maximal du vecteur. Avec ce registre, on n'a pas besoin d'une seconde boucle pour traiter les éléments restants, et une simple instruction vectorielle peut suffire.

 

 

Autre obstacle à la vectorisation : la présence de branchements conditionnels dans les boucles à vectoriser. Si une boucle contient des branchements conditionnels, elle ne peut pas être vectorisée facilement : il est impossible de zapper certains éléments d'un vecteur suivant une condition. Pour résoudre ce problèmes, les processeurs vectoriels utilisent un registre de mask, ou Vector Mask Register. Celui-ci stocke un bit pour chaque donnée présente dans le vecteur à traiter, qui indique s'il faut ignorer la donnée ou non.

 

 

 

La gestion des accès mémoire est assez hétéroclite, la façon de faire étant différente selon le architectures.

* Sur certains processeurs assez anciens, les instructions vectorielles lisent et écrivent en mémoire RAM, sans passer par des registres : on parle de '''processeurs memoire-mémoire'''.

* Les '''processeurs à registres vectoriels''' possèdent des registres vectoriels dédiés aux vecteurs.

Les processeurs vectoriels incorporent aussi un dernier type d'accès à la mémoire : le '''scatter-gather'''. Les accès en Scatter-Gather peuvent être vus comme une généralisation de l'adressage indirect à registre aux vecteurs : chaque élément du vecteur est adressé via adressage indirect. Cet accès demande d'avoir une liste d'adresses mémoires des données. Quand une instruction exécute un accès en scatter, les données présentes dans ces adresses sont rassemblées dans un vecteur, et enregistrée dans un registre vectoriel. Bien sûr, il existe aussi l’inverse : on peut écrire les données d'un vecteur dans des emplacements mémoires dispersés : c'est l'accès en gather. Cet accès sert à mieux gérer les matrices creuses. Dans ces matrices, une grande partie des éléments sont nuls. Dans un souci d'optimisation, seuls les éléments non nuls de la matrice sont stockés en mémoire. Avec ce genre d'organisation, les instructions vectorielles ne seraient pas utilisables sur ce genre de matrices, sans Scatter-Gather

 

 

===Exemple avec les processeurs x86===

</gallery>

 

 

Commençons par étudier le MMX. Le MMX ajoutait pas mal d'instructions SIMD assez basiques, essentiellement des instructions arithmétiques : addition, soustraction, opérations logiques, décalages, rotations, mise à zéro d'un registre, etc. La multiplication est aussi supportée, mais avec quelques petites subtilités, via l'instruction PMULLW. Ce MMX introduisait 8 registres vectoriels, du nom de MM0, MM1, MM2, MM3, MM4, MM5, MM6 et MM7. Ceux-ci avaient une taille de 64 bits et ne pouvaient contenir que des nombres entiers : pas de nombres flottants à l'horizon. Il n'y a pas de registre d'état pour les instructions MMX. Pire : les instructions MMX ne mettent aucun registre d'état à jour et ne préviennent pas en cas d'overflow ou d'underflow si ceux-ci arrivent (pour les instructions qui ne travaillent pas en arithmétique saturée).

[[File:SSE registers.PNG|centre|vignette|upright=2.0|Registres MMX.]]

 

 

[[File:XMM registers.svg|droite|vignette|XMM registers]]

Le '''SSE4''' fut un peu plus complexe et fut décliné lui-même en 2 sous-versions. Le SSE4.1 introduit ainsi des opérations de calcul de moyenne, de copie conditionnelle de registre (un registre est copié dans un autre si le résultat d'une opération de comparaison précédente est vrai), de calcul de produits scalaire, de calcul du minimum ou du maximum de deux entiers, des calculs d'arrondis, et quelques autres. Avec le SSE4.2, le vice à été poussé jusqu'à incorporer des instructions de traitement de chaines de caractères.

 

 

Enfin, la dernière extension en date est l''''AVX'''. Avec celle-ci, on retrouve 16 registres nommés de YMM0 à YMM15, dédiés aux instructions AVX et d'une taille de 256 bits. Ces registres YMM sont partagés avec les registres XMM : les 128 bits de poids faible des registres YMM ne sont autre que les registres XMM. L'AVX complète le SSE et ses extensions, en rajoutant quelques instructions, et surtout en permettant de traiter des données de 256 bits. Son principal atout face au SSE, et que les instructions AVX permettent de préciser le registre de destination en plus des registres stockant les opérandes. Avec le SSE et le MMX, le résultat d'une instruction SIMD était écrit dans un des deux registres d'opérande manipulé par l'instruction : il fallait donc sauvegarder son contenu si on en avait besoin plus tard. Avec l'AVX, ce n'est plus le cas : on peut se passer des opérations de sauvegarde sans problème, ce qui supprime pas mal d'instructions.

 

 

 

Les instructions SIMD sont assez rudimentaires, et certains processeurs assez anciens allaient un peu plus loin : ces processeurs sont ce qu'on appelle des '''processeurs vectoriels'''. Ils incorporent diverses techniques que de simples instructions SIMD n'ont pas forcément. Les processeurs vectoriels ne font pas leurs calculs de la même manière que les processeurs SIMD, et n'accèdent pas à la mémoire de la même façon. Par exemple, pour permettre les accès en scatter-gather, les processeurs vectoriels sont souvent combinés à des mémoires multiports ou pipelinées. De plus, les processeurs vectoriels ne possèdent aucune mémoire cache pour les données (même s'ils ont des cache d'instruction).

 

 

La différence entre processeur vectoriel et SIMD tient dans la façon dont sont traités les vecteurs : les instructions SIMD traitent chaque élément en parallèle, alors que les processeurs vectoriels pipelinent ces calculs ! Par pipeliner, on veut dire que l’exécution de chaque instruction est découpée en plusieurs étapes indépendantes : au lieu d'attendre la fin de l’exécution d'un opération avant de passer à la suivante, on peut ainsi commencer le traitement d'une nouvelle donnée sans avoir à attendre que l'ancienne soit terminée.

Pour donner un exemple, on peut donner l'exemple d'une multiplication flottante effectuée entre deux registres. Son exécution peut être décomposée en plusieurs étapes.

Par exemple, on peut avoir 3 étapes :

* une première étape E qui va additionner les exposants et gérer les diverses exceptions ;

* une étape M qui va multiplier les mantisses ;

L’exécution de notre opération flottante sur un vecteur donnerait donc quelque chose dans le genre, où chaque ligne correspond au traitement d'un nouvel élément dans un vecteur, dans un paquet SIMD.

 

 

Avec une unité de calcul pipelinée découpée en N étages, on peut gérer plusieurs opérations simultanées : autant qu'il y a d'étapes différentes. Mais ce nombre maximal d'opérations met un certain temps avant d'être atteint : l'unité de calcul met un certain temps avant d'arriver à son régime de croisière. Durant un certain temps, elle n'a pas commencé à traiter suffisamment d’éléments pour que toutes les étapes soient occupées. Ce temps de démarrage est strictement égal du nombre d'étapes nécessaires pour effectuer une instruction. La même chose arrive vers la fin du vecteur, quand il ne reste plus suffisamment d’éléments à traiter pour remplir toutes les étapes.

 

 

Pour amortir ces temps de démarrage et de fin, certains processeurs démarrent une nouvelle instruction sans attendre la fin de la précédente : deux instructions peuvent se chevaucher pour remplir les vides. Par contre, il peut y avoir des problèmes lorsque deux instructions qui se suivent manipulent le même vecteur. Il faut que la première instruction ait fini de manipuler un élément avant que la suivante ne veuille commencer à le modifier. Pour cela, il faut avoir des vecteurs suffisamment qui contiennent plus d’éléments qu'il n'y a d'étapes pour effectuer notre instruction.

 

 

Cette technique du pipeline peut encore être améliorée dans certains cas particuliers. Imaginons que l'on ait trois paquets : A, B et C. Pour chaque i-éme élément de ces paquets, je souhaite effectuer le calcul Ai+Bi×Ci. Mon processeur ne disposant pas d'instruction permettant de faire en une fois ce calcul, je dois utiliser deux instruction vectorielles : une d'addition, et une autre de multiplication. On pourrait penser que l'on doit effecteur d'abord la multiplication des paquets B et C, stocker le résultat dans un paquet temporaire, et effectuer l'addition de ce tableau avec le paquet A. Mais en rusant un peu, on s’aperçoit qu'on peut simplifier le tout et utiliser notre pipeline plus correctement. Une fois que le tout premier résultat de la multiplication du premier vecteur est connu, pourquoi ne pas démarrer l'addition immédiatement après, et continuer la multiplication en parallèle ? Après, tout les deux calculs ont lieu dans des ALUs séparés. Il s'agit de ce qu'on appelle le Vector Chaining.

 

 

Pour ce faire, on doit modifier notre pipeline de façon à ce que le résultat de chaque étape d'un calcul soit réutilisable au cycle d’horloge suivant. La sortie de l'unité de multiplication doit être connectée à l'entrée de l'ALU d'addition. Un processeur implémentant le chaining a toutes ses unités de calcul reliées entre elles de cette façon : la sortie d'une unité est reliée aux entrées de toutes les autres.

 

 

Certains de nos processeurs vectoriels utilisent plusieurs ALU pour accélérer les calculs. En clair, ils sont capables de traiter les éléments d'un vecteur dans des ALU différentes. Vu que nos ALU sont pipelinées, rien n’empêche d’exécuter plusieurs instructions vectorielles différentes dans une seule ALU, chaque instruction étant à une étape différente. Mais d'ordinaire, les processeurs vectoriels comportent plusieurs ALUs spécialisées : une pour les additions, une pour la multiplication, une pour la division, etc.

 

 

Les '''processeurs de flux''', aussi appelés ''stream processors'', sont des processeurs SIMD qui utilisent une hiérarchie de registres. Voici à quoi ressemble l'architecture d'un Stream Processor :

 

 

A première vue, les schémas du dessus ne ressemblent à rien de connu. Et pourtant on peut déjà faire quelques remarques assez intéressantes. Déjà, il n'y a pas de mémoires caches. Ensuite, l'ensemble ressemble fortement à ce qu'on trouve sur les processeurs vectoriels, à part que les registres vectoriels sont scindés en plusieurs exemplaires.

Mais attention : si un Stream Processor ne contient pas de mémoire cache pour les données, ce n'est pas le cas pour les instructions. Après tout, si l'on doit exécuter ces instructions plusieurs fois de suite sur des données différentes, autant éviter de les charger de la mémoire à chaque fois. Pour éviter cela, les suites d'instructions à exécuter sont stockées dans une petite mémoire une bonne fois pour toute. Il s'agit bel et bien d'une petite mémoire cache.

 

 

Les Streams Processors ont plusieurs bancs de registres. On trouve d'abord quelques '''Local Register File''', directement connectés aux unités de calcul. Plus bas, ces Local Register Files sont reliés à un Register File plus gros, le '''Global Register File''', lui-même relié à la mémoire. Ce Global Register File sert d'intermédiaire entre la mémoire RAM et le Local Register File. La différence entre ce Global Register File et un cache vient du fait que les caches sont souvent gérés par le matériel, tandis que ces Register Files sont gérés via des instructions machines. Le processeur dispose ainsi d'instructions pour transférer des données entre les Register Files ou entre ceux-ci et la mémoire. Leur gestion peut donc être déléguée au logiciel, qui saura les utiliser au mieux. Outre son rôle d'intermédiaire, le Global Register File sert à transférer des données entre les Local Register Files, où à stocker des données globales utilisées par des Clusters d'ALU différents. Les transferts de données entre la mémoire et le Global Register File ressemblent fortement à ceux qu'on trouve sur les processeurs vectoriels. Un Stream Processor possède quelques instructions capables de transférer des données entre ce Global Register File et la mémoire RAM. Et on trouve des instructions capables de travailler sur un grand nombre de données simultanées, des accès mémoires en Stride, en Scatter-Gather, etc.

 

 

On peut se demander pourquoi utiliser plusieurs couches de registres ? Le fait est que les Streams Processors disposent d'une grande quantité d'unités de calcul. Et cela peut facilement aller à plus d'une centaine ou d'un millier d'ALU ! Si on devait relier toutes cas unités de calcul à un gros Register File, celui-ci serait énorme, lent, et qui chaufferait beaucoup trop. Pour garder un Register Files rapide et pratique, on est obligé de limiter le nombre d'unités de calcul connectées dessus, ainsi que le nombre de registres contenus dans le Register File. La solution est donc de casser notre gros Register File en plusieurs plus petits, reliés à un Register File plus gros, capable de communiquer avec la mémoire. Ainsi, nos unités de calcul vont aller lire ou écrire dans un Local Register File très rapide.