Le cours présente les méthodes permettant la
construction de programmes
parallèles performants sur des architectures distribuées:
machine 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).
Planning 2005-2006
Le cours a lieu le mercredi en salle C04 - 9h45 - 12h45
Semaines: 41, 42, 43, 44, 45, 46, 47, 48 possibilite de remplacement
semaine 49
Questions sur les articles : Clicker ici !
Cours du 12/10/2005 : Introduction à la programmation
parallèle
Transparents du cours (pdf)
Compléments:
Cours du 19/10/2005 : Algorithmes parallèles - SMP / Sans
prise
en compte des communications
Transparents du cours (pdf) 1.
Algorithmes en cascade
2. Grain adaptatif
Compléments:
Cours du 26/10/2005 : 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
Compléments:
Cours du 2/11/2005 : Algorithmes parallèles - Prise
en compte des communications (2)
Cours du 9/11/2005 : Applications de simulation distribuée
(Thierry Gautier, Bruno Raffin)
Cours du 16/11/2005 : Ordonnancement par liste et clustering
(Denis Trystram)
Cours du 23/11/2005 : Complexité parallèle -
Problèmes P-complet
(Jean-Louis Roch)
- Modèles théoriques:
- PRAM EREW, CREW, CRCW.
- Modèles circuits booléens et
arithmétiques. Uniformité. Liens avec les modèles
de programmation.
- Classes EREW^k, NC^k, AC^k.
- NC-1 réduction
- Applications: la classe DET
- Problèmes P-complets
- Caractérisation d'un programme séquentiel
polynomial.
- MCVP est P-complet
- Exemple: recherche en profondeur d'abord. Ensemble
indépendant lexicographique. Compression par Lempel-Zipf. Pivot
de Gauss.
- Parallélisation systématique
- Evaluation d'expressions [Brent]
- Evaluation de circuits arithmétiques (straight-line
programme) [Kaltofen-Miller-Ramachandran]
- Applications: la classe DET
Cours du 30/11/2005 : Exposé d'articles ou de programmes.
Autres références utiles pour le cours :
Archives - Années antérieures