Ordonnancement pour les nouvelles plates-formes de calcul
- Niveau : Master recherche
- Responsables : Denis Trystram (Denis.Trystram@imag.fr) and Pierre-François Dutot (Pierre-François.Dutot@imag.fr)
- Mots-clés : ordonnancement, multi objectifs, optimisation combinatoire
- Duration : 4 to 6 months
Responsables
Denis Trystram, Professeur Grenoble INP, LIG-MOAIS
Pierre-François Dutot, Maître de Conférences à l'UPMF
Contexte général
Le sujet proposé s'inscrit dans le contexte d'une bourse obtenue grâce à un "Google research award",
Description
L'objectif de ce master est de d'étudier et de développer de nouveaux algorithmes d'ordonnancement d'applications sur les nouvelles plates-formes de calcul en utilisant les méthodes d'analyse les plus récentes. L'accent sera mis sur les deux aspects suivants : optimisation sur des objectifs non conventionnels et optimisation multi-objectifs.
Le contexte applicatif est la gestion efficace des ressources (calcul, mémoire, communications) sur les plates-formes de calcul modernes (machines massivement parallèles multi-coeurs). Les développements considérables des dernières années a conduit à des plates-formes à grande échelle (grand nombre de "processeurs" connectés à distance), hiérarchiques avec des unités de calcul hétérogènes (processeurs classiques avec accélérateurs GPU). Ces nouvelles caractéristiques ont fait émerger de nouveaux espoirs pour les utilisateurs, mais aussi de nouveaux problèmes. Ainsi, les outils d'ordonnancement d'applications existants, largement utilisés, restent rudimentaires et souvent mal adaptés. En particulier, ils visent presque exclusivement à minimiser le temps d'exécution d'un ensemble de tâches.
La puissance toujours croissante des plates-formes de calcul a fait naître des besoins nouveaux pour les utilisateurs. C'est pourquoi il est devenu indispensable d'étudier également ce problème sous l'angle de l'optimisation multi-objectifs, pour répondre à des attentes souvent contradictoires.
L'approche proposée consistera à déterminer des modèles d'exécution appropriés, capables de prendre en compte les nouvelles caractéristiques de ces nouvelles plates-formes. On s'intéressera au calcul d'ordonnancements prédéterminés par des méthodes exactes pour certaines applications et à des algorithmes approchés à approximation garantie pour les problèmes plus généraux. L'ordonnancement dynamique des calculs sera également envisagé en tenant compte de contraintes identifiées pour cette nouvelle classe de problème.
Compétences requises
- Algorithmique, mathématiques discrètes, optimisation combinatoire.
- La connaissance du domaine de parallélisme est un plus, mais pas une condition nécessaire.
Cadrage
L'étude envisagée devra rester équilibrée entre la théorie (conception d'algorithmes, analyse des problèmes, approximation garantie), des développements-validations par simulation, et si possible, implémentation et tests en intégrant les outils développés en vraie grandeur au sein d'une infrastructure d'ordonnancement existante (dont le choix n'est pas encore fixé).
Le travail s'intègre au sein d'équipes bien reconnues disposant d'un support technique compétent pour tous les aspects liés au développement et de plusieurs plates-formes de calcul.