Thèmes de recherche

Je m'intéresse de manière générale aux problématiques liées au calcul haute-performance (HPC) et aux applications distribuées (Big Data ou Cloud Computing par exemple). Je me concentre en particulier sur l'aspect ordonnancement de ces thématiques, plus particulièrement les ordonnancements statiques (calculés en amont) basés sur des modélisations. Au cours de ma carrière je me suis concentré sur plusieurs problèmes spécifiques.


Collaborateurs : Olivier Beaumont (Inria Bordeaux, LaBRI), Loris Marchal (CNRS, LIP) et Bastien Thomas (Inria Rennes,IRISA).

Publications liées : CEBDA 2019 et FGCS 2020.

Les systèmes de fichiers distribués appliquent généralement une réplication des données qui permet d'éviter une perte définitive en cas de panne. Cette redondance peut aussi s'utiliser afin d'améliorer le parallélisme du calcul. En effet, un fichier dupliqué est présent sur un plus grand nombre de machines qui sont donc susceptibles de traiter les tâches correspondantes plus rapidement (c'est à dire sans avoir à attendre la récupération des données depuis une autre machine). Cette technique est depuis longtemps au coeur des stratégies de placement de calculs de type MapReduce où la localité est depuis longtemps étudiée. Lors de la seconde partie de ma thèse, nous avons décidé de traiter cette question sous la forme d'un problème bi-critère (équilibrage de charge, localité). Pour résoudre les deux facettes de ce problème, nous avons fait appel à la littérature sur le couplage, plus particulièrement celle sur les "semi-matchings". Le principe d'un semi-matching est de sélectionner les arêtes d'un graphe biparti de façon à avoir une seule arête exactement par sommet "à gauche" (c'est un couplage dont on a relâché la contrainte d'unicité pour un des deux ensembles de sommets). Un tel modèle permet de représenter un placement entièrement local, la répartition des réplicas étant modélisée par un graphe biparti (les fichiers d'un côté, les machines de l'autre et une arête représentant la présence d'un réplica d'un fichier sur une machine). Afin de relier ce modèle à notre problème, nous avons défini deux métriques correspondant chacune à un critère : le degré maximum (nombre de tâches calculées par le processeur le plus chargé) et le déséquilibre total (nombre de tâches à déplacer pour équilibrer la charge de calcul, donc une estimation de la non-localité). Dans le cas de tâches de durées homogènes, les algorithmes existants de semi-matching permettent de résoudre, en temps polynomial, ces deux problèmes de manière optimale, ce que nous avons été les premiers à mettre en avant. En plus de ces résultats, nous avons aussi étudié la qualité de ces solutions de manière probabiliste. En particulier, en utilisant une équivalence avec un problème d'orientation de graphes, nous avons montré que la meilleure solution possédait, avec forte probabilité, au plus n/m +1 tâches sur la machine la plus chargée (m nombre de machines, n nombre de tâches). Nous avons aussi étendu cette analyse au cas de l'ordonnancement glouton présent par défaut sur Hadoop. L'espérance de la charge de la machine avec le plus de tâches allouées est cette fois n/m + O(\log \log m), résultat obtenu en nous basant sur une équivalence avec un problème de "balls-in-bins". Ces résultats théoriques ont ensuite été corroborés par une série de simulations. Nous avons ensuite étendu ces stratégies au cas où les tâches sont de durées hétérogènes et non connues à l'avance, basant ces durées sur les traces d'un serveur Hadoop. Nous avons aussi ajouté un mécanisme de vol de tâches à nos stratégies pour pouvoir réagir aux tâches trop longues. Nous avons montré que nos stratégies, dans le cadre de tâches peu ou moyennement hétérogènes, augmentent significativement la localité des tâches par rapport aux stratégies dynamique. A noter que dans ces cas, nos stratégies sont capables de produire des placements entièrement locaux, ce que les autres stratégies ne sont jamais en mesure de faire. Dans le cas de tâches très hétérogènes, l'efficacité de notre stratégie diminue mais reste satisfaisante.


Adapted from a template by FreeHTML5.co