Cache Aware Dynamics Data Layout for Efficient Shared Memory Parallelisation
Un modèle de structure de données Cache-aware pour un parallélisme et un équilibrage dynamique de la charge
Résumé
Scientific and industrial applications that need high computational performance to be used are always
facing a processing time issue. One of the procedures to deal with this issue is managing properly data in
order to take full advantage of the shared memory specifications of the computing platforms.
Our claim is to exploit the techniques of parallelism adapted to multi-level loops in order to ensure memory
locality. In this report, we propose a new organization of the data structure for FEM based simulation
codes that require interesting speedups. We applied our approach on the industrial fast transients
simulator EUROPLEXUS. Experiments on various datasets show that our approach is efficient for the
cache use since it reduces the execution time by around 40% for a well-defined data group size.
Our approach consists on the implementation of an outer level loop around the main loop iterating on the
simulation elements. The outer loop is among GROUPs of contiguous elements. Iterations for the two
nested level loops are independent, offering a potential parallelism with the OpenMP library. Performance
gain obtained show that the parallelization of the outer loop with the standard OpenMP library achieves
high performance gain comparable to those obtained by XKAAPI library. Then, we discuss the limitations
of the standard OpenMP library to handle with load balancing for nested parallelism. We propose a new
loop scheduler that ensures load balancing between different nested levels while respecting the hierarchy
of the parallel platform. Performance gain obtained by several cases study, proves that to get an optimal
load balancing with our scheduler we should opt for a constrained scheduling for the different nested
levels.
Les applications scientifiques et industrielles qui ont besoin d’une haute performance de calcul sont souvent confrontées à un problème de temps d’exécution. Pour tirer profit du parallélisme, il est impératif de bien exploiter les nœuds de calcul mis à notre disposition. Pour ce faire, il faut gérer d’une façon optimale l’utilisation de la mémoire et adopter une stratégie efficace pour la distribution des tâches sur les nœuds de calcul.
L’enjeu consiste à exploiter les techniques du parallélisme pour différents niveaux de boucle dans le but d’assurer une meilleure localité des données dans la mémoire. Dans ce rapport, nous proposons une nouvelle organisation de la structure de données pour les codes de simulations qui utilisent la méthode des éléments finis. Nous avons appliqué notre approche sur le code industriel EUROPLEXUS, code de simulation en dynamique rapide des transitoires accidentels. Les mesures de performances sur différents jeux de données montrent que notre approche est efficace pour l'utilisation de la mémoire cache. Cette approche nous a permis de réduire le temps d'exécution d'environ 40% pour une taille de groupe de données bien définie selon les caractéristiques matérielles de la plateforme de calcul (taille de la mémoire cache L3) et selon la complexité du cas test simulé. Notre approche porte dans une première phase, en l’implémentation d’un premier niveau de parallélisme autour de la boucle élémentaire qui constitue 80% du temps d’exécution global du code. La boucle externe est une boucle sur des groups d’éléments contigus en mémoire. Les itérations sur les deux niveaux de boucles sont indépendantes, et elles offrent ainsi, un parallélisme potentiel avec la bibliothèque de programmation parallèle OpenMP. Les performances obtenues montrent que la parallélisation de la boucle externe nous a permis de réaliser un gain de performance important comparable à celui obtenu avec la bibliothèque KAAPI. Nous discutons ensuite, les limitations de OpenMP pour aborder l’équilibrage dynamique de charge pour les boucles parallèles imbriquées. Nous proposons un nouvel ordonnanceur dans KAAPI qui assure l’équilibrage dynamique de charge entre les différents niveaux du parallélisme tout en respectant la hiérarchie de la plateforme parallèle. Le gain en performance que nous avons obtenu pour différent cas tests prouve que pour avoir un équilibrage optimal de charge avec notre ordonnanceur, nous devrions mettre en place un ordonnancement contraint pour les différents niveaux imbriqués.
Loading...