A cache-aware data structure layout for parallelism and dynamic load balancing
Un modèle de structure de données Cache-aware pour un parallélisme et un équilibrage dynamique de la charge
Résumé
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.
Origine : Version validée par le jury (STAR)