DEA - Module ALPA : Algorithmique Parallèle
1999-2000
Intervenants
Sanjay Rajopadhye (Chercheur
CNRS), et Tanguy
Risset (Chercheur INRIA).
Horaire et lieu
Jeudi après-midi, 16h00 - 18h00, Salle Jersey
Resumé et Plan du cours
ALPA est un cours du tronc commun du DEA de
l'IFSIC. Les cours ont lieu par tranches de deux heures pendant 10
semaines. L'examen final aura une durée de 3h. En complément des cours aura
lieu une étude individuelle, appelée "approfondissement", qui prépare au
travail de recherche. Pour l'année 1999-2000, le sujet de l'approfondissement
est le pavage de boucle, une transformation de boucle utilsée pour augmenter
la localité dans les codes de calcul intensifs.
- 7 octobre (Rajopadhye): Notions de base du
parallélisme. La loi d'Amdhal. Le modèle PRAM, la
méthode de saute de pointeurs, le prefix parallèle. Voir le
chapitre 30 (sections 30.1 à 30.3) du livre Algorithms de
Cormen, Liserson et Rivest.
- 14 octobre (Rajopadhye): Le modèle PRAM suite:
Mésures de performances, le thèoreme de Brent, simulations entre algorithmes
PRAM.
- 21 octobre (Rajopadhye): L'analyse de scalabilité des
couples algorithmes/architectures (voir le tutorial de Kumar
et al.). Leur ouvrage Introduction to Parallel Computing publié
par Benjamin Cummings pourrait aussi être intéressant.
- 28 octobre (Rajopadhye): Le modèle BSP (Bulk
Synchronous Parallelism). La référence principale est Questions
and answers about BSP de Skillicorn, Hill et McColl (Scientific
Programming, 6(3): 249-274, Fall 1997). Le modèle a été proposé dans A
bridging model for parallel computation par Valiant dans "Communications
of the ACM" en août 1990 (v33 n8 p103). Il existe plusieurs sites donnant
plus d'infos comme celui maintenu
par McColl et un autre de nature tutoriel (même un
peu marketing :-). Il existe aussi un organisme BSP Worldwide des chercheurs et
utilisateurs du BSP.
- 4 novembre, 18 novembre (Rajopadhye): Parallélisation
automatique et le modèle polyédrique: analyse des dépendances, forme
d'assignation unique, systèmes d'équations récurrentes, ordonnancement et
détection de parallélisme, transformation des équations et génération du code
(voir ce papier de
Feautrier pour une introduction, qui merite d'une étude sérieuse).
- 25 novembre (1h) et 2 décembre (1h) (Rajopadhye):
Parallélisation automatique selon le modèle polyédrique (conclusion):
transformation des équations, le langage Alpha et sa compilation,
ordonnancement et détection de parallélisme. Pour un document decrivant les
contenus de ces deux cours, ainsi qu'un rappel des idées du cours de 18
novembre cliquez
ici. Voici les transparents sur le
langage Alpha et sa compilation, et voici un fichier .ps
avec quatre transps par page que vous pouvez imprimer.
- 2 décembre, 9 décembre, 16 décembre, 6 janvier (Risset):
Algorithmes parallèles avec modélisation du réseau
de communication: réseau lineaires (support de
cours pour les réseaux linéaires), grilles et
arbres, voir la section exercices
Des cours similaires sont enseignés à l'université du
caroline du nord, à IIT
Bombay, et bien sur, ailleurs.
Approfondissement
ALPA comprend une étude indépendente détaillée d'un sujet de recherche
contemporain. Vous démarerez de quelques références, puis selon vos
motivations irez en chercher d'autres pour vous faire une idée assez claire du
domaine de recherche considéré. Une partie de l'examen final sera basé sur
cette étude. Vous êtes fortement encouragés à travailler ensemble afin
d'échanger vos points de vue avec les autres étudiants et éventuellement avec
les enseignants. Il est aussi crucial que vous commenciez cette étude tôt car
c'est un travail de longue haleine qui ne pourra être fait au dernier moment.
Le pavage (partitionnement ou "tiling" en anglais) est un partitionnement
régulier d'un espace d'index représentant soit des calculs (par exemple,
l'espace d'itération d'un boucle imbriqueé), soit des données (par exemple, un
tableau disttribué à travers les processeurs d'une machine parallèle).
Originellement présenté dans le papier de F. Irigoin et R. Triolet [5] pour augmenter la granularité des calculs parallèles, le
pavage peut être utilisé pour plusieurs choses: exploiter la localité des
données dans les machines à hiérarchie de mémoire, optimiser les
communications par agrégation de messages, recouvrir les calculs et les
communications, réduire la latence, etc. Deux autres papiers décrivant la
transformation ont étés proposés par Schreiber et Dongarra [8] et Ramanujam et Sadayappan [7].
Xue [9] propose une bonne synthèse de ces résultats
précurseurs et de quelques extensions. Il y eu des travaux sur le choix des
paramètres du pavage (notament la taille et la forme des tuiles) pour
optimiser divers critères plus ou moins réalistes suivant le contexte dans
lequel le pavage est réalisé, notamment par Andonov et Rajopadhye [1], Hodzic et Shang [3], Ohta et al [6] (qui est beaucoup cité en dépit d'une erreur dans leur
theorème principal), ainsi que Hogstedt et al [4]. En
1998 le workshop Tiling for Optimal Resource
Utilization s'est tenu en allemagne la page correspondante contient
des liens vers d'autre références.
Votre étude d'approfondissement consistera en l'étude de l'optimisation de
la taille de tuile . La première tâche est d'étudier les papiers cités
plus haut (pas nécéssairement dans le détail, certains papiers en citent
d'autres). Comme mentionné précédement, il est fortement conseillé d'étudier
ensemble, et de discuter des lectures avec les autres étudiants et les
enseignants (en dehors des heures de cours)
Plus tard, sera posé dans le cours un problème relatif à l'optimization de
taille de tuile pour une application spécifique (relaxation de Jacobi sur des
grilles 1-D ou 2-D). Le problème de l'examen portera sur ce sujet spécifique
et sur les lectures ci-dessus.
Exercices
voici
quelques exercices pour les cours de T.Risset et
leur corrigés .
Voici les corrigés de
l'exercise sur l'analyse exacte de dépendances. Un exercise sur Alpha
utilisant les regles de
normalisation d'Alpha est aussi disponible.
Bibliographie du cours ALPA
1. F. Thomson Leighton, Parallel Algorithms and Architectures: arrays, trees,
Hypercubes. Un énorme pavé de 700 pages, dont le seul exemplaire
de la bibliothèque est pour le moment en ma possession et duquel je
tire l'essentiel des parties 2 et 3.
2. M. Cosnard et Denis Trystram, Algorithmes et architectures
parallèlesm InterEditions, 1993. Ouvrage général couvrant
la plupart des aspects du parallélisme.
3. P. Quinton et Y. Robert, Algorithmes et architectures systoliques,
Masson, 1989. Il commence à dater, mais la partie algorithmique et les
chapitres 11 et 12 sont toujours d'actualité.
4. V. Kumar, A. Grama, A. Gupta et G. Karypis, Introduction to Parallel
Computing, Benjamin Cummings, 1994. Ouvrage général, dont
l'exemplaire de la bibliothèque est pour le moment en ma possession.
5. P. Feautrier, Dataflow analysis of array and scalar references, dans
"International Journal of Parallel Programming", Fevrier, 1991 (volume 20,
numéro 1, pages 23-53).
Bibliographie pour l'étude d'approfondissement:
[1] Andonov et Rajopadhye, Optimal Orthogonal Tiling of
2-D Iterations dans Journal of Parallel and Distributed Computing,
septembre 1997 (pages 159-165)
[2] Desprez, Dongarra, Rastello et Robert,
Determining the Idle Time of a Tiling à paraître dans Journal of
Information Science and Engineering (Special Issue on Compiler Techniques for
High-Performance Computing) 1998.
[3] Hodzic et Shang, On Supernode Transformation with
Minimized Total Running Time dans IEEE Transactions on Parallel and
Distributed Systems, mai 1998 (pages 417-428)
[4] Hogstedt, Carter et Ferrante, Determining the Idle
Time of a Tiling dans 1997 ACM Symposium on the Principles of Programming
Languages, janvier 1997
[5] Irigoin et Triolet, Supernode Partitioning
dans 15th ACM Symposium on Principles of Programming Languages, janvier 1988,
(pages 319-328)
[6] Ohta, Saito, Kainaga et Ono, Optimal Tile Size
Adjsutment in Compiling General DOACROSS Loop Nests dans ACM
International Conference on Supercomputing juillet 1995 (pages 270-279)
[7] Ramanujam et Sadayappan, Tiling Multidimensional
Iteration Spaces for Multicomputers dans Journal of Parallel and
Distributed Computing, volume 16, numero 2, 1992 (pages 108-120)
[8] Schreiber et Dongarra, Automatic blocking of nested
loops Technical Report No. 90.38 RIACS, NASA Ames Research Center, août
1990
[9] Xue, On Tiling as a Loop Transformation dans
Parallel Processing Letters, , volume 7, numero 4, octobre (?) 1997 (pages
490-424)
Dernière modification de cette page :
