Ce mémoire d'habilitation retrace les travaux que j'ai effectués depuis ma thèse dans le domaine de l'ordonnancement pour les plates-formes de calcul parallèle. Je me suis en particulier intéressé à l'influence de la capacité limitée de la mémoire pour les applications de calcul scientifique. Ces applications sont généralement décrites par des graphes de tâches, et l'ordre dans lequel ces tâches sont effectuées influence la quantité de mémoire nécessaire pour le calcul. Dans le cas où la mémoire serait trop limitée, on peut se résoudre à utiliser un stockage secondaire (le disque), mais on cherche alors à limiter le nombre d'entrées/sorties, également influencé par l'ordonnancement.
Ce mémoire décrit tout d'abord les modèles historiques pour prendre en compte ces contraintes, à base de "pebble game", ainsi que quelques algorithmes préexistants, notamment pour les arbres de tâches. Ces algorithmes sont ensuite étendus dans plusieurs directions: graphes séries-parallèles, plates-formes de calcul hybrides composées de deux mémoire, traitement parallèle d'un arbre de tâche avec une mémoire partagée. À chaque fois, la complexité du problème est étudiée et des solutions pratiques (optimales ou heuristiques) sont proposées.
Une deuxième partie traite d'autres problèmes liés aux mouvements de données pour les calculs matriciels: distribution du produit de matrices sur processeur multi-cœur pour améliorer l'utilisation des caches, redistribution de données avant un noyau de calcul, et distribution dynamique de tâches pour le produit de matrices sur plate-forme hétérogène.
Section CNU n°27 - Informatique
Gratuit
Mots clés
Disciplines