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.


Collaborateur : Rizos Sakellariou (Université de Manchester).

Publication liée : Cloud Workshops 2018.

Nous nous sommes intéressés à un problème autour du modèle publieurs/abonnés (publisher/subscriber), qui est un modèle très populaire pour représenter les interactions entre des producteurs de données (les publieurs) et des demandeurs (les abonnés). Un tel modèle représente efficacement aussi bien des applications de type interaction sociale que de la gestion de capteurs ou de flux RSS, et c'est pourquoi plusieurs services de ressources de calcul proposent des applications génériques basées sur ce modèle. Notre objectif lors de cette étude a été de considérer un tel graphe de publieurs/abonnés ainsi qu'un ensemble de machines et d'essayer d'optimiser le placement des transferts de données sur ces machines afin de maximiser la quantité de données en sortie. Notre modèle est simple : un graphe représentant les interactions publieurs/abonnés, un taux de publication par abonné et un ensemble de machines disposant d'une bande-passante (qui peut être utilisée en entrée comme en sortie). Notre but est alors d'allouer les arêtes aux machines en respectant les contraintes de bande-passante (la somme des flux d'entrée et de sortie ne doit pas dépasser la bande-passante). La difficulté est de gérer habilement la répartition des publieurs afin d'éviter de dupliquer leurs flux de données sur trop de machines différentes. Afin de résoudre ce problème, nous avons proposé deux heuristiques, l'une gloutonne, GreedyScheduling, l'autre, MKBPS, inspirée par le problème du sac à dos multiple (placer le plus d'objets possibles dans plusieurs sacs de tailles bornées). Nous avons évalué nos stratégies sur des simulations en les comparant à la fois à une borne supérieure et à une stratégie optimale utilisant la programmation linéaire (uniquement dans les instances très régulières et de petites tailles). Les résultats ont montré deux choses. Tout d'abord nos deux heuristiques obtiennent des résultats très proches de l'optimal (quand il est disponible) et de la borne supérieure, cet écart se resserrant lorsque la taille des instances augmente (MKPBS obtient de légèrement meilleurs résultats). Ensuite, ces heuristiques possèdent des temps de calculs très rapides et linéaires en fonction du nombre d'arêtes, ce qui permet une utilisation sur des instances de très grande taille.


Adapted from a template by FreeHTML5.co