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 18 septembre 2018

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 les unité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.