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 : Lionel Eyraud-Dubois, Olivier Beaumont et Abdou Guermouche (Inria Bordeaux, LaBRI), Alexey Lastovetsky, Bret Becker et Ashley DeFlumere (University College of Dublin).

Publications liées : SBAC-PAD 2015, IPDPS 2016, Euro-Par 2016, ICPP 2018 et TPDS 2018.

Le produit de matrices est un élément clé de nombreuses applications de calcul scientifique. Cette opération est coûteuse en terme d'échange de données car les éléments des matrices d'entrée doivent être partagés entre de nombreux processeurs pour obtenir un parallélisme efficace. Par ailleurs, les machines parallèles utilisent des processeurs de plus en plus différents, notamment des accélérateurs (GPUs, Xeon Phi, etc.), créant une hétérogénéité des plateformes qu'il faut prendre en compte lors du placement des tâches et de l'ordonnancement. Nous nous sommes intéressés au problème particulier des communications lors du calcul parallèle du produit de matrice en essayant de prendre en compte cette hétérogénéité. Pour cela nous avons utilisé un modèle basé sur un problème de partitionnement de carré (qui représente la matrice résultat) où l'équilibrage de charge est donné en entrée (avec potentiellement un grand déséquilibre). Avec cet équilibrage, le but est de minimiser la somme des semi-périmètres des rectangles couvrant des zones ainsi créées (le semi-périmètre étant proportionnel à la quantité de données à charger pour réaliser les calculs sur un processeur). Si cette modélisation n'est pas nouvelle, nous avons néanmoins étendu l'état de l'art, notamment en améliorant les algorithmes d'approximation existants. Plus particulièrement, avec notre algorithme NRRP (Non-Rectangular Recursive Partitionning), nous avons descendu le ratio d'approximation à environ 1.15 dans le cas général, contre 5/4 = 1.25 auparavant. Par ailleurs nous nous sommes intéressés à une modélisation alternative où le partitionnement concernait cette fois un cube. L'idée était de considérer le partitionnement de l'ensemble de l'espace de calcul plutôt que celui uniquement de la matrice résultat. Nous avons montré que cette approche pouvait apporter un gain significatif dans le cas d'une plate-forme de grande taille. Nous avons aussi montré la NP-complétude de ce nouveau problème (qui ne pouvait être dérivée trivialement de la NP-complétude du premier) et proposé 3D-NRRP qui est une 1.51-approximation et le seul algorithme, à ce jour, à avoir un ratio d'approximation prouvé. Finalement, tous ces travaux ont été utilisés pour réaliser une implémentation en situation réelle de NRRP et 3D-NRRP en utilisant la librarie de calcul StarPU (le code est disponible avec mes publications). Afin d'assurer un temps de calcul aussi faible que possible, nous avons ajouté une composante dynamique à nos placements (grâce à une approche basée sur le vol de tâche). Cette implémentation a prouvé les bons résultats de notre approche hybride quand on la compare à l'état de l'art, diminuant la quantité de données échangées de 12 à 48% par rapport à Chameleon, une librairie d'algèbre linéaire pour architectures parallèle hybride.


Adapted from a template by FreeHTML5.co