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 (15 octobre)
- 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 (17 octobre)
- notes du cours (re-mises à jour)
- l'article de Lenstra, Shmoys et Tardos d'où est tiré l'algorithme d'approximation pour R||Cmax
- Pour plus d'information sur P||Cmax (preuve de NP-complétude, borne de Graham, etc.) vous pouvez vous rapporter au chapitre 7 Scheduling du livre Parallel Algorithms par H. Casanova, A. Legrand, et Y. Robert chez CRC Press ou pour une version française au livre Algorithmique parallèle : cours et exercices corrigés par A. Legrand et Y. Robert chez Dunod (tous deux sont disponibles à la bibliothèque de l'ENS).
Cours 3: lundi 5 novembre, 16h
- Fin de la 2-approximation de R||Cmax (voir notes du cours précédent)
- Ordonnancement de tâches divisibles: notes du cours
Cours 4: mardi 13 novembre, 10h15
- Ordonnancement de tâches divisibles, réseau en arbre et distribution multi-tournées: notes du cours
DM: à rendre au plus tard le 9 décembre
- Sujet du DM, version française ou version anglaise
- Quelques questions qui m'ont été posées
à propos du DM:
- Pour la question 2, je demande simplement comment prédire les performances de calculs lorsque les transferts suivants ont lieu simultanément: A envoie des données à B et A envoie des données à C.
- Pour la question 3, il suffit de donner une (ou plusieurs) référence(s) à un (des) résultat(s) vu(s) en cours, éventuellement en le(s) justifiant.
Cours 5: mercredi 14 novembre, 8h
- Ordonnancement en régime permanent: notes du cours
- Documents: l'article de D. Bertsimas et D. Gamarnik sur le routage de paquets (première partie du cours) et l'article sur la seconde partie (Scatter).
Cours 6: lundi 19 novembre, 16h
- transparents du cours
- l'article sur l'instabilité de l'ordonnanceur EASY 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: mercredi 21 novembre, 10h15
- article sur l'ordonnancement multi-organisation sans coopération
- article présentant l'ordonnancement multi-organisation avec coopération
Cours 8: mercredi 28 novembre, 13h30, par Frédéric Vivien
- transparents du cours
Cours 9: lundi 3 décembre, 16h
- L'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 (pebble game).
- Un article J. Liu sur la version hétérogène de la minimisation de la mémoire dans le cas d'un arbre.
- Un article article récent avec la comparaison postorder/optimal sur les arbres de tâches.
Cours 10: mercredi 5 décembre, 10h15
- Un article d'ensemble sur les problèmes algorithmiques liés à la consommation énergétique.
- L'article fondateur de Yao, Demers et Shenkers sur la minimisation de l'énergie avec fréquences continues.
- Transparents sur la partie minimisation de l'énergie (Guillaume Aupy) et le rapport de recherche correspondant.
Cours 11: lundi 17 décembre, 16h
- Les notes [fr] du cours sur la gestion de cache (première partie)
- L'article pour la deuxième partie.
Cours 12: mercredi 19 décembre, 10h15
- 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.
Le rapport doit me parvenir au plus tard le 6 janvier. Les présentations auront lieu le vendredi 11 janvier entre 9h15 et12h15.
| article | étudiant |
A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities
| Vincent Despré |
|
Scheduling Parallel Task Graphs on (Almost) Homogeneous Multi-cluster Platforms
| |
|
Messages Scheduling for Parallel Data Redistribution between Clusters
| |
|
Hierarchical Work-Stealing
| Gabriel Radanne |
|
On Scheduling Dags to Maximize Area
| Thomas Lambert |
|
A Flexible Checkpoint/Restart Model in Distributed Systems
| Chloé Cahuet |
|
Probabilistic Allocation of Tasks on Desktop Grids
| Silviu Filip |
|
Analysis of Scheduling Algorithms with Reservations
| Jean-Florent Raymond |
Quelques outils de recherche bibliographique:
Les pages de ce cours pour les années précédentes : 2008/2009, 2010/2011 et 2011/2012.