La partie « algorithmes data-parallèles » du cours AP en 2ème
année STI à l’ENSI-Bourges
ATTENTION: les informations ci-dessous pouvant changer,
n'oubliez pas de recharger ces pages.
Contenu du cours
Ce cours est une introduction aux concepts et techniques de base utilisés
pour l'écriture et la mise au point de programmes data-parallèles.
Ceux-ci constituent la base logicielle du calcul haute performance et sont
dorénavant utilisés dans les SGBD, la réalité virtuelle, les résolveurs de
contraintes et plusieurs autres domaines d'application, en
plus de leur utilisation courante en calcul
scientifique et simulation.
- Algorithmes élémentaires:
réduction, diffusion, échange total, calcul des préfixes, tri, opérations
matricielles etc. Analyse des temps de calcul par le modèle BSP: prévision
des temps sur les architectures existantes.
- Programmation de ces
algorithmes pour un simulateur séquentiel à partir de Caml. Structures
parallèles explicites, barrières de synchronisation. Estimation des temps
de calcul.
Une connaissance pratique du noyau fonctionnel du langage
Caml sera suffisante pour les exercices de programmation.
Format 2006-2007:
5 séances de CM et 5 séances de TD. Voir mon emploi
du temps.
Calendrier prévu:
|
Premier cours
|
Intro à CAML IF8.05(A)
(programmation fonctionnelle) : fonctions récursives, types, listes.
Algorithmes parallèles modèle PRAM (mémoire partagée) : diffusion
(broadcast), réduction (fold), préfixes parallèles (scan).
|
|
Deuxième cours
|
Algorithmes PRAM suite et fin : algorithmes par blocs
et réduction du nombre de processeurs. Rappels sur le langage CAML.
|
|
Troisième cours
|
Le modèle BSP: variante réaliste de la PRAM en mémoire
répartie. Modèle de performance et algorithme de base : broadcast, fold,
scan.
Programmation BSP en CAML : BSML. Opérations par, mkpar, apply, get et
put.
|
|
Quatrième cours
|
Suite sur les algorithmes BSP et leur programmation. Conditionnelle parallèle et algorithmes
itératifs.
|
|
Cinquième cours
|
Algorithmes plus complexes: tri-bulle, sample sort,
produit matrice-vecteur, jointure, conversion liste->tableau (list
ranking).
|
|
Quand ?
|
Examen écrit.
|
Matériel pédagogique
- Introduction aux
algorithmes parallèles et au modèle BSP
- Une introduction très
générale à l'informatique parallèle [1999]: introduction.ps
- Un exposé sur
l'efficacité des algorithmes parallèles, leurs applications et leur
programmation [6/2001]: polymtl2001
.
- Introduction aux
algorithmes parallèles (modèle PRAM) : intro_pram.ps
- [1/2001]: Paramètres BSP mesurés en 2000.
- Programmation des
algorithmes parallèles BSP en Objective Caml: BSML.
- Le langage séquentiel
hôte: ocaml. Voir le sous-module IF8.05(A).
- Deux articles
d'introduction à BSML
- High-level BSP programming:
BSML and BS-lambda sfp99
- Functional Bulk Synchronous
Parallel Programming using the BSMLlib Library cmpp2000-bsml.
- Simulation
séquentielle des opérations BSML [31/1/2002]: bsml.ml
- Exercices de
programmation en BSML [24/1/2002]: tp.html.
- Difficultés et
erreurs courantes en BSML [2001]: difficultes.html.
- Algorithmes BSML
solutions aux exercices utilisant les définitions ci-dessus [31/1/2002]: sol.ml
- Micro-projet de février 2001.
- Références et
articles
- Sur l'algorithmique
parallèle en général:
- 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.
- 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).
- Pages web et copies
électroniques d' articles
sur BSP: W. McColl, Université d'Oxford (GB).
- BSMLLib. Les
opérations BSML en ocaml, implantation parallèle. Compilateur
pour systèmes parallèles et mode interactif séquentiel. Pour suivre l'évolution de la
bibliothèque : les pages du projet CARAML.
- Sujets d'examens
incluant les années passées :
(*.ps: format postscript; *.ml programme Caml; [...]
dernière révision)
Evaluation
Examen final sur les deux sous-modules, celui de J-F Lalande sur la
programmation concurrente et celui-ci sur les algorithmes data-parallèles.
En cas de problème ou de questions, n'hésitez pas à écrire: mailto:Gaétan
Hains
L'URL de cette page est: http://www.hains.org/ap-ensib/index.html
Gaétan HAINS