Ordonnancement sous contraintes
- Niveau : Master recherche
- Contacts :
- Frédéric Wagner, MdC INP, frederic.wagner@imag.fr
- Mots-clés : ordonnancement, restriction d'ensemble de processeurs
- Durée : 4 à 6 mois
Description du sujet
La programmation parallèle est une activité complexe nécessitant de nombreuses compétences. En particulier, la répartition des différents travaux sur les différentes ressources forme un problème souvent difficile, auquel cherche à répondre la théorie de l'ordonnancement. Parmi les nombreux problèmes d'ordonnancement existants, nous nous intéressons ici au problème chaque machine ne peut exécuter l'ensemble des tâches disponibles mais uniquement un sous-ensemble particulier. Ce problème nous intéresse par exemple, lors d'ordonnancement de codes mixtes fonctionnant sur CPU et/ou GPU. Une autre utilisation envisageable vise l'exécution sur plates-formes distribuées dans le cas où les logiciels requis ne sont pas disponibles sur toutes les machines. Ce problème est étudié dans la littérature sous le nom de "scheduling with processing set restrictions" ou encore "scheduling for multi-purpose machines".Objectif du stage
L'objectif du stage est de proposer de nouveaux algorithmes d'approximation pour le problème considéré. Les algorithmes pourront être génériques ou cibler plus spécifiquement les problèmes pratiques mentionnés ci-dessus. Dans ce dernier cas, un travail d'analyse et de modélisation s'avérera nécessaire. Les algorithmes peuvent également mener à une campagne d'expérimentation, selon les goûts et compétences du stagiaire.Résultats attendus
- une étude bibliographique
- le développement d'algorithmes d'ordonnancement
- une étude théorique sur ces algorithmes
- une validation expérimentale (simulations ou pratique) complétera éventuellement ces résultats.
Compétences
Bonne compétence en algorithmique. Un plus est certainement d'avoir déjà une connaissance des algorithmiques d'approximation.