Algorithmique Parallèle

A.LEGRAND - Y.ROBERT

Un vieux proverbe de l'Ouest assure qu'il est plus facile de conduire un attelage avec deux b\oeufs qu'avec mille poulets. Faire coopérer un grand nombre de processeurs du commerce, agencés en grappes et reliés par un réseau plus ou moins rapide, s'avère en effet nettement plus complexe que d'utiliser un supercalculateur Cray monolithique, encombrant et ruineux. Mais c'est tellement plus amusant! En plus c'est l'avenir, alors pourquoi se priver du plaisir de l'algorithmique parallèle? Notre objectif est de proposer aux étudiants, chercheurs et enseignants un outil pédagogique complet pour la découverte (accompagnée ou autonome) de l'algorithmique parallèle. Ce livre se veut original à plusieurs titres: sa structuration, sa thématique, et son contenu. Ce livre est édité par les Éditions Dunod.

Structuration

Nous calquons la structure du livre sur le schéma de l'enseignement universitaire qui alterne cours magistraux et travaux dirigés. Chaque chapitre est divisé en trois parties: (i) une partie cours; (ii) une série d'exercices constituant une séance type de travaux dirigés; (iii) la correction détaillée de ces exercices. Par ailleurs, nous maintenons une page concernant le livre sur la toile, à l'adresse
http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar
Cette page contient un grand nombre d'exercices complémentaires, tirés de sujets de devoirs, de partiels ou d'examens; ces exercices, tous corrigés, sont classés selon les différents chapitres du livre. Régulièrement maintenu (avec notamment une liste d'erreurs répertoriées), le site web constitue un utile prolongement au livre. Nous sommes persuadés de l'intérêt d'inclure les corrigés des exercices, surtout pour une découverte en autodidacte du domaine. Mais nous ne saurions trop conseiller au lecteur de passer du temps à essayer de trouver les réponses aux questions posées avant d'aller lire les solutions. L'expérience montre qu'on ne se souvient vraiment que de ce que l'on a vraiment cherché!

Thématique

Au cours des trente dernières années, le calcul parallèle a évolué très vite, trop vite pour pouvoir en suivre les derniers développements technologiques: à peine sorties sur le marché, les machines sont obsolètes, alors ne parlons pas des livres qui parlent des machines! Il n'empêche, les concepts restent, et nous voulons les faire découvrir. L'algorithmique parallèle emprunte beaucoup à l'algorithmique classique dans sa problématique: conception, analyse, étude de complexité. Les résultats sont quelquefois moins précis, car les problèmes sont plus récents, et aussi plus difficiles. Fondamentalement, il y a quand même une nouvelle dimension, un degré de liberté supplémentaire avec l'exploitation simultanée de plusieurs ressources. On peut identifier un c\oeur de connaissances fondamentales, largement indépendantes des détails architecturaux. Nous décrivons dans les pages qui suivent des modèles, des algorithmes et des techniques (ordonnancement, compilation) qui ne seront pas obsolètes dans trois ans (c'est une promesse), ni dans dix ans (c'est une profession de foi!). Le calcul parallèle a connu, disions-nous, une évolution rapide. Il faudrait ajouter chaotique, avec des hauts (la résolution annoncée des grands défis scientifiques dans les années quatre-vingt) et des bas (faillites successives de constructeurs). Il se trouve que nous sommes actuellement en haut de la vague: le parallélisme est omniprésent, et ce aux deux extrémités du spectre. Au niveau microscopique, les processeurs multiplient les unités arithmétiques pipelinées sur un même circuit intégré. Au niveau macroscopique, on interconnecte les stations de travail en grappes pour construire des supercalculateurs à peu de frais: Killer micros, killer nets, killer apps. On interconnecte même les grappes en grappes de grappes pour construire la grille de métacalcul mondiale. Difficile de passer à côté du parallélisme dans ces conditions!

Contenu

On ne trouvera pas dans ce livre une introduction générale au calcul parallèle. Disons simplement qu'il y a deux raisons fondamentales de faire travailler plusieurs ressources en parallèle: (i) résoudre un même problème plus vite (typiquement pour diminuer un temps de réponse) et (ii) résoudre un problème de plus grande taille (en utilisant plusieurs ressources de calcul, et un espace mémoire plus important qu'avec un seul processeur). On peut combiner ces deux schémas, par exemple pour résoudre dans un temps imparti un problème de taille maximale (on trouve le matin les résultats d'un calcul lancé la veille au soir). Pour une présentation du domaine, nous renvoyons au livre de Gengler, Ubéda et Desprez [4] (excellente initiation au parallélisme, en français), ou à ceux de El-Rewini et Lewis [3], (calcul parallèle et distribué, en anglais) et Culler et Singh [1] (architectures parallèles, en anglais). Tous les chapitres sont largement indépendants, qu'ils traitent de modèles, d'algorithmique, de techniques de pipeline ou de compilation-parallélisation. Tous les chapitres peuvent être lus séparément. Sauf difficulté exceptionnelle, toutes les démonstrations sont incluses. Les notes bibliographiques donnent au lecteur des pointeurs sur les développements les plus intéressants, tandis que le site web déjà mentionné fournit des liens sur les articles les plus récents.
Voici en détail le contenu de chaque chapitre.

Partie 1: Modèles

C'est une partie théorique certes, mais les modèles, même éloignés de la réalité, sont indispensables pour bâtir les fondements d'une discipline.
Chapitre 1: Machines P-RAM.
Ce chapitre traite des machines P-RAM. P-RAM signifie Parallel RAM, un modèle où les processeurs peuvent accéder simultanément à une (grosse) mémoire commune en une unité de temps, sans payer de coût de communication. Le chapitre propose d'abord des exemples d'algorithmes simples, mais se poursuit sur la machine à trier de Cole: pour trier par tri-fusion deux suites de taille $n$ en temps $O(\log n)$, et comme il y a $\log n$ étapes de fusion, il faut savoir faire la fusion en temps constant! Pas facile du tout, mais très joli.

Nouveaux documents:

 
Chapitre 2: Réseaux de tri.
Ce chapitre aborde les réseaux de tri, un autre modèle de calcul classique, moins général que les P-RAM, mais plus réaliste, du moins si l'on considère qu'un circuit spécialisé pour le tri peut avoir un intérêt pratique. On commence par le réseau de tri-fusion de Batcher, qui fait le pendant de la machine P-RAM de Cole du chapitre précédent, et on finit par le réseau de transposition pair-impair et ses variantes.

Nouveaux documents:

 
Chapitre 3: Ordonnancement.
Ce chapitre présente quelques résultats élémentaires pour l'ordonnancement des graphes de tâches. On considère d'abord un modèle très simple, où les coûts de communications sont négligés: le problème sans limitation de ressources est polynomial, tandis que celui à ressources bornées est NP-complet, et résolu de manière sous-optimale à l'aide d'heuristiques de listes. On passe alors à un modèle plus réaliste, où les coûts de communication sont pris en compte: la difficulté s'accroît notablement, car même le problème sans limitation de ressources devient NP-complet.

Partie 2: Algorithmique parallèle

Quelques grands classiques! On prend un algorithme bien connu, comme le produit de deux matrices ou la décomposition LU, et on le tord dans tous les sens sur un anneau, une grille 2D, un hypercube, ou encore une grappe de processeurs hétérogènes. Le but est d'analyser les facteurs qui limitent l'efficacité (déséquilibrage de charge, coût des communications, inactivité forcée due aux dépendances), et de mener des analyses de complexité, ou de scalabilité.
Chapitre 4: Algorithmique sur un anneau de processeurs.
La topologie la plus simple va nous permettre de concevoir et d'écrire nos premiers algorithmes parallèles, sans rien connaître aux architectures de machines. On commence par les primitives de communications globales, et on enchaîne sur le produit matrice-vecteur. Même sur un anneau, l'algorithmique peut se compliquer, comme le prouvent les exemples de la transformée en distance et de la décomposition LU.

Nouveaux documents:

 
Chapitre 5: Communications et routage.
On décrit quelques réseaux d'interconnexion classiques, et les mécanismes de routage les plus usuels. Deux études de cas sont approfondies: l'analyse des propriétés topologiques de l'hypercube, et l'étude de plusieurs algorithmes pour la multiplication de deux matrices carrées, tous destinés à s'exécuter sur des grilles toriques 2D de processeurs.

Nouveaux documents:

 
Chapitre 6: Équilibrage de charge pour plate-forme hétérogène.
Ce chapitre présente quelques algorithmes parallèles destinés à s'exécuter sur un réseau de stations hétérogène, i.e. dont les processeurs travaillent avec des vitesses différentes. Autant l'équilibrage de charge 1D reste facile (nous revisitons les algorithmes sur l'anneau du chapitre 4, autant l'équilibrage de charge 2D s'avère complexe (retour au produit de matrices du chapitre 5). Le chapitre se poursuit avec l'étude du produit de matrices sur un réseau hétérogène: l'équilibrage de charge redevient facile, puisqu'on peut toujours configurer le réseau en un anneau virtuel, mais l'impact des communications doit être pris en compte. Le chapitre se conclut avec l'étude du paradigme maître-esclave, revisité dans un contexte hétérogène.

Partie 3: Pipelines et techniques de compilation

Peu de parties de l'ordinateur ont résisté à la pipelinisation (désolé pour ce néologisme!). Dans cette partie, nous décrivons le fonctionnement des unités arithmétiques pipelinées, qui ont conduit à l'avènement des ordinateurs vectoriels. Nous faisons un détour par les mémoires-cache pour expliquer pourquoi l'algorithmique doit désormais se concevoir par blocs. Nous présentons brièvement les architectures systoliques et leur synthèse: le pipeline y est exploité dans toutes ses dimensions. Le dernier chapitre est consacré aux techniques de compilation, dont l'importance va aller grandissante avec l'arrivée de microprocesseurs dotés de multiples unités de calcul. Le parallélisme doit d'abord être détecté, à partir de l'analyse des dépendances dans le programme, puis le code doit être transformé pour faire apparaître des boucles parallèles.
Chapitre 7: Pipelines et calcul vectoriel.
Nous expliquons le principe du pipeline des opérations arithmétiques et des accès mémoire; l'enchaînement de ces pipelines est à la base du fonctionnement des calculateurs vectoriels. Les techniques de réutilisation des registres et des données présentes dans le cache ont un impact déterminant sur la conception des algorithmes, et nous l'illustrons à l'aide de nos exemples favoris (produit de matrices et décomposition LU). Le chapitre se conclut par une brève discussion des techniques de parallélisation pour machines à mémoire partagée.
Chapitre 8: Architectures systoliques.
Intégrer plusieurs centaines de multiplieurs et d'additionneurs sur un même circuit intégré, c'était le rêve des architectures systoliques il y a vingt ans! La technologie n'a pas suivi, mais les algorithmes systoliques sont bien présents dans les processeurs spécialisés. Nous en décrivons brièvement quelques-uns, mais surtout nous présentons l'approche qui permet leur synthèse semi-automatique: on retrouvera les méthodes de transformation temps-espace dans l'étude des techniques de compilation.
Chapitre 9: Nids de boucles.
Ce chapitre est consacré aux techniques d'extraction du parallélisme dans les nids de boucles imbriquées. On commence par l'analyse de dépendance, et les différentes abstractions des dépendances. On poursuit par la présentation des algorithmes classiques de transformation de code: distribution/fusion de boucle et algorithme d'Allen-Kennedy, transformations unimodulaires et algorithme de Lamport.

Remerciements

Le contenu de ce livre a été enseigné au magistère d'informatique et de modélisation de l'ENS Lyon, à la majeure d'informatique de l'École Polytechnique, et au cours CS594 de l'université du Tennessee à Knoxville. Merci à tous les étudiants pour leurs commentaires et réactions diverses. Le choix des travaux dirigés et des exercices s'appuie sur une base de données constituée au fil des ans: merci à Olivier Beaumont, Emmanuel Jeannot et Fabrice Rastello, pour avoir posé les premières pierres de cet édifice. Les chapitres 3 et 9 sont largement issus du livre Scheduling and Automatic Parallelization, dont les auteurs sont Alain Darte, Yves Robert et Frédéric Vivien [2]. Merci à Alain et Frédéric pour cette excellente source :-) Merci aussi à Frédéric Desprez, à qui nous avons emprunté plusieurs paragraphes du chapitre 5, et à Fabrice Rastello (une seconde fois), dont la thèse a fortement inspiré le chapitre 6. Enfin, nous remercions tous ceux qui ont relu un ou plusieurs chapitres avant le tirage final: Vincent Boudet, Philippe Combes, Vincent Danjean, Laure Danthony, Samuel Hym, Jean-Yves L'Excellent, Clément Ménier, Philippe Raoult, Nicolas Schabanel et Frédéric Suter.
Arnaud Legrand et Yves Robert


mailto:Arnaud.Legrand@imag.fr
http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/

mailto:Yves.Robert@ens-lyon.fr
http://perso.ens-lyon.fr/yves.robert/

Bibliographie

1
D. E. Culler and J. P. Singh.
Parallel Computer Architecture: A Hardware/Software Approach.
Morgan Kaufmann, San Francisco, CA, 1999.

2
A. Darte, Y. Robert, and F. Vivien.
Scheduling and Automatic Parallelization.
Birkhaüser, 2000.

3
H. El-Rewini and T.G. Lewis.
Distributed and parallel computing.
Manning, 1997.

4
M. Gengler, S. Ubéda, and F. Desprez.
Initiation au Parallélisme.
Masson, 1996.


Arnaud Legrand
2005-11-04