Ordonnancement centré sur les utilisateurs
- Niveau : Master recherche
- Responsable : Denis Trystram (Denis.Trystram@imag.fr)
- Mots-clés : ordonnancement, multi-utilisateurs, multi-objectifs
- Durée : 4 à 6 mois
Responsables
Daniel Cordeiro, chercheur à l’université de Sao Paolo, Brésil
Denis Trystram, Professeur Grenoble INP, LIG-MOAIS
Description du sujet
Il est aujourd'hui acquis que les modèles de calcul actuels sont fortement distribués et à large échelle. Une des raisons de la popularité de ces nouveaux supports d'exécution est la facilité d'installation et leur relativement faible coût. A contrario, il y a peu d'outils d'exploitation disponibles (communications efficaces, équilibrage de charge, etc.) laissant inutilisée une grande partie de la puissance potentielle.
Le problème de l'utilisation optimisée des systèmes parallèles et distribués est un sujet qui motive à l'heure actuelle de très nombreuses recherches de par le monde. Des solutions acceptables existent pour des objectifs usuels communs pour tous les utilisateurs, il convient d’étudier des solutions avec des objectifs plus diversifiées et surtout, avoir la possibilité de considérer un grand nombre d’objectifs simultanément.
Le sujet de master de recherche que nous proposons ici consiste à développer une méthode d’optimisation où chaque utilisateur possède son propre objectif. Cette méthode sera analysée du point de vue théorique, implémentée et testée à partir d’un simulateur construit sur des logs d’exécutions réelles. La méthode développée sera évaluée avec des indicateurs de performance pour algorithmes multi-objectifs (Hyper-volume, epsilon-indicateur, etc.) et devra garantir une certaine équité entre les utilisateurs.
Il est possible de construire une approximation de la courbe de Pareto où les objectifs sont triés selon un ordre lexico-graphique, par exemple en utilisant la méthodologie introduite par Papadimitriou et Yannakakis à FOCS en 2000, mais cette méthode est difficile à généraliser à un grand nombre d’objectifs. Un premier travail théorique (effectué récemment) existe, il établit des bornes d’inapproximabilité dans le cas où les utilisateurs ont le même objectif, mais portant sur leurs propres jobs :
- - E. Saule and D. Trystram. Multi-users scheduling in parallel systems. Proceedings of the 2009 IEEE International Parallel and Distributed Processing (IPDPS 2009).
On dispose également d’un générateurs d’instances pour tester les algorithmes.
Les résultats attendus sont la conception et si possible l’analyse d’algorithmes garantis.