DEA - Module ALPA : Algorithmique Parallèle
2000-2001
English version
of this page
Intervenants
Sanjay Rajopadhye (Chercheur
CNRS), et Tanguy
Risset (Chercheur INRIA).
Horaire et lieu
Jeudi 10h00 à 12h00, 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.
-
semaines 1, 2 et 3 (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.
Mésures de performances, le thèoreme de Brent, simulations entre
algorithmes PRAM. Voir le chapitre 30 (sections 30.1 à 30.3) du livre
Algorithms de Cormen, Liserson et Rivest.
-
semaines 4, 5 et 6 (Rajopadhye) :
Parallélisation automatique selon le modèle
polyédrique . Ce papier
de 12 pages en Francais (qui a quelques ereurs qui seront corrigées dans une version
anglaise à paraître) explique la méthode sans rentrer dans trop de
détails.
- Cours de la
sémaine 4 (.html), pour un fichier .ps (x4) clicquez
ici. Notions mathématiques de base : les boucles à contrôle affine,
les polyèdres, la représentation duale, les équations recurrentes, l'analyse
éxacte de flots de données (qui est basé sur ce papier de
Feautrier); voir aussi l'example du cours en détail.
- Cours de la
sémaine 5, partie motivation (format .html), pour un fichier .ps (x4) clicquez
ici. : Le langage Alpha, sa syntaxe, sémantique, et les
transformations de programmes, (partie 2, en .html),
pour un fichier .ps (x4) clicquez ici.
Pour les sémaines 5 et 6, voir aussi ce papier). En
plus, voici les règles
de normalization des programmes Alpha, qui seront utile pour faire ces exercises
- Cours de la
sémaine 6 (.html): Compilation et parallélisation d'Alpha. Pour un
fichier .ps (x4) clicquez
ici
-
semaine 7, 8, 9 et 10 (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 hypercube. Algorithmes
de routage, complexité des primitives de communications sur
différentes architectures.
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.
Des cours similaires sont enseignés à l'université du
Caroline du Nord, à IIT
Bombay, et bien sur, ailleurs.
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.
Cliquez ici
Pour avoir plus de détails sur le sujet de cette année, ainsi que les "regles
de jeux".
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).
6 Cormen, Leiserson, Rivest, Introduction à l'algorithmique, Dunod 1994
(chapitre 30), Une très bonne référence en général.
Dernière modification de cette page :
