• Langue : Anglais
• Discipline : Informatique et applications
• Identifiant : 2025ULILB003
• Type de thèse : Doctorat
• Date de soutenance : 10/01/2025

Résumé en langue originale

Les algorithmes Branch-and-Bound (B&B) sont couramment utilisés pour la résolution exacte de nombreux problèmes d'optimisation combinatoire. Leur mise en œuvre parallèle pour la résolution d'instances de plus en plus grandes pose plusieurs défis liés à la génération dynamique de grands arbres fortement irréguliers. Avec l'arrivée de l'ère exascale, les supercalculateurs modernes sont désormais composés de milliers de nœuds de calcul hybrides, chacun intégrant des processeurs multi-cœurs couplés à des accélérateurs graphiques (GPUs). Cette organisation hiérarchique, fournissant un parallélisme multi-niveau (intra-nœud, GPU, inter-nœud ou cluster, etc.), rend complexe l'implémentation parallèle exascale. Pour faire face à cette complexité, la majorité des travaux existants utilise l'approche "évolutionnaire" MPI+X, qui consiste à étendre le standard MPI utilisé pour le niveau inter-noeud avec des environnements pour le parallélisme intra-nœud (OpenMP, CUDA, etc.). Dans cette thèse, nous investiguons l'approche PGAS (Partitioned Global Address Space), alternative à MPI+X, dans le contexte de la mise en œuvre des algorithmes B&B pour l'exascale. Cette approche "révolutionnaire" fournit un niveau d'abstraction du parallélisme plus élevé, unifiant les niveaux intra-nœud et inter-nœud.La première contribution de cette thèse porte sur la conception et l'implémentation d'une structure de données PGAS, nommée distBag-DFS, dédiée à l'exploration en profondeur d'abord d'arbres irréguliers de grande taille. Cette structure de données multi-pool intègre un mécanisme d'équilibrage de charge dynamique basé sur le paradigme de vol de tâches large échelle, opéré aux deux niveaux intra- et inter-nœud. Ce mécanisme, qui a nécessité une synchronisation sophistiquée, favorise la localité des vols de tâches permettant son passage à l'échelle. La structure de données et son mécanisme d'équilibrage de charge sont implémentés en Chapel, et fournis comme module dans ce langage basé sur PGAS et conçu pour l'exascale. La deuxième contribution de cette thèse porte sur l'extension des travaux proposés au contexte multi-GPU pour accélérer l'évaluation massive et coûteuse des nœuds de l'arbre exploré. Le défi de la portabilité de l'implémentation sur architectures GPU multi-fournisseurs (NVIDIA et AMD) est considéré.Les algorithmes développés dans cette thèse ont été conçus pour être génériques et favoriser leur réutilisation. Ceci est attesté par l'application de ces algorithmes à différents problèmes d'optimisation combinatoire, notamment les problèmes d'ordonnancement Flow-Shop à permutation, de sac à dos binaire, des N-reines ainsi que le benchmark Unbalanced Tree-Search. La validation expérimentale a été réalisée, entre autres, sur deux supercalculateurs du classement TOP500 (MeluXina et LUMI). Les résultats obtenus montrent qu'en plus de favoriser la productivité logicielle, nos algorithmes basés sur l'approche PGAS sont compétitifs en termes de passage à l'échelle aux deux niveaux intra- et inter-nœud, en comparaison de ceux obtenus avec l'approche MPI+X. De plus, les résultats ont confirmé l'optimalité des solutions pour certaines des plus difficiles instances du Flow-Shop, en utilisant jusqu'à 400 nœuds de calcul, soit 51 200 cœurs CPU. D'autre part, le passage à l'échelle par rapport au nombre de GPU a été évalué sur 128 nœuds de calcul, totalisant 1 024 accélérateurs GPU. De manière générale, nos résultats montrent la compétitivité des approches PGAS par rapport à MPI+X, tout en mettant en lumière certaines perspectives d'amélioration.

Résumé traduit

Branch-and-Bound (B&B) algorithms are widely used for the exact resolution of many combinatorial optimization problems. Their parallel implementation to solve increasingly large instances presents several challenges related to the dynamic generation of large and highly irregular trees. With the advent of the exascale era, modern supercomputers are now composed of thousands of hybrid compute nodes, each integrating multi-core processors coupled with GPU accelerators. This hierarchical organization, providing multi-level parallelism (intra-node, GPU, inter-node or cluster, etc.), makes core complex the parallel exascale implementation. To address this complexity, most existing works use the "evolutionary" MPI+X approach, which extends the MPI standard used for inter-node level with environments for intra-node parallelism (OpenMP, CUDA, etc.). In this thesis, we investigate the PGAS (Partitioned Global Address Space) approach, an alternative to MPI+X, in the context of the implementation of B&B algorithms for exascale. This "revolutionary" approach provides a higher level of parallelism abstraction, unifying intra-node and inter-node levels.The first contribution of this thesis focuses on the design and implementation of a PGAS-based data structure, named distBag-DFS, dedicated to depth-first exploration of large, irregular trees. This multi-pool data structure integrates a dynamic load-balancing mechanism based on large-scale work-stealing, operating at both intra- and inter-node levels. This mechanism, which required sophisticated synchronization, promotes locality in work-stealing, enabling scalability. The data structure and its load-balancing mechanism are implemented in Chapel and provided as a module in this PGAS-based language designed for exascale. The second contribution of this thesis extends the proposed work to the multi-GPU context to accelerate the massive and costly evaluation of tree nodes being explored. The challenge of ensuring implementation portability across multi-vendor GPU architectures (NVIDIA and AMD) is addressed.The algorithms developed in this thesis have been designed to be generic and to promote their reuse. This is evidenced by the application of these algorithms to various combinatorial optimization problems, including permutation flow-shop scheduling, binary knapsack problems, the N-Queens problem, and the Unbalanced Tree-Search benchmark. Experimental validation was conducted on two TOP500 supercomputers (MeluXina and LUMI), among others. The results show that our PGAS-based algorithms are competitive in terms of scalability at both intra-node and inter-node levels compared to those obtained with the MPI+X approach. Additionally, the results confirmed the optimality of solutions for some of the largest flow-shop instances, utilizing up to 400 compute nodes, or 51,200 CPU cores. Furthermore, scalability concerning the number of GPUs was evaluated on 128 compute nodes, totaling 1,024 GPU accelerators. Overall, our results demonstrate the competitiveness of PGAS approaches compared to MPI+X, while identifying opportunities for further enhancement.