Ordonnancement
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Frédéric Vivien (Frederic.Vivien)
Les besoins croissants en puissance de calcul, et le
coût prohibitif des ordinateurs parallèles, ont entraîné l'émergence
de nouvelles plates-formes de calcul, distribuées à plus ou moins
grande échelle, et le plus souvent hétérogènes (grappes de grappes,
grilles, etc.). Cette évolution des plates-formes de calcul n'a bien
évidemment pas entraîné une simplification des problèmes qui étaient
déjà difficiles dans le cadre d'un parallélisme « régulier ».
Comment, dans ce cadre, pouvons nous décider où (placement) et quand
(ordonnancement) exécuter les différents calculs constitutifs d'une
grosse application de calcul scientifique ?
Dans ce cours, après avoir rappelé des résultats et techniques
classiques en ordonnancement, nous présenterons deux techniques de
relaxation de la problématique de l'ordonnancement (modèles des
tâches divisibles et ordonnancement du régime permanent), nous
étudierons la modélisation des réseaux d'interconnexion ainsi que
l'impact de la nature de ces réseaux sur la complexité du problème,
et nous aborderons le problème de la gestion de la dynamicité, tant
au niveau de l'application que de la plate-forme (ordonnancement à
la volée, robustesse, équilibrage de charge, etc.).
Bibliographie
-
R. G. Parker. Deterministic Scheduling Theory. Chapman and
Hall, 1995.
- P. Chrétienne et E. G. Coffman. Scheduling Theory and its
Applications. J. Wiley and Sons. 1995.
- P. Brucker. Scheduling Algorithms. Springer, 1998.