Architectures des systèmes informatiques
CHAPITRE 10
Parallélisme, taxinomies et classifications
Année 2002-2003
Suite
N°1...
10.3 QUELQUES FAITS ET QUELQUES DATES
Avertissement :
Nous n'avons pas beaucoup de recul sur ce sujet, encore moins que sur l'informatique en général. L'histoire événementielle touffue est connue; l'histoire des idées et de leurs imbrications n'est pas toujours claire. L'auditeur qui connaîtrait un document de qualité sur le sujet est invité à me le faire connaître.
Ce paragraphe contient une liste de faits. Ils ont été choisis parmi de très nombreux autres, on n'y trouvera donc pas TOUT sur les machines parallèles. Nombre des citations sont dues à Gregory V. Wilson de l'université de Toronto : gvw@cs.toronto.edu
Le modèle théorique des machines parallèles est ici aussi la machine de Turing. Il a été démontré que les machines de Turing peuvent être assemblées en série et en parallèle.
Dans les années 1940 et 1950, un ordinateur série très simple était encore très cher, une machine parallèle n'était pas envisageable.
Une des toutes premières machines parallèles est le Gamma 60 de la Compagnie de machines Bull livré en 1959. Il contient plusieurs unités fonctionnelles et les primitives fork et join, 19 exemplaires seulement sont fabriqués. La société sortira exsangue de cette opération, l'argent avait manqué pour écrire un système d'exploitation.
La même année, John Cocke et Daniel Slotnick de chez IBM, écrivent un document important sous la forme d'un mémorandum. Il porte sur le parallélisme dans le calcul numérique. D. Slotnick sera plus tard le concepteur de la machine SOLOMON, de type SIMD contenant 1024 processeurs élémentaires disposant chacun de 128 mots de 32 bits et travaillant sur un bit. Cette machine n'a pas été fabriquée, mais ces idées ont eu une grande influence.
1962 est une grande année.
En recherche, C.A. Petri publie
ses réseaux, outils de description des systèmes concurrents.
En production, l'Atlas
de Ferranti est opérationnel. Il contient la pagination, la mémoire
virtuelle et en parallélisme implicite le pipeline et des unités
fonctionnelles distinctes pour les calculs en virgule fixe et en virgule
flottante.
Le D825 produit par Burroughs
est un MIMD symétrique. Une à
quatre unités centrales accèdent à un à seize
modules de mémoire par un tableau d'interconnexion. L'unité
centrale est celle du B5000; le système d'exploitation est symétrique
à base de files d'attente.
En 1964,
commence la concurrence entre
machine parallèle et super ordinateur. Dans la suite, de nombreux
projets seront arrêtés ou réduits.
En 1966,
Arthur Bernstein publie la condition
d'indépendance entre données qui portera son nom.
UNIVAC devenu une division de
Sperry Rand corporation, livre les UNIVAC 1108. Chacun contient
une à trois unités centrales et deux contrôleurs d'entrées
et sorties. Il est géré par un système d'exploitation
original EXEC8.
Michael Flynn publie sa taxinomie.
En 1967,
Gene Amdahl et Daniel Slotnick
discutent publiquement sur la faisabilité du traitement simultané
dans la conférence AFIPS. Les arguments d'Amdahl sur les limites
du parallélisme seront connus sous le nom de première
loi d'Amdahl. La deuxième loi d'Amdahl
déjà mentionnée est une règle empirique.
En 1968,
Edsger Dijkstra décrit
les sémaphores et le problème connu sous la dénomination
de «dîner des philosophes».
En 1969,
le CDC 7600 remplace
le CDC 6600.
Compass commence un compilateur
Fortran parallèle pour ILLIAC IV. Cette société
fera sa spécialité de la compilation des langages por le
parallélisme.
Le système Multics
gère un multiprocesseur symétrique à 8 processeurs.
En 1970,
l'université Carnegie-Mellon
commence les travaux sur le multiprocesseur C.mmp avec le soutien de DEC.
En 1971,
Texas Instruments produit l'Advanced
scientific computer, une retombée d'Illiac IV. Il contient quatre
pipelines. Les instructions vectorielles opèrent de mémoire
à mémoire. Sa mémoire est plus sûre par un code
qui détecte deux erreurs et en corrige une (SECDED ou single error
correction, double error detection). Ce code détecteur et correcteur
sera utilisé pour la mémoire des Cray et dans certains réseaux
de disques RAID.
En 1972,
plusieurs travaux importants
sont publiés.
Une étude du parallélisme
massif par bit, par Reddaway d'ICL. Elle aboutira à la machine DAP
pour «distributed array processor» mise en chantier en 1974.
En 1995, sa quatrième version est en service.
Harold Stone décrit un
schéma de réseau d'interconnexion à plusieurs niveaux,
«perfect shuffle network». Il sera largement utilisé
dans les machines à messages.
Tony Hoare et Per Brinch Hansen
publient indépendamment leurs travaux sur les sections critiques
conditionnelles.
Bolt Beranek Newman (BBN) construit
les machines Pluribus pour servir de nœuds au réseau ARPA (précurseur
d'internet). La même entreprise utilisera à nouveau cette
technique dans les multiprocesseurs papillons (butterfly machines).
Goodyear fabrique STARAN,
un réseau de 4x256 processeurs à 1 bit qui utilise l'accès
associatif et un réseau FLIP.
Burroughs commence la production
de PEPE (Parallel element processor ensemble) qui contient 8x36
processeurs et un accès associatif. Le premier sera livré
en 1976.
En 1973,
Shore
publie sa classification.
En 1974,
Jack Dennis et David Misunas
du MIT publient la première description d'un ordinateur à
flot de données.
Leslie Lamport publie «Parallel
execution of do-loops», fondement théorique de nombreux
travaux sur la vectorisation automatique et la parallélisation en
mémoire partagée.
Tony Hoare décrit le
moniteur, mécanisme d'exclusion mutuelle structuré qui sera
utilisé dans de nombreux langages de programmation.
En 1975,
Duncan Lawrie décrit
le réseau d'interconnexion Oméga, à plusieurs étages.
On le trouvera dans plusieurs machines parallèles.
Les travaux sur C.mmp
de 1970 sont prolongés par le multiprocesseur Cm* à
l'université Carnegie-Mellon, toujours avec DEC. Cette machine est
un assemblage de PDP11 reliés par des bus hiérarchisés.
Edsger Dijkstra décrit
les commandes gardées, un mécanisme pour structurer la concurrence,
on les trouvera dans de nombreux langages.
Intel commence la définition
de l'iAPX 432 multiprocesseur symétrique.
En
1976,
les machines parallèles
sont de plus en plus nombreuses.
Floating point systems produit
son premier calculateur vectoriel AP-120B à mots de 38 bits.
Il traite plusieurs instructions par cycle par pipeline superscalaire.
Cray Research produit le CRAY-1.Tandem
produit sa première machine insensible aux pannes ou machine non
stop. Elle est constituée de mémoires indépendantes,
de 2 à 16 processeurs; elle fonctionne par messages sur un jeu de
bus inter processeurs doublé.Control
Data produit le Flexible processor, processeur programmable pour
le traitement du signal à mots de 48 bits.
Fujitsu livre sa première
machine vectorielle FACOM 230.
Utpal Banerjee formalise la
notion de dépendance entre données et propose l'algorithme
qui porte son nom dans sa thèse à l'université de
l'Illinois,.
En 1977,
une machine pyramidale de 5
à 21 processeurs, due à Haendler, Hofmann et Schneider, est
construite à l'université d'Erlangen en Allemagne sous le
nom de Erlangen general purpose architecture.
Le C.mmp est achevé
avec 16 PDP-11 interconnectés avec mémoires partagées.
Le projet Massively parallel
processor pour le traitement d'images est mis en chantier par Goodyear
et la NASA.
Handler
publie sa classification.
En 1978,
Tony Hoare publie le modèle
dit «communicating sequential processes» (CSP). Il mêle
la communication synchrone point à point et les commandes gardées.
Il sera à la base de plusieurs langages de programmation parallèle.
Le premier multiprocesseur (32)
à flots de données est construit au CERT à Toulouse.
En 1979,
ICL livre le premier DAP.
Inmos commence la définition
du Transputeur.
Le PAX-9, un MIMD à
9 processeurs M68000 est construit à l'université de Tokyo.
En 1980,
le premier PS-2000 est
mis en service en URSS. Il contient 64 processeurs à 24 bits. Il
est donné pour 200 MIPS.
DEC construit le KL10
à trois processeurs symétriques.
En 1981,
Floating Point Systems livre
le FPS-164 processeur réseau.
Control Data livre le super
ordinateur vectoriel Cyber 205.
DEC produit le premier biprocesseur
asymétrique VAX 11/782.
Le Caltech lance un projet d'hypercube.
Bolt Beranek Newman fabrique
le multiprocesseur papillon à base de Motorola 68000.
Intel abandonne le multiprocesseur
iAPX 432.
En 1982,Lancement
tonitruant du projet Superspeed, plus connu sous le nom de «cinquième
génération» par le ministère de l'industrie
(MITI) japonais. On en verra un aboutissement très modeste en 1990.Production
du
X-MP chez Cray, il contient deux processeurs à pipeline.
Hitachi produit le superordinateur
vectoriel S-810 donné pour 800 MFLOPS.
Construction des PAX-32
et
PAX-128 à l'université de Kyoto; ils contiennent
32 et 128 processeurs Motorola 68000.
Control Data transforme le Flexible
processor en Advanced flexible processor, le mot d'instruction a
210 bits; c'est la première forme de VLIW.
Pacific-Sierra Research (PSR)
écrit l'outil VAST pour traduire les boucles DO en processus parallèles.
En 1983,
le manuel de référence
d'Ada est publié. On y trouve la communication et la synchronisation
par rendez vous.
NEC produit un superordinateur
vectoriel
SX-1.
Le système VMS de DEC
gère des grappes des VAX en couplage faible.
Création de Thinking
Machines Corporation pour construire des machines massivement parallèles
pour l'intelligence artificielle, ce seront les CM-X, «connection
machines» numéro X.
Le langage SISAL (Streams and
Iterations in a Single-Assignment Language) issu des langages à
flots de données est publié.
Le premier réseau annulaire
en fibres optiques est du à Tandem.
Goodyear Aerospace fournit le
MPP pour «massively parallel processor» à la
NASA. Il contient 16K processeurs en grille de 128x128, chacun a 1024 bits
de mémoire.
En 1984,
la famille des CRAY X-MP
est étendue à des machines à quatre processeurs.
Sequent livre la machine Balance,
multiprocesseur symétrique à base de microprocesseurs NS32016.
Mitsui Shipbuilding Company
construit un multiordinateur à topologie torique, le PAX-64J.
Le CRAY X-MP monoprocesseur
atteint 21 MFLOPS au banc Linpack.
Multiflow est créé
pour produire des machines VLIW, il fermera en 1990.
En 1985,
Inmos commence la production
des Transputeurs T414. En 1993, David May avait publié la
première description de leur langage Occam fondé sur le modèle
CSP de T. Hoare.
Cray Research produit le CRAY-2,
avec quatre processeurs de fond et un processeur frontal, la période
d'horloge est de 4,1ns, il a 256 Mmots de mémoire. Le refroidissement
est fait par circulation de fluorocarbone.
Les ordinateurs vectoriels VP-400
de Fujitsu, FX/8 de Valiant,
SX-2 de Nec crédité
de 885 MFLOPS et de 1300 MFLOPS crête, et IBM 3090 sont sur
le marché.ICL
produit le MiniDAP à 1024 processeurs comme co-processeur.
nCUBE lance le nCUBE/10
hypercube qui utilise des processeurs de type VAX.
En 1986,
Nouvelles machines ou machines
modifiées.Loral
Instrumentation livre une machine à flots de données LDF-100,
il n'y en aura que deux autres.
Scientific Computer Systems
produit le SCS-40, supermini compatible avec les Cray, arrêt
en 1989.
Thinking Machines livre la première
Connection machine CM-1. Elle a au plus 65536 processeurs à
1 bit en hypercube.
Floating Point Systems produit
les hypercubes nommés série T, à base de transputeurs
et de coprocesseurs de Weitek.
General Electric construit un
prototype de machine systolique à dix processeurs à 1 bit
appelé
Warp.
Nouvelles idées
et réalisations.
Une publication de Gul Agha,
de l'université d'Illinois, décrit une nouvelle forme du
modèle acteur à la base de nombreux travaux sur les machines
à grain fin et leurs logiciels.
Le système de programmation
CrOS III, le gestionnaire de fichiers Cubix et le gestionnaire graphique
Plotix sont écrits pour les hypercubes du Caltech. Il seront largement
réutilisés pour la programmation des systèmes à
messages ultérieurs.
En 1987,
Nouvelles machines ou machines
modifiées.
ETA (filiale de CDC) produit
les
ETA-10 refroidis à l'azote liquide. Un seul processeur
atteint 52 MFLOPS selon un Linpack 100x100, cette filiale sera fermée
en 1989.
Sequent produit la machine Symmetry
à base de 80386 communiquant par bus.
L'hypercube Mark III
du Caltech à base Motorola 68020 est achevé.
La CM-2 Connection machine
de Thinking Machines Corporation contient 65536 processeurs à 1
bit.
Parsytec livre le SuperCluster
à base de Transputeurs.
Cydrome produit le Cydra
5 qui contient un processeur VLIW à mot d'instruction de 256
bits. La société disparaît en 1988.
Le Trace/200 de Multiflow
est un VLIW à instructions de longueurs variables de 256 à
1024 bits.
Nouvelles idées et
réalisations.
Piyush Mehrotra et John Van
Rosendale décrivent BLAZE, un langage pour programmer les systèmes
à mémoire partagée.
Une version commerciale de CrOS
est disponible.
En 1988,
Nouvelles machines ou machines
modifiées.
Le Laboratoire d'électrotechnique
du Japon construit Sigma-1 à 128 processeurs et 100 MFLOPS.Convex
construit
C2, mini superordinateur qui contient des réseaux
de portes en AsGa.
Cray livre le premier multiprocesseur
vectoriel Y-MP, 74 MFLOPS pour un processeur, 2,1 GFLOPS pour 8.
Intel définit les hypercubes
iPSC/2 à base de 80386-80387.
Silicon Graphics produit la
série
Power, stations de travail multiprocesseurs à
base de R2000 connectés par bus, au plus 8 Mips.Inmos
produit les transputeurs T800 à virgule flottante.
Les universités de Bologne,
Padoue, Pise et Rome et le CERN achèvent la machine QCD à
300 MFLOPS moyens et 1 GFLOPS en crête.
Nouvelles idées
et réalisations.
Strand est un nouveau langage
de programmation parallèle de type logique. La programmation en
logique est surtout connue par le langage Prolog d'Alain Colmerauer. Strand
software technologies commercialise Strand88.
Description de Superb par Hans
Zima, Heinz Bast et Hans Michael Gerndt, c'est le premier système
de parallélisation automatique pour des ordinateurs à mémoires
disjointes.
Description de Kali par Piyush
Mehrotra et John Van Rosendale, il sera en partie repris dans le Fortran
de Vienne et le langage HPF.
Description de Dino par Rosing
et Schnabel, c'est une extension de C pour les machines à mémoire
distribuée.
Création du groupe de
travail Scalable coherent interface (SCI) pour définir une norme
de réseau d'interconnexion.
En 1989,
Nouvelles machines ou machines
modifiées.
Fujitsu commence la production
du
VP-2000 superordinateur vectoriel.
Evans et Sutherland, constructeurs
de systèmes graphiques annoncent la machine parallèle ES-1.
Deux exemplaires sont fabriqués avant fermeture.
Meiko introduit des SPARC et
des Intel i860 dans ses machines Computing surface, en plus des
transputeurs T800.
Bolt Beranek Newman produit
le TC2000 machine papillon avec des Motorola 88000.
Multiflow lance le Trace/300,
machine VLIW, l'entreprise disparaît l'année suivante.
Le CRAY Y-MP à
8 processeurs atteint 275 MFLOPS en Linpack 100x100 et 2,1 GFLOPS en Linpack
1000x1000.
Supertek Computers produit le
S-1 supermini compatible avec les Cray, en 10 exemplaires.
nCUBE produit sa deuxième
génération nCUBE/2 toujours avec des processeurs du
commerce.
Nouvelles idées et
réalisations.
Un prototype de SUPERB décrit
en 1988 est achevé comme partie du projet allemand SUPREMUM.
Seymour Cray quitte Cray Research
et fonde Cray Computer Corporation.
National Aerospace Laboratory
commence l'étude de faisabilité d'une soufflerie numérique
avec Fujitsu, Hitachi et NEC.
En 1990,
Nouvelles machines ou machines
modifiées.
Cray Research achète
Supertek Computers Inc. fabricant de superminiordinateurs compatibles avec
le X-MP.
NEC livre le SX-3, superordinateur
vectoriel. Chaque machine a jusqu'à quatre processeurs avec 4 jeux
de pipelines, la période de l'horloge est 2,9 ns.
Intel commence la production
du
iPSC/860, hypercube à base de i860.
DEC livre le VAX 9000,
processeur à mémoire partagée sous VMS.
Le premier MasPar MP-1
est livré, chacun contient jusqu'à 16k processeurs à
4 bits.
Intel met en démonstration
le réseau systolique iWarp issu du Warp de General Electric (1986)
utilisant des processeurs du commerce.
Fujitsu livre le VP-2600
dont un processeur atteint 2,9 GFLOPS sur un Linpack 1000x1000.
Fujitsu, Hitachi et NEC assemblent
un superordinateur vectoriel qui utilise 4 VP-2600, la mémoire partagée
de NEC et le logiciel d'Hitachi. C'est l'aboutissement très modeste
de la très médiatisée cinquième génération
annoncée en 1982.
Alliant livre les FX/2800
à base de i860.
Wavetracer construit le premier
réseau à trois dimensions DTC (Data Transport Computer)
constitué de 1 à 4 jeux de 16x16x16 processeurs à
1 bit.
Fujitsu commence la production
de l'AP1000 qui contient 64 à 512 processeurs Sparc connectés
en réseau torique point à point avec un arbre de diffusion
et un bus de synchronisation.
Les deux derniers ETA-10
de 1987 n'ont pas eu d'acheteurs, ils sont détruits à la
masse.
Nouvelles idées et
réalisations.
Charles Koelbel décrit
une méthode de génération de code pour transmission
par messages dans des programmes écrits en Kali.
Le prix Gordon Bell dans la
catégorie prix/performance est attribué à Geist, Stocks,
Ginatempo et Shelton qui ont atteint 800 MFLOPS par million de dollars
avec 128 nœuds d'Intel iPSC/860.
Le prix Gordon Bell dans la
catégorie compilateurs parallèles est attribué à
Sabot, Tennies et Vasilevsky pour avoir atteint 1,5 GFLOPS sur une machine
CM-2 dans un code Fortran 90 dérivé du Fortran 77.
Le projet Parallel virtual machine
(PVM) est lancé pour développer le logiciel nécessaire
aux ordinateurs distribués hétérogènes.
La suite relève de l'histoire contemporaine.
Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 10
Parallélisme, taxinomies et classifications
Année 2002-2003