Le cours présente les méthodes permettant la
construction de programmes
parallèles performants sur des architectures distribuées:
machine multicores ou multiprocesseur SMP, grappe ou cluster de multiprocesseurs,
grille formée de l'interconnexion de plusieurs grappes.
Une partie importante du cours concerne l'algorithmique
parallèle dont l'objectif
est d'extraire le parallélisme maximal d'un problème tout
en conservant un
nombre d'opérations total proche des meilleurs algorithmes
séquentiels.
Une fois ce parallélisme dégagé, les algorithmes
d'ordonnancement permettant de répartir l'exécution sur
les ressources
sont présentés; basiquement, les ressources sont
supposées identiques,
mais le cours aborde aussi l'ordonnacement sur des ressources
hétérogènes et en nombre dynamiquement variable.
Le cours illustre la mise en oeuvre de tels algorithmes sur des
interfaces de programmation standard (threads Posix et
bibliothèques de
communication).
En complément au cours, les étudiants étudient,
au choix,
soit l'analyse et la programmation parallèle d'une application
de leur choix, soit un article de recherche (au choix dans une liste
d'articles proposés)
auquel est associé une question.
Les étudiants
doivent rédiger un rapport de 4 pages : soit descriptif de
l'analyse, soit une réponse à la question).
Ce travail est présenté par l'étudiant dans un
exposé de 15' avec 5' de questions.
Evaluation du cours: exposé (coef 1/3) et examen
écrit (coef 2/3).
Questions sur les articles : Clicker ici !
Planning 2007-2008
Le cours a lieu le vendredi en salle F321 - 13h30 - 16h45
aux dates suivantes (avec des slots de remplacement possible):
- S1 12/10 JL Roch
- S2 19/10 JL Roch
- S3 26/10 JL Roch / D Trystram
- S4 9/11 V Danjean
- S5 16/11 T Gautier
- S6 23/11 B Raffin
- S7 30/11 JL Roch / D Trystram
- 7/12 (slot de remplacement)
- 14/12 (slot de remplacement)
- 21/12 (slot de remplacement)
- 4/1 (slot de remplacement)
- S8 11/1 [tous: presentation des articles/programmes]
- 18/1: examen (?)
Cours 1 : Introduction à la programmation
parallèle
Transparents du cours (pdf)
Compléments:
Cours 2 : Algorithmes parallèles - SMP / Sans
prise
en compte des communications
Transparents du cours (pdf) 1.
Algorithmes en cascade
2. Grain adaptatif
Compléments:
Cours 3 : Algorithmes parallèles - Fin cascade
et Prise
en compte des communications (1)
- Exemples de cascades : Fusion et tri:
- Fusion par cascade (en n, puis log n, puis loglog n)
- Tri par seaux en log n
- Prise en compte des communications Transparents du cours (pdf)
- Modélisation des communications
- Ordonnancement avec communications. Distribution et
regroupement de données
- Exercice: FFT
- Produit de matrices
- Comparaison de différents algorithmes pour le produit de
matrices
Transparents du cours (pdf)
- Compléments:
Cours 4 : Ordonnancement par liste et clustering
(Denis Trystram)
- Défintions et classification; complexité
théorique du problème.
- Algorithmes de type glouton et borne de Graham;
- Approche récursive type top-down ; work-stealing
- Approche par regroupement de tâches, type bottom-up ;
clustering
- Problème d'allocation: analogie avec le packing.
- Transparents du cours.
Cours 5 : Mise en oeuvre d'algorithmes parallèles
(Jean-Francois Mehaut)
- Architectures parallèles d'aujourd'hui et de demain
- Programmation des architectures à mémoire commune
- Programmation des grappes de multiprocesseurs
- Transparents du cours
<>
Cours 6 : Applications interactives et importance des
communications globales
Bruno Raffin
- Simulation interactive distribuée. Exemple de la
plateforme Grimage.
- Algorithmes de communication globale sur modèle
linéaire (Bruno Raffin)
- Transparents:
Cours 7 : Complexité parallèle -
Problèmes P-complet
(Denis Trystram et Jean-Louis Roch)
Cours 8 : Exposé d'articles ou de programmes
A compléter ...
Autres références utiles pour le cours :
Archives - Années antérieures