Previous Up Next

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 : 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
Note that extensive lecture notes are handed out at the beginning of the class.






Previous Up Next