Les plates-formes multi-coeurs avec un accès mémoire non uniforme (NUMA) sont devenu des ressources usuelles de calcul haute performance. Dans ces plates-formes, la mémoire partagée est constituée de plusieurs bancs de mémoires physiques organisés hiérarchiquement. Cette hiérarchie est également constituée de plusieurs niveaux de mémoires caches et peut être assez complexe. En raison de cette complexité, les coûts d'accès mémoire peuvent varier en fonction de la distance entre le processeur et le banc mémoire accédé. Aussi, le nombre de coeurs est très élevé dans telles machines entraînant des accès mémoire concurrents. Ces accès concurrents conduisent à des ponts chauds sur des bancs mémoire, générant des problèmes d'équilibrage de charge, de contention mémoire et d'accès distants. Par conséquent, le principal défi sur les plates-formes NUMA est de réduire la latence des accès mémoire et de maximiser la bande passante. Dans ce contexte, l'objectif principal de cette thèse est d'assurer une portabilité des performances évolutives sur des machines NUMA multi-coeurs en contrôlant l'affinité mémoire. Le premier aspect consiste à étudier les caractéristiques des plates-formes NUMA que sont à considérer pour contrôler efficacement les affinités mémoire, et de proposer des mécanismes pour tirer partie de telles affinités. Nous basons notre étude sur des benchmarks et des applications de calcul scientifique ayant des accès mémoire réguliers et irréguliers. L'étude de l'affinité mémoire nous a conduit à proposer un environnement pour gérer le placement des données pour les différents processus des applications. Cet environnement s'appuie sur des informations de compilation et sur l'architecture matérielle pour fournir des mécanismes à grains fins pour contrôler le placement. Ensuite, nous cherchons à fournir des solutions de portabilité des performances. Nous entendons par portabilité des performances la capacité de l'environnement à apporter des améliorations similaires sur des plates-formes NUMA différentes. Pour ce faire, nous proposons des mécanismes qui sont indépendants de l'architecture machine et du compilateur. La portabilité de l'environnement est évaluée sur différentes plates-formes à partir de plusieurs benchmarks et des applications numériques réelles. Enfin, nous concevons des mécanismes d'affinité mémoire qui peuvent être facilement adaptés et utilisés dans différents systèmes parallèles. Notre approche prend en compte les différentes structures de données utilisées dans les différentes applications afin de proposer des solutions qui peuvent être utilisées dans différents contextes. Toutes les propositions développées dans ce travail de recherche sont mises en œuvre dans une framework nommée Minas (Memory Affinity Management Software). Nous avons évalué l'adaptabilité de ces mécanismes suivant trois modèles de programmation parallèle à savoir OpenMP, Charm++ et mémoire transactionnelle. En outre, nous avons évalué ses performances en utilisant plusieurs benchmarks et deux applications réelles de géophysique. / Multi-core platforms with non-uniform memory access (NUMA) design are now a common resource in High Performance Computing. In such platforms, the shared memory is organized in an hierarchical memory subsystem in which the main memory is physically distributed into several memory banks. Additionally, the hierarchical memory subsystem of these platforms feature several levels of cache memories. Because of such hierarchy, memory access costs may vary depending on the distance between tasks and data. Furthermore, since the number of cores is considerably high in such machines, concurrent accesses to the same distributed shared memory are performed. These accesses produce more stress on the memory banks, generating load-balancing issues, memory contention and remote accesses. Therefore, the main challenge on a NUMA platform is to reduce memory access latency and memory contention. In this context, the main objective of this thesis is to attain scalable performances on multi-core NUMA machines by controlling memory affinity. The first goal of this thesis is to investigate which characteristics of the NUMA platform and the application have an important impact on the memory affinity control and propose mechanisms to deal with them on multi-core machines with NUMA design. We focus on High Performance Scientific Numerical workloads with regular and irregular memory access characteristics. The study of memory affinity aims at the proposal of an environment to manage memory affinity on Multi-core Platforms with NUMA design. This environment provides fine grained mechanisms to manage data placement for an application by using compilation time and architecture information. The second goal is to provide solutions that show performance portability. By performance portability, we mean solutions that are capable of providing similar performances improvements on different NUMA platforms. In order to do so, we propose mechanisms that are independent of machine architecture and compiler. The portability of the proposed environment is evaluated through the performance analysis of several benchmarks and applications over different platforms. Last, the third goal of this thesis is to design memory affinity mechanisms that can be easily adapted and used in different parallel systems. Our approach takes into account the different data structures used in High Performance Scientific Numerical workloads, in order to propose solutions that can be used in different contexts. We evaluate the adaptability of such mechanisms in two parallel programming systems. All the ideas developed in this research work are implemented in a Framework named Minas (Memory affInity maNAgement Software). Several OpenMP benchmarks and two real world applications from geophysics are used to evaluate its performance. Additionally, Minas integration on Charm++ (Parallel Programming System) and OpenSkel (Skeleton Pattern System for Software Transactional Memory) is also evaluated.

Les joueurs exigeants acquièrent dès que possible une carte graphique capable de satisfaire leur soif d'immersion dans des jeux dont la précision, le réalisme et l'interactivité redoublent d'intensité au fil du temps. Depuis l'avènement des cartes graphiques dédiées au calcul généraliste, ils n'en sont plus les seuls clients. Dans un premier temps, nous analysons l'apport de ces architectures parallèles spécifiques pour des simulations physiques à grande échelle. Cette étude nous permet de mettre en avant un goulot d'étranglement en particulier limitant la performance des simulations. Partons d'un cas typique : les fissures d'une structure complexe de type barrage en béton armé peuvent être modélisées par un ensemble de particules. La cohésion de la matière ainsi simulée est assurée par les interactions entre elles. Chaque particule est représentée en mémoire par un ensemble de paramètres physiques à consulter systématiquement pour tout calcul de forces entre deux particules. Ainsi, pour que les calculs soient rapides, les données de particules proches dans l'espace doivent être proches en mémoire. Dans le cas contraire, le nombre de défauts de cache augmente et la limite de bande passante de la mémoire peut être atteinte, particulièrement en parallèle, bornant les performances. L'enjeu est de maintenir l'organisation des données en mémoire tout au long de la simulation malgré les mouvements des particules. Les algorithmes de tri standard ne sont pas adaptés car ils trient systématiquement tous les éléments. De plus, ils travaillent sur des structures denses ce qui implique de nombreux déplacements de données en mémoire. Nous proposons PaVo, un algorithme de tri dit adaptatif, c'est-à-dire qu'il sait tirer parti de l'ordre pré-existant dans une séquence. De plus, PaVo maintient des trous dans la structure, répartis de manière à réduire le nombre de déplacements mémoires nécessaires. Nous présentons une généreuse étude expérimentale et comparons les résultats obtenus à plusieurs tris renommés. La diminution des accès à la mémoire a encore plus d'importance pour des simulations à grande échelles sur des architectures parallèles. Nous détaillons une version parallèle de PaVo et évaluons son intérêt. Pour tenir compte de l'irrégularité des applications, la charge de travail est équilibrée dynamiquement par vol de travail. Nous proposons de distribuer automatiquement les données en mémoire de manière à profiter des architectures hiérarchiques. Les tâches sont pré-assignées aux cœurs pour utiliser cette distribution et nous adaptons le moteur de vol pour favoriser des vols de tâches concernant des données proches en mémoire. / Gamers are used to throw onto the latest graphics cards to play immersive games which precision, realism and interactivity keep increasing over time. With general-propose processing on graphics processing units, scientists now participate in graphics card use too. First, we examine these architectures interest for large-scale physics simulations. Drawing on this experience, we highlight in particular a bottleneck in simulations performance. Let us consider a typical situation: cracks in complex reinforced concrete structures such as dams are modelised by many particles. Interactions between particles simulate the matter cohesion. In computer memory, each particle is represented by a set of physical parameters used for every force calculations between two particles. Then, to speed up computations, data from particles close in space should be close in memory. Otherwise, the number of cache misses raises up and memory bandwidth may be reached, specially in parallel environments, limiting global performance. The challenge is to maintain data organization during the simulations despite particle movements. Classical sorting algorithms do not suit such situations because they consistently sort all the elements. Besides, they work upon dense structures leading to a lot of memory transfers. We propose PaVo, an adaptive sort which means it benefits from sequence presortedness. Moreover, to reduce the number of necessary memory transfers, PaVo spreads some gaps inside the data structure. We present a large experimental study and confront results to reputed sort algorithms. Reducing memory requests is again more important for large scale simulations with parallel architectures. We detail a parallel version of PaVo and evaluate its interest. To deal with application irregularities, we do load balancing with work-stealing. We take advantage of hierarchical architectures by automatically distributing data in memory. Thus, tasks are pre-assigned to cores with respect to this organization and we adapt the scheduler to favor steals of tasks working on data close in memory.

La résolution de systèmes d'équations linéaires creux est au cœur de nombreux domaines d'applications. De même que la quantité de ressources de calcul augmente dans les architectures modernes, offrant ainsi de nouvelles perspectives, la taille des problèmes rencontré de nos jours dans les applications de simulations numériques augmente aussi et de façon significative. L'exploitation des architectures modernes pour la résolution efficace de problèmes de très grande taille devient ainsi un défit a relever, aussi bien d'un point de vue théorique que d'un point de vue algorithmique. L'objectif de cette thèse est d'adresser les problèmes de scalabilité des solveurs creux directs basés sur les méthodes multifrontales en environnements parallèles asynchrones. Dans la première partie de la thèse, nous nous intéressons a l'exploitation du parallélisme multicoeur sur les architectures a mémoire partagée. Nous introduisons une variante de l'algorithme Geist-Ng afin de gérer aussi bien un parallélisme a grain fin, a travers l'utilisation de librairies BLAS séquentiel et parallèle optimisées, que d'un parallélisme a plus gros grain, a travers l'utilisation de parallélisme a base de directives OpenMP. Nous considérons aussi des aspects mémoire afin d'améliorer les performances sur des architectures NUMA: (i) d'une part, nous analysons l'influence de la localité mémoire et utilisons des stratégies d'allocation mémoire adaptatives pour gérer les espaces de travail privés et partagés; (ii) d'autre part, nous nous intéressons au problème de partages de ressources sur les architectures multicoeurs, qui induisent des pénalités en termes de performances. Enfin, afin d'éviter que des ressources ne reste inertes a la fin de l'exécution de leurs taches, et ainsi, afin d'exploiter au mieux les ressources disponibles, nous proposons un algorithme conceptuellement proche de l'approche dite de vol de travail, et qui consiste a assigner les ressources de calculs inactives au taches de travail actives de façon dynamique. Dans la deuxième partie de cette thèse, nous nous intéressons aux architectures hybrides, a base de mémoire partagées et de mémoire distribuées, pour lesquels un travail particulier est nécessaire afin d'améliorer la scalabilité du traitement de problèmes de grande taille. Nous étudions et optimisons tout d'abord les noyaux d'algèbre linéaire danse utilisé dans les méthodes multifrontales en environnent distribué asynchrone, en repensant les variantes right-looking et left-looking de la factorisation LU avec pivotage partiel dans notre contexte distribué. De plus, du fait du parallélisme multicoeurs, la proportion des communications relativement aux calculs et plus importante. Nous expliquons comment construire des algorithmes de mapping qui minimisent les communications entres nœuds de l'arbre de dépendances de la méthode multifrontale. Nous montrons aussi que les communications asynchrones collectives deviennent christiques sur grand nombres de processeurs, et que les broadcasts asynchrones a base d'arbres de broadcast doivent être utilisés. Nous montrons ensuite que dans un contexte multifrontale complètement asynchrone, où plusieurs instances de tels communications ont lieux, de nouveaux problèmes de synchronisation apparaissent. Nous analysons et caractérisons les situations de deadlock possibles et établissons formellement des propriétés générales simples afin de résoudre ces problèmes de deadlock. Nous établissons par la suite des propriétés nous permettant de relâcher les synchronisations induites par la solutions précédentes, et ainsi, d'améliorer les performances. Enfin, nous montrons que les synchronisations peuvent être relâchées dans un solveur creux danse et illustrons les gains en performances, sur des problèmes de grande taille issue d'applications réelles, dans notre environnement multifrontale complètement asynchrone. / The solution of sparse systems of linear equations is at the heart of numerous applicationfields. While the amount of computational resources in modern architectures increases and offersnew perspectives, the size of the problems arising in today’s numerical simulation applicationsalso grows very much. Exploiting modern architectures to solve very large problems efficiently isthus a challenge, from both a theoretical and an algorithmic point of view. The aim of this thesisis to address the scalability of sparse direct solvers based on multifrontal methods in parallelasynchronous environments.In the first part of this thesis, we focus on exploiting multi-threaded parallelism on sharedmemoryarchitectures. A variant of the Geist-Ng algorithm is introduced to handle both finegrain parallelism through the use of optimized sequential and multi-threaded BLAS libraries andcoarser grain parallelism through explicit OpenMP based parallelization. Memory aspects arethen considered to further improve performance on NUMA architectures: (i) on the one hand,we analyse the influence of memory locality and exploit adaptive memory allocation strategiesto manage private and shared workspaces; (ii) on the other hand, resource sharing on multicoreprocessors induces performance penalties when many cores are active (machine load effects) thatwe also consider. Finally, in order to avoid resources remaining idle when they have finishedtheir share of the work, and thus, to efficiently exploit all computational resources available, wepropose an algorithm wich is conceptually very close to the work-stealing approach and whichconsists in dynamically assigning idle cores to busy threads/activities.In the second part of this thesis, we target hybrid shared-distributed memory architectures,for which specific work to improve scalability is needed when processing large problems. We firststudy and optimize the dense linear algebra kernels used in distributed asynchronous multifrontalmethods. Simulation, experimentation and profiling have been performed to tune parameterscontrolling the algorithm, in correlation with problem size and computer architecture characteristics.To do so, right-looking and left-looking variants of the LU factorization with partialpivoting in our distributed context have been revisited. Furthermore, when computations are acceleratedwith multiple cores, the relative weight of communication with respect to computationis higher. We explain how to design mapping algorithms minimizing the communication betweennodes of the dependency tree of the multifrontal method, and show that collective asynchronouscommunications become critical on large numbers of processors. We explain why asynchronousbroadcasts using standard tree-based communication algorithms must be used. We then showthat, in a fully asynchronous multifrontal context where several such asynchronous communicationtrees coexist, new synchronization issues must be addressed. We analyse and characterizethe possible deadlock situations and formally establish simple global properties to handle deadlocks.Such properties partially force synchronization and may limit performance. Hence, wedefine properties which enable us to relax synchronization and thus improve performance. Ourapproach is based on the observation that, in our case, as long as memory is available, deadlockscannot occur and, consequently, we just need to keep enough memory to guarantee thata deadlock can always be avoided. Finally, we show that synchronizations can be relaxed in astate-of-the-art solver and illustrate the performance gains on large real problems in our fullyasynchronous multifrontal approach.

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures. / New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures.