Search

The current parallel architectures integrate processors with many cores to shared memory growing and responding to specific usage constraints, particularly in the cache management. To take advantage of this power, a unique distributed memory parallelism, to manage the inter-node communications is not directly adapted to the characteristics of multi-core architectures. In addition, the shared memory computing environments offer techniques for balancing the load among available cores more appropriate than those in a distributed memory context.Thus, programming models like OpenMP and KAAPI is a tailored response to the specific characteristics of these architectures.Given these issues, we are interested in developing a hardware-aware approach taking into consideration the hierarchical organization of parallel architectures with shared memory. Our approach provides an optimization model for the use of storage space in this context of parallelism.To prove the pertinence of this approach, we have implemented it in the fast dynamic simulation software EUROPLEXUS of fluids and structures, focusing on the shared memory parallelism complementary to the distributed memory approach developed elsewhere. Because of its wide range of applications, EUROPLEXUS is characterized by a very rich data structure and very complex dependencies among its routines. We focused on accelerating the main loop iterating over the mesh elements. The heterogeneity of the formulations and the materials of the elements that can co-exist in the same simulated model generates a large variability between the costs of the iterations of this loop. A first parallelization of the loop with the XKAAPI library based on a dynamic workstealing scheduling has been implemented. However, despite the acceleration achieved by the parallel implementation, performance has been restrained by frequent and dispersed access costs to a complex data structure. This makes the implementation of the code difficult to optimize. Because of this structure, much of the execution time has elapsed in cache misses. The work is based on the implementation of a model approximating the data structure that ensures a better access locality. It mainly consists in moving from the global data structure in which the physical fields are stored in separate tables to a structure based on the storage of data in independent structures called groups. These groups contain the data relating to a number of elements in the local tables. This number is an adjustable parameter depending on the size of the cache levels. Specifically, this method returns to the nest of the elementary loop in a loop iterating on groups. The iterations among the groups are distributed over the cores of the architecture.The execution of the inner loop is sequentially by core. The best results are obtained for groups of the L2 cache size. For this particular size, the use of a dynamic load balancing in XKAAPI allowed us to double the acceleration of the elementary loop compared to the reference version of the code. The second part of this thesis is based on the parallelization of elementary loop inside the already parallelized loop. We demonstrated that this second level of parallelism is less efficient than the single. However, this nested parallelism might be interesting on Intel Xeon Phi architectures incorporating hyper-threaded cores at their calculation units., Les architectures parallèles actuelles intègrent des processeurs avec un nombre de cœurs à mémoire partagée de plus en plus important et répondant à des contraintes d'utilisation spécifiques, notamment en matière de gestion de la mémoire cache. Pour tirer parti de cette puissance, un parallélisme unique à mémoire distribuée, nécessaire pour gérer les communications inter-nœuds, présente le désavantage de ne pas s'adapter directement aux particularités des architectures multi-cœurs. De plus, les environnements de calcul à mémoire partagée proposent des techniques pour l'équilibrage de la charge entre les cœurs disponibles, qui se présentent de manière plus délicate dans un contexte de mémoire distribuée. Ainsi, des modèles de programmation tels qu’OpenMP et XKAAPI sont une réponse bien adaptée aux spécificités de ces architectures.Au regard de ces problématiques, nous nous sommes intéressés, à développer une approche Hardware-aware prenant en considération l'organisation hiérarchique des architectures parallèles à mémoire partagée. Notre approche offre un modèle d'optimisation de l'utilisation des espaces de stockage dans ce contexte de parallélisme. Pour démontrer la pertinence de cette approche, nous l'avons implémentée dans le logiciel de simulation en dynamique rapide des fluides et des structures EUROPLEXUS, en se concentrant sur le parallélisme à mémoire partagée, complémentaire d'une approche à mémoire distribuée développée par ailleurs. De par son large panel d'applications, EUR0PLEXUS est caractérisé par une structure de données très riche et des dépendances très complexes entre ses routines. Nous nous sommes concentrés sur l'accélération de la boucle principale itérant sur les éléments du maillage. L'hétérogénéité des formulations et des matériaux des éléments pouvant co-exister dans un même modèle simulé engendre une grande variabilité entre les coûts des itérations de cette boucle. Une première parallélisation de cette boucle avec la bibliothèque XKAAPI basée sur un ordonnancement dynamique par vol de tâches a été implémentée. Cependant, malgré l'accélération atteinte par cette implémentation parallèle, les performances ont été freinées par les coûts des accès fréquents et dispersés à une structure de données complexe rendant l'exécution du code délicate à optimiser. A cause de cette structuration, une grande partie du temps d'exécution est écoulée dans des défauts de cache.Ces travaux reposent sur l’implémentation d'un modèle de structure de données assurant une meilleure localité des accès. Il consiste majoritairement à passer de la structure de données globale dans laquelle les champs physiques sont stockés dans des tableaux séparés à une structure basée sur le stockage des données dans des structures indépendantes appelées groupes. Ces groupes contiennent les données relatives à un certain nombre d'éléments dans des tableaux locaux. Ce nombre est un paramètre réglable selon la taille des niveaux du cache. Concrètement, cette méthode revient à imbriquer la boucle élémentaire dans une boucle itérant sur les groupes. Les itérations sur les groupes sont distribuées sur les cœurs de l'architecture. L'exécution de la boucle interne est séquentielle par cœur. Les meilleurs résultats sont obtenus pour des groupes de la taille du cache L2 privé par cœur. Pour cette taille particulière, l'utilisation d'un équilibrage dynamique de charge sous XKAAPI nous a permis de doubler l'accélération de la boucle élémentaire par rapport à une parallélisation avec XKAAPI de la version de référence du code.La deuxième partie de cette thèse repose sur la parallélisation de la boucle élémentaire à l'intérieur de la boucle déjà parallélisée. Nous avons démontré que ce second niveau de parallélisme est moins performant que celui à un seul niveau. Cependant, ce parallélisme imbriqué pourrait être intéressant sur les architectures Xeon Phi de Intel intégrant des cœurs hyper-threadés au niveau de leurs unités de calcul.

Scientific and industrial applications that need high computational performance to be used are alwaysfacing a processing time issue. One of the procedures to deal with this issue is managing properly data inorder 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 memorylocality. In this report, we propose a new organization of the data structure for FEM based simulationcodes that require interesting speedups. We applied our approach on the industrial fast transientssimulator EUROPLEXUS. Experiments on various datasets show that our approach is efficient for thecache 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 thesimulation elements. The outer loop is among GROUPs of contiguous elements. Iterations for the twonested level loops are independent, offering a potential parallelism with the OpenMP library. Performancegain obtained show that the parallelization of the outer loop with the standard OpenMP library achieveshigh performance gain comparable to those obtained by XKAAPI library. Then, we discuss the limitationsof the standard OpenMP library to handle with load balancing for nested parallelism. We propose a newloop scheduler that ensures load balancing between different nested levels while respecting the hierarchyof the parallel platform. Performance gain obtained by several cases study, proves that to get an optimalload balancing with our scheduler we should opt for a constrained scheduling for the different nestedlevels.; 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.