Sauf mention contraire, les documents présentés sur cette page sont en anglais, au format PDF.
Présentation du cours: transparents
Cours 1: Introduction à l'ordonnancement, ordonnancement sur une machine (14 septembre)
- notes du cours
- transparents [ppt] de l'exposé "Complexity of scheduling" par Peter Brucker, lors d'EPIT 2007
- une classification très complète des problèmes d'ordonnancement: Complexity results for scheduling problems
Cours 2: Ordonnancement sur machines parallèles (21 septembre)
- notes du cours
- Les cours sur P||Cmax et les ordonnancement de liste d'où proviennent la plupart des résultats vus en cours
Cours 3: Ordonnancement de tâches divisible: réseau de type bus et étoile (28 septembre)
Cours 4: Ordonnancement de tâches divisible: réseaux hiérarchiques (arbres) et ordonnancement à plusieurs tournées (5 octobre)
- notes du cours
- un rapport de recherche avec la plupart des résultats vus en cours sur les tâches divisibles
DM: Interference aware scheduling
- Devoir à rendre pour le 19 octobre. Ce devoir est facultatif, il ne sera pris en compte dans la notation que s'il est favorable à l'étudiant.
- Télécharger le sujet avec les questions et l'article "Interference-Aware Scheduling", de B. Kreaseck, L. Carter, H. Casanova, J. Ferrante et S. Nandy.
- Erratum : Dans la question 2, il fallait lire "Quelle méthodologie les auteurs proposent-ils pour prévoir les performances des calculs lorsque A envoie des données à B et C ?"
- notes du cours
- l'article de D. Bertsimas et D. Gamarnik sur le routage de paquets (première partie du cours)
- un article pour une opération de distribution de paquets (proche de la seconde partie du cours mais sans calcul)
- un rapport de recherche très complet pour l'ordonnancement de graphes de tâches en régime permanent
Cours 6: Dynamicité des plates-formes et robustesse des ordonnancements (19 octobre)
- notes du cours ou transparents (même contenu)
- l'article sur l'instabilité de l'ordonnanceur backfilling en présence de rafales de tâches
- l'article sur les ordonnancements maximisant le nombre de tâches prêtes (Internet-based Computing)
- l'article sur l'utilisation d'information ancienne pour l'ordonnancement
Cours 7: Ordonnancement en-ligne (3 novembre)
- slides à venir, voir la page du cours de l'an dernier (lien ci-dessous)
Cours 8: Ordonnancement multi-organisations (16 novembre)
- article sur l'ordonnancement multi-organisation sans coopération
- article présentant l'ordonnancement multi-organisation avec coopération
- Un article de S. Toledo sur la multiplication de matrices et la minimisation du nombre de communication (partie 2.1)
- L'article de R. Sethi (1973) sur le problème d'allocation de registre (version homogène).
- Un article J. Liu sur la version hétérogène de la minimisation de la mémoire dans le cas d'un arbre.
- Notes [fr] sur la partie gestion d'un cache de pages
- Transparents sur la partie minimisation de l'énergie (Guillaume Aupy) et le rapport de recherche correspondant.
- Ce cours est inspiré du chapitre "Algorithmic Game Theory and Scheduling" dans le livre "Handbook of Approximation Algorithms and Metaheuristics", (éditeur T. F. Gonzales, Chapman & Hall/CRC). Ce livre est disponible à la bibliothèque de l'ENS Lyon (espace Laurent Schwartz, cote I.2.6/GONZ). Je peux en fournir des copies si besoin.
- Des transparents [ppt] sur le même sujet, par un des auteurs du chapitre ci-dessus (version pdf).
Examen final
L'évaluation finale de ce module est une étude bibliographie, sur un article de recherche (fourni). Chaque étudiant doit choisir un article dans la liste ci-dessous, en m'envoyant un mail. Il doit écrire un rapport présentant l'article et le commentant (de 4 à 8 pages), puis le présenter devant la classe (20 minutes de présentation + 10 minutes de questions).
Si vous souhaitez une version papier de l'article choisi, envoyez-moi un mail, je laisserai une impression pour vous dans mon casier.
Note :
Quelques-uns des articles sont un peu longs, avec beaucoup de preuves. Dans ce cas, il n'est pas demandé de présenter ou de connaître le détail de toutes les preuves.
Quelques outils de recherche bibliographique:
Les pages de ce cours pour les années précédentes : 2008/2009 et 2010/2011.