SAR4: Algorithmique parallèle et répartie

Responsable:

Prérequis:

Objectif:

Programme:

1. Introduction aux architectures parallèles et réparties :
   • motivations (mémoire, speed-up),
   • paradigmes (SIMD, MIMD, ...),
   • architectures de machines,
   • réseaux d'interconnexion (point-à-point ou switches),
   • promesses des réseaux locaux
2. Problèmes de communication structurées (diffusion, commérage,...)
3. Interblocage
4. Modèles du parallélisme : PRAM, BSP, ...
5. Algorithmique parallèle :
   1. cas régulier : parallélisme de données (ex traitement de matrices)
   2. cas irrégulier : parallélisme de contrôle (ex Branch and Bound)
6. Algorithmique répartie : élection, routage, horloges logiques, résistance aux pannes...
7. Environnements de programmation et langages : passage de messages (RPC, PVM, MPI, ...), ou data-parallèle HPF (High Performance Fortran), Pratique de PVM.
8. Systèmes multi-threads : Nexus, PM2, ... Introduction au placement et à l'équilibrage de charge dynamique.
9. Applications - Exemples : calcul scientifique, simulation, traitement d'images ...

Contenu des TD:

Bibliographie:

• Designing and Building Parallel Programs by Ian Foster Addison-Wesley, 1995 ISBN 0-201-57594-9
• PVM: Parallel Virtual Machine - A Users' Guide and Tutorial for Networked Parallel Computing. Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, and Vaidy Sunderam MIT Press (1994)
• Initiation au Parallélisme Concepts, Architectures et Algorithmes. Marc Gengler, Stéphane Ubéda, Frédéric Desprez. Manuels Informatiques MASSON, ISBN 2-225-85014-3
• Distributed Operating Systems. Andrew Tanenbaum - Prentice Hall, 1995 pages 648, ISBN 0-13-219908-4

Dernière mise à jour : février 1999