Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
On lit avec un ordinateur, une tablette ou son smartphone (streaming)
En savoir plus
ou
Achetez pour : 49,00 €

Lecture en ligne + Téléchargement

Format(s) : PDF

sans DRM

Partagez cette publication

Traité des Nouvelles Technologies
série Informatique
Informatique
parallèle
et systèmes
multiprocesseurs
Jean-Louis Jacquemin
m m u s Informatique parallèle
et
systèmes multiprocesseurs Collection dirigée par Michael Griffiths et Pierre Rolin
Titres parus
Michae l GRIFFITHS et Michel VAYSSADE, Architecture des systèmes
Ed'exploitation, 1990 (2 édition).
Habib ABDULRAB, de Common Lisp à la programmation objet, 1990.
Robert OGOR et Robert RANNOU, langage ADA et algorithmique, 1990 et 1993
Epour la 2 édition revue et corrigée.
Ivan LAVALLÉE, Algorithmique parallèle et distribuée, 1990.
Jean-Pierre CHARDON et Dominique BISSEY, Télécommunications d'entreprise
E— techniques et organisation, 1990 et 1992 pour la 2 édition revue et
complétée.
Victor SANDOVAL, Technologie de l'EDI, 1990.
Xavier MARSAULT, Compression et cryptage en informatique, 1992.
Christian PÉLISSIER, Utilisation et administration du système UNIX, 1992. n, Guide de sécurité des systèmes UNIX, 1993.
Michel ADIBA, Christine COLLET, Objets et bases de données — le SGBD0,
2
1993 . Traité des Nouvelles Technologies
série Informatique
Informatique parallèle
et
systèmes
multiprocesseurs
Jean-Louis Jacquemin
HERMES ©Hermès, Paris 1993
Éditions Hermès
14, rue Lantiez
75017 Paris
ISBN 2-86601-366-2
ISSN 0993-5037 A Odile,
à Michaël,
à Lise et Nora. Table des matières
Remerciements 11
Préface3
Introduction5
Chapitre - Pourquoi le parallélisme ?9
1.1. CONCEPTS GÉNÉRAUX ET DÉFINITIONS 1
1.2. LES MOTIVATIONS POUR LE PARALLÉLISME 2
1.2.1. Gain de performances 24
1.2.2. Flexibilité et extensibilité
1.2.3. Aide à l'accroissement du débit et de la capacité des mémoires 26
1.2.4. Outil de structuration7
1.2.5. Adéquation au traitement temps réel8
1.2.6. Tolérance aux pannes (fault tolerance)9
1.2.7. Aide à la vérification 31
1.3. QUELQUES DOMAINES D'APPLICATIONS DU PARALLÉLISME ... 32
1.3.1. Applications orientées vers un accroissement de puissance 33
1.3.2.ss vers l'adéquation au modèle
1.3.3.s orientées vers les systèmes à tolérance de pannes9
1.4. LES DIFFICULTÉS DU TRAITEMENT PARALLÈLE 4
1.4.1. Problèmes de communication dans les systèmes parallèles
1.4.2. Choix de la topologie d'interconnexion des processeurs3
1.4.3. Routage (routing) 44
1.4.4. Blocage mutuel (deadlock)
1.4.5. Organisation de la mémoire5
1.4.6. Cohérence de l'information (information consistency) 46
1.4.7. Famine (starvation)8
1.4.8. Décomposition et équilibrage des charges (partitionning and
load balancing)
1.4.9. Placement ou affectation (Mapping) 50
1.4.10. Le non-déterminisme2
1.4.11. Terminaison des programmes parallèles3
1.4.12. Les difficultés qui restent à résoudre6 8 Informatique parallèle et systèmes multiprocesseurs
Chapitre 2 - Architectures 59
2.1. LE MODÈLE SISD (Single Instruction Single Data Stream) 61
2.1.1. Le modèle de base 6
2.1.2. Modèle à pipeline2
2.2. LE MODÈLE SIMD (Single Instruction Multiple Data Stream)4
2.2.1. Modèle SIMD de base
2.2.2. Mise en œuvre des systèmes SIMD6
2.2.3. Les réseaux cellulaires et systoliques7
2.2.4. Exemples de machines SIMD et de leurs applications 6
2.3. LE MODÈLE MISD (Multiple Instruction Single Data Stream) 7
2.4. LEE MIMD Multiple Data2
2.4.1. Systèmes multiprocesseurs à mémoire partagée 73
2.4.2.ss àe distribuée
2.4.3. Systèmess à bus hiérarchisés9
2.4.4. L'architecture VLIW (Very Long Instruction Word)
2.4.5. Machines à flot de données 81
2.4.6.s à réduction3
2.4.7. Réseaux de neurones5
2.5. UN CAS PARTICULIER : LE S ORDINATEURS OPTIQUES 8
Chapitre 3 - Topologies 9
3.1. CARACTÉRISTIQUES D'UNE TOPOLOGIE 92
3.2. TOPOLOGIES EN BUS3
3.2.1. Bus simple
3.2.2. Bus multiples4
3.2.3. Bus hiérarchisés
3.3. TOPOLOGIES A CONNEXIONS DIRECTES6
3.3.1. Topologies standards 9
3.3.2.s hiérarchisées 10
3.4. TOPOLOGIES RÉCURSIVES8
3.5. RÉSEAUX MULTIPROCESSEURS COMMUTABLES 109
3.5.1. Réseaux matriciels de commutateurs (crossbars) 110
3.5.2. Exemples 111
3.5.3. Réseaux à étages multiples3
Chapitre 4 - Langages de programmation parallèle 119
4.1. LANGAGES DE PROGRAMMATION ASYNCHRONE 120
4.1.1. Langages à gestion centralisée des variables1
4.1.2.s àn distribuée dess
4.2. LANGAGES DEN SYNCHRONE 138
4.2.1. Langages pour compilateurs à détection du parallélisme
4.2.2.s à expression du parallélisme de la machine 142
4.2.3. Langages àn due du problème5
4.3. MODÈLES DE TRAITEMENT ABSTRAITS 14Table des matières 9
4.3.1. Langages de programmation fonctionnelle 148
4.3.2.s orientés objet 151
4.3.3. Langages den en logique concurrente 152
4.4. AU CŒUR D'UN LANGAGE PARALLELE : OCCAM3
4.4.1. Généralités
4.4.2. Les processus en OCCAM6
4.4.3. Les constructeurs (constructs)8
4.4.4. Les canaux de communication 167
4.4.5. Les protocoles de canaux9
4.4.6. Les priorités 173
4.4.7. Programmation en temps réel5
4.4.8. Configuration d'une application OCCAM sur un réseau de transputers. 176
Chapitre 5 - Systèmes d'exploitation pour machines parallèles 17
5.1. MULTIPROGRAMMATION ET PARALLÉLISME 181
5.2. ORDONNANCEMENT ET SÉQUENCEURS4
5.3. INTERACTIONS DE PROCESSUS 185
5.4. L'EXCLUSION MUTUELLE8
5.4.1. Méthodes de Dekker et Dijkstra
5.4.2. L'instruction 'Test-and-Set" 190
5.4.3.n d'échange
5.4.4. Sémaphores binaires1
5.4.5.s n-aires2
5.4.6. Moniteurs
5.4.7. Verrous 196
5.4.8. Jetons7
5.5. LA SYNCHRONISATION8
5.5.1. Généralités
5.5.2. Outils matériels de synchronisation 200
5.5.3. Outils logiciels den1
5.6. LE BLOCAGE 205
5.7. MÉTHODES FORMELLES D'ANALYSE DES
SYSTÈMES PARALLÈLES
5.7.1. Réseaux de Petri9
5.7.2. Automates à états finis 21
5.8. GESTION DE LA RÉPARTITION ET DE LA COHÉRENCE DE
L'INFORMATION 213
5.9. SYSTÈMES D'EXPLOITATION POUR MACHINES
MULTIPROCESSEURS4
5.9.1. Utilisation du système d'exploitation de l'hôte
5.9.2. Systèmes d'exploitation dérivés d'UNLX 215
5.9.3. Systèmes d'exploitation pour réseaux de transputers 217
5.9.4. Autres systèmes d'exploitation9
5.10. COMPILATEURS POUR MACHINES PARALLÈLES 221
5.11. TEMPS RÉEL 222
5.11.1. Généralités
5.11.2. Exemples de systèmes temps réel multiprocesseurs4 10 Informatique parallèle et systèmes multiprocesseurs
5.11.3. L'aspect temps réel dans les langages de programmation parallèle .. 225
5.11.4. Exemples de noyaux temps réel pour transputers 228
Chapitre 6 - Les processeurs 231
6.1. PROCESSEURS RISC ET PROCESSEURS CISC2
6.2. EXEMPLES DE PROCESSEURS RISC
6.3.S DES CISC3
6.4. MICROPROCESSEURS A ARCHITECTURE PARALLÈLE 23
6.5. LES PROCESSEURS CELLULAIRES6
6.6. LES TRANSPUTERS : RISC ou CISC ?7
6.6.1. Principales caractéristiques de l'architecture des transputers
6.6.2. Les hens des transputers 238
6.6.3. Le planificateur 240
6.6.4. Jeu d'instructions
6.6.5. Les commutateurs matriciels programmables 24
Chapitre 7 - Exemples de machines multiprocesseurs3
7.1. MACHINES SIMD
7.2.S MIMD A MÉMOIRE PARTAGÉE 245
7.3.SD AE DISTRIBUÉE7
7.3.1. Les hypercubes 248
7.3.2. Les machines à base de transputers9
7.3.3. DAD0 2 : une machine arborescente pour l'I.A 252
7.4. CAS PARTICULIER : UNE MACHINE VLIW
Chapitre 8 - Évaluation des performances des machines parallèles 255
8.1. GÉNÉRALITÉS ET DÉFINITIONS 25
8.2. ÉVALUATION DU DÉBIT THÉORIQUE MAXIMUM 256
8.3. UTILISATION DE PROGRAMMES STANDARDS7
8.4. TESTS SUR UN SEUL TYPE D'OPÉRATION OU D'APPLICATION... 259
8.5. LE CAS PARTICULIER DE L'I.A9
Conclusion 261
Bibliographie3
Liste des figures 275
Liste des programmes
Index 28
Lexique français-anglais , 289
Lexique anglais-français 293 Remerciements
L'auteur adresse ses plus vifs remerciements à Michael Griffiths qui a eu la
constance de lire d'un bout à l'autre, et dans le détail, le manuscrit. Les remarques et
suggestions, constructives et pertinentes, de cet informaticien chevronné et grand
connaisseur en parallélisme, ont été un appoint inestimable dans la rédaction de
l'ouvrage.
Ses remerciements vont aussi à Daniel Lafaye de Micheaux, maître de
conférences à l'Université de Nice, dont l'expérience en informatique parallèle a été
très précieuse, et avec qui les concepts de base, état des recherches, applications et
expériences pédagogiques ont été méticuleusement passés en revue au cours de
fertiles discussions.
L'enseignement de l'informatique parallèle est, encore à ce jour, assez peu
développé en France. Aussi, l'auteur a beaucoup apprécié les entretiens avec de
nombreux enseignants étrangers qui lui ont fait part de leur expérience pédagogique
dans ce domaine. Il remercie tout particulièrement le professeur Hersch, de l'Ecole
polytechnique fédérale de Lausanne, les enseignants du Parallélisme de l'Université
d'Exeter, de l'Université de Tokyo et ceux du Royal Melbourne Institute of
Technology.
Il serait injuste d'oublier tous les étudiants de diverses origines qui ont, eux
aussi, apporté leur indiscutable pierre à l'édifice à travers leurs questions et
remarques multiples ; celles-ci ont permis à l'auteur, au cours des années, d'affiner
ses cours et conférences dont cet ouvrage est le reflet. Leur vif intérêt pour
l'informatique parallèle, que certains découvraient pour la première fois, a été un
encouragement pour l'auteur à se lancer dans la tâche exigente de rédaction d'un
ouvrage couvrant un aussi vaste domaine. Curieux du matériel comme des langages,
des systèmes comme des concepts de base, ils ont suscité des approfondissements,
des éclaircissements et des compléments bibliographiques. Une reconnaissance
particulière est due aux étudiants du diplôme d'études approfondies en informatique
de l'Université de Nantes, à ceux des mastères de l'ESIM de Marseille et "Bases de
Données" de Sophia-Antipolis, aux élèves-ingénieurs de l'École des Mines de Paris
et à ceux de 1'EERIE de Nîmes.
Le présent ouvrage s'appuie largement aussi sur l'expérience acquise par l'auteur
à travers ses travaux de recherches menés sur le parallélisme depuis près de 10 ans.
Que tous les chercheurs qui ont contribué, au cours de ces dernières années, à ces
travaux sous sa direction, tant au Laboratoire SISE de Marseille qu'au Laboratoire
d'informatique d'Avignon, trouvent ici l'expression de sa reconnaissance, en
particulier B. Achispon, S. Allemand, Y. Fernandez, T.T. Huynh, A. Khoury,
A. Lakkis, C. Martin et C. Salagnon. Préface
C'est pour moi un plaisir de présenter cet ouvrage sur le parallélisme, sujet qui
prend de plus en plus d'importance de nos jours. Mais ce n'est pas parce qu'un
sujet est à la mode qu'il faut croire qu'il est tout nouveau. On pourrait discuter
longtemps pour savoir à quel moment on a produit la première machine parallèle.
Ce qui est sûr, c'est que dès 1958, l'IBM 709 comportait un système d'interruptions,
c'est-à-dire que ses éléments périphériques travaillaient en vrai parallèle avec le
processeur central.
A l'époque, le parallélisme était déjà un moyen d'accélération des matériels ; en
faisant travailler n circuits en parallèle, on peut théoriquement aller n fois plus vite.
Mais les techniques relevaient du bricolage électronique (d'une grande difficulté
d'élaboration, faut-il le dire). Par la suite, on a absorbé les concepts de la
multiprogrammation et du temps partagé, qui introduisent un faux parallélisme en
partageant un processeur entre plusieurs tâches.
Au cours des années soixante, on a introduit dans des ordinateurs
commercialisés dispositifs tels que les pipe-Unes, les caches et les processeurs
spécialisés, qui donnaient lieu à un vrai parallélisme à l'intérieur d'un seul
processeur. On a aussi créé des ordinateurs multiprocesseurs, qui permettaient un
vrai parallélisme entre tâches en multiprogrammation. Ces efforts allaient toujours
dans le sens de V amélioration des performances des matériels par des exploits
d'électroniciens, le travail restant transparent pour les informaticiens (à quelques
exceptions près).
Pendant ce temps, les informaticiens ont beaucoup travaillé sur des problèmes
tels que la concurrence entre tâches, la gestion de systèmes distribués, l'écriture de
programmes incorporant le temps réel, bref, le contrôle conceptuel du parallélisme.
Ces deux mondes ont vécu à part, chacun continuant dans la ligne de sa culture
spécifique. Ce type d'isolement n'est pas nouveau dans nos affaires ; Varchitecture
des puces standards des PC est une autre illustration des méfaits de l'ignorance
mutuelle.
Avec la baisse du prix unitaire des processeurs, les années quatre-vingts ont vu
l'avènement sur le terrain d'architectures parallèles qui nécessitent un changement
d'habitudes chez les informaticiens, les méthodes de programmation traditionnelles
ne permettant plus d'exploiter correctement le matériel disponible. Jusqu'alors, ces
matériels n'étaient étudiés que par quelques spécialistes dans les laboratoires
suffisamment riches pour pouvoir y accéder. Maintenant que chacun peut se trouver
en face de tels matériels, il faut déjà ajouter des cours dans notre panoplie
universitaire afin de préparer les étudiants. 14 Informatique parallèle et systèmes multiprocesseurs
Dans ce cadre, l'ouvrage de Jean-Louis Jacquemin est le bienvenu. Cet
enseignant expérimenté est particulièrement qualifié pour nous faire part des
travaux dans le domaine ; il a travaillé dans /'électronique avant d'assurer sa
conversion vers l'informatique. Il est donc à même d'expliquer l'architecture
"matériel" dans des mots compréhensibles pour l'informaticien.
Sur un plan plus large, certains s'étonnent de la lenteur avec laquelle les
applications exploitant le parallélisme arrivent sur le marché. Une analyse de la
situation indique un manque d'outils adéquats, et de personnes compétentes pour les
créer. Ce n'est donc pas seulement pour des raisons académiques que nous
souhaitons former nos étudiants dans le domaine ; nous attendons des retombées
économiques. Nous espérons que ce livre soutiendra l'effort nécessaire.
Michael GRIFFITHS Introduction
"L'Informatique de demain sera répartie et parallèle", proclamaient certains à la
fin des années 80. En 1993, la prophétie se révèle partiellement exacte :
l'Informatique moderne est bien répartie, personne ne le conteste. Mais pour son
aspect parallèle, les choses sont-elles aussi nettes ? En 1985, l'avènement des
transputers, microprocesseurs spécialement conçus pour le parallélisme, avait fait
naître beaucoup d'espoir sur l'avenir des machines multiprocesseurs, espoir d'autant
plus justifié que le coût relativement modeste des transputers permettait à bon
nombre d'informaticiens d'envisager des systèmes constitués de centaines de ces
processeurs, voire de milliers pour les plus optimistes. Le vieil adage "l'union fait la
force" devrait, pensait-on, pouvoir s'extrapoler à l'informatique pour donner
d'extraordinaire s puissances de traitement et de stupéfiants rapports
performance/coût.
Deux camps se formèrent : d'un côté, les éternels sceptiques qui craignaient de
redoutables bouleversements et des remises en cause à la fois des matériels et des
logiciels, des concepts et des techniques, des méthodes d'analyse et de celles de
programmation. A leur côté, la plupart des industriels, pragmatiques et prudents,
attendaient pour voir...
Dans l'autre camp, ceux, franchement optimistes, qui s'enthousiasmaient, peut-
être un peu vite, pour ces nouveaux systèmes. Le moins que l'on puisse dire est que
le parallélisme avait divisé le monde des informaticiens.
Un an à peine après le début de la commercialisation des premiers transputers, on
ne recensait pas moins de 1000 équipes de recherche travaillant, dans le monde
entier, sur les systèmes multiprocesseurs à transputers : un signe qui ne trompait pas.
La plupart d'entre eux voyaient là une réponse adéquate à la redoutable question de
savoir comment continuer à accroître la progression de la puissance de calcul des
processeurs, et donc des machines, au même rythme effréné que celui que nous
connaissions depuis de nombreuses années. Les informaticiens avaient pris pour
habitude de se tourner vers les concepteurs de machines et de processeurs qui, il faut
bien le dire, ne les avaient encore jamais déçus : à peine une machine arrivait-elle
sur le marché qu'une autre, 10 fois plus puissante était déjà annoncée pour le
lendemain ou presque.
Aujourd'hui est-on assuré de disposer d'un rythme de progression toujours aussi
rapide ? La question se pose avec d'autant plus d'acuité que les processeurs
séquentiels traditionnels approchent des limites imposées par les lois de la Physique,
tandis que les utilisateurs, tellement gâtés pendant tant d'années, se font de plus en 16 Informatique parallèle et systèmes multiprocesseurs
plus exigeants et rêvent déjà de machines 3T (traitement de 1000 milliards
d'opérations en virgule flottante par seconde, mémoire de 1000 milliards d'octets, et
débits de 1000 milliards de bits par seconde...). Comment relever ce formidable
défi ? Et bien puisque les lois de la Physique barrent la route de la progression des
machines, il faut contourner l'obstacle en peaufinant les architectures, et plus
précisemment en développant le parallélisme. L'idée n'est pas nouvelle mais les
contraintes qui l'imposent le sont ; et dans cette nouvelle vision des machines de
demain, les systèmes multiprocesseurs semblaient bien devoir occuper le premier
plan.
Avec un recul de quelques années par rapport à la vague d'enthousiasme que
nous venons d'évoquer, force est de constater que les systèmes multiprocesseurs
n'ont peut-être pas révolutionné l'Informatique comme le prédisaient certains, mais
qu'ils occupent néanmoins une place que plus personne ne leur conteste : si les
machines universelles massivement parallèles se font encore attendre, en revanche
de nombreuses applications, y compris en entreprise, fonctionnent sur des systèmes
multiprocesseurs, et l'on ne compte plus les micro et mini-ordinateurs "dopés" aux
transputers qui donnent toute satisfaction dans les domaines d'applications les plus
variés.
L'informatique des systèmes multiprocesseurs, dont il sera beaucoup question
dans cet ouvrage, fait donc partie de ce qu'il est convenu d'appeler l'Informatique
Parallèle. Encore faut-il définir précisemment ce qu'elle est, et surtout ce qu'elle
n'est pas : en effet, le lecteur non averti pourrait penser a priori, en raison du
qualificatif "parallèle", qu'il s'agit d'une sorte d'Informatique "marginale" (un peu
au sens où l'on parle d'activités ou de marchés parallèles !), destinée à apporter un
peu d'originalité et de fantaisie au quotidien de quelques chercheurs en mal
d'innovation. Cette vision des choses ferait oublier que le parallélisme est utilisé
depuis plus de quinze ans dans les supercalculateurs : le CRAY-1, commercialisé en
1976, était pour l'époque un formidable outil de calcul grâce à l'utilisation du
processeur vectoriel pipeline. Ses performances furent à ce point probantes que ses
successeurs en furent tous dotés. Si cette forme de parallélisme est restée, pendant
plusieurs années, l'apanage des processeurs pour gros systèmes, il n'en n'est plus de
même de nos jours : les microprocesseurs les plus récents, comme le transputer
T9000 d'INMOS, le processeur i860 d'INTEL ou encore le C40 de TEXAS
INTRUMENTS , font preuve de performances étonnantes grâce à une large
utilisation interne du parallélisme.
Ce parallélisme au niveau du processeur, que nous appellerons
"microparallélisme", au même titre que l'on parle de microprocesseur, se double
d'une forme de parallélisme beaucoup plus "visible", celle que l'on peut constater au
niveau de l'organisation des processeurs dans une machine et que nous appellerons
le macroparallélisme avec la possibilité de mettre en œuvre plusieurs processeurs
dans la même machine ; c'est ce que l'on peut faire avec les transputers grâce à leurs
hens de communication série permettant de les associer à d'autres pour constituer
des réseaux multiprocesseurs théoriquement illimités, ou plus modestement, en
implantant quelques uns d'entre eux sur une simple carte additionnelle pour micro-
ordinateur.
Qu'il s'agisse de parallélisme interne au processeur ou de véritables systèmes
multiprocesseurs, le principe de base consiste toujours à faire exécuter plusieurs
tâches en même temps. Dans un processeur vectoriel, ou pipeline, ou les deux à la
fois, il s'agit d'exécuter en parallèle des opérations élémentaires : c'est le Introduction 17
parallélisme à "grain fin". Dans un système multiprocesseur, plusieurs programmes
autonomes s'exécutent en parallèle, leur mode d'interaction étant la communication
interprocesseur directe ou bien une mémoire commune. C'est le parallélisme " à
gros grain".
Il est devenu courant aujourd'hui de "doper" un micro ou un mini-ordinateur
avec une ou plusieurs cartes à transputers dont la modularité, l'extensibilité et la
souplesse permettent une augmentation de puissance sans aucune mesure avec
l'investissement consenti ; c'est un des arguments les plus solides pour convaincre
ceux qui gardent un comportement réservé vis-à-vis de l'Informatique Parallèle.
Pourtant, à la question "Pourquoi le parallélisme ?", que nous posons dans le
premier chapitre, on ne saurait répondre seulement : "Pour accroître la puissance de
calcul". En effet, le parallélisme est une forme "naturelle" du traitement de
l'information en liaison directe avec le monde dans lequel nous vivons. Le
parallélisme intrinsèque des problèmes que traite l'informatique est omniprésent.
Or, traiter à l'aide d'une machine parallèle un problème intrinsèquement parallèle
est non seulement une démarche satisfaisante pour l'esprit mais aussi une garantie
de simplification dans la conception, la vérification et la validation. De la
modélisation des phénomènes météorologiques au traitement du signal, de la
synthèse d'images aux systèmes à tolérance de pannes, de la robotique rapide aux
simulateurs en temps réel, nombreux sont ceux qui trouvent dans cette branche de
l'Informatique les solutions les plus "naturelles", les plus efficaces, les plus
évolutives et... les moins chères.
Pratiquer l'informatique parallèle conduit inévitablement à s'intéresser un
jour ou l'autre à chacun des aspects de cette technique, aspects aussi bien logiciels
que matériels. Cet ouvrage ne développe pas dans le détail les structures
algorithmiques propres au parallélisme. Cependant, le lecteur y trouvera exposés de
nombreux outils, techniques et langages qui devront lui permettre, à travers les
exemples qui les illustrent, d'avoir une vision suffisamment précise de ce qu'est
l'algorithmique parallèle, de ses principales techniques, de ses difficultés, et
finalement d'apprécier ce qu'il est en droit d'en attendre par rapport aux techniques
séquentielles conventionnelles.
Les atouts du parallélisme ainsi que ses difficultés seront présentés en premier.
Les domaines d'application étant extrêmement variés, nous nous efforcerons d'en
donner un aperçu suffisamment vaste pour convaincre le lecteur que l'immense
majorité des applications de l'informatique peut être efficacement parallélisée.
L'organisation des machines parallèles est un problème complexe étudié au
chapitre 2 (architectures). En ne se limitant pas à la description des architectures des
systèmes multiprocesseurs, cet ouvrage peut donner au lecteur un moyen de
comparer les différents types d'architectures classiques existantes. Les topologies
(chapitre 3) sont une suite logique au chapitre sur les architectures. De nombreuses
références à des applications opérationnelles montrent la nécessaire adéquation entre
la façon dont sont organisés les processeurs et la nature du problème à traiter.
Le chapitre 4, consacré aux langages parallèles, est destiné à montrer que
l'apprentissage de ce type de langage ne doit pas constituer un obstacle dans une
démarche vers l'informatique parallèle ; au contraire même, le lecteur qui dispose
déjà d'une certaine expérience en informatique séquentielle découvrira dans le
parallélisme, à l'issue d'une courte phase de familiarisation peut-être un peu
déconcertante, une nouvelle "dimension" dans sa façon de concevoir des
algorithmes. Certains n'hésitent pas à comparer cette transition intellectuelle à celle 18 Informatique parallèle et systèmes multiprocesseurs
que l'on peut ressentir quand on commence à maîtriser le jeu d'échecs après avoir
pendant dix ans joué aux dames ! Ce sera au lecteur d'en juger... Toutes les finesses
de la programmation parallèle ne sont certainement pas abordées dans ce chapitre ;
cependant , une étude relativement approfondie du langage OCCAM, et la
présentation des principales caractéristiques d'autres langages parallèles comme C
parallèle et ADA, devraient permettre au lecteur d'aborder ce domaine sans avoir
l'impression d'abandonner ses acquis. Bien au contraire, les bonnes habitudes prises
en programmation séquentielle, notamment en matière de programmation structurée,
sont l'indispensable sésame pour l'accès à la programmation parallèle.
Le chapitre 5 est consacré aux systèmes d'exploitation des machines parallèles ;
nous passerons en revue les différentes techniques de résolution des problèmes
d'exclusion mutuelle, de synchronisation, de communication et nous donnerons un
panorama non exhaustif mais cependant assez complet de ce que permettent de faire
les systèmes d'exploitation multiprocesseurs disponibles. Le traitement
d'applications en temps réel est un cas particulier suffisamment important par lui-
même pour qu'il mérite d'être développé dans ce cadre.
Nous poursuivrons par deux chapitres consacrés au matériel (chapitres 6 et 7) :
les processeurs et les machines multiprocesseurs les plus représentatifs du
parallélism e en 1993. Malgré le danger de présenter des informations
nécessairement obsolètes à très court terme, le lecteur non averti aura la surprise de
découvrir qu'il existe un large éventail de produits disponibles qu'il n'avait
probablemement pas soupçonné : machines autonomes de toutes puissances, cartes
additionnelles pour machines hôtes, processeurs pour le parallélisme. Adaptabilité,
flexibilité, évolutivité restent les maîtres mots de ce type de matériel.
Enfin l'auteur a voulu présenter brièvement les techniques d'évaluation des
performances des machines : comment s'y retrouver dans des catalogues qui vantent
les mérites de telle ou telle machine en termes de MIPS, MOPS, MFlops ou
"benchmarks" ? Les points de repère ne sont pas facilement identifiables. Mieux
vaut les connaître pour choisir le matériel en connaissance de cause... Chapitre 1
Pourquoi le parallélisme ?
1.1. CONCEPTS GÉNÉRAUX ET DÉFINITIONS
En informatique, le parallélisme au sens le plus général pourrait être défini
comme une technique qui permet d'utiliser simultanément plusieurs machines pour
mener à bien l'exécution d'un programme. Toutefois, une telle définition ne saurait
suffire à donner un cadre précis à cet ouvrage ; en effet, il n'y a pas de commune
mesure entre, d'une part, un processeur et un coprocesseur intégrés sur la même
puce de silicium (le second déchargeant le premier, par exemple, des tâches de
calcul en virgule flottante) et, d'autre part, deux gros ordinateurs autonomes chargés
de contrôler la production industrielle de deux ateliers d'une grande usine. De même
peut-on comparer la coopération existant entre deux machines reliées par un bus à
l'intérieur d'un même local, et deux autres échangeant de l'information d'un
continent à l'autre ? On voit clairement que les puissances de calcul mises en
oeuvre, tout autant que les moyens de communication permettant les échanges
d'information, sont fondamentalement différents. Le seul caractère commun à ces
machines est qu'elles s'opposent à la notion de système centralisé, et que chacune
d'elle dispose d'une certaine, voire d'une totale, autonomie.
Ajoutons, à cet éventail, des formes plus subtiles du parallélisme, comme celles
des processeurs vectoriels et pipelines où il intervient au niveau le plus fin, c'est-à-
dire dans le traitement de l'instruction elle-même et des données qu'elle manipule.
Ces techniques, largement répandues depuis longtemps dans les gros calculateurs,
font maintenant une apparition remarquée dans les microprocesseurs récents.
De nombreux auteurs se sont attachés à donner une définition plus ou moins
précise, à défaut d'une classification rigoureuse, des différents types de systèmes
parallèles dont les exemples ci-dessus suffisent à donner une idée de leur
extraordinaire diversité.
Nous retiendrons tout particulièrement la distinction entre systèmes parallèles et
systèmes distribués (ou répartis) proposée par P. Bertsekas et J.N. Tsitsiklis
[BERTSEKAS 89] selon laquelle dans les systèmes parallèles plusieurs processeurs
situés à faible distance l'un de l'autre exécutent conjointement un traitement de telle
sorte que les communications entre processeurs soient fiables et prévisibles. Au
contraire, selon ces auteurs, dans un système distribué les processeurs peuvent être 2 0 Informatique parallèle et systèmes multiprocesseurs
éloignés et les communications interprocesseurs plus problématiques (retards,
modification de topologie, pannes,...).
Toutefois cette distinction, essentiellement fondée sur un critère de distance, ne
suffit pas à définir clairement un système multiprocesseur. Nous définirons donc ce
dernier comme un système parallèle constitué d'un ensemble de processeurs rebés
entre eux par une de communication interne à la machine. Il s'agit donc
avant tout d'une machine unique, constituée de plusieurs processeurs qui traitent un
seul problème à un instant donné. Il entre donc dans les attributions du concepteur
de le gérer totalement, c'est-à-dire de contrôler les échanges, la synchronisation, les
exclusions mutuelles. Nous utiliserons le mot "système" multiprocesseur de
préférence à "réseau" multiprocesseur du fait que le terme "réseau" rappelle trop
fortement la notion de réseau de communication et donc de système distribué.
En fait, dans la réalité la distinction n'est pas toujours facile à établir car il arrive
aussi que, sur de puissantes machines multiprocesseurs, l'on fasse "tourner"
simultanément plusieurs applications indépendantes ; à l'inverse il se peut aussi
qu'une application très gourmande en temps CPU soit distribuée sur plusieurs
groupes de processeurs, chaque groupe faisant partie d'une machine parallèle et
chaque machine étant elle-même reliée aux autres par un réseau classique (de type
ETHERNET par exemple). Mais il n'y a pas lieu de s'étonner de cet état de fait ; il
témoigne au contraire de la grande vitalité du traitement parallèle au sens large et il
est bien compréhensible que, au sein de cette grande famille, cohabitent des
technique s complémentaires associant à la fois les atouts des systèmes
multiprocesseurs au sens strict défini ci-dessus, et ceux des systèmes distribués.
Trois notions de base suffisent à évoquer le mode de fonctionnement des
systèmes multiprocesseurs : la coopération, la concurrence et la communication. La
coopération est une notion qui vient naturellement à l'esprit puisque c'est grâce à
elle que plusieurs processeurs vont, conjointement et simultanément, collaborer à
l'exécution d'une même tâche. La dénomination de "systèmes concurrents" utilisée
par certains auteurs pour désigner les systèmes multiprocesseurs est en fait une
traduction abusive de l'anglais "concurrent systems" (qui signifie "systèmes
coopérants") car la notion de concurrence, donc de rivalité, de compétition, ne
domine généralement pas dans ce type de systèmes ; certes elle existe lorsqu'il s'agit
d'accéder à une ressource commune, à un bus de communication, mais un des rôles
essentiels du concepteur de programme parallèle est au contraire de favoriser autant
que possible une coopération harmonieuse des processeurs et d'éviter les "rivalités".
La communication est la troisième notion de base qui découle des deux
précédentes. Pour le néophyte en matière de programmation parallèle, la gestion des
communications interprocesseurs soulève des problèmes nouveaux et souvent
difficiles à résoudre ; nous les évoquerons tout au long de cet ouvrage et nous
présenterons au fil des chapitres les méthodes à la fois matérielles et logicielles qui
permettent de les gérer, de les optimiser et de les contrôler.
Les différents processeurs d'un système vont se voir confier des tâches
spécialisées (special purpose processors) ou non (general purpose processors) ; on
pourra évidemment n'avoir que des processeurs du premier type, ou bien
uniquement du second, ou encore toute combinaison des deux.
La taille moyenne des tâches exécutées par une unité de traitement (processeur
ou ordinateur) est caractérisée par sa granularité ; celle-ci est extrêmement variable
selon que l'on a affaire par exemple à un réseau d'ordinateurs, à un réseau de
processeurs, ou encore à un processeur vectoriel ou pipeline ; la granularité peut Pourquoi le parallélisme ? 21
donc refléter la taille de chaque noeud d'un réseau, cette taille étant évaluée par la
capacité de traitement du noeud et celle de sa mémoire associée.
Il est habituel de se référer à trois grands types de granularité :
- le grain fin (fine grain parallelism) : les tâches sont fréquemment entrecoupées
de demandes de communication ; les processeurs sont nombreux mais rudimentaires :
il est fréquent qu'ils ne traitent qu'un seul bit à la fois et que leur mémoire ne
dépasse pas quelques Koctets. Parmi les machines à grain fin, citons la célèbre
CONNECTIO N MACHINE de THINKING MACHINE, le système MPP de
GOODYEAR AEROSPACE ou plus simplement les processeurs vectoriels.
Un des problèmes les plus difficiles est de trouver, pour de telles machines, un
compromis entre le nombre et la taille des éléments de traitement ; W.D. Hillis a
présenté une méthode dans le cas de la CONNECTION MACHINE [HILLIS 85].
- le gros grain (coarse grain parallelism) : les processeurs sont peu nombreux
mais puissants ; chacun dispose d'une mémoire importante (au moins 0,5 Moctets)
et l'application peut être divisée en modules de taille importante qui peuvent être
traités en parallèle. C'est le cas de supercalculateurs comme le CRAY-2 ou le SX-3
de NEC.
- le grain moyen concerne la plupart des machines parallèles commercialisées. Il
s'agit d'un type de granularité intermédiaire entre les deux types précédents, dans
lequel on peut classer l'hypercube iPSC de INTEL, le MULTIMAX de ENCORE
COMPUTERS ou bien le BUTTERFLY de BBN. Ils utilisent des microprocesseurs
puissants mais "classiques" et bon marché tels les séries 68000 de MOTOROLA, ou
32000 de NATIONAL SEMICONDUCTOR, ou encore les processeurs 80286 ou
80386 d'INTEL. La série T de ALLIANT COMPUTERS s'appuie quant à elle sur
les transputers. De tels systèmes délivrent de 15 à 100 MIPS (Millions d'Instructions
Par Seconde) pour 16 à 128 processeurs.
La granularité a un impact sur le temps d'exécution [MOHAN 83]. S'il est
certain que le parallélisme à grain fin présente les meilleures potentialités quant à la
rapidité d'exécution, encore faut-il que l'application se prête bien à une bonne
répartition des tâches élémentaires sur les différents processeurs d'une machine à
grain fin. De plus, il est nécessaire de s'assurer que la perte d'efficacité due à la
communication (communication overhead) n'amoindrit pas les performances, et que
le compilateur génère un code efficace pour un système pouvant contenir plusieurs
centaines, voire plusieurs milliers, de processeurs.
Un autre concept général indissociable des systèmes parallèles, et en particulier
de s systèmes multiprocesseurs, est la notion de couplage. Lorsque les
communications ont heu avec une mémoire modulaire globale partagée par tous les
processeurs, des conflits d'accès peuvent se produire. On a alors affaire à un système
à couplage étroit (tightly coupled system) et les communications se font par partage
des variables. Les conflits d'accès peuvent être logiciels si un processeur essaie
d'utiliser un ensemble de données en cours d'utilisation par un autre processeur, ou
matériels si deux processeurs tentent d'accéder au même module mémoire. S'il
s'agit d'une lecture, il est concevable que la logique autorise de satisfaire
simultanément toutes les requêtes d'accès à un simple mot mémoire. S'il s'agit
d'une écriture, le problème est plus compliqué. On peut, par exemple, n'autoriser
qu'une seule requête à la fois pour atteindre la mémoire, comme c'est le cas de
l'ULTRACOMPUTER de l'Université de New-York. 22 Informatique parallèle et systèmes multiprocesseurs
Dans un système dit à couplage lâche (loosely coupled system), la mémoire est
distribuée parmi les processeurs sous forme de mémoires locales. Il n'y a alors plus
de conflit d'accès mémoire et les communications interprocesseurs se produisent par
transmission de message. Toutefois, la perte d'efficacité due à celles-ci peut devenir
importante ; aussi de tels systèmes ne peuvent-ils être efficaces que dans le cas où il
existe des interactions minimales entre tâches, à l'inverse des systèmes fortement
couplés qui acceptent quant à eux un haut degré d'interactions. Les systèmes
construits à base de transputers sont le type même des systèmes à couplage lâche.
Les performances d'un système multiprocesseur peuvent être évaluées de
plusieurs façons : une des méthodes les plus simples consiste à calculer le rendement
R (efficiency), c'est-à-dire le rapport, en pourcentage, entre le temps T l mis par un
seul processeur pour exécuter une tâche donnée, et n fois les Tn mis par n
processeurs pour effectuer ce même travail :
R = 100 * ( Tl / (n*Tn) )
Le rendement peut prendre des valeurs très variables selon le type de problème
et... le talent du programmeur. Certaines applications présentent un parallélisme
trivial comme, par exemple, celles qui consistent à traiter des données différentes à
l'aide d'algorithmes identiques. Le rendement peut alors tendre vers 100% sans
toutefois lui être strictement égal en raison de l'inévitable perte d'efficacité due aux
communications interprocesseurs (au minimum transmission des paramètres et
récupération des résultats par le processeur maître) et à condition aussi qu'un
processus ne se "singularise" pas par rapport aux autres en tardant à rendre ses
résultats en raison, par exemple, d'un calcul de convergence particulièrement
défavorable.
Inversement, dans de nombreux problèmes, lorsque chaque processeur n'exécute
pas la même séquence d'instructions que les autres, ou bien lorsque une portion de
programme ne peut pas être parallélisée, le rendement peut se réduire à 25 ou 30 %,
parfois même moins. On pourrait penser que l'on peut toujours dans ce cas réduire le
temps de calcul en augmentant autant que nécessaire le nombre de processeurs. Ce
n'est pas toujours possible et il arrive que l'accroissement inconsidéré du nombre de
processeurs augmente le temps de communication dans de grandes proportions,
incompatibles avec l'efficacité du système.
Les performances peuvent être évaluées en comparant simplement, pour une
application donnée, le temps mis pour exécuter cette application sur un système
multiprocesseur et sur un système monoprocesseur standard.
Pou r une évaluation plus générale des performances d'un système r donné, on peut faire appel à des programmes standards, appelés
"benchmarks", tel le "benchmark de Whetstone", le plus connu, destiné à comparer
les performances pour des applications scientifiques. De tels outils de comparaison
ont fait l'objet d'une élaboration très soignée mais ne font cependant pas l'unanimité
car les proportions d'entrées-sorties, d'appels de sous-programmes, de boucles de
calculs, etc, sont évidemment très variables d'une application à l'autre. Les
problèmes d'évaluation de performances seront évoqués au chapitre 8.
Les performances matérielles dépendent d'un très grand nombre de paramètres
dont l'optimisation fait appel à la fois à la physique des solides, à l'électronique, à
l'architecture des systèmes. Toutefois, ces performances peuvent grossièrement être
divisées en deux grandes familles : celles qui dépendent directement des qualités Pourquoi le parallélisme ? 23
intrinsèques des processeurs et de leurs mémoires, et celles qui dépendent de la
qualité de la communication.
En ce qui concerne la qualité des processeurs, le concept RISC (Reduced
Instruction Set Computer) a permis des réalisations aux performances spectaculaires
tels les transputers qui seront présentés au chapitre 6.
Le concept de RISC fait appel à des primitives logicielles simples stockées en
mémoire comme de simples programmes. Ainsi, les instructions produites par le
compilateur ne sont plus interprétées à l'aide d'un microcode situé en ROM ; la
logique d'interprétation est donc beaucoup plus simple que dans les processeurs
CIS C classiques (Complex Instruction Set Computer). De ce fait, il est
théoriquement possible d'exécuter une instruction à chaque impulsion d'horloge ;
toutefois, les instructions RISC réalisent moins de travail que les instructions CISC ;
mais leur structure simple et régulière se prête bien à une large utilisation des
techniques de pipeline.
Dans la catégorie des processeurs RISC, on trouve les RISC I et II de Berkeley
[PATTERSO N 82], le MC 88000 de MOTOROLA, le SPARC de SUN
MICROSYSTEMS. Le transputer dispose d'une architecture partiellement RISC. Le
i860 d'INTEL a un noyau central RISC (RISC core).
Dans la catégorie des processeurs CISC, on rencontre les processeurs les plus
classiques tels la série 68000 de MOTOROLA, la famille 32000 de NATIONAL
SEMICONDUCTOR, less 80286/80287 et 80386 d'INTEL.
La qualité de la communication peut-être évaluée à l'aide de deux paramètres : le
débit (throughput), qui décrit la vitesse de communication interprocesseur^ et la
largeur de bande (bandwidth) quand on se réfère au débit total d'information qui
peut circuler à un instant donné sur l'ensemble des liaisons interprocesseurs.
La communication est dite synchrone lorsqu'il existe un mécanisme de rendez-
vous : l'émetteur et le récepteur se synchronisent pour transférer un message de
sorte que le premier processeur arrivé au rendez-vous attend l'autre (handshaking).
C'est le cas des transputers. De telles communications sont aussi qualifiées de
bloquantes.
Au contraire, dans une communication asynchrone, l'émetteur envoie des
messages puis poursuit son travail sans attendre que le processeur récepteur signale
l'arrivée de ce message. On dit alors que la communication est non bloquante.
1.2. LES MOTIVATIONS POUR LE PARALLÉLISME
Le gain de performance est un des avantages du parallélisme auquel on pense en
premier lieu. En fait, si le parallélisme permet virtuellement une puissance de calcul
illimitée, son introduction dans l'architecture des ordinateurs n'a pas eu comme but
premier un accroissement de la puissance de calcul, mais plutôt une meilleure
rentabilité des machines : utilisation simultanée des unités fonctionnelles, mémoires
hiérarchisées avec transferts en parallèle, temps partagé et multiprogrammation,
réseaux d'ordinateurs. Les études menées il y a une trentaine d'années par Grotsch,
d'une part, et Minsky, d'autre part, avaient instauré un certain pessimisme quant à
l'avenir du parallélisme multiprocesseur. En effet, le premier affirmait qu'il serait
plus coûteux de fabriquer n processeurs plutôt qu'un seul n fois plus puissant ("loi
de Grotsch") ; de nos jours, les contraintes de la technologie VLSI permettent
d'affirmer tout à fait le contraire. Quant au second, il assurait que la perte 24 Informatique parallèle et systèmes multiprocesseurs
d'efficacité due à la communication vouait à l'échec économique toute architecture
multiprocesseur selon ce qu'il était convenu d'appeler la "conjecture de Minsky"
[THURBER 71].
La technologie a beaucoup évolué depuis, les idées aussi, et le parallélisme a
prouvé sa capacité à accroître les performances de façon spectaculaire à tel point que
cette technique semble avoir pour vocation première l'augmentation de la puissance
de traitement ; en effet, on conçoit très bien intuitivement n processeurs en parallèle
exécutant une application n fois plus vite qu'un seul, bien que la réalité soit loin
d'être aussi simple. C'est le premier aspect du traitement parallèle que nous
examinerons aux paragraphes 1.2.1., 1.2.2. et 1.2.3.
Mais le parallélisme est aussi un puissant outil de structuration capable de
contribuer, bien mieux que le traitement séquentiel, à une conception beaucoup plus
modulaire des problèmes, en particulier ceux concernant le temps réel. Ce sera
l'objet des paragraphes 1.2.4. et 1.2.5.
Le parallélisme contribue enfin à la réalisation de systèmes plus fiables : d'une
part, il autorise la mise en oeuvre de machines à tolérance de panne efficaces et,
d'autr e part, il apporte une aide considérable au difficile problème de la
vérification ; ce thème sera abordé aux paragraphes 1.2.6. et 1.2.7.
1.2.1. Gain de performances
Les performances d'une machine numérique sont un compromis entre la vitesse,
la précision, la fiabilité et le coût. En fait, performance est souvent pris au sens de
vitesse ; c'est le cas dans les calculs scientifiques intensifs, dans les dispositifs de
traitement du signal où la vitesse de traitement fixe une limite à la quantité de
données qui peut être traitée à la seconde, ou encore dans la simulation de systèmes
dynamiques pour lesquels la vitesse détermine, par exemple, le temps nécessaire
pour faire avancer d'un pas la solution d'un système d'équations non linéaires.
Selon [SEITZ 84], les performances des systèmes monoprocesseurs tendent vers
9une asymptote d'environ 3*10 opérations par seconde, même en tenant compte de
la mise en oeuvre de techniques telles que les unités fonctionnelles multiples ou le
pipeline.
Pour accroître la vitesse de traitement des ordinateurs, l'imagination des
concepteurs n'a pas de limite ; cependant, on peut mettre en évidence trois grands
types de stratégies :
- employer des composants à grande vitesse : les supercalculateurs
commercialisés par CRAY et par NEC adoptent cette stratégie. Les processeurs sont
peu nombreux mais très puissants. Par exemple, dans la gamme des machines SX-3
de NEC, le système ne dispose, au plus, que de quatre processeurs, mais chacun
d'eux est capable de traiter, en mode vectoriel, un milliard d'instructions par
seconde. De plus, comme de tels systèmes font appel à d'énormes mémoires
centralisées à gros débit, leur coût est évidemment extrêmement élevé (au-delà de
quinze millions de dollars).
- modifier l'architecture interne de la machine : au lieu d'utiliser un petit
nombre de processeurs très puissants, voire un seul, cette stratégie fait au contraire
largement appel à une véritable architecture multiprocesseur. Cette idée n'est pas Pourquoi le parallélisme ? 25
nouvelle, mais ce qui est plus surprenant c'est que sa mise en oeuvre ne l'est pas non
plus puisque, dès 1972, BURROUGHS commercialisait son fameux ILLIAC IV
(ILLInois Automatic Computer) qui fut la première grosse machine multiprocesseur
(64 processeurs). Ce type d'architecture resta cependant isolé aussi longtemps que le
coût unitaire des processeurs resta élevé ; de nos jours, il n'en est plus ainsi, et il est
tout à fait envisageable de fabriquer des machines constituées d'un grand nombre de
processeurs "peu" puissants et bon marché. Une grande mémoire centralisée est
alors inutilisable et la communication a plutôt lieu à travers un réseau
d'interconnexion complexe qui privilégie les mémoires locales. Les systèmes à
transputers sont tout à fait représentatifs de ce type d'architecture dont on peut
penser qu'il est promis à un grand avenir en terme de rapport performance/coût.
Sont considérés comme petits systèmes multiprocesseurs, les systèmes ayant
moins de 16 processeurs. Entre 16 et 1024 processeurs, ils sont qualifiés de gros
systèmes. Au-delà de 1024, il s'agit de ce qu'il est convenu d'appeler le parallélisme
massif.
- diminuer le temps de parcours des signaux : en une nanoseconde, la lumière
parcourt à peine la longueur d'une feuille de papier de format A4. Or, la
nanoseconde est devenue "l'unité de temps" de la microélectronique moderne, et
dans un semi-conducteur l'information est loin de se déplacer à la vitesse de la
lumière. Pour contourner les limites de cette loi de la nature, la solution consiste soit
à réduire le nombre d'éléments d'un ordinateur, et l'on retombe alors sur la
"philosophie" des supercalculateurs évoquée ci-dessus, soit à réduire la longueur des
connexions entre composants de type VLSI à l'intégration toujours plus poussée.
1.2.2. Flexibilité et extensibilité
De façon générale, si un système n'a pas assez de puissance de traitement ou
manque d'un certain type de ressources, il est plus facile d'accroître cette puissance
ou d'ajouter les ressources requises s'il est distribué plutôt que s'il est centralisé
[MEYER 85].
En matière de traitement parallèle, les risques associés à l'achat de gros systèmes
sont réduits : l'utilisateur peut commencer avec un configuration peu onéreuse et un
équipement modeste, et acquérir des modules supplémentaires au fur et à mesure des
besoins en puissance et en ressources, aussitôt que le système de base a été avéré.
Dans le cas des systèmes à transputers, par exemple, l'ajout de processeurs
supplémentaires accroît la largeur de bande de communication en raison de
l'absence de mémoire partagée.
Prenons l'exemple du traitement des signaux fournis par un radar embarqué à
bord d'un engin spatial et chargé de fournir des images bidimensionnelles
[ELLIOTT 89]. Dès lors que l'altitude est telle que l'on ne peut pas faire l'hypothèse
d'un e vision plane de la terre, les calculs deviennent complexes. Elliott fait
remarquer qu'un traitement en temps réel nécessiterait 4000 transputers T414
répartis sur 250 cartes de 16 transputers chacune pour un coût total de 4 millions de
livres ! Or, une telle application met en oeuvre la duplication d'une même structure
de base ; de plus, le matériel et le logiciel peuvent être développés et testés sur un
système beaucoup plus petit que le système global nécessaire à un traitement en
temps réel. 26 Informatique parallèle et systèmes multiprocesseurs
L'extension ne nécessite donc qu'une duplication des unités matérielles, et des
modifications mineures des instructions de configuration logicielle. On peut donc
réduire les risques encourus lors de la phase de développement :
- en testant le logiciel sur un matériel limité dans un premier temps.
- en utilisant des processeurs relativement lents, donc moins onéreux, dans la
phase de mise au point ou bien dans le cas où les utilisateurs ne souhaitent pas
disposer de la version temps réel.
Remarquons toutefois que pour les grands projets, il est préférable de surestimer
les besoins en matériel si cela peut faciliter le développement du logiciel. En effet, le
coût logiciel de développement atteint couramment 90 % du coût total du projet et il
est fréquent que les chefs de projet sous-estiment le coût logiciel de 50 %...
[BELL 87].
Les informaticiens familiarisés avec un langage parallèle comme OCCAM, le
langage du transputer, savent tirer le meilleur parti du développement de leurs
applications selon les deux phases évoquées ci-dessus : en effet, un programme écrit
en langage OCCAM peut parfaitement être développé, mis au point et testé sur un
seul transputer qui fonctionne donc en pseudo-parallélisme. Ce n'est que dans la
phase ultime de développement de l'application, c'est-à-dire lorsque l'on veut
réellement évaluer son rendement, que la mise en oeuvre sur un réseau est
nécessaire, moyennant quelques modifications très mineures du code (instructions
de configuration). On peut seulement à ce moment-là parler de parallélisme vrai.
1.2.3. Aide à l'accroissement du débit et de la capacité des mémoires
Dans l'optique de l'amélioration des performances des machines modernes,
l'accroissement du débit et de la capacité des mémoires est une des préoccupations
principales. Il est tout à fait louable de chercher à accroître la vitesse de traitement
des machines, soit en fabricant des processeurs de plus en plus performants, soit en
les associant en grande quantité dans les systèmes multiprocesseurs, soit encore en
combinant les avantages de ces deux stratégies ; encore faut-il que les mémoires
indispensables qui leur sont associées voient leurs performances s'accroître dans les
mêmes proportions.
De la même façon que les progrès de la technologie n'expliquent pas à eux seuls
la formidable progression de la puissance de calcul des machines, les performances
que l'on demande à l'heure actuelle aux mémoires ne peuvent pas être attribuées
seulement au progrès des techniques de la microélectronique : en effet, il est
nécessaire d'avoir à l'esprit l'importance des progrès en matière d'architecture des
systèmes ; les mémoires elles aussi en ont bénéficié et les concepteurs se sont
ingéniés à élaborer les architectures les plus efficaces. On peut citer les exemples
bien connus de machines telles que le CRAY X-MP ou le CYBER 205 qui
bénéficient d'une organisation de mémoire telle que les éléments qui constituent un
ensemble de mots, appelé vecteur, se trouvent dans différents modules mémoire de
façon à assurer une largeur de bande maximum.
Les structures à mémoires hiérarchisées sont également très répandues. On les
rencontre non seulement dans les systèmes monoprocesseurs, mais aussi dans les
systèmes de traitement parallèle pour minimiser le temps d'accès effectif à la
mémoir e et améliorer les performances ; une telle architecture fournit des Pourquoi le parallélisme ? 27
performances proches de celles des mémoires les plus rapides avec un coût par bit à
peine supérieur à celui des mémoires lentes. Cependant, pour les machines
parallèles, ce type d'organisation est délicat à mettre en oeuvre, le degré de
complexité allant de pair avec le nombre de niveaux dans la hiérarchie.
S'il s'agit de systèmes faiblement couplés, c'est-à-dire pour lesquels il existe une
mémoire locale par processeur, éventuellement associée à une mémoire cache (petite e très rapide située entre le processeur et la mémoire proprement dite), le
problème reste relativement simple : la conception des caches pour de tels systèmes
diffère peu de celle des caches pour systèmes monoprocesseurs. En revanche, dans
les systèmes fortement couplés, c'est-à-dire disposant d'une grosse mémoire
partagée, la mise en oeuvre est beaucoup plus complexe, d'autant plus que s'y
adjoignent des caches et des mémoires locales ; il est en effet nécessaire de
conserver la cohérence de l'information (cache consistency) entre le cache et la
mémoire partagée, cohérence intimement liée à la conception du système de
communication (réseau en bus ou à étages multiples).
Pour les systèmes fortement couplés, les mémoires cache ont une forte influence
sur les performances du système ; leur conception s'écarte fortement de celles que
l'on rencontre dans les systèmes séquentiels. Le délicat problème de la cohérence de
l'information dans less parallèles sera évoqué au paragraphe 1.4.6. Le
lecteur intéressé pourra aussi consulter à ce sujet l'ouvrage [DECEGAMA 89].
1.2.4. Outil de structuration
Le parallélisme est sans aucun doute une technique qui apporte beaucoup de
simplifications à toutes les étapes d'un projet. Au niveau de la conception tout
d'abord, où le traitement parallèle est un outil remarquable pour structurer de vastes
projets logiciels, très souvent difficiles à organiser efficacement. Un logiciel
parallélisé apporte une réponse naturelle : les contributions de plusieurs équipes
indépendantes peuvent facilement être rassemblées pour construire un système
robuste. Cette démarche facilite la gestion de la phase de développement et les
procédures de test réalisées en parallèle sur différents modules. Ceci est tout
particulièrement vrai dans les applications temps réel où le parallélisme est
concrètement très présent. Il permet d'établir un lien direct entre la structure de
conception et la structure physique du système.
Des simplifications seront également sensibles au niveau des phases de
développement et de validation où l'intérêt de la structuration n'est plus à
démontrer.
Enfin, au niveau de la maintenance et de la portabilité, il sera appréciable,
lorsque l'on remplacera un dispositif par un autre, de ne voir affecté qu'un seul
module du système : seul le module chargé de piloter le composant sait comment
procéder. Tout autre module qui veut avoir accès aut doit passer par le
module qui le pilote (information hiding).
Pour une application programmée dans un langage tel que OCCAM, la
structuration logicielle peut être très étroitement liée à la structuration matérielle :
des composants séparés pourront être associés à des processus parallèles distincts,
tandi s que les connexions physiques seront directement affectées à des
interconnexions de canaux logiciels. 28 Informatique parallèle et systèmes multiprocesseurs
12.5. Adéquation au traitement temps réel
L e concepteur de systèmes temps réel est fréquemment confronté à
l'inadéquation de son outil (une machine monoprocesseur) au problème qu'il doit
résoudre (un ensemble d'événements simultanés qu'il faut contrôler, modéliser ou
simuler). Séquentialiser un problème temps réel pour le rendre exécutable par une
machine monoprocesseur, au lieu d'en exploiter le parallélisme naturel, est une
démarche de simplification qui se fait au détriment de la fidélité par rapport aux
phénomènes réels.
A l'inverse, si l'outil dont on dispose est une machine multiprocesseur, la
démarche consistera à représenter aussi fidèlement que possible le problème sous
forme d'un ensemble de processus parallèles, l'outil étant cette fois au service de la
méthode et non pas l'inverse ; un des grands attraits des machines parallèles est de
pouvoir traiter des algorithmes qui fournissent une représentation plus simple et plus
directe du monde réel que les machines conventionnelles.
La nécessité du traitement parallèle pour gérer un ensemble de processus de
production industrielle est suffisamment évidente pour qu'il ne soit pas nécessaire
d'argumenter. On remarque simplement à l'heure actuelle, en raison de la baisse du
coût des microprocesseurs, une tendance vers la généralisation de terminaux
"intelligents" tant dans le monde de l'informatique (imprimantes à microprocesseur,
par exemple) que dans celui de la production industrielle (capteurs, actionneurs
"intelligents"). Les systèmes d'instrumentation distribués en particulier bénéficient
de cette technique par une implantation des processeurs là où l'on en a besoin plutôt
que dans une salle de contrôle, ce qui ne peut que contribuer à une réduction des
coûts de connexion. Il n'y a donc rien d'étonnant à ce qu'une des motivations
majeures de la conception à la fois des transputers et de leur langage "natif
OCCAM , ait été la programmation en temps réel de systèmes intégrés. La
modélisation peut, elle aussi, s'appuyer avec profit sur cette technique : par exemple,
les phénomènes météorologiques peuvent être modélisés par un "découpage" de
l'atmosphère en grille de points selon une technique de type éléments finis. De très
nombreux phénomènes atmosphériques simultanés peuvent ainsi être modéusés sur
un système multiprocesseur comme l'ont fait Graham et Purnell sur un système à
transputers [GRAHAM 88].
Dan s le cas de calculs très complexes, comme les calculs de flux
aérodynamiques , décrivant par exemple les turbulences provoquées par le
déplacement d'un avion et faisant appel aux équations de Navier-Stockes, le
traitement parallèle s'avère non seulement mieux adapté à la modélisation de très
nombreux phénomènes éminemment simultanés, mais apporte la puissance de calcul
nécessaire à l'obtention des résultats dans un délai raisonnable.
Autre exemple de bonne adéquation au traitement en temps réel, un émulateur
d'interconnexion de réseaux peut prendre en compte les échanges d'information
entre deux réseaux locaux quelconques : il s'avère capable de simuler le
comportement de ponts, passerelles ou convertisseurs grâce à une mise en oeuvre sur
réseaux de transputers. La distribution des tâches parmi plusieurs processeurs permet
une juste simulation du comportement en temps réel du fait que les tâches de calcul
et d'affichage sont exécutées en parallèle pour ne pas freiner la simulation
proprement dite ; un superviseur, implanté sur un processeur spécifique, permet de
visualiser des "instantanés" de l'état du système et des données statistiques du trafic,

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin