Calcul parallèle et distribué, et Grilles de calculs
Cours de 3ième année IIC à Supélec
Stéphane Vialle
Ce cours est une
introduction aux architectures, middleware et environnements de calcul parallèle et
distribué (supercalculateurs, clusters et grilles), et un apprentissage
théorique et appliqué de leur algorithmique et programmation.
This course introduces the architectures and development
environments for parallel and distributed computing (supercomputers, clusters
and grids). It includes theoretical and practical learning of parallel and
distributed algorithm design and programming.
-
Contenu du cours :
- Notions d’architectures parallèles et distribuées : Les principales
étapes d’évolution des architectures MIMD, les enjeux économiques de la
construction des supercalculateurs, analyse des « ruptures » passées en
architecture de calcul intensif et des tendances actuelles.
- Bases d'algorithmique parallèle et distribuée : Partitionnement
statique par domaine, avec échange de frontières ou circulation de données,
recouvrement des calculs et des communications. Premières modélisation des performances
et analyse de résultats expérimentaux.
- Langages de programmation parallèles et distribués :
Principaux outils
de développement actuels sur architectures parallèles et distribuées modernes
(MPI, OpenMP, Grid-Services), tendance actuelles (JavaSpaces, Objets Actifs,
nouvelles bibliothèques objets de calcul intensif), et programmation d'accélérateurs SIMD (CUDA sur GPU).
- Modélisation, mesure et analyse de performances : Difficultés et
règles de mesure de performances. Modélisations et lois de Amdahl et de
Gustafson, et liens entre ces deux lois. Analyse de phénomènes
d’hyper-accélération.
- Algorithmique parallèle et distribuée avancée : Tris parallèles
réguliers et irréguliers, recherche de compromis entre rapidité et régularité.
Comparaisons théoriques et expérimentales. Equilibrage de charge dynamique,
mécanisme de work-pool, détection de terminaison de programmes
parallèles et distribués.
- Introduction au Grid computing : Motivations, enjeux
économiques, hétérogénéité
et volatilité des ressources, besoin de tolérance
aux pannes, incorporation dynamique de nouvelles ressources. Projets phares nationaux, Européens et mondiaux, et produits industriels.
- Intergiciels de Grilles : Introduction aux
concepts de base des intergiels de Grilles. Limites actuelles des intergiels de grille.
- Notions d’architectures parallèles et distribuées :
| Notes de cours : |
 |
2 slides par page |
|
3 slides par page |
|
6 slides par page |
- Bases d'algorithmique parallèle et distribuée :
| Notes de cours : |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
- Langages de programmation parallèles et distribués :
Notes de cours :
OpenMP |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
| Notes de cours : MPI-1 - comm bloquantes |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
| Notes de cours : MPI-1 - comm non-bloquantes |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
| Notes de cours : MPI-2 - spécificités |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
Notes de cours :
CUDA - introduction | | 2 slides par page | | 3 slides par page | | 6 slides par page |
Notes de cours :
CUDA - cluster de GPUs | | 2 slides par page | | 3 slides par page | | 6 slides par page |
Environnements de développement initialement conçus pour les machines parallèles et distribuées
| MPI-1 : |
|
Manuel de référence |
|
Errata |
| Documentation hyper-texte MPI-Pro : index.html |
| MPI-2 : |
|
Manuel de référence |
| OpenMP-1 : |
|
Manuel de référence pour C /C++ (1998)
|
| OpenMP-2 : |
|
Manuel de référence 2.0 pour C/C++ (2002) |
|
Manuel de référence 2.5 pour C/C++ et Fortran (unifié) (2005) |
| OpenMP-3 : |
| Manuel de référence 3.0 pour C/C++ et Fortran (2008) | | |
| CUDA-1.1: |
| Manuel de programmation en CUDA 1.1 |
| Compilateur CUDA "nvcc" |
|
| Bibliothèque CUBLAS |
| Bibliothèque CUFFT |
|
| Machine virtuelle PTX | | |
| CUDA-2.0: |
| Manuel de programmation en CUDA 2.0 |
| Manuel de référence de CUDA 2.0 |
|
| Bibliothèque CUBLAS |
| Bibliothèque CUFFT |
Environnements de développement initialement conçus pour le Grid-computing
- Modélisation, mesure et analyse de performances :
| Notes de cours : |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
- Algorithmique parallèle et distribuée avancée :
Tris parallèles,
notes de cours : |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
| Répartition dynamique par work-pool et détection de terminaison |
|
notes de cours |
| Expérimentations d'E/S parallèles (travaux anciens) |
|
notes de cours
(2 slides par page) |
|
notes de cours
(3 slides par page) |
- Grid computing :
Le cours de middleware de Virginie Galtier introduit une partie des concepts présents dans les middleware de grille, et une introduction au grid computing est disponible dans le cours de Système d'Information de Stéphane Vialle en 2A.
Par
conséquent, et par manque de temps, les grilles ne sont plus
abordées dans ce cours de 3A. Nous privilégions une introduction au
calcul scientifique sur GPU (ou "GPGPU") à partir de CUDA et CUDA+MPI.
Nous redonnons toutefois ci-dessous divers documents relatifs
au grilles.
Notes de cours étendues, d'une introduction au Grid
computing du cours de Système d'Information de
Stéphane Vialle en 2A. |
| 2 slides par page |
| 3 slides par page |
| 6 slides par page |
Anciennes notes de cours de Virginie Galtier :
Introduction aux grilles. |
|
2 slides par page |
|
3 slides par page |
|
6 slides par page |
Anciennes notes de cours de Virginie Galtier :
Middleware de grille. |
| 2 slides par page |
| 3 slides par page |
| 6 slides par page |
Exemples de middlewares :
Exemples de grands projets :
Séminaire de parallélisme (1 par an) :
| 2006-07 | Guillaume Mecheneau | Platform Computing | Adoption et adaptation du grid à la réalité de l'entreprise. |
| 2007-08 | Eric Mittelette, Eric Vernie | MicroSoft | Découvrir le développement parallèle sur Windows : De Win32 à PFx, de la station
de travail au Cluster CCS de calcul. |
| 2008-09 | Guy Chesnot | SGI | Systèmes de fichiers parallèles. |
| 2009-10 | Luigi Brochard | IBM | Power consumption and optimization |
Partage de mémoire
|
Implantation de barrières et écluses de synchronisation |
énoncé |
| Producteurs-consommateurs et lecteurs-rédacteurs en multiprocessus |
énoncé |
| Parallélisation de boucles en OpenMP |
énoncé |
| Envoi de messages |
Renumérotation d'un anneau de processeurs |
énoncé |
| Tri parallèle : Merge-Sort sur arbre de processeurs |
énoncé |
| Somme de distance dans un tore de processeurs |
énoncé |
| Relaxation de Jacobi à voisinage étendu sur barre de processeurs |
énoncé |
| Programmation par messages bloquants et non-bloquants |
énoncé |
| Réseau d'interconnexion |
Dimensionnement du réseau d'un cluster |
énoncé |
| Problèmes complets |
FFT sur cluster de PC bi-processeurs |
énoncé |
| Calculs et communications sur un cluster |
énoncé |
| Algorithme génétique sur un anneau de processeurs |
énoncé |
-
Bibliographie :
- Algorithmique parallèle et distribuée :
- G. S. Almasi and A. Gottlieb. "Highly parallal computing". The
Benjamin/Cummings publishing company, Inc. 1994, second edition.
- I. Foster. "Designing and building parallel
programs". Addison-Wesley publishing company. 1994.
- V. Kumar, A. Grama, A. Gupta, G. Karypis.
"Introduction to parallel computing". The Benjamin/Cummings publishing company.
1994.
- B.P. Lester. "The art of parallel programming".
Printice Hall. 1993.
-
Grid computing :
- I. Foster and C. Kesselman editors. "The
Grid 2: Blueprint for a New Computing Infrastructure". Morgan Kaufmann
publisher. 2004.
- F. Berman, G. Fox and T. Hey. "Grid Computing: Making the Global
Infrastructure a Reality". Wiley Series in Communications Networking and
Distributed Systems. 2003.
-
Programmation parallèle et distribuée :
- P.S. Pacheco. "Parallel programming with MPI". Morgan Kaufmann. 1997.
- R. Chandra, R. Menon, L. Dagum, D.
Kohr, D.
Maydan, J.
McDonald. "Parallel Programming in OpenMP". Morgan Kaufmann Publishers. 2000.
- Site web nVIDIA pour la programmation GPGPU en CUDA: http://www.nvidia.com/object/cuda_home.html