Thèse Algorithmes Parallèles Multi-Critères de Placement de Graphes pour les Architectures Non-Uniformes et Exaflopiques H/F - 33

Établissement : Université de Bordeaux
École doctorale : Mathématiques et Informatique
Laboratoire de recherche : LaBRI - Laboratoire Bordelais de Recherche en Informatique
Direction de la thèse : François PELLEGRINI ORCID 0000000339836289
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-04T23:59:59

Le partitionnement de graphes est une technique utilisée pour la résolution de nombreux problèmes en calcul scientifique, tels que la décomposition d'un maillage en sous-domaines afin d'équilibrer la charge de calcul d'une simulation sur une architecture parallèle. Les versions parallèles à mémoire distribuée des logiciels de partitionnement, tel que l'outil PT-Scotch que nous développons, ne prennent pas intégralement en compte l'hétérogénéité des communications et des unités de calcul des machines parallèles modernes, notamment celles de très grande taille, ce qui peut conduire à des performances dégradées lors de l'exécution des simulations numériques utilisant les résultats de partitionnement.
L'objectif de cette thèse est de résoudre les défis algorithmiques et de mise en oeuvre permettant de disposer d'une bibliothèque parallèle, à mémoire distribuée et partagée, capable de placer statiquement et de replacer dynamiquement des graphes comprenant jusqu'à un billion (c'est-à-dire 10^12) de sommets, distribués sur un million d'unités de traitement, au moyen d'algorithmes multi-critères (chaque sommet du graphe à placer étant alors caractérisé par plusieurs poids, correspondant chacun à une fonction de coût à équilibrer sur chaque sous-domaine créé). Les travaux à mener pour lever les verrous scientifiques identifiés comprennent: (i)la conception d'algorithmes de placement parallèles pour des architectures cibles de tout type, d'abord en mémoire partagée, puis en mémoire distribuée. Ces algorithmes pourront être d'abord synchrones, avant de s'intéresser à des algorithmes plus asynchrones afin d'améliorer leur performance et la qualité des résultats produits; (ii)l'extension de ces algorithmes au cas du replacement dynamique; (iii)l'extension de ces algorithmes au cas multi-critères; (iv) la prise en compte, comme architectures cibles, de sous-ensembles d'éléments de calcul représentant des parties d'architectures parallèles, telles que celles fournies par les systèmes d'exécution de ces machines; (v) la découverte dynamique de ces sous-architectures.
Les résultats scientifiques attendus consistent en des algorithmes robustes et passant à l'échelle pour le placement et le replacement parallèle à mémoire distribuée de graphes de grande taille sur des architectures non uniformes complexes. Ces algorithmes seront mis en oeuvre au sein du logiciel Scotch/ PT-Scotch, et seront par ce biais accessibles à la communauté internationale intéressée.
La thèse se déroulera dans les locaux du centre Inria de l'Université de Bordeaux. Elle s'inscrit dans un projet scientifique et industriel plus large, dont le logiciel Scotch constitue l'étendard: fournir à l'ensemble de la communauté académique et industrielle un outil de partitionnement et placement éprouvé contribuant à la résolution de problèmes frontières.

Cette thèse s'inscrit dans un projet scientifique et industriel plus large, dont le logiciel Scotch (et sa déclinaison parallèle à mémoire distribuée PT-Scotch) constitue l'étendard: fournir à l'ensemble de la communauté académique et industrielle un outil de partitionnement et placement éprouvé contribuant à la résolution de problèmes frontières (notamment concernant la fonctionnalité de placement de processus sur des architectures de très grandes tailles).
Le doctorant sera en relation étroite avec les ingénieurs associés au Consortium Scotch. Ceux-ci pourront lui apporter leur aide pour accélérer le développement de ses prototypes et leur mise en production éventuelle dans le cadre de campagnes de tests qui pourront impliquer des membres et/ou prospects du consortium. Ces derniers comprennent de grands industriels nationaux et des centres de recherche internationaux, pour qui Scotch représente un outil stratégique pour mener à bien leurs simulations frontières.

Le but de cette thèse est de résoudre les défis algorithmiques et de mise en oeuvre permettant de disposer d'une bibliothèque parallèle, à mémoire distribuée et partagée, capable de placer statiquement et de replacer dynamiquement des graphes comprenant jusqu'à un billion (c'est-à-dire 10^12) de sommets, distribués sur un million d'unités de traitement, au moyen d'algorithmes multi-critères.

La méthode employée pour arriver aux résultats attendus suit les canons de la démarche scientifique: étude de l'état de l'art, modélisation itérative du problème, conception d'algorithmes supposés adaptés, prototypage, tests, et publication des résultats en maximisant la reproductibilité de ceux-ci.
Le sujet de la thèse concernant l'algorithmique parallèle expérimentale, dans laquelle la réalisation des outils tiers (tels que les bibliothèques de communication) peuvent conditionner fortement les performances espérées, la validation des algorithmes par des campagnes de test en conditions réelles constitue un élément essentiel du travail.