Algorithmique et Programmation Parallèle et Distribuée

Cours du M1 2015-2016, premier semestre.

Programme de l’UE :

Le parallélisme est devenu incontournable en informatique, le moindre
processeur étant multi-cœurs. Cette UE a pour objet la conception
d’algorithmes parallèles et distribués efficaces, et aborde leur mise
en œuvre pratique sous forme de TPs.
Les séances de cours auront pour objet les modèles théoriques utilisés
pour la conception et l’analyse des algorithmes et l’étude de
problèmes algorithmiques particuliers (complexité, définition et
analyse d’algorithmes, algorithmes d’approximations, etc.).
Les quatorze séances de cours seront accompagnées de sept séances de
TDs et de sept séances de TPs. Les TPs auront pour but l’initiation
la programmation parallèle et distribuée par passage de messages
(MPI). Un petit projet de programmation est organisé sous forme de
devoir à la maison.

Plan indicatif des cours :

  • Modèle théorique des réseaux de tri
  • Modèle théorique des PRAMs
  • Algorithmique sur anneau et grille de processeurs: produit matrice-vecteur,
    produit matrice-matrice, stencil 2D, etc.
  • Algorithmique distribuée: modèles, élection, consensus, détection de
    terminaison
  • Ordonnancement de graphes de tâches avec et sans communications,
    avec ou sans contraintes de ressources: complexité, algorithmes
    d’approximations et heuristiques
  • Analyse de dépendance et parallélisation automatique
  • Exemple d’algorithme pour GPU

La note de contrôle continu est établie à partir d’un partiel organisé
en milieu de semestre, du devoir à la maison de programmation, et d’un
examen final.