Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Un article des Communications of the Association for Computing Machinery :
La Renaissance du parallélisme
Article mis en ligne le 8 juillet 2010
dernière modification le 3 mars 2014
logo imprimer

Beautés et décadence du calcul parallèle

De 1960 à la fin des années 1980 le calcul parallèle fut un domaine de recherche actif, avec des débouchés industriels remarquables qui culminèrent avec les Connection Machines de Thinking Machines Corporation dont le premier modèle comptait 65 536 processeurs !

L’essor de ces développements passionnants fut brisé par les progrès de la micro-électronique : l’amélioration rapide des performances et de l’efficacité des microprocesseurs, au rythme prévu par la loi de Moore,
assurait la croissance de l’industrie et le développement des usages de l’informatique sans remettre en cause ni les logiciels existants ni les méthodes de programmation, alors que se convertir au calcul parallèle aurait exigé, outre des investissements matériels significatifs, des remises en cause intellectuelles et techniques considérables du côté de la programmation.

Année après année, les progrès des processeurs procuraient gratuitement les mêmes gains de performance que le dur labeur de parallélisation des programmes. Si paralléliser un programme prenait deux ans, ce délai procurait conformément à la loi de Moore un doublement de la densité des circuits, et les gains qui en résultaient.

Dans le numéro de juin des Communications of the ACM Peter
J. Denning
et Jack B. Dennis consacrent un point de vue dense et profond à la Renaissance du parallélisme. En effet les progrès techniques dont la loi de Moore rend compte commencent à atteindre des limites fixées par la physique : quand l’épaisseur du diélectrique des transistors se mesure en dizaines
d’atomes, on comprend bien qu’il va falloir trouver un autre moyen pour continuer à accroître la puissance de calcul. D’ailleurs les fréquences d’horloge n’augmentent plus guère.

Parmi les autres moyens envisageables pour accroître les performances, utiliser plusieurs processeurs (ou des processeurs multi-cœurs, ce qui revient au même) au lieu d’un semble une idée prometteuse. Il est aussi possible d’utiliser plusieurs ordinateurs qui se répartissent le travail, cela s’appelle une grappe (cluster), la liaison entre lesunités de calcul est moins intime que dans un multiprocesseur, les
problèmes à résoudre sont différents mais pas trop. Répartir une charge de travail entre plusieurs processeurs pose des problèmes de synchronisation et de coordination qui ne sont pas triviaux : cela s’appelle le calcul parallèle.

Idées nouvelles, idées anciennes

L’apparition des multiprocesseurs, des multi-cœurs et des clusters,
et leur corollaire, la réapparition du parallélisme, tombent dans un
océan d’oubli, et les ingénieurs et chercheurs de la nouvelle
génération redécouvrent des problèmes qu’ils croient
nouveaux. L’article de Denning et Dennis propose une brillante
synthèse des acquis du premier parallélisme, directement réutilisables
avec les nouveaux processeurs.

La première architecture multiprocesseurs fut celle du Burroughs
B5000
, lancé
en 1961 par une équipe sous la direction de Robert S. Barton. Le B5000 comportait
de nombreuses innovations significatives qui lui donnaient 20 ans
d’avance sur le reste de l’industrie :

- premier système d’exploitation écrit en langage évolué, Algol en
l’occurrence ;
- multiprocesseur à mémoire partagée et commutation crossbar ;
- architecture à pile ;
- jeu d’instructions réduit ;
- code automatiquement ré-entrant, etc.

L’apparition d’un multiprocesseur tel que le B5000 stimula la recherche
en parallélisme : en 1971 un groupe de chercheurs de Brown University et
de General Electric mirent au point un modèle d’environnement d’exécution parallèle qui serait parfaitement apte à résoudre des problèmes considérés aujourd’hui comme des défis pour la recherche.

Déterminisme du calcul parallèle

Le problème théorique central du calcul parallèle est celui du
déterminisme, qui demande qu’un réseau de tâches parallèles en mémoire
partagée produise toujours le même résultat à partir des mêmes
données, indépendamment des vitesses d’exécution respectives des
tâches. Un résultat majeur de la recherche dans ce domaine est le
théorème du déterminisme, qui donne une condition suffisante pour
garantir le résultat. En voici l’énoncé :

- une tâche est un calcul élémentaire qui réalise l’application d’une
fonction à des arguments pour produire un résultat ;
- deux tâches sont dites en conflit si l’une d’elles modifie une
cellule de mémoire utilisée par l’autre ;
- dans un système de tâches concurrentes, des situations de
compétition (race conditions) peuvent survenir qui feraient
que le résultat du calcul dépende des vitesses d’exécution relatives
des différentes tâches ;
- le déterminisme du calcul est garanti si le système est soumis à la
contrainte que, pour chaque couple de tâches en conflit, l’ordre
d’exécution soit toujours le même pour tout calcul du système.

Programmation fonctionnelle et composition de programmes parallèles

Il résulte du théorème du déterminisme exposé ci-dessus un corollaire
selon lequel un programme constitué de tâches concurrentes implanté
sans recours à l’opération d’affectation au moyen d’un langage de
programmation fonctionnel sera, de façon inhérente (« gratuitement »),
déterministe, puisque chaque tâche délivre son résultat à son
successeur sans interférence entre leurs zones mémoire respectives.

On consultera avec profit la thèse que Francis Dupont a consacrée à une implantation parallèle du langage fonctionnel CAML, disponible sur ce site ici :

Thèse de Francis Dupont
Parallel CAML

Les chercheurs en systèmes parallèles avaient un autre sommet à
atteindre : la composition de programmes parallèles, c’est-à-dire
l’établissement des conditions auxquelles un programme parallèle
peut être incorporé, sans modification, à un programme parallèle
plus grand. Il faut pour cela satisfaire trois principes :

- masquage de l’information : l’état interne d’une tâche ne doit pas
être accessible à une autre tâche ;
- indépendance du contexte : une tâche ne doit pas dépendre de valeurs
extérieures à sa mémoire locale ;
- non-interférence des arguments : si deux tâches concurrentes
accèdent à la même donnée, aucune des deux ne doit la modifier.

Les langages de programmation fonctionnels satisfont automatiquement
ces trois principes ; leurs modules sont donc, de façon inhérente,
composables.

Tous les problèmes ne relèvent pas de solutions déterministes ; les
systèmes transactionnels en sont l’illustration : une place dans un
avion ne peut être réservée qu’une fois, et ce sera par la tâche la
plus rapide. Comment construire des systèmes parallèles par
composition de modules dont certains ne sont pas déterministes,
voilà une question ouverte.

Mémoire virtuelle et abandon des fichiers

La mémoire virtuelle n’est pas juste une astuce technique pour
faciliter le rangement des objets : en découplant la programmation
de la gestion de la mémoire, elle procure un écran d’abstraction
et un mécanisme centralisé d’accès aux données qui débarrasse les
modules des lourdeurs qui seraient des obstacles à leur composition
parallèle.

Le système Multics a démontré, dans les années 1960, qu’il était
possible, de façon efficace, d’implanter toutes les données, tant
persistantes que temporaires, dans un espace-adresse unique. Chaque
donnée y a une adresse, et la persistance est un attribut facultatif.
Cette conception ouvre la voie à la disparition des fichiers, cette
plaie de l’informatique, héritée de la mécanographie, et qui rend
tout incompréhensible au profane.

Multics est venu trop tôt pour réussir, il coûtait trop cher sur
des ordinateurs trop gros et pas assez puissants. Aujourd’hui la
voie est ouverte aux systèmes parallèles persistants sans fichiers,
qui formeront l’informatique de demain.


Forum
Répondre à cet article
La Renaissance du parallélisme
Francis Dupont - le 12 juillet 2010

Deux remarques :

- il faut ajouter « massivement » devant parallèle dans ton article
sinon tu rentres en conflit avec le parallèlisme restreint avec
un petit nombre de processeurs (4-8) que nous connaissons bien ;
- le problème du déterminisme (ou plus exactement de la sémantique séquentielle) est plus compliquée que tu le décris, en effet le résultat d’un calcul est une valeur sémantique, càd il faut ajouter dans l’espace des valeurs l’indéfini (noté bottom, le T à l’envers).

Pour prendre un exemple canonique, il y a 4 opérateurs or :
or gauche, or droit, or strict et or parallèle, avec comme tables
de vérité (bottom, faux, vrai)

(les cas « intéressants » sont bottom et vrai pour les arguments).

Pour résumer or gauche évalue l’argument de gauche (le premier) puis
celui de droite, l’or droit commence par celui de droite, l’or strict
évalue d’abord les deux arguments (note que dans la plupart des langages
de programmation les fonctions sont toujours strictes mais que certains
opérateurs ou constructions ne le sont pas, le ’if’ est l’exemple
canonique. Au passage f() stricte si f(bottom) = bottom, cf Jean
Vuillemin). Enfin l’or parallèle évalue ’en parallèlé les deux arguments
et retourne vrai si au moins l’un des deux est vrai.

Pour revenir à la sémantique séquentielle elle interdit bien sûr l’or
parallèle. Bien sûr un langage de programmation parallèle pour avoir
une sémantique séquentielle, cf. ma thèse de doctorat (sur parallel CAML).

Mon opinion maintenant que j’ai changé plusieurs fois d’activité reste
que le non-déterminisme rend la programmation très difficile à mettre au
point et quasiment impossible avec le parallélisme massif. D’où
l’intérêt d’une sémantique séquentielle qui est une propriété plus forte.

Je peux en rajouter mais le plus simple est que tu lises ma thèse (j’ai
le DVI (elle est en latex, y compris les dessins) sur mes machines).

À plus

Francis.Dupont@fdupont.fr



pucePlan du site puceContact puceEspace rédacteurs puce

RSS

2004-2017 © Site WWW de Laurent Bloch - Tous droits réservés
Site réalisé sous SPIP
avec le squelette ESCAL-V3
Version : 3.87.35