Algorithmique et architectures parallèles
Cours de base (30 h de cours, 30h de TD)
Cours : Yves Robert (Yves.Robert)
TD : Emmanuel Agullo, Cédric Tedeschi (Emmanuel.Agullo, Cedric.Tedeschi)
Présentation
“Killer micros, killer nets, killer apps”, le parallélisme
est parmi nous, pour les très riches avec les
super-calculateurs-multiprocesseurs vectoriels, et pour les moins
riches avec les réseaux de stations de travail ou piles de PC,
reliées par un réseau dédié rapide ou par un
simple Ethernet.
Mettre en oeuvre le parallélisme impose de repenser les
applications, donne une nouvelle dimension à l'algorithmique,
et nécessite de prendre en compte les paramètres clés
de l'architecture cible. Ce cours propose une introduction
approfondie aux concepts et techniques de l'algorithmique
parallèle, en relation étroite avec le modèle
d'architecture considéré.
On commence par les modèles théoriques (PRAM, BSP) et la complexité. On étudie quelques
algorithmes parallèles simples pour des machines à mémoire partagée et à mémoire
distribuée. On dépassera rarement le produit de matrices ou les plus longs chemins dans un graphe,
mais que de complications! La hiérarchie mémoire, le surcoût des communications, l'équilibrage
de charge, tout se conjugue pour modifier en profondeur les algorithmes usuels.
Plan
Quelques sujets abordés dans ce module :
-
PRAM et complexité
- tri fusion
- Mémoire partagée
- vectorisation, hiérarchie
mémoire, algorithmes
d'algèbre linéaire par blocs
- Mémoire distribuée
- réseaux d'interconnexion,
macro-communications, algorithmes d'algèbre linéaire
- Ordonnancement
- graphe de tâches et heuristiques classiques
- Architectures spécialisées
- introduction aux techniques de
parallélisation automatique
Organisation
Le cours est organisé selon le schéma hebdomadaire
suivant :
-
2h de cours;
- 2h de travaux dirigés;
- Deux devoirs à la maison (conception, analyse
et mise en oeuvre d'un
algorithme parallèle).
La note de contrôle continu est obtenue à partir de ces
devoirs. Un partiel et un examen final sont organisés en
milieu et en fin de semestre.
Bibliographie
-
V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to
Parallel Computing, The Benjamin/Cummings Publishing (1994).
- A. Legrand et Y. Robert, Algorithmique Parallèle: Cours et
Exercices Corrigés, Dunod, 2003
Note that extensive lecture notes are handed out at the beginning of the
class.