CR-07 : Ordonnancement

Programme de l’UE

L’ordonnancement est une branche de la recherche opérationnelle qui vise à allouer des ressources à un ensemble de tâches, et de planifier leur exécution dans le but d’optimiser une certaine fonction objective (temps d’exécution, rendement, etc). Dans ce cours, nous étudierons les problèmes d’ordonnancement présents dans les systèmes informatiques, et en particulier dans les plates-formes de calcul parallèles.

Nous commencerons par présenter des problèmes et techniques classiques en ordonnancement, puis nous introduirons progressivement des modélisations qui permettent de prendre en compte les spécificités des plates-formes de calcul actuelles tout en permettant de résoudre les problèmes d’ordonnancement. Nous présenterons enfin des objectifs propres à ces plates-formes, ainsi que les techniques employées pour résoudre les problèmes qu’ils soulèvent.

Plan du cours

  1. Approches classiques de l’ordonnancement
    • introduction et problèmes classiques (list scheduling, Smith ratio, etc.)
    • modélisation des applications (graphes de tâches, flow-shop, tâches malléables, etc.)
    • rappel de NP-complétude, algorithmes d’approximation
    • ordonnancement à la volée et non-clairvoyant
  2. Vers une modélisation plus réaliste des plates-formes de calcul introduction des coûts de communications
    • ordonnancement de tâches divisibles
    • ordonnancement en régime permanent
    • prise en compte de interférences calculs/communications
  3. Nouveaux objectifs et nouvelles techniques en ordonnancement
    • tolérance aux pannes, robustesse
    • réduction de la consommation d’énergie
    • ordonnancement multi-organisation
    • apports de la théorie des jeux
    • approche stochastique
    • ordonnancement multi-critère

Toutes les techniques exposées seront abondamment illustrées par des études de cas.

Modalités d’examen. L’évaluation consistera à une analyse et présentation d’articles. Certains cours seront d’ailleurs l’occasion pour les étudiants de pratiquer la lecture et l’analyse d’articles.

Pré-requis: il est souhaitable (mais pas indispensable) d’avoir suivi le cours d’Algorithmique Parallèle de M1. Des étudiants motivés peuvent s’en passer en lisant quelques chapitres importants du livre correspondant.

Intervenants

  • Loris Marchal, CR CNRS
  • Frédéric Vivien, DR INRIA