«Algorithmes parallèles efficaces appliqués aux calculs sur maillages non structurés» par Loïc Thebault

Résumé :
L'informatique est devenue un outil central dans de nombreux domaines scientifiques.
La majorité des recherches menées dans le domaine scientifique et technologique reposent sur la simulation numérique. Ce besoin croissant en simulation a conduit à l'élaboration de supercalculateurs complexes et d'un nombre croissant de logiciels hautement parallèles. Ces supercalculateurs requièrent un rendement énergétique et une puissance de calcul de plus en plus importants. Les récentes évolutions matérielles consistent à augmenter le nombre de noeuds de calcul et de coeurs par noeud. Cette augmentation continuera certainement jusqu'à atteindre plusieurs milliers de noeuds de calcul, eux-mêmes composés d'un millier de coeurs. Certaines ressources n'évoluent cependant pas à la même vitesse. La multiplication des coeurs de calcul implique une diminution de la mémoire par coeur, plus de trafic de données, un protocole de cohérence plus coûteux et requiert d'avantage de parallélisme. De plus, les architectures actuelles sont de plus en plus hétérogènes. De nombreuses applications et modèles actuels peinent ainsi à s'adapter à ces nouvelles tendances. En particulier, générer du parallélisme massif dans des méthodes d'éléments finis utilisant des maillages non structurés, et ce avec un nombre minimal de synchronisations et des charges de travail équilibrées, s'avèrent particulièrement difficile. Les approches actuelles basées sur la décomposition de domaine et le coloriage se retrouvent confrontées à ce problème, en particuliers avec les nouvelles architectures hautement multicoeurs. Il devient donc nécessaire d'explorer de nouvelles approches parallèles. Afin d'exploiter efficacement les multiples niveaux de parallélisme des architectures actuelles, différentes approches parallèles doivent être combinées. Le parallélisme massif de données se limite habituellement aux problèmes réguliers pouvant être décomposés en grilles de calcul. Ces problèmes sont adaptés aux exécutions de type programme unique, données multiples (SPMD) sur CPUs ou flux d'instruction unique, flux d'exécution multiples (SIMT) sur GPUs. Cette thèse propose plusieurs contributions destinées à aller au-delà de cette limitation en adressant les codes et les structures irrégulières de manière efficace. Nous avons développé une approche parallèle hybride par tâches à grain fin combinant les formes de parallélisme distribuée, partagée et vectorielle sur des structures irrégulières. De plus, une application industriel pouvant difficilement être intégralement réécrite, nous avons exploré le concept de proto-application en offrant une représentation simplifiée. Nous avons développé Mini-FEM, une proto-application représentative de l'application DEFMESH développée par Dassault Aviation. Nous avons ensuite développé la librairie D&C à partir de cette proto-application, puis l'avons validée sur DEFMESH. Nous avons également porté la librairie D&C sur AETHER, un autre code de mécanique des fluides développé par Dassault Aviation. Les résultats obtenus sur la proto-application ont ainsi pu être reproduits sur des applications grandeur réelle utilisant des schémas de calcul similaires. Nous avons testé notre approche sur des multicoeurs Xeon classiques et sur le Xeon Phi type KNC. Sur 512 coeurs Sandy Bridge avec seulement 2000 sommets par coeur, D&C dépasse l'approche purement MPI de 3.47x et atteint 77% d'efficacité parallèle. Sur 4 KNC, D&C obtient 96% d'efficacité parallèle et une accélération de 2.9x comparé à l'approche MPI commune basée uniquement sur la décomposition de domaine. De plus, la performance obtenue avec D&C est équivalente à 96 coeurs de type Xeon Sandy Bridge. En réduisant l'intensité arithmétique du code, l'efficacité parallèle de D&C sur les 4 KNC descend à 92% mais l'écart avec la version purement MPI augmente à 6.56x.

Abstract :
Computing science is at the center of a wide range of scientific domains. Almost all current scientific and technological research activity relies on numerical simulations to solve new problems or to design new products. There is a growing need for numerical simulations which results in larger and more complex computing centers and more HPC softwares. Actual HPC system architectures have an increasing requirement for energy efficiency and performance. Recent advances in hardware design result in an increasing number of nodes and an increasing number of cores per node. In future post-exascale systems, one can reasonably foresee thousands of nodes composed of thousand cores.
However, some resources do not scale at the same rate. The increasing number of cores and parallel units implies a lower memory per core, higher requirement for concurrency, higher coherency traffic and higher cost for coherency protocol. Moreover, current trends result in an increasing usage of heterogeneous architectures. Most of the applications and runtimes currently in use struggle to scale with the present trend. In the context of finite element methods, exposing massive parallelism on unstructured mesh computations with efficient load balancing and minimal synchronizations is challenging. Current approaches relying on domain decomposition and coloring exacerbate these issues, especially with new manycore accelerators. HPC users have to explore new paradigms for applications, runtimes, and programming models. To make efficient use of these architectures, several parallelization strategies have to be combined together to exploit the multiple levels of parallelism. Parallelization approaches exposing massive data parallelism are usually bounded to regular problems. These problems can be decomposed in compute grids and are well suited to Single Program Multiple Data (SPMD) executions on CPUs or Single Instruction Multiple Threads (SIMT) executions on GPUs. This P.h.D. thesis proposes several contributions aimed at overpassing this limitation by addressing irregular codes and data structures in an efficient way. We have developed an hybrid parallelization approach combining the distributed, shared, and vectorial forms of parallelism in a fine grain task-based parallelism approach applied on irregular structures. Moreover, since very large industrial codes cannot be rewritten from scratch, we experiment the concept of proto-application as a proxy between computer scientists and application developers on a real industrial use-case. We developed the Mini-FEM proto-application representative of the DEFMESH application from Dassault Aviation. Then, we built the D&C library on top of the proto-application and validated it on the original DEFMESH application. We also ported the D&C library to another fluid dynamic application, AETHER, also developed by Dassault Aviation. The results show that the speed-up validated on the proto-application can be reproduced on other full scale applications using similar computational patterns.
We have experimented our approach using standard Xeon multicores and Xeon Phi KNC manycores. On 512 Sandy Bridge cores, we overpass the pure MPI approach by up to 3.47x and reach 77% of parallel efficiency with only 2000 vertices per core. Running an intensive computation kernel on 4 Xeon Phi, we achieve an excellent parallel efficiency of 96% and a 2.9x acceleration compared to the common approach using only MPI domain decomposition. By reducing the arithmetic intensity by a factor of 100x, the parallel efficiency of the D&C library decreases to 92% but becomes 6.56 times faster than the pure MPI version. Finally, running on 4 Xeon Phi, D&C has similar performance to 96 Intel Xeon Sandy Bridge cores.