Mesures de performance
- Ê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.
- Bonne connaissance de C
- Connaissance des algorithmes classiques (recherche dans un tableau, tris)
- Connaissance de base en architecture des ordinateurs et en système
- Environnement de développement C avec support OpenMP et MPI
- 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
TD1 (Sémaphores)
TD2 (Parallélisme)
TD3 (Simulation)
TD4 (Tri)
TP1 (Multithread en Java et C)
TP2 (introduction à OpenMP) et quelques résultats expérimentaux
TP3 (OpenMP et Préfixe Parallèle)
TP4 (Sections Parallèles)
Projet OpenMP IFI-SI : Sous-séquence Maximale
Projet OpenMP MAM : Ligne de vue
TP5 (MPI)
TP6 (Broadcast et produit Matriciel)
TP7 Map-Reduce
IFI-RIF : Projet - Produit Matriciel Distribué
SI4-MAM4 : Produit Matrice Vecteur
Examens
Examen 2010-2011
Examen 2014-2015