Parallélisme et Distribution

Objectifs Généraux

Être capable de "penser parallèle" dès la spécification d'une application jusqu'à sa mise en œuvre efficace dans un environnement de calcul multi-processeurs (à mémoire partagée ou non).
Avoir acquis les connaissances et concepts de base minimum pour affronter sereinement la "révolution du multi-coeur" en tant que développeur logiciel

Calcul haute performance
Architectures parallèles, Supercalculateurs, Grilles de calcul
Modèles théoriques du parallélisme (PRAM, Machine à tri)
Mesures de performance, passage à l'échelle, prise en compte des modèles de mémoire
Modèles classiques d'expression du parallélisme (maitre/esclaves, diviser pour régner, Map-Reduce)
Algorithmes parallèles classiques (Max-préfixes, tris, algèbre, imagerie ...)
Langages ou bibliothèques standard (openMP, MP)
Quelques algorithmes distribués (Jacobi, Produit Matrice-Vecteur,...)

14h de cours (7 séances de 2h)
14h de TD (7 séances de 2h)
14h de TP (7 séances de TP)
Il n'y a pas de transparents pour ce cours, tout se fait à l'ancienne, avec craie, feuille et crayons.

Introduction au Parallélisme
- Architectures, classification de Flynn
- Loi de Moore
- Machines Parallèles
- Logiciels pour le Parallélisme
Formes de Parallélisme
- Parallélisme de données, de contrôle et de flux
- Exemple de modèle : Map-Reduce
- Introduction à Open-MP
PRAM et efficacité
- Lecture-écriture
- Exemples d'algorithme : calcul du maximum en parallèle
- Notion d'efficacité parallèle
- Calcul des préfixes en parallèle (SCAN)
Réduction de travail et tri sur PRAM
- Principe de Brent
- Beta-reduction logarithmique
- Tri par rang en parallèle
- Tri fusion parallèle (Cole)
Réseaux de tri
- Tri bitonique
- Tri fusion (Batcher)
Programmation Distribuée, introduction à MPI
- Types de communication
- Exemple : pipeline bloquant
- Topologie virtuelle en anneau
- Modèle de coût des communications
- Introduction à MPI
Algorithmes distribués sur anneau
- Broadcast simple
- Scatter
- All-to-All
- Broadcast avec pipeline
Produit matriciel
- Produit matrice-vecteur sur anneau
- Produit matrice-matrice sur anneau
- Produit matrice-matrice sur grille 2D (Cannon)
Limites du parallélisme
- Loi de Amdhal
- Loi de Gustafson-Barsis
- Iso-efficacité
Autre modèle de programmation distribuée : Map-Reduce
- Exemples d'algorithmes simples (Wordcount, average, PageRank...)
- Mise en pratique : Hadoop

Parallel Algorithm, Henri Casanova, Armaud Legrand, Yves Robert, Chapman & Hall, 2008.
Algorithmique Parallèle, Cours et exercices corrigés, Arnaud Legrand, Yves Robert, Dunod, 2003, compléments sur http://mescal.inria.fr/membres/arnaud.legrand/algopar (tres bien fait, bien que nous ne nous servons que de tous petits extraits)
A Grama, A. Gupt, G. Karpys, V. Kumar, Introduction to Parallel Computing (2nd edition), Addison Wesley 2003. (en partie ici www-users.cs.umn.edu/~karpys/parbook )
P.S. Pacheco. "Parallel programming with MPI". Morgan Kaufmann. 1997.
R. Chandra, R. Menon, L. Dagum, D. Kohr, D. Maydan, J. Mc_Donald. "Parallel Programming in openMP". Morgan Kaufmann Publishers. 2000. Voir aussi www.openmp.org