Cette thèse porte sur trois thématiques principales liées à l'ordonnancement de graphes de tâches qui modélise des applications de calcul scientifique sur des plates-formes de calcul modernes: exploiter le parallélisme intrinsèque des tâches, utiliser des accélérateurs tels que des GPU, et prendre en compte une mémoire limitée. Au début de ma thèse, j'ai également travaillé sur des structures de données en mémoire externe, projet initié lors d'une visite de recherche dans l'équipe de Michael Bender, USA.
Certaines applications présentent deux types de parallélisme que l'on peut exploiter: plusieurs tâches peuvent être exécutées simultanément et chaque tâche peut être exécutée sur plusieurs processeurs, afin de réduire son temps de calcul. Nous proposons et étudions deux modèles permettant de régir ce temps de calcul, afin d'exploiter ces deux types de parallélisme.
Nous avons ensuite étudié comment utiliser efficacement des accélérateurs de calcul lorsque l'on ne connaît pas les futures tâches à ordonnancer.
La dernière thématique abordée concerne le problème d'une mémoire principale limitée, et le recours à des transferts de données coûteux. Nous avons traité ce problème via deux scénarios. S'il est possible d'éviter de tels transferts, nous avons proposé de rajouter des contraintes afin de garantir que toute exécution ne dépasse pas la mémoire disponible, ce qui permet par exemple de laisser un outil dédié déterminer un ordonnancement dynamiquement. Si tout ordonnancement nécessite des transferts, nous avons étudié le problème consistant à minimiser leur quantité.
Tous les algorithmes proposés ont été validés numériquement par des simulations.
Gratuit
Mots clés
Disciplines