Le SCM3IO13 (APP)

Le module SCM3IO13 (APP, Master Recherche): Algorithmique, performance et parallélisme

ATTENTION: les informations ci-dessous pouvant changer, n'oubliez pas de recharger ces pages.

Résumé

Ce cours propose un rappel des notions d'algorithme séquentiel et de performance asymptotique, puis une introduction à la conception et à l'analyse d'algorithmes parallèles en utilisant le modèle PRAM. Comme pour l'analyse des algorithmes séquentiels, les problèmes à résoudre sont formulés comme des relations entrée-sortie et proviennent des mathématiques discrètes. [La plupart ont aussi une version continue mais il n'en sera pas question dans ce cours car ils nécessitent soit une analyse poussée de leur stabilité numérique (cas d'une implantation en virgule flottante) soit des méthodes de parallélisation encore mal comprises (dans le cas d'une implantation par intervalles). ] Les problèmes de minimisation des communications seront abordés dans le contexte d'un raffinement du modèle PRAM appelé BSP. Les algorithmes résultants sont alors propres à des implantations dont les performances sont portables et extensibles. La programmation des algorithmes parallèles sera l'objet d'un cours d'option en semestre 4 du Master Recherche.

Format 2004-2005:

5 fois 3h de cours (dont 15 min de pause) selon le calendrier (prévu) suivant:

Jeu 7/10, 9-12h: Rappels d'algorithmique séquentielle. Le modèle PRAM.

Lun 11/10, 9-12h: Algorithmes PRAM élémentaires: maximalement parallèles et par blocs. Le théorème de Brent.

Lun 18/10, 9-12h: Algèbres de chemins.

Jeu 4/11, 9-12h: Algorithmes de tri. Le modèle BSP.

Lun 8/11, 9-12h: Algorithmes BSP, évaluation des performances.

Lun 22/11, 9-12h: Examen écrit, documents permis.

Matériel pédagogique

Rappels d'algorithmique [1998] rappels.ps
Page web du cours sur l'analyse des algorithmes séquentiels, IF5.05(B) [2002].
Chapitre d'introduction au modèle PRAM [4/10/2000] intro.ps
Chapitre sur les algèbres de chemin [24/10/2000] chemins.ps
Chapitre sur les arbres sous-tendants [25/10/2000]: ast.ps
Chapitre sur la contraction d'arbres [18/10/2000] contraction.ps
Chapitre sur le tri [25/10/2000]: tri.ps
Le modèle BSP [1/11/1999] bsp.ps
Paramètres BSP [4/2002] parametres-bsp.html
Sujets d'examens pour ce cours:
Répertoire contenant tous les fichiers du cours (compressé) app.tar

(*.ps: format postscript; *.txt: texte pur; *.sdw/*.sdc: star office writer; *.html: page web HTML; [...] dernière révision)

Références

Sur l'algorithmique séquentielle:
- T.H. Cormen, C.E. Leiserson, R.L. Rivest et C. Stein, Introduction à l'algorithmique 2ème édition, Dunod, 2004 (exemplaire à la bibliothèque du LIFO).
- G. Brassard et P. Bratley, Algorithmique. Conception et Analyse. Masson, 1987.
- A. Aho, J. Hopcroft et J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
Sur l'algorithmique parallèle:
- A. Gibbons et W. Rytter, Efficient Parallel Algorithms , Cambridge University Press, 1988. [Disponible à la bibliothèque de l'Université, section sciences, no.510.5.GIB.]
- J. JàJà, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
Sur les deux:
- L. Kronsjö, Computational Complexity of Sequential and Parallel Algorithms, John Wiley, 1985.
Sur l'algorithmique BSP:
- Les publications d'A. Tiskin: Université de Warwick (GB).
- Un tutoriel sur les algorithmes BSP par Jonathan Hill (Université d'Oxford).
Bibliographie longue du cours [24/10/2000] biblio.ps

L'URL de cette page est www.hains.org/scm3io13

Gaétan HAINS

Jeu 7/10, 9-12h:	Rappels d'algorithmique séquentielle. Le modèle PRAM.
Lun 11/10, 9-12h:	Algorithmes PRAM élémentaires: maximalement parallèles et par blocs. Le théorème de Brent.
Lun 18/10, 9-12h:	Algèbres de chemins.
Jeu 4/11, 9-12h:	Algorithmes de tri. Le modèle BSP.
Lun 8/11, 9-12h:	Algorithmes BSP, évaluation des performances.
Lun 22/11, 9-12h:	Examen écrit, documents permis.