[Algorithme de localisation de points avec équilibrage de charge dynamique pour le transfert de données]
Data mapping between geometric domains with non-matching discretizations is an essential step in multi-component numerical simulation workflows. This paper presents a novel point location algorithm, designed for transferring data from unstructured meshes to point clouds, in a massively parallel distributed environment. Special emphasis is placed on load balancing, which is paramount for making the most of computing resources and achieve optimal performance. In general, the geometric entities of interest are unevenly distributed in the input frame provided by the calling codes. The algorithm therefore aims to rapidly prune the search space using a series of parallel preconditioning techniques, while redistributing data equitably across all processes at each step. Exact point-in-cell location is then computed in an embarrassingly parallel, well-balanced frame. All data movements performed throughout the point location algorithm are transparent to the calling codes, as the resulting geometric and parallel mappings are returned in the same frame as the input data. These mappings enable data transfer via spatial interpolation and optimized process-to-process communications. A weak scaling study is carried out in three scenarios representative of the variety of real-life applications. Comparison with a state-of-the-art algorithm shows that the new algorithm performs better overall, with speed-ups of up to a factor of 10 on 4,800 CPU cores.
Le transfert de données entre des domaines géométriques avec des discrétisations non conformes est une étape essentielle dans les workflows de simulation numérique multicomposants. Cet article présente un nouvel algorithme de localisation de points, conçu pour transférer des données depuis des maillages non-structurés vers des nuages de points, dans un environnement distribué massivement parallèle. Une attention particulière est accordée à l’équilibrage de charge, qui est primordial pour tirer le meilleur parti des ressources informatiques et obtenir des performances optimales. En général, les entités géométriques d’intérêt sont réparties de manière inégale dans la distribution d’entrée fournie par les codes appelants. L’algorithme vise donc à réduire rapidement l’espace de recherche à l’aide d’une série de techniques de préconditionnement parallèles, tout en redistribuant les données de manière équitable entre tous les processus à chaque étape. La localisation exacte des points dans les cellules est ensuite calculée en parallèle dans une distribution bien équilibrée. Les mouvements de données effectués tout au long de l’algorithme de localisation des points sont transparents pour les codes appelants, car les mappings géométriques et parallèles résultants sont renvoyés dans la même distribution que les données d’entrée. Ces mappings permettent le transfert de données par interpolation spatiale et des communications optimisées entre les processus. Une étude de scalabilité faible est réalisée dans trois scénarios représentatifs de la diversité des applications réelles. La comparaison avec un algorithme de l’état de l’art montre que le nouvel algorithme est globalement plus performant, avec des accélérations pouvant atteindre un facteur 10 sur 4800 cœurs CPU.
Révisé le :
Accepté le :
Publié le :
Mots-clés : Calcul haute performance (HPC), interface de passage de messages (MPI), équilibrage dynamique de charge, géométrie algorithmique
Bastien Andrieu 1 ; Bruno Maugars 2 ; Eric Quémerais 1
CC-BY 4.0
@article{CRMECA_2026__354_G1_53_0,
author = {Bastien Andrieu and Bruno Maugars and Eric Qu\'emerais},
title = {Dynamic load-balanced point location algorithm for data mapping},
journal = {Comptes Rendus. M\'ecanique},
pages = {53--70},
year = {2026},
publisher = {Acad\'emie des sciences, Paris},
volume = {354},
doi = {10.5802/crmeca.335},
language = {en},
}
TY - JOUR AU - Bastien Andrieu AU - Bruno Maugars AU - Eric Quémerais TI - Dynamic load-balanced point location algorithm for data mapping JO - Comptes Rendus. Mécanique PY - 2026 SP - 53 EP - 70 VL - 354 PB - Académie des sciences, Paris DO - 10.5802/crmeca.335 LA - en ID - CRMECA_2026__354_G1_53_0 ER -
Bastien Andrieu; Bruno Maugars; Eric Quémerais. Dynamic load-balanced point location algorithm for data mapping. Comptes Rendus. Mécanique, Volume 354 (2026), pp. 53-70. doi: 10.5802/crmeca.335
[1] Design of a high fidelity Fluid–Structure Interaction solver using LES on unstructured grid, Comput. Fluids, Volume 265 (2023), 105963 | DOI | Zbl
[2] Modeling and simulation of chemical reactions at the surface of an ablative wall interacting with a hypersonic flow (2022) Conference paper: 9th European Conference for Aeronautics and Aerospace Sciences (EUCASS-3AF)
[3] A parallel matrix-free conservative solution interpolation on unstructured tetrahedral meshes, Comput. Methods Appl. Mech. Eng., Volume 299 (2016), pp. 116-142 | DOI
[4] A hybrid Eulerian-Lagrangian flow solver (2015) | arXiv
[5] CFD Vision 2030 Road Map: Progress and Perspectives, AIAA AVIATION 2021 FORUM, American Institute of Aeronautics and Astronautics (2021), AIAA 2021-2726 | DOI
[6] MPI: a message passing interface, Proceedings of the 1993 ACM/IEEE conference on Supercomputing (Bob Borchers; Dona Crawford, eds.), ACM Press (1993), pp. 878-883 | DOI
[7] preCICE v2: A sustainable and user-friendly coupling library, Open Res. Eur., Volume 2 (2022), 51, 47 pages
[8] Efficient and scalable initialization of partitioned coupled simulations with preCICE, Algorithms, Volume 14 (2021) no. 6, 166, 17 pages | DOI
[9] Optimizing Code_Saturne computations on Petascale systems, Comput. Fluids, Volume 45 (2011) no. 1, pp. 103-108 | DOI
[10] Massively parallel location and exchange tools for unstructured meshes, Int. J. Comput. Fluid Dyn., Volume 34 (2020) no. 7–8, pp. 549-568 | DOI
[11] The Data Transfer Kit: A geometric rendezvous-based tool for multiphysics data transfer, International Conference on Mathematics & Computational Methods Applied to Nuclear Science & Engineering (M&C 2013) (2013), pp. 5-9
[12] A parallel rendezvous algorithm for interpolation between multiple grids, J. Parallel Distrib. Comput., Volume 64 (2004) no. 2, pp. 266-276 | DOI
[13] Hybrid Multi-GPU Distributed Octrees Construction for Massively Parallel Code Coupling Applications, PASC ’24 — Proceedings of the Platform for Advanced Scientific Computing Conference, ACM Press (2024), 14 | DOI
[14] Bottom-up construction and 2: 1 balance refinement of linear octrees in parallel, SIAM J. Sci. Comput., Volume 30 (2008) no. 5, pp. 2675-2708 | DOI
[15] A computer oriented geodetic data base and a new technique in file sequencing, IBM, 1966
[16] Parallel domain decomposition and load balancing using space-filling curves, Proceedings 4th International Conference on High-Performance Computing, IEEE (1997), pp. 230-235
[17] Parallel mesh partitioning based on space filling curves, Comput. Fluids, Volume 173 (2018), pp. 264-272 | DOI
[18] Mean value coordinates for arbitrary planar polygons, ACM Trans. Graph., Volume 25 (2006) no. 4, pp. 1424-1441 | DOI
[19] Mean Value Coordinates for Closed Triangular Meshes, ACM Trans. Graph., Volume 24 (2005) no. 3, pp. 561-566 | DOI
[20] La Bibliothèque de Couplage CWIPI — Coupling With Interpolation Parallel Interface, ONERA, le centre français de recherche aérospatiale, 2013 https://w3.onera.fr/... (Accessed 2025-11-27)
[21] onera/cwipi: Library for coupling parallel scientific codes via MPI communications to perform multi-physics simulations https://github.com/onera/cwipi/tree/cwipi-1.1.0 (Accessed 2025-11-27)
[22] PT-Scotch: A tool for efficient parallel graph ordering, Parallel Comput., Volume 34 (2008) no. 6–8, pp. 318-331 | DOI
[23] Towards the Large-Eddy Simulation of a Full Engine: Integration of a 360 Azimuthal Degrees Fan, Compressor and Combustion Chamber. Part I: Methodology and Initialisation, J. Global Power Propul. Soc., Volume 2021 (2021), pp. 1-16 | DOI
Cité par Sources :
Commentaires - Politique