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 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.

Puisque les ordinateurs sont omniprésents dans notre société et que, de plus en plus, nous dépendons de programmes pour accomplir nos activités de tous les jours, les bogues peuvent parfois avoir des conséquences cruciales. Une grande proportion des programmes existants sont écrits en C ou en C++ et la plupart des erreurs avec ces langages sont dues à l’absence de sûreté d’accès à la mémoire. Notre objectif à long terme est d’être en mesure de vérifier si un programme C ou C++ accède correctement à la mémoire malgré les défauts de ces langages. À cette fin, nous avons créé un cadre de développement d’analyses statiques que nous présentons dans ce mémoire. Il permet de construire des analyses à partir de petits composants réutilisables qui sont liés automatiquement par métaprogrammation. Il incorpore également le modèle de conception (design pattern) du visiteur et des algorithmes utiles pour faire de l’analyse statique. De plus, il fournit un modèle objet pour le RTL, la représentation intermédiaire de bas niveau pour tous les langages supportés par GCC. Ceci implique qu’il est possible de concevoir des analyses indépendantes des langages de programmation. Nous décrivons également les modules que comporte l’analyse statique que nous avons développée à l’aide de notre cadre d’analyse et qui vise à vérifier si un programme respecte les règles d’accès à la mémoire. Cette analyse n’est pas complète, mais elle est conçue pour être améliorée facilement. Autant le cadre d’analyse que les modules d’analyse des accès à la mémoire sont distribués dans RTL-Check, un logiciel libre. / Since computers are ubiquitous in our society and we depend more and more on programs to accomplish our everyday activities, bugs can sometimes have serious consequences. A large proportion of existing programs are written in C or C++ and the main source of errors with these programming languages is the absence of memory safety. Our long term goal is to be able to verify if a C or C++ program accesses memory correctly in spite of the deficiencies of these languages. To that end, we have created a static analysis framework which we present in this thesis. It allows building analyses from small reusable components that are automatically bound together by metaprogramming. It also incorporates the visitor design pattern and algorithms that are useful for the development of static analyses. Moreover, it provides an object model for RTL, the low-level intermediate representation for all languages supported by GCC. This implies that it is possible to design analyses that are independent of programming languages. We also describe the modules that comprise the static analysis we have developed using our framework and which aims to verify if a program is memory-safe. This analysis is not yet complete, but it is designed to be easily improved. Both our framework and our memory access analysis modules are distributed in RTL-Check, an open-source project.

La problématique abordée dans ce travail est celle de la gestion mémoire automatique pour des programmes Java temps-réel embarqués. Dans des langages comme le C ou le C++, la mémoire est typiquement gérée explicitement par le programmeur, ce qui est la source de nombreuses erreurs d'exécution causées par des manipulations hasardeuses. Le coût de correction de telles erreurs est très important car ces erreurs sont rarement reproductibles et donc difficiles à appréhender. En Java la gestion mémoire est entièrement automatique, ce qui facilite considérablement le développement. Cependant, les techniques classiques de recyclage de la mémoire, typiquement basées sur l'utilisation d'un ramasse-miettes, sont souvent considérées comme inapplicables dans le contexte des applications temps-réel embarquées, car il est très difficile de prédire leur temps de réponse. Cette incompatibilité est un frein important à l'adoption de langages de haut niveau comme Java dans ce domaine.<br />Pour résoudre le problème de la prévisibilité du temps d'exécution des opérations mémoire, nous proposons une approche fondée sur l'utilisation d'un modèle mémoire en régions. Cette technique, en groupant physiquement les objets de durées de vie similaires dans des zones gérées d'un seul bloc, offre en effet un comportement temporel prévisible. Afin de décider du placement des objets dans les différentes régions, nous proposons un algorithme d'analyse statique qui calcule une approximation des relations de connexion entre les objets. Chaque structure de données est ainsi placée dans une région distincte. L'analyse renvoie également au programmeur des informations sur le comportement mémoire du programme, de façon à le guider vers un style de programmation propice à la gestion mémoire en régions, tout en pesant le moins possible sur le développement. <br />Nous avons implanté un gestionnaire mémoire automatique en régions dans la machine virtuelle JITS destinée aux systèmes embarqués à faibles ressources. Les résultats expérimentaux ont montré que notre approche permet dans la plupart des cas de recycler la mémoire de façon satisfaisante, tout en présentant un comportement temporel prévisible. Le cas échéant, l'analyse statique indique au développeur quels sont les points problématiques dans le code, afin de l'aider à améliorer son programme.

Cette thèse est consacrée à l'étude de plusieurs problèmes d'optimisation combinatoire qui se présentent dans le domaine du calcul parallèle embarqué. En particulier, la gestion optimale de la mémoire et des problèmes d'ordonnancement pour les applications flot de données exécutées sur des processeurs massivement multicœurs sont étudiés. Deux techniques d'optimisation d'accès à la mémoire sont considérées : la réutilisation des données et le préchargement. La gestion des accès à la mémoire est déclinée en trois problèmes d'optimisation combinatoire. Dans le premier problème, une stratégie de préchargement pour les applications flot de données est étudiée, de façon à minimiser le temps d'exécution de l'application. Ce problème est modélisé comme un flow shop hybride sous contraintes de précédence, un problème \mathcal{NP}\text{-difficile} . Un algorithme de résolution heuristique avec deux bornes inférieures sont proposés afin de faire une estimation conservatrice, quoique suffisamment précise, de la distance à l'optimum des solutions obtenues. Le deuxième problème traite de l'exécution conditionnelle dépendante des données et de la gestion optimale du préchargement pour les structures de branchement. Quelques fonctions économiques, ainsi que des techniques de préchargement, sont examinées. Dans tous ces cas des algorithmes de résolution polynomiaux sont proposés. Le troisième problème consiste à ordonner un ensemble de tâches de façon à maximiser la réutilisation des données communes. Ce problème étant \mathcal{NP}\text{-difficile} , ce que nous avons établi, nous avons proposé deux algorithmes heuristiques. La distance à l'optimum des solutions est estimée en utilisant des solutions exactes. Ces dernières sont obtenues à l'aide d'une méthode branch-and-bound que nous avons proposée.

La mémoire est considérée comme étant gloutonne en consommation d'énergie, un problème sensible, particulièrement dans les systèmes embarqués. L'optimisation globale de fonctions multimodales est également un problème délicat à résoudre du fait de la grande quantité d'optima locaux de ces fonctions. Dans ce mémoire, je présente différents nouveaux algorithmes hybrides et distribués afin de résoudre ces deux problèmes d'optimisation. Ces algorithmes sont comparés avec les méthodes classiques utilisées dans la littérature et les résultats obtenus sont encourageants. En effet, ces résultats montrent une réduction de la consommation d'énergie en mémoire d'environ 76% jusqu'à plus de 98% sur nos programmes tests, d'une part. D'autre part, dans le cas de l'optimisation globale de fonctions multimodales, nos algorithmes hybrides convergent plus souvent vers la solution optimale globale. Des versions distribuées et coopératives de ces nouveaux algorithmes hybrides sont également proposées. Elles sont, par ailleurs, plus rapides que leurs versions séquentielles respectives. / Résumé en anglais : Memory is considered to be greedy in energy consumption, a sensitive issue, especially in embedded systems. The global optimization of multimodal functions is also a difficult problem because of the large number of local optima of these functions. In this thesis report, I present various new hybrid and distributed algorithms to solve these two optimization problems. These algorithms are compared with conventional methods used in the literature and the results obtained are encouraging. Indeed, these results show a reduction in memory energy consumption by about 76% to more than 98% on our benchmarks on one hand. On the other hand, in the case of global optimization of multimodal functions, our hybrid algorithms converge more often to the global optimum solution. Distributed and cooperative versions of these new hybrid algorithms are also proposed. They are more faster than their respective sequential versions.

Du fait qu'il constitue un passage obligé du flux d'information, un serveur de données joue un rôle central dans l'architecture d'un système d'information (SI). Il doit en conséquence implanter des mécanismes de gestion de ressources efficaces et des politiques de gestion adaptées aux caractéristiques comportementales du SI.<br />Il n'est malheureusement pas possible d'offrir un serveur de données universel capable de répondre aux exigences de tous les SI. Ceux-ci diffèrent en effet significativement par le type des informations qu'ils traitent, la nature des traitements effectués, les propriétés de traitement qu'ils garantissent, les caractéristiques du matériel sous-jacent, etc. De ce fait, chaque système d'information intègre son ou ses propres serveurs de données implantant des politiques de gestion figées.<br />Les inconvénients d'une telle approche sont loin d'être négligeables. Tout d'abord, la ré-implantation de mécanismes élémentaires de gestion de ressources augmente le coût de conception. Ensuite, la rigidité comportementale réduit considérablement la réactivité à l'évolution tant en qualité qu'en quantité des informations, traitements et ressources matérielles. Enfin, l'opacité des tels systèmes rend difficile leur coexistence sur une même plate-forme.<br />Cette thèse montre qu'il n'existe pas de politique de gestion de la mémoire idéale. Plutôt que d'essayer d'offrir un serveur idéal, elle tente de définir une infrastructure permettant de concevoir des serveurs de données adaptés et évolutifs. Elle adresse plus particulièrement le problème de la gestion de la mémoire physique et se place dans le contexte des grappes de machines. Elle propose le support mémoire adaptable ADAMS basé sur un modèle de gestion hiérarchique et un modèle de communication par événements. Ce support facilite l'intégration de différents types de politiques tout en séparant bien leurs rôles respectifs sans faire d'hypothèse sur leur inter-dépendances.<br />Une intégration d'ADAMS à la mémoire virtuelle répartie permanente et adaptable du système Arias est ensuite exposée. ADAMS étend les caractéristiques de ce système afin de prendre en compte les besoins particulier de gestion des serveurs de données tout en réduisant le grain d'adaptabilité. Nous illustrons à travers un exemple comment le support résultant permet d'implanter un serveur de données dont les politiques de gestion peuvent être adaptées dynamiquement.