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 efficaces et leur mise en œuvre pratique.
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 séances de cours seront accompagnées de six séances de TDs et de six séances de TPs. Les TPs auront pour but l’initiation à la programmation parallèle par passage de messages (MPI).

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.
– 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 et d’un devoir à la maison de programmation.

Intervenants