Les Machines Vectorielles
Jean-Paul Sansonnet
On ne peut pas présenter les machines Vectorielles sans évoquer l'itinéraire du fondateur de Cray Research Inc. : Seymour Cray. Diplômé de l'Université du Minnesota, il est co-fondateur de Control Data Corporation. Il conçoit l'architecture de tous les ordinateurs de haut de gamme, jusqu'au CDC 7600. Il a aussi participé à la définition des STAR-100 ancêtres des Cyber 203 et 205. En 1972 ayant quitté CDC, il crée dans sa ville natale de Chippewa Falls, Wisconsin, la société Cray. En 1976, le premier prototype du Cray-1 fonctionne ; il n'est plus commercialisé, seul subsiste le Cray X-MP et le Cray 2. Aujourd'hui Seymour Cray est indépendant et il continue à travailler sur l'architecture des ordinateurs. Il aime à dire que son outil de travail est désormais un MacIntosh !
La Firme Cray Research Inc. n'a pas le monopole des Supercalculateurs Vectoriels dans le monde. La société Control Data fut longtemps le leader de ce marché. IBM avec sa série 3090-VF offre aussi des machines puissantes. Les Japonnais NEC (avec le SX1 et SX2), Hitachi (avec le S-810 à S-830) ne sont pas en reste mais ces produits ne sont pas diffusés hors du Japon ; les processeurs vectoriels de Fujitsu (modèles VP 50 à VP 400) sont commercialisés en Europe sous les noms de Amdahl et Siemens.
Les Machines Vectorielles.
Sommaire.
Structure des Grandes Applications Scientifiques.
Eloge de la Virgule Flottante.
Types d'Architectures SIMD.
Principe du Pipe-Line.
La Vectorisation.
Schéma de Principe de l'exécution Vectorielle.
Le Chaînage.
Les Techniques de Gather / Scatter.
Mémoire Centrale Entrelacée.
Compilation en Instructions Vectorielles.
Conditions de Vectorisation.
Les Quatre Classes de Dépendances.
Analyse de Graphes de Dépendances.
Le Vectoriseur PARAFRASE.
Analyse des Performances Théoriques de 3 Modèles.
Définition de la Puissance de Crête.
Efficacité du Pipe-Line et du Chaînage.
Influence des Registres Vectoriels sur la Performance.
Influence du Mode Scalaire sur la Performance.
Architecture du Cray-1.
La Wish-list du Cray X-MP.
Architecture d'un Processeur du Cray X-MP.
Architecture Multiprocesseurs du Cray X-MP.
Caractéristiques des Systèmes Cray.
Architecture de l'IBM 3090-VF.
Architecture du Control Data Cyber 205.
Les composants Pipe-Line de la Famille Weitek.
Fonctionnement du Profil MAC sur le Weitek.
Le Microprocesseur Intel i860.
Fonctionnement Superscalaire du i860.
Comparaison des principaux Supercalculateurs.
Les grandes applications scientifiques présentent des caractéristiques étonnamment semblables : cela vient du fait qu'elles étudient le milieu physique dans lequel nous ; elles partagent la notion d'espace et de temps continus.
Un exemple typique de grande application scientifique est l'étude de la mécanique des fluides qui sert aussi bien dans la météorologie que l'aérodynamique (aéronautique, automo-bile...). On est amené à réaliser des souffleries digitales qui ne remplacent pas les souffleries physiques (analogiques) mais qui permettent de tester à moindre coût des hypothèses (a).
Le problème consiste à analyser des flux aérodynamiques autour d'un objet en mouvement. On cherche à déterminer en chacun des points du milieu et à tout instant la valeur des paramètres (température, pression etc.). Le phénomène étudié peut être décrit par les équations de Navier-Stokes (b). On ne sait pas, à l'heure actuelle, résoudre un tel système d'équations.
On recherche alors des solutions approchées, en utilisant par exemple la méthode des Eléments finis. La région étudiée est discrétisée sous forme d'une grille tridimensionnelle de points (c). Le milieu continu est remplacé par un nombre fini de points (il en est de même pour le temps continu qui est remplacé par des intervalles de temps).
Mathématiquement, cela revient à remplacer un système d'équations aux dérivées partielles (que l'on ne sait pas résoudre) en un système d'équations algébrique ordinaires, dont la résolution (que l'on maîtrise parfaitement) conduit à la détermination d'une valeur approximative des paramètres.
On aboutit alors à de très grands systèmes d'algèbre linéaire et de calcul matriciel qui sont historiquement programmés en FORTRAN. En algèbre linéaire, les opérations typiques à réaliser sont des itérations sur des couples d'opération : Multiplication-Addition-Cumul (MAC) Par exemple, si on doit faire le produit de la matrice M(N, N) par le Vecteur X(N) on obtient le programme FORTRAN (d) où l'instruction centrale revient très souvent dans ce type d'application.
La Virgule Flottante est une notation qui permet aux Scientifiques de manipuler de très grands ou de très petits nombres. Par exemple, la distance de la Terre au Soleil est de : 149500000000 mètres. Il est plus facile en physique de le noter : 1495 . 108. Pour les distances, il est plus "lisible" en puissances de mille ; cela donne alors : 149,5 . 109 ce qui veut dire que la distance de la Terre au Soleil est de 150 milliards de mètres (environ).
De même un nombre très petit comme : 0,000 000 012 secondes peut être écrit comme : 12 . 109 ce qui veut dire "12 nanosecondes".
Dans le calcul scientifique on utilise généralement des nombres exprimés dans la notation suivante :
M . B±N
où M est la mantisse, B la base et N l'exposant. Les avantages de cette notation sont :
Un ordinateur à vocation scientifique se doit donc de posséder à côté d'un jeu d'instructions de calcul entier un jeu complet d'instructions pour effectuer ces calculs. En général, le système de notation est normalisé : cela veut dire que la position relative de la virgule dans le nombre est ajustée automatiquement par l'ordinateur de manière à ce qu'elle se trouve toujours à la même position. En général on choisit de représenter les mantisses entre 0 et 1 ; cela produit des nombres de la forme : 0,1234 . 10n. Ansi, le nombre 12,34 . 103 sera ajusté automatiquement en : 0,1234 . 105 . On dit que la virgule est flottante (en fait elle est fixe c'est plutôt l'exposant qui flotte), d'où le nom de nombre flottant et de calcul flottant donné à ce système de représentation des nombres.
La précision d'un nombre flottant est fixée par la quantité de chiffres composant la mantisse. On trouve les formats suivants :
le nombre flottant est représenté sur 32 bits. C'est la notation employée sur les machines courantes qui n'ont pas de vocation scientifique particulière. On exploite alors le chemin de données standard de 32 bits, qui permet d'effectuer des calculs flottants "simples" :
le nombre flottant est représenté sur 64 bits. C'est le mode le plus souvent utilisé dans les calculateurs à vocation scientifique dont le chemin des données (taille des Bus, des UALs, des Registres...) est alors porté à 64 bits :
le nombre flottant est représenté sur 128 bits. Ceci correspond à des besoins spécifiques ; ce mode est émulé sur un chemin de données 64 bits.
Sur les Ordinateurs de Calcul scientifique, on voit que le facteur de mesure de l'efficacité n'est pas le nombre de Millions d'Instructions courantes (Load, Store, Addition entière...) exécutées Par Seconde, exprimé en MIPS, mais le nombre de Millions d'Opérations Flottantes exécutées Par Seconde. Il est exprimé en MegaFLOPS (Mega FLoat Operation Per Second).
Les machines SIMD partagent avec le modèle de machine séquentielle de Von Neumann (SISD) la propriété importante d'exécuter un seul programme dont le contrôle est séquentiel. Il existe quatre types d'Architectures parallèles qui ont cette propriété :
a) Les machines Pipe-Line sont des extensions du modèle de Von Neumann où on a pipeliné l'unité d'exécution des instructions. Ceci permet de recouvrir le temps d'extraction des instructions. Dans ce chapitre on les appellera le plus souvent des machines ou des processeurs Scalaires (par opposition à Vectoriel).b) Les machines Vectorielles sont des extensions du modèle de Von Neumann où on a pipeliné l'Unité Arithmétique et Logique. Ceci permet de recouvrir le temps d'exécution des instructions.
c) Les machines VLIW possèdent plusieurs unités arithmétiques et Logiques en parallèle qui exécutent chacune une partie de l'instruction longue, fournie par l'unité de contrôle centralisée.
d) Les machines Cellulaires (encore appelées Array Processors) sont des machines à mémoire distribuée : chaque PE comprend une mémoire locale et une Unité arithmétique et logique.
Dans une machine classique, les instructions sont exécutées de manière séquentielle (a). Chaque instruction contient plusieurs phases (c). Le temps d'exécution d'une phase se mesure en cycles (plus petite unité d'horloge de la machine) ; en général, les accès mémoire (Fetch Inst, Fetch Op. ...) prennent deux cycles de base (à condition qu'on utilise un cache !) et les autres phases un seul cycle. Si on utilise des instructions complexes (calcul flottant...) alors une phase peut prendre plusieurs cycles.
Deux techniques de base furent appliquées dans les premiers supercalculateurs et sont utilisées aujourd'hui dans les supermicroprocesseurs (RISC ou VLIW) :
Si on considère le "programme-idiot" proposé par Gajski (a), on peut décomposer son graphe d'exécution de deux manières différentes :
(a) Programme-idiot de Gajski :
Begin
c0 := 0 ;
For i := 1 to 8 do
ai := di / ei ;
bi := ai ¥ fi ;
ci := bi + ci-1
End
End
Le principe de l'exécution vectorielle est expliqué ici par une machine fictive très simplifiée qui possède des Registres Vectoriels RV de 64 mots. En mode vectoriel, la compilation de l'instruction :
For i := 1 to 64 do
C [ i] := A [i] + B [ i] provoque l'exécution des instructions machines suivantes :
Vload A, RV1 Vload B, RV2 Vadd RV1, RV2, RV0 Vstore C, RV0
Chaque instruction contient une boucle de 64 cycles qui correspondent aux cycles mineurs ou cycles de base de la machine pipe-line. Par exemple, pour Vload A, RV1 les 64 mots de A sont chargés dans le Registre Vectoriel RV1 en 64 cycles mineurs mémoire : ces cycles mineurs sont obtenus en plaçant chaque élément du tableau A dans le banc mémoire respectif, permettant ainsi de les lire en pipe-line (les limitations n'étant alors plus dues qu'à la bande passante de la liaison mémoire <--> registres vectoriels). L'unité Arithmétique et Logique est composée de quatre étages Pipe-lines qui ont un temps de traversée fixe égal à un cycle mineur ; chaque étage est dédié à une partie de l'opération d'addition flottante.
La technique de chaînage est employée pour pipe-liner des instructions qui se suivent fréquemment dans le code-source comme c'est souvent le cas lorsqu'on il s'agit d'un profil typique MAC : Multiplication - Addition - Cumul (a). Il faut bien sûr que la machine Vectorielle dispose de plusieurs unités vectorielles qui sont mises bout-à-bout. Au micro-pipe-line à l'intérieur d'une unité vectorielle correspond le macro-pipe-line du chaînage des unités vectorielles entre elles. Par exemple, la compilation de l'instruction (a) provoque l'exécution des instructions pipe-line :
Vload B, RV1 Vload C, RV2 Vload A, RV3 Vadd (Vmult RV1, RV2), RV3, RV0 Vstore A, RV0
On voit que l'expression du corps de boucle est compilée comme une instruction chaînée, ce qui permet à la machine d'enchaîner les opérateurs pipe-line d'addition et de multiplication pour créer un macro-opérateur pipe-line à 8 étages.
L'exploitation optimale d'une machine Vectorielle repose sur le postulat que l'application contient des données vectorielles. Il arrive assez souvent que les données d'une application ne se présentent pas sous une forme aussi régulière : par exemple des matrice creuses, des valeurs dispersées dans un tableau... Dans ce cas, la non-contiguïté des données empêche l'utilisation de l'unité vectorielle de la machine. Cependant, certaines machines Vectorielles possèdent des outils matériels qui facilitent le traitement des opérations sur les données dispersées grâce aux opérations de :
On utilise deux techniques de base pour les opérations de Gather/Scatter : la méthode des registres de masque (a) permet d'effectuer un compression et une décompression sur les données (on associe un registre de masque par profil de dispersion ; dans cet exemple on a supposé pour simplifier que les tableaux A, B et C avaient le même profil de dispersion). La méthode des registres d'index (b) remplace chaque bit du registre de masque par un entier qui spécifie la position de l'élément dans le vecteur destination. Ceci permet d'effectuer des compressions (l'indice 0 veut dire que la donnée n'a pas de destination) mais aussi des permutation variées (par exemple une permutation circulaire comme ci-dessus) ; plus coûteuse, cette méthode est aussi plus puissante.
Ce qui fait la qualité d'une machine Vectorielle c'est l'équilibre des flux d'information qui circulent entre les diverses unités de la machine. Cet équilibre peut être rompu si une des unités n'a pas assez de débit : c'est généralement le cas de la mémoire centrale qui est technologiquement plus lente que les unités de calcul Vectorielles ou même Scalaires. Pour compenser cette faiblesse on utilise des mémoires centrales organisées en bancs entrelacés (a).
Supposons que l'on veuille lire un vecteur de 10 éléments, rangé en mémoire centrale de manière à ce que chaque élément du vecteur soit placé dans un banc : le mot 1 du vecteur est à l'adresse @ du banc 1, le mot 2 du vecteur est aussi à l'adresse @ du banc 2, .... le mot 10 du vecteur est à l'adresse @ du banc 10. Grâce à cet entrelacement, on peut lire le vecteur en mode pipe-line (b) : après un temps d'amorce, l'unité centrale reçoit un mot à chaque cycle alors que le temps d'accès d'un banc est 4 fois plus lent !
Dans cet exemple, on calcule les adresses successives des éléments du vecteur de manière très simple : l'unité de calcul des adresses ajoute 1 à l'adresse de banc et ne modifie pas l'adresse relative dans le banc : on dit que le pas (ou Stride) est de 1. Il existe des cas plus défavorables :
Les machines Vectorielles doivent être accompagnées d'outils logiciels spécifiques chargés de réaliser la Vectorisation des programmes utilisateurs écrits en mode séquentiel normal. Généralement ces programmes sont des bibliothèques de calcul numérique écrites en Fortran. L'exemple le plus simple d'opération de vectorisation est fourni par le programme Fortran (a) : on effectue l'addition de deux tableaux de N éléments. Le programme de vectorisation est capable de prendre ce code-source et de le traduire en une seule instruction vectorielle (b) qui ressemble à une instruction APL.
Certaines machines comme l'IBM 3090 possèdent à côté de leur jeu d'instructions classique un jeu d'instructions spécifique pour traiter les opérations vectorielles de base. On peut alors compiler (b) en (c) où les instructions vectorielles de bas niveau débutent par la lettre "V". Dans le cas de l'IBM 3090, les opérations vectorielles s'effectuent par paquets (bursts) de 128 mots de données.
La Vectorisation des boucles est soumise dans le cas général à des conditions draconiennes : Il ne faut pas qu'ils existe des dépendances entre les itérations. Par exemple dans la boucle FORTRAN (a) le i-ème élément du tableau X est calculé en fonction de sa valeur à l'itération i-1, ce qui empêche l'expression sous forme d'instruction vectorielle !
En procédant à des transformations sur le programme source, il arrive qu'on puisse éliminer les dépendances. Par exemple, si on considère le produit matriciel :
on l'écrit en FORTRAN sous la forme (b) car les matrices sont rangées en colonnes d'abord. C'est pourquoi on veut que l'indice i varie le plus vite (on suppose que le tableau C a été initialisé préalablement à 0).
On constate alors qu'il y a une dépendance entre les itérations k et k+1, due au fait que C(i,j) sert d'accumulateur pour les calculs (c).
La solution consiste à inverser l'ordre des itérations (d). On obtient alors une instruction centrale qui a la forme (e) : ici, le calcul de la partie gauche ne dépend que des éléments de même indice i ou de constantes.
La boucle peut être traduite sous forme vectorisée, par exemple en FORTRAN 8X comme indiqué en (f). Dans cet exemple, la transformation est triviale, mais dans les programmes plus généraux, il n'est pas du tout facile d'exercer automatiquement (par trans-formation de source à source) des suppressions de dépendances complexes.
Les outils de Vectorisation qui prennent comme source des programmes classiques, écrits en FORTRAN par exemple, doivent effectuer des analyses poussées pour analyser les dépendances qui existent entre les variables. A partir du programme source (b) on peut alors construire le graphe de contrôle (a) et surtout le graphe des dépendances (c) pour obtenir toutes les dépendances associées à une variable (e).
On voit que la variable A a une dépendance de flot entre les instructions 1 et 3 mais aussi une dépendance de sortie entre les instructions 1 et 6 et une anti-dépendance de flot entre les instructions 1 et 3. Le vectoriseur doit tenir compte de ces informations pour effectuer ses transformations de programme.
L'outil logiciel Vectoriseur PARAFRASE est un compilateur Fortran qui effectue plusieurs opérations sur le code source :
L'outil Vectoriseur PARAFRASE contient 50 Modules dédiés à ces diverses tâches qui peuvent être combinées pour obtenir des codes plus ou moins optimisés et plus ou moins vectorisés et surtout pour viser diverses machines-cibles parallèles. PARAFRASE peut accélérer de 2 à 5 fois le code Fortran. Parmi les techniques employées dans PARAFRASE on peut citer :
Considérons un tableau de n données sur lequel on effectue p opérations (OP) pour chaque élément. On utilise une machine séquentielle où les opérations prennent un cycle fixe de durée t (ou Téta dans le dessin) :
Si on considère que le temps de mise en place de la boucle (startup) est s, le temps d'exécution total sera :
Tseq = (s +n.p) t
Le temps moyen de traitement d'un élément est :
tseq = Tseq / n
Lorsque n devient grand, le temps moyen de traitement d'un élément tend vers :
a = Limn->inf Tsq / n = p.t
Si maintenant on considère qu'on exécute cette même boucle en mode pipe-line (p étages) sur une machine vectorielle, on a le schéma de fonctionnement suivant :
Le temps d'exécution devient :
Tpipe = ((s+p) + (n-1)) . t
où (s+p) est le temps de remplissage du pipe-line (obtention du premier résultat) et où (n-1) est le temps d'obtention des autres résultats. Lorsque n devient grand, le temps moyen de traitement d'un élément tend vers :
b = Limn->inf Tpipe / n = t
Le gain de vitesse obtenu (speedup) est égal à :
a / b = p
Ce qui démontre que le gain maximal idéal (en vitesse de croisière sur de grands tableaux) obtenu par une machine vectorielle est égal au nombre de ses étages pipe-line.
Si maintenant on considère qu'on exécute cette même boucle sur une machine parallèle, on a le schéma de fonctionnement suivant :
Dans ce modèle de machine, on considère qu'on dispose de m unités de calcul (PEs) placées en parallèle ; nous supposerons ici que n < m. Le temps d'exécution total sera :
Tpar = (s+p) . t
Le temps moyen de traitement d'un élément est :
tpar = 1/n . (s+p) . tLimn->inf Tpar / n = 0
Ceci montre que plus le nombre d'éléments traités est grand plus le temps moyen diminue (cela suppose qu'on dispose d'un très grand nombre de PEs). Les courbes ci-dessous résument les performances théoriques des trois modes de fonctionnement :
Le profil MAC (a) est rencontré si souvent dans les applications en Calcul Scientifique massivement parallèle qu'il est devenu un standard. Pratiquement toute machine Vectorielle digne de ce nom se doit d'offrir un mode pipe-line qui effectue le chaînage des MACs.
Supposons que le temps de startup du pipe-line de l'unité vectorielle de multiplication est appelé m (dans cet exemple m = 3) et si le temps de startup du pipe-line de l'unité vectorielle d'addition est appelé a (dans cet exemple a = 3 aussi). Si on ne dispose pas du chaînage, pour traiter un profil MAC sur un vecteur de N éléments, le temps d'exécution sera :
T = (m + N) + ( a + N)
Si on considère des grands vecteurs, alors
Limn->inf T == 2 . N
Si on dispose du chaînage, le temps d'exécution sera seulement :
T = m + a + N
Si on considère des grands vecteurs, alors
Limn->inf T == N
En doublant virtuellement le nombre d'étages pipe-line on divise (asymptotiquement) le temps d'exécution par 2. Ceci permet de définir la performance de crête d'une machine Vectorielle comme le nombre de millions d'opérations flottantes exécutées par seconde (Mega FLOPS) lorsqu'elle fonctionne sur des profils MAC. On dit alors qu'elle est capable d'exécuter deux opérations flottantes par cycle et on obtient la formule :
Pcrête = 2. 103 / C
où C est le cycle de base de la machine (en nanosecondes). Par exemple, une machine qui a un temps de cycle de 10 ns aura une puissance de crête de 200 Mega FLOPS.
Dans le calcul de la puissance d'un calculateur Vectoriel, les constructeurs se placent souvent dans le cas d'un profil MAC asymptotique. Cette mesure est donc très favorable car elle suppose, pour être correcte, que l'application ne contient aucun traitement scalaire et que tous les traitements vectoriels sont des MACs ! Ainsi, la puissance annoncée par les constructeurs est la puissance de crête qui doit plutôt être comprise comme "une garantie de la puissance que ne dépassera pas la machine" ...
Si on travaille en mode pipe-line simple avec une unité d'addition en virgule flottante à 4 étages, on peut ramener le temps d'exécution de l'addition de deux vecteurs ayant n éléments de Ts = 4n (en mode séquentiel) à Tp = 3+n (en mode pipe-line) où 3 est le temps de Startup du pipe-line et où le temps est exprimé en cycles de base. Le gain de vitesse est donc :
G = 4n / (3+n)
Cette formule correspond à la courbe (a). On voit que le facteur d'accélération est de 4 (car on a supposé que l'unité de calcul est un pipe-line à 4 étages), mais cette performance n'est atteinte qu'asymptotiquement. En pratique, on voit que pour un vecteur de longueur 10 on a déjà un gain de 3 et que pour un vecteur de longueur 40 on atteint 93% de la performance théorique.
Remarque : on ne tient compte ici que du temps de startup intrinsèque au pipe-line. Il faudrait aussi tenir compte du temps de startup propre à la machine : ce temps peut aller de 10 à 20 cycles de base jusqu'à 100 à 200 cycles de base ; dans ces dernières machines, la performance théorique ne peut être approchée que pour de très grands vecteurs !
Supposons maintenant qu'on travaille avec une unité d'addition en virgule flottante à 4 étages, et une unité de multiplication en virgule flottante à 4 étages aussi. On peut donc enchaîner des profils MAC . Dans le cas de l'exécution d'un tel profil MAC, le temps d'exécution serait en mode séquentiel Ts = 8n et en mode pipe-line Tp = 6+2n. Le gain de vitesse est :
G = 8n / (6+2n) = 4n / (3+n)
Cette formule correspond encore à la courbe (a). C'est normal car il n'y a pas de chaînage.
Si maintenant, on utilise la technique du chaînage sur ce même profil MAC, alors le temps d'exécution devient Tc = 7+n. Le gain est cette fois ci :
G = 8n / (7+n)
Cette formule correspond à la courbe (b). Les opérations chaînées portant sur des profils MAC ont un gain théorique de 8. En pratique une application n'est pas composée uniquement de telles opérations. Son gain varie donc entre les courbes (a) et (b) selon le taux de MACs qu'elle contient.
Les vecteurs longs conduisent à de meilleures performances de l'utilisation du pipe-line. Cependant, pour alimenter ce pipe-line, il faut aller chercher les données en mémoire centrale et les placer dans les registres vectoriels qui font alors office de cache. Pour un profil MAC typique (a), si on suppose que les données sont déjà placées dans les registres vectoriels, alors on obtient la courbe théorique déjà vue (c).
Mais si les données ne sont pas déjà placées dans les registres vectoriels, alors il faut ajouter au temps de startup du pipe-line le temps de chargement des registres vectoriels concernés à partir de la mémoire centrale ; dans les machines vectorielles, cette opération est généralement optimisée grâce à des mécanismes matériels spécifiques : mode de chargement en "burst" (c'est-à-dire par blocs). Il n'en demeure pas moins que le chargement des registres vectoriels augmente le temps de startup.
De plus, les registres vectoriels ont une petite taille : 32, 64, 256 mots... Dans beaucoup de cas, les vecteurs à traiter sont plus longs que les registres vectoriels. Cela impose un travail supplémentaire au compilateur qui doit saucissonner les boucles (b). Il utilise comme paramètre la taille des registres vectoriels R (fixée par le hardware) et la taille N du vecteur à traiter (fixée par l'application). Une fois ce travail effectué, seule la boucle centrale de (b) est vectorisable ; la boucle externe correspond à relancer N/R fois le pipe-line ce qui génère N/R startups. Les performances sont diminuées comme le montre la courbe (d) où on a supposé qu'on utilise des Registres de taille R = 64.
Lorsqu'on exécute une application sur une machine Vectorielle, il n'est généralement pas possible de vectoriser l'ensemble de cette application. Souvent, une bonne partie de l'application concerne des opérations scalaires : ce sont des opérations qui portent sur des variables simples (de type flottant aussi). Bien sûr, il serait possible en théorie d'exécuter ces opérations sur l'unité vectorielle, mais cela conduirait à une perte d'efficacité considérable : le temps de startup étant alors beaucoup plus long que l'opération elle-même ! C'est pour cette raison que les machines vectorielles possèdent toutes à côté de l'unité de calcul Vectorielle une autre unité de calcul Scalaire.
Lorsque l'unité Scalaire exécute une partie scalaire d'un programme, elle développe une puissance exprimée aussi en Mega FLOPS ; elle est bien plus faible que la puissance de l'unité Vectorielle. Pour le programmeur, ce qui compte c'est le temps que va mettre réellement la machine pour exécuter le programme dans son entier : son temps d'exécution est égal à la somme des Mega FLOPS exécutés en mode Scalaire et des Mega FLOPS exécutés en mode Vectoriel. On obtient ainsi une autre unité de mesure : la puissance nominale (sustained) qui dépend de l'application est qui est souvent beaucoup plus faible que la puissance de crête (peak) annoncée par le constructeur.
Une application est dite vectorisable si une certaine partie du code de l'application peut être transformé en instructions vectorielles simples (opération unique sur un vecteur) ou chaînées. On définit alors le pourcentage de vectorisation comme le pourcentage de code scalaire qui est transformable en code vectoriel. Par exemple, considérons un programme qui s'exécute en 100 secondes sur un ordinateur séquentiel (scalaire).
Vectorisons ce programme et passons le sur une machine vectorielle dont l'unité scalaire a la même performance que celle de l'ordinateur séquentiel : si le temps d'exécution de la partie du programme qui continue à être exécutée sur l'unité scalaire (que nous n'avons pas pu vectoriser) est de 20 secondes, alors on dira que le pourcentage de vectorisation de cette application est de 80%. A partir des définitions suivantes :
T le temps d'exécution du programme avant vectorisation t le temps d'exécution du programme après vectorisation P le pourcentage de code vectorisé n le rapport de vitesse Unité Vectorielle/ Vitesse Scalaire
On peut écrire :
T = T (1-P) + P.Tt = T (1-P) + P. T/n
où T(1-p) est la partie scalaire du traitement et T/n la partie vectorielle. Le gain de vitesse est alors :
G = T / t = n / (n. (1-P) + P)
La courbe correspondant à cette formule (a) amène à remarquer :
L'architecture du Cray-1 est celle d'une machine Vectorielle pure. Il contient un processeur d'instructions qui décode et séquence les instructions ; il dispose pour cela de 12 unités fonctionnelles indépendantes : 6 sont utilisées pour les instructions scalaires et les calculs d'adresses, 3 sont utilisées uniquement pour les opérations vectorielles entières et logiques, enfin 3 sont utilisées pour les opérations vectorielles flottantes. Le nombre d'étages pipe-line dans les unités varie de 2 à 14. Le temps de cycle de chaque étage est de 12.5 ns. Le startup est seulement de 3 cycles (opérations vectorielles de registre à registre).
Le port mémoire unique du Cray-1 est un goulet d'étranglement important pour des instructions aussi simples que (a). Il faut lire le vecteur A puis B puis faire l'opération puis écrire le vecteur C. Dans le Cray X-MP, il est possible d'effectuer ces opérations en parallèle sur des ports mémoire différents.
Le chaînage du Cray-1 est fragile à mettre en oeuvre. Par exemple pour (a), après que le vecteur A a été lu, on peut enchaîner l'addition avec la lecture de B par chaînage (b) à la condition que l'opération d'addition arrive avant un certain temps qui est fixe. Pour exploiter le phénomène de chaînage, le compilateur (et l'utilisateur aussi !) doit s'assurer que l'addition interviendra bien au bon moment : d'autres actions qui pourraient être insérées par le programmeur ou par le compilateur pour ses propres besoins feraient dérailler le chaînage. Sur le Cray X-MP les ports mémoire sont asynchrones et autorisent un chaînage dynamique.
Dans beaucoup de programmes numériques on trouve des indirections dans les tableaux : en lecture c'est le Gather :
For i := 1 to N do C[i] := A[X[i]] + B[i]
en écriture c'est le scatter :
For i := 1 to N do C[X[i]] := A[i] + B[i]
Le Cray-1 n'a pas de mécanismes matériels pour gérer ces cas et les traite en mode scalaire alors que le Cray X-MP permet de les vectoriser.
Le Cray-1 bloque tout accès à la mémoire quand un défaut apparaît dans le cache adresses ou données.
Le registres scalaires du Cray-1 sont décomposés en registres d'adresses et registres de données. La banalisation dans le Cray X-MP des registres scalaires simplifie le compilateur et évite certaines impossibilités d'utiliser les ressources.
On a ajouté la possibilité d'effectuer des écritures de vecteurs masquées où on précise les éléments qui sont modifiés, ainsi que des opérateurs binaires spéciaux pour accélérer les Transformées de Fourier ...
La première machine de Seymour Cray fut le Cray-1 qui a vu le jour en 1976 : il s'agit d'une machine de traitement vectoriel pipe-line qui utilise une technologie de pointe. Cependant, sur le plan de l'architecture il s'agit d'une machine SISD à mémoire unique et à processeur unique. La deuxième génération des machines de Seymour Cray est le Cray X-MP (à l'architecture duquel il n'a pas participé directement). Le Cray X-MP possède une mémoire centrale multi-bancs et il s'agit d'un vrai Multiprocesseur. Par ailleurs, le processeur de base du Cray X-MP est une version très améliorée du mono-processeur du Cray-1 : on tire mieux profit des multiples accès mémoire, on augmente les possibilités de chaînage etc. Comme le Cray 1, le Cray X-MP travaille sur des mots de 64 bits mais il comporte en plus de nouveaux opérateurs qui accélèrent les traitement de certaines application numériques et statistiques.
Le Cray X-MP est une machine multiprocesseurs de type M SIMD composée de 1 à 4 processeurs et de 16 à 64 bancs mémoire selon les versions ; c'est en fait un multi Cray-1. La machine se comporte comme un dorsal d'un gros système IBM 3090. Elle dispose aussi de canaux d'entrée/sortie très performants, en particulier avec un RAM disque (RAM statique singeant le fonctionnement d'un disque) qui permet de faire des acquisitions de données rapides.
Le Cray X-MP ne possède pas à proprement parlé de caches, mais les registres vectoriels font office d'accélérateurs des accès mémoire : ici, on compte sur le compilateur pour détecter quelles sont les variables qui peuvent être chargées en mode "burst" dans les registres vectoriels.
La synchronisation entre les tâches est réalisée au plan matériel par un bloc de registres partagés par les quatre processeurs. La gestion de la synchronisation est laissée à la charge du programmeur. Il faut remarquer que le petit nombre de processeurs impose un grain de parallélisme macroscopique fondé sur le concept de tâche. Dans ce cas, le nombre de variables partagées est faible et les problèmes de synchronisation restent discrets.
Ce qui fait la spécificité des machines de Seymour Cray, en dehors de l'architecture vectorielle pipe-line, c'est l'effort constant qui a été porté sur la technologie. Ces machines sont toujours restées peu intégrées pour pouvoir profiter des technologies les plus rapides : ECL, bientôt AsGa ... Ces technologies ont tendance à consommer de l'énergie et donc à dissiper énormément de chaleur ; cela impose le recours à des technologies de refroidissement sophistiquées et coûteuses. Le résultat de ces efforts est que le cycle de base a toujours été très faible : de 12 ns dès 1976 à 1 ns en 1990 ! La puissance exprimée en Mega FLOPS est en rapport.
|
Cray 1 |
Cray X-MP |
Cray 2 |
Cray 3 |
|
|
Année |
1976 |
1983 |
1985 |
1990 ? |
|
Intégration |
SSI |
MSI |
MSI |
MSI |
|
Technologie |
ECL |
ECL |
ECL Packaging 3D |
AsGa |
|
Vitesse techno. |
12,5 ns |
9,5 ns |
4,1 ns |
1 ns |
|
Nombre de processeurs |
1 |
1, 2 ou 4 |
4 Background 1 Foreground |
16 |
|
Gamme de vitesse (MegaFLOPS) |
30 - 60 |
60 - 700 |
120 - 2000 |
16 000 |
|
Mémoire maximale (Méga mots 64 bits) |
1M |
16M |
256 M + 16 k mémoire locale / processeur |
2000 M |
|
Operating système |
COS |
COS |
Unix système V |
Unix |
|
Refroidissement |
Liquide réfrigérant |
Liquide réfrigérant |
en immersion liquide |
? |
Le Cray 2 a été introduit en 1985 et produit en très peu d'exemplaires. Il a une puissance de 5 à 10 fois supérieure à celle du "vieux" Cray-1. La mémoire centrale peut atteindre 256 Méga mots de 64 bits et le cycle machine est de 4 ns seulement ! L'architecture multiprocesseur du Cray 2 est très semblable à celle du Cray X-MP : quatre processeurs de structure proche de celle de ceux du Cray X-MP peuvent travailler de manière séparée (mode multi- utilisateurs) ou bien sur une même application parallèle (mode multi-tâches). L'architecture système de la machine est améliorée avec des systèmes d'interface séparés.
Les machines Vectorielles sont proposées sous deux formes : d'un côté on trouve des Coprocesseurs vectoriels (comme le FPS-164 ou l'IBM 3838) qui se placent en périphérique d'un ordinateur classique. De l'autre côté on trouve des machines où l'unité de calcul vectorielle est intégrée (comme les Crays ou les Cyber de CDC). L'IBM Vector Facility (VF) est un mélange des deux : Il est intégré, car le jeu d'instructions vectorielles est ajouté au jeu d'instructions de l'IBM S/370 ; il est séparé, car il est implémenté sur une carte séparée qui d'ailleurs est optionnelle.
La solution proposée par IBM s'appuie donc sur une technologie scalaire déjà existante et très performante. IBM pense que l'influence du mode Scalaire sur la performance globale est déterminante et qu'en pratique les applications ont un pourcentage de vectorisation assez faible (entre 30% et 60%).
En travaillant dans la Zone utile (c), IBM propose une unité Vectorielle 3 à 5 fois plus puissante que l'unité Scalaire qui permet des gains de performances moyens compris entre 1,5 et 3.
L'architecture générale de l'IBM 3090-VF (a) permet d'avoir 1, 2 ou 4 Processeurs Centraux (ces processeurs peuvent fonctionner en mode MIMD comme un Multiprocesseur à Mémoire Partagée classique). Chaque processeur (b) comprend une mémoire cache de 64 k octets, une unité d'exécution des instructions qui commande une Unité Scalaire très performante (cycle de base 18.5 ns) et une Unité Vectorielle.
L'unité vectorielle possède deux unités fonctionnelles : une pour la multiplication, une autre pour l'arithmétique et la logique ; le profil MAC est possible. Les registres vectoriels peuvent contenir 128 éléments. En mode 32 bits flottant, on dispose de 16 registres vectoriels ; en mode 64 bits flottant, le nombre de registres vectoriels est réduit à 8.
Le Cyber 205 est une machine Vectorielle qui a été proposée par la firme Control Data Corp. en même temps que le Cray-1S. Il est intéressant car il a la particularité de ne pas posséder de registres vectoriels. Ce manque est compensé par une organisation mémoire particulièrement sophistiquée qui offre une bande passante très large : 10 fois celle du Cray-1.
L'Unité Vectorielle est proposée avec une, deux, ou quatre unités fonctionnelles capables d'effectuer des opérations arithmétiques et logiques ainsi que du calcul flottant. Elles sont pipe-linées et ont un temps de cycle de 20 ns. Avec 4 unités pipe-lines, le Cyber offre une puissance de 400 Mega FLOPS environ (avec notre définition de la puissance de crête).
Une unité spéciale de gestion du Flux Vectoriel distribue les données aux unités fonctionnelles de manière cyclique. La conséquence est que le temps de startup est très long, mais il n'y a pas d'effets de tronçonnage dûs à la présence des registres vectoriels. Pour pouvoir exploiter efficacement une telle architecture, il faut donc lui donner à manger des vecteurs très longs (plusieurs centaines d'éléments).
Pour offrir la largeur de bande nécessaire, la mémoire est découpée en bancs : 16 bancs par Mégamot (de 32 bits). Les bancs peuvent être lus en parallèle, ce qui donne un débit de 64 octets par cycle de base. De plus, chaque banc mémoire est entrelacé en 8 blocs. Il faut 4 cycles de base (20ns) pour exécuter un accès mémoire et une instruction d'accès mémoire peut être lancée à chaque cycle ; on obtient ainsi une accélération supplémentaire du flux.
La société Weitek s'est spécialisée dans les composants VLSI à très hautes performances. Elle propose des chips Cmos comportant des unités pipe-linées de calcul flottant 32 bits (simple précision).
Le XL 3132 est un chip ayant la même architecture interne que le WTL 3132, mais ils est conçu spécialement pour être associé à deux autres chips : le XL 8136 PSU (Program Sequencing Unit) qui gère les instructions ; le XL 8137 IPU (Integer Processing Unit) qui traite l'arithmétique entière. Ensembles, ces trois chips permettent de construire une architecture complète de processeur général (c). Elle est de type harvard (à mémoires de programme et de données séparées) pour améliorer le débit d'alimentation du FPU et de l'IPU.
La famille Weitek offre une gamme étendue de composants flottants pipe-linés spécialisés dans la cons- truction d'architectures vectorielles.
Le chemin des données du Weitek WTL 3132 (a) est conçu pour exécuter en mode pipe-line des opération flottantes 32 bits sur des données provenant soit du port d'entrée X, soit d'un des 32 registres généraux. Chaque registre général peut contenir un nombre flottant IEEE en simple précision ou un entier en complément à deux. La mémoire de registres a 4 ports : cela veut dire qu'on peut effectuer 4 opérations de lecture ou d'écriture (selon les ports) à chaque cycle de base. En particulier, il est possible de charger et de lire des données dans la mémoire de registres en même temps que le WTL calcule. La mémoire de registres à 4 ports permet d'effectuer des instructions à trois adresses de registres : Ra := Rb + Rc. Il est possible d'effectuer une addition seulement (en trois cycles de base) une multiplication seulement (en trois cycles de base aussi) ou bien une multiplication chaînée avec une addition.
En cas d'opération chaînée, il faut 6 cycles pour avoir le résultat, mais une fois le pipe-line amorcé, le WTL peut produire un résultat à chaque cycle. Le WTL est capable de fonctionner en mode MAC, c'est-à-dire une multiplication et une addition chaînées suivies d'une accumulation : Rx := Rx + (Ry*Rz). On se sert alors d'un registre temporaire pour ré-injecter la valeur calculée (Rx) dans le pipe-line (en même temps qu'elle est mémorisée dans un registre général). La gestion du timing MAC (b) est très délicate : elle doit être faite par un compilateur sophistiqué.
Le microprocesseur Intel i860™ est un Supercalculateur complet dans un seul VLSI de 168 broches, comportant 1 000 000 de transistors, réalisé en technologie Cmos 1 m. Il a un chemin de données interne de 64 bits (avec aussi des bus 128 et 32 bits). Il traite l'arithmétique entière, l'arithmétique flottante et possède des opérations spéciales pour le traitement graphique. La fréquence maximale de l'horloge est 40 Mhz soit un temps de cycle de base de 25ns, ce qui lui permet de produire 80 Mega FLOPS de crête en simple précision. Le i860 est organisé en 9 unités fonctionnelles :
Le microprocesseur Intel i860 fait partie de la classe des machines Superscalaires. Il s'agit de processeurs qui combinent une unité scalaire puissante (généralement un noyau RISC pipe-liné) et une unité de calcul flottant (FPU pour Floating Point Unit) capable de fonctionner en parallèle avec l'unité scalaire de manière analogue au VLIW. A chaque cycle de base (25 ns dans le cas du i860) une double instruction de 64 bits est exécutée : la demi-instruction scalaire de 32 bits par le noyau RISC et la demi instruction flottante de 32 bits par le FPU. Bien que cela ne soit pas facile à gérer (il faut recourir à un compilateur sophistiqué), dans les applications nécessitant beaucoup de calcul flottant, le temps d'exécution scalaire peut être "fait à côté" sans perturber le pipe-line vectoriel.
Le FPU du i860 a une structure proche de celle du Weitek. Il comporte une unité de multiplication (à 3-4 étages pipe-line) et une unité d'addition (à 3 étages pipe-line). En régime, l'additionneur produit une addition flottante 32 ou 64 bits par cycle et le multiplieur produit une multiplication flottante 32 bits par cycle ou 64 bits chaque deux cycles. L'additionneur et le multiplieur peuvent fonctionner séparément (un résultat par cycle) en parallèle (deux résultats par cycle ) ou en mode chaîné pour obtenir un profil MAC (un MAC par cycle).
Source : K. Hwang "Advanced parallel processing with Supercomputer Architectures" Proceedings IEEE oct 1987.
Notations :
mP : Multiprocesseurs
mC : MultiCalculateurs (Passage de Messages)
1P : monoprocesseur
1S : 1 processeur Scalaire
nUV : n processeurs Vectoriels
MC : Mémoire centralisée
MD : Mémoire distribuée
PàP : liaisons Point-à-Point
R... : Réseau en ...
hyper : réseau en Hypercube
switch : réseau multi-étages
[SIMD] : fonctionnement en mode SIMD
E/S : Processeur d'entrées/sorties
Weit. : VLSI Weitek
Custom : conçu par le constructeur
TCM : Thermal Conduction Module
Mo : Méga octet
Mips : Million d'Instructions par seconde
[ii]* : performance réellement mesurée par J.J Dongarra sur un
système d'équations Linéaires d'ordre 100 avec LINPACK