Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 10
Parallélisme, taxinomies et classifications
Année 2002-2003

Sachant
qu'un terrassier creuse un trou cubique d'un mètre de côté
en une heure,
combien
de temps mettront 50 terrassiers pour creuser le même trou ?
Auteur inconnu
10.0 PRÉSENTATION
Ce chapitre et les trois suivants
traitent du parallélisme explicite entre processeurs ou entre données.
Les formes plus modestes du parallélisme ou parallélisme
fin,
pipelines (flot unique d'instructions),
chemins de données (plusieurs octets d'un même flot), superscalaire
ont été traités précédemment.
Ce chapitre contient :
10.1 une introduction
générale;
10.2 quelques informations sur
les
modes de programmation;
10.3 des repères
historiques qui n'étaient pas dans le chapitre 1;
10.4 la présentation
de plusieurs
taxinomies;
10.5 l'état actuel des
taxinomies et des classifications;
10.6 les caractères
généraux du parallélisme.
10.1.
QU'EST CE QUE LE PARALLÉLISME EN INFORMATIQUE ?
C'est une organisation et des
techniques de réalisation telles que des travaux (pris dans le sens
le plus général) y sont exécutés en simultanéité.
Le but est de faire plus vite les mêmes travaux ainsi que de faire
des travaux plus longs ou plus complexes.
|
Le parallélisme
caractérise
l'organisation matérielle
et les techniques de mise en œuvre.
En découle une simultanéité
qui caractérise
les processus exécutés
sur des machines dotées de parallélisme.
|
|
Le parallélisme et la
simultanéité qui en découle ont des degrés.
On distingue, allant du détail
au global :
-
les bits traités simultanément
par 8, 12, 16, 32 ou 64 dans les bus, les registres, les unités
fonctionnelles;
-
les données traitées
par collections petites, grandes ou très grandes dans les machines
dites vectorielles;
-
les instructions décodées
en concomitance dans un pipeline;
-
la prise en compte de plusieurs
instructions à la fois (VLIW);
-
les instructions exécutées
simultanément dans un processeur superscalaire;
-
la gestion des entrées et
sorties pendant que le processeur continue à opérer;
-
plusieurs processeurs traitant des
parties d'une même tâche;
-
plusieurs processeurs traitant des
tâches différentes.
Il existe aussi des simultanéités
apparentes quand on exécute sur un processeur unique :
-
des miniprocessus (threads);
-
des tâches différentes
(multitâche);
-
des travaux indépendants
(multiutilisateur);
Depuis peu (2003) il existe une
simultanéité apparente quand un seul processeur est vu comme
deux, technique nommée «hyper
threading» par Intel.
Plus largement encore, un site
de la toile a proposé en 1996 [MER96]
de contribuer à la recherche de nombres premiers. Le visiteur se
voit proposer une tranche de nombres à explorer et un logiciel à
charger. Le logiciel s'exécute ensuite en tâche de fond et
cherche les nombres premiers dans la tranche. Des milliers d'ordinateurs
dans le monde recherchent simultanément des nombres premiers.
10.2.
POURQUOI LE PARALLÉLISME ?
Nous venons de voir que
les machines série qui respectent plus ou moins strictement le schéma
de Neumann incorporent du parallélisme à des degrés
divers. Néanmoins les traitements y sont faits sur un seul processeur.
La rapidité de traitement dépend alors à la fois de
la rapidité de commutation des circuits, de la vitesse de transport
des données et de divers temps de latence.
Pour fixer les idées,
une cadence d'exécution, et non une fréquence d'horloge,
de 100 millions d'instructions par seconde correspond à une instruction
exécutée chaque 10 ns. Le GHz d'exécution, soit un
milliard d'instructions par seconde est attendu vers 2004.
Pour ce qui est de la
vitesse de déplacement des données, les limites sont très
différentes.
La célérité
de la lumière dans le vide, limite absolue, est d'environ 30 cm/ns.
La célérité
de l'électricité dans le fil de cuivre est inférieure
à 20 cm/ns, dans un conducteur de qualité moyenne elle est
de l'ordre de 15 cm/ns. Elle est bien moindre quand le signal parcourt
des circuits, environ 1 cm par nanoseconde.
On
pourrait penser que 100 millions à un milliard d'instructions par
seconde suffisent pour traiter les problèmes humainement concevables.
Il n'en est rien. Au moins deux grandes classes de problèmes demandent
un traitement plus rapide. Ce sont :
-
des simulations et modélisations
parce qu'elles sont basées sur des approximations successives et
que plus petite est la largeur de la maille, plus grand est le nombre de
calculs et plus précis est le résultat;
-
des traitements de grandes
quantités de données :
-
des traitements de signaux
comme l'analyse sismique;
-
le traitement de l'image
animée;
-
l'animation d'images de
synthèse;
-
les accès multiples
aux bases de données.
En termes concrets, citons
:
-
la modélisation du
climat et la circulation des océans;
-
la modélisation des
fluides turbulents (mécanique statistique);
-
la modélisation des
semi-conducteurs et des supraconducteurs;
-
la dispersion de la pollution;
-
la gestion du code du génome
des êtres vivants;
-
la chromodynamique quantique
en physique fondamentale;
-
la simulation des systèmes
explosifs et en combustion.
Tous demandent une rapidité
de calcul que les ordinateurs série actuels et du futur prévisible
n'atteignent pas. La figure ci-dessous résume quelques unes de leurs
caractéristiques.
Plusieurs de ces thèmes
seront vus à nouveau comme domaines d'application des processeurs
de traitement du signal.
Vue en ultra grand angle
de l'IBM «Blue Pacific» (1998)
1464 nœuds de 4 processeurs
POWER, 3.9 TeraFlops, 2.6 TB de SDRAM et 75TB de RAID.
10.3 LE PASSAGE AU PARALLÉLISME
EST UN CHANGEMENT IMPORTANT
La fabrication des machines parallèles
est simple. Leur mise en œuvre est difficile comme on le verra dans le
chapitre
12.
Une tâche de grande dimension
peut toujours être exécutée pas à pas. Il se
peut qu'on puisse la décomposer en tâches plus petites exécutables
simultanément.
La simultanéité
est d'exécution pour une tâche est réalisable en :
-
décomposant le travail à
faire en tâches de moindre importance;
-
confiant ces tâches à
des processeurs différents pour qu'ils les exécutent simultanément;
-
coordonnant ces opérateurs;
-
prenant soin de ne pas décomposer
le travail en tâches si petites qu'il serait plus rapide de les exécuter
plutôt que d'expliquer au processeur ce qu'il doit faire.
La mise en œuvre du parallélisme
est courante dans le monde du travail. Le taylorisme a consacré
son apparition en termes d'organisation bien que le travail simultané
soit présent depuis des temps immémoriaux. En matière
informatique, on trouvera plus loin quelques repères
historiques relatifs à l'apparition des idées et des
réalisations.Les différences et ressemblances entre machine
série et machine parallèle constituée
d'une collection de processeurs qui coopèrent et communiquent pour
traiter le problème, sont résumées
dans le tableau suivant.
|
Ordinateur série
|
Ordinateur parallèle
|
Technique |
le processeur unique est
conçu pour être le plus rapide possible;
la performance est atteinte
avec une mémoire et des bus à bandes passantes élevées.
|
on utilise de nombreux processeurs
pour exécuter des parties d'un même travail. La performance
de chacun n'est pas cruciale;
on doit sommer les résultats.
|
Avantages |
il accepte la programmation
séquentielle bien connue;
il y a 40 ans d'expérience
en compilation et outils de développement;
les entrées et sorties
sont simples.
|
on atteint la capacité
à traiter des problèmes insolubles avec un ordinateur série;
me rapport coût/efficacité
de chaque processeur est plus petit;
on peut utiliser des systèmes,
mémoire, disques et bandes propres à chaque processeur;
le tout est extensible ou
peut l'être (scalability);
des composants nouveaux
peuvent être intégrés.
|
Limitations |
un processeur à très
grandes performances est très cher;
sa climatisation est indispensable;
ses performances sont toujours
limitées.
|
les techniques de programmation
nouvelles doivent être apprises;
les programmes séquentiels
ne sont pas efficaces;
les compilateurs et autres
outils ne sont pas mûrs;
les entrées et sorties
sont complexes à maîtriser.
|
Le calcul parallèle
va nécessiter :
-
des opérateurs ou
processeurs nombreux;
-
un ou des liens entre eux;
-
des outils spéciaux
pour gérer le calcul en parallèle en termes de
-
de système d'exploitation;
-
de compilateurs;
-
des outils de programmation
pour gérer les communications et la coordination des processeurs;
-
un algorithme particulier
et un programme qui le réalise; décomposition du problème
en morceaux, que plusieurs opérateurs peuvent traiter simultanément.
-
des processeurs particuliers
pour certains usages.
|
Dans la plupart
des cas,
l'algorithmique spécifique
aux machines parallèles
présente une
difficulté conceptuelle.
|
|
Les processeurs
pour le traitement du signal sont présentés dans le chapitre
13.
Questionnaire
Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 10
Parallélisme, taxinomies et classifications
Année 2002-2003

