Le domaine du calcul haute performance (i.e. la science des super-calculateurs)est caractérisé par l’évolution continuelle des architectures de calcul, la proliférationdes ressources de calcul et la complexité croissante des problèmes que les utilisateursveulent résoudre. Un des logiciels les plus importants de la pile logicielle dessupercalculateurs est le Système de Gestion des Ressources et des Tâches. Il est lelien entre la charge de travail donnée par les utilisateurs et la plateforme de calcul. Cetype de logiciels spécialisés fournit des fonctions pour construire, soumettre, planifieret surveiller les tâches dans un environnent de calcul complexe et dynamique.Pour pouvoir atteindre des supercalculateurs exaflopiques, de nouvelles con-traintes et objectifs ont été inventés. Cette thèse développe et teste l’idée que lesutilisateurs de ces systèmes peuvent aider à atteindre l’échelle exaflopique. Spé-cifiquement, nous montrons des techniques qui utilisent les comportements desutilisateurs pour améliorer la consommation énergétique et les performances glob-ales des supercalculateurs.Pour tester ces nouvelles techniques, nous avons besoin de nouveaux outils etméthodes qui sont capables d’aller jusqu’à l’échelle exaflopique. Nous proposonsdonc des outils qui permettent de tester de nouveaux algorithmes capables des’exécuter sur ces systèmes. Ces outils sont capables de fonctionner sur de petitssupercalculateurs en émulant ou simulant des systèmes plus puissants. Après avoirévalué différentes techniques pour mesurer l’énergie dans les supercalculateurs, nousproposons une nouvelle heuristique, basée sur un algorithme répandu (Easy Backfill-ing), pour pouvoir contrôler la puissance électrique de ces énormes systèmes. Nousmontrons aussi comment, en utilisant la même méthode, contrôler la consommationénergétique pendant une période de temps. Le mécanisme proposé peut limiterla consommation énergétique tout en gardant des performances satisfaisantes. Sil’énergie est une ressource limitée, il faut la partager équitablement. Nous présen-tons de plus un mécanisme permettant de partager la consommation énergétiqueentre les utilisateurs. Nous soutenons que cette méthode va motiver les utilisateursà réduire la consommation énergétique de leurs calculs. Finalement, nous analysonsle comportement actuel et passé des utilisateurs pour améliorer les performancesdes supercalculateurs. Cette approche non seulement surpasse les performances destravaux existants, mais aussi ouvre la voie à l’utilisation de méthodes semblablesdans d’autres aspects des Systèmes de Gestion des Ressources et des Tâches. / The field of High Performance Computing (HPC) is characterized by the contin-uous evolution of computing architectures, the proliferation of computing resourcesand the increasing complexity of applications users wish to solve. One of the mostimportant software of the HPC stack is the Resource and Job Management System(RJMS) which stands between the user workloads and the platform, the applica-tions and the resources. This specialized software provides functions for building,submitting, scheduling and monitoring jobs in a dynamic and complex computingenvironment.In order to reach exaflops HPC systems, new constraints and objectives havebeen introduced. This thesis develops and tests the idea that the users of suchsystems can help reaching the exaflopic scale. Specifically, we show and introducenew techniques that employ users behaviors to improve energy consumption andoverall cluster performances.To test the proposed techniques, we need to develop new tools and method-ologies that scale up to large HPC clusters. Thus, we designed adequate tools thatassess new RJMS scheduling algorithms of such large systems. These tools areable to run on small clusters by emulating or simulating bigger platforms. Afterevaluating different techniques to measure the energy consumption of HPC clusters,we propose a new heuristic, based on the popular Easy Backfilling algorithm, inorder to control the power consumption of such huge systems. We also demonstrate,using the same idea, how to control the energy consumption during a time period.The proposed mechanism is able to limit the energy consumption while keepingsatisfying performances. If energy is a limited resource, it has to be shared fairly.We also present a mechanism which shares energy consumption among users. Weargue that sharing fairly the energy among users should motivate them to reducethe energy consumption of their applications. Finally, we analyze past and presentbehaviors of users using learning algorithms in order to improve the performancesof the parallel platforms. This approach does not only outperform state of the artmethods, it also shows promising insight on how such method can improve otheraspects of RJMS.

La hiérarchie mémoire des serveurs de calcul est de plus en plus complexe. Les machines disposent de plusieurs niveaux de caches plus ou moins partagés et d’une mémoire distribuée. Plus récemment le paysage du Calcul Haute Performance (CHP) a vu apparaître des mémoires adressables embarquées dans le processeur ainsi que de nouvelles mémoires non-volatiles (périphérique mémoire sur le bus d’entrées sorties et prochainement de la mémoire non-volatile directement sur le bus mémoire). Cette hiérarchie est nécessaire pour espérer obtenir de bonnes performances de calcul, au prix d’une gestion minutieuse du placement des données et des tâches de calcul. Là où la gestion des caches était entièrement matérielle et masquée au développeur, le choix du placement des données dans telle ou telle zone de mémoire, plus ou moins rapide, volatile ou non, volumineuse ou non, est maintenant paramétrable logiciellement. Cette nouvelle flexibilité donne une grande liberté aux développeurs mais elle complexifie surtout leur travail quand il s’agit de choisir les stratégies d’allocation, de communication, de placement, etc. En effet, les caractéristiques des nombreux niveaux de hiérarchie impliqués varient significativement en vitesse, taille et fonctionnalités. Dans cette thèse, co-encadrée entre Atos Bull Technologies et Inria Bordeaux– Sud-Ouest, nous détaillons la structure des plates-formes contemporaines et caractérisons la performance des accès à la mémoire selon plusieurs scénarios de localité des tâches de calcul et des données accédées. Nous expliquons comment la sémantique du langage de programmation impacte la localité des données dans la machine et donc la performance des applications. En collaboration avec le laboratoire INESC-ID de Lisbonne, nous proposons une extension au célèbre modèle Roofline pour exposer de manière intelligible les compromis de performance et de localité aux développeurs d’applications. Nous proposons par ailleurs un outil de synthèse de métriques de localité mettant en lien les évènements de performance de l’application et de la machine avec la topologie de cette dernière. Enfin, nous proposons une approche statistique pour sélectionner automatiquement la meilleure politique de placement des tâches de calcul sur les coeurs de la machine et des données sur les mémoires. / Through years, the complexity of High Performance Computing (HPC) systems’ memory hierarchy has increased. Nowadays, large scale machines typically embed several levels of caches and a distributed memory. Recently, on-chip memories and non-volatile PCIe based flash have entered the HPC landscape. This memory architecture is a necessary pain to obtain high performance, but at the cost of a thorough task and data placement. Hardware managed caches used to hide the tedious locality optimizations. Now, data locality, in local or remote memories, in fast or slow memory, in volatile or non-volatile memory, with small or wide capacity, is entirely software manageable. This extra flexibility grants more freedom to application designers but with the drawback of making their work more complex and expensive. Indeed, when managing tasks and data placement, one has to account for several complex trade-offs between memory performance, size and features. This thesis has been supervised between Atos Bull Technologies and Inria Bordeaux – Sud-Ouest. In the hereby document, we detail contemporary HPC systems and characterize machines performance for several locality scenarios. We explain how the programming language semantics affects data locality in the hardware, and thus applications performance. Through a joint work with the INESC-ID laboratory in Lisbon, we propose an insightful extension to the famous Roofline performance model in order to provide locality hints and improve applications performance. We also present a modeling framework to map platform and application performance events to the hardware topology, in order to extract synthetic locality metrics. Finally, we propose an automatic locality policy selector, on top of machine learning algorithms, to easily improve applications tasks and data placement.

Le besoin de simuler des phénomènes toujours plus complexes accroît les besoinsen puissance de calcul, tout en consommant et produisant de plus en plus dedonnées.Pour répondre à cette demande, la taille et l'hétérogénéité des plateformes decalcul haute performance augmentent.L'hétérogénéité permet en effet de découper les problèmes en sous-problèmes,pour lesquels du matériel ou des algorithmes ad hoc sont plus efficients.Cette hétérogénéité se manifeste dans l'architecture des plateformes et dans lavariété des applications exécutées.Aussi, les performances sont de plus en plus sensibles au contexte d'exécution.L'objet de cette thèse est de considérer, qualitativement et à faible coût,l'impact du contexte d'exécution dans les politiques d'allocation etd'ordonnancement.Cette étude est menée à deux niveaux: au sein d'applications uniques, et àl'échelle des plateformes au niveau inter-applications.Nous étudions en premier lieu la minimisation du temps de complétion pour destâches séquentielles sur des plateformes hybrides intégrant des CPU et des GPU.Nous proposons de tenir compte du contexte d'exécution grâce à un mécanismed'affinité améliorant le comportement local des politiques d'ordonnancement.Ce mécanisme a été implémenté dans un run-time parallèle.Une campagne d'expérience montre qu'il permet de diminuer les transferts dedonnées tout en conservant un faible temps de complétion.Puis, afin de prendre implicitement en compte le parallélisme sur les CPU, nousenrichissons le modèle en considérant les tâches comme moldables sur CPU.Nous proposons un algorithme basé sur la programmation linéaire en nombresentiers.Cet algorithme efficace a un rapport de compétitivité de 3/2+ε.Dans un second temps, nous proposons un nouveau cadre de modélisation danslequel les contraintes sont des outils de premier ordre.Plutôt que d'étendre les modèles existants en considérant toutes lesinteractions possibles, nous réduisons l'espace des ordonnancements réalisablesvia l'ajout de contraintes.Nous proposons des contraintes raisonnables pour modéliser l'étalement desapplications ainsi que les flux d'E/S.Nous proposons ensuite une étude de cas exhaustive dans le cadre de laminimisation du temps de complétion pour des topologies unidimensionnelles,sous les contraintes de convexité et de localité. / The demand for computation power is steadily increasing, driven by the need tosimulate more and more complex phenomena with an increasing amount ofconsumed/produced data.To meet this demand, the High Performance Computing platforms grow in both sizeand heterogeneity.Indeed, heterogeneity allows splitting problems for a more efficient resolutionof sub-problems with ad hoc hardware or algorithms.This heterogeneity arises in the platforms' architecture and in the variety ofprocessed applications.Consequently, the performances become more sensitive to the execution context.We study in this thesis how to qualitatively bring—at a reasonablecost—context-awareness/obliviousness into allocation and scheduling policies.This study is conducted from two standpoints: within single applications, andat the whole platform scale from an inter-applications perspective.We first study the minimization of the makespan of sequential tasks onplatforms with a mixed architecture composed of multiple CPUs and GPUs.We integrate context-awareness into schedulers with an affinity mechanism thatimproves local behavior.This mechanism has been implemented in a parallel run-time, and experimentsshow that it is able to reduce the memory transfers while maintaining a lowmakespan.We then extend the model to implicitly consider parallelism on the CPUs withthe moldable-task model.We propose an efficient algorithm formulated as an integer linear program witha constant performance guarantee of 3/2+ε.Second, we devise a new modeling framework where constraints are a first-classtool.Rather than extending existing models to consider all possible interactions, wereduce the set of feasible schedules by further constraining existing models.We propose a set of reasonable constraints to model application spreading andI/O traffic.We then instantiate this framework for unidimensional topologies, and propose acomprehensive case study of the makespan minimization under convex and localconstraints.

La période de réionisation est une transition dans l'histoire de l'Univers qui change sont état d'ionisation. Les progrès en calcul intensif permettent maintenant de modéliser l'évolution du phénomène. D'habitude, les analyses se concentrent sur l'évolution de propriétés globales dans les simulations. Différemment, j'ai mis au point une nouvelle technique d'analyse de simulations qui permet d'appréhender le phémomène global de manière locale. Elle s'appuie sur l'extraction d'un arbre de fusion de régions HII pour caractériser le processus de réionisation. La technique a été appliqué dans plusieurs simulations où différents modèles de sources ont été considérés pour étudier leur impact sur la chrono-morphologie du processus. Dans un second temps, l’arbre a permis de caractériser l'histoire de réionisation passée de galaxies de types Voie Lactée. Enfin, la technique a été appliquée dans des simulations du Groupe Local pour quantifier l'histoire de réionisation de MW et M31. / The reionization period is a major step in the history of the Universe that change its ionization state. The increasing progress in high performance computing, allows us to model the phenomenon. Usually, the simulation analyses focus on global properties to constrain the impact of the physic put in the simulations. Alternately, I implemented a method of analysis that apprehend theglobal reionization in terms of multiple ‘local reionizations’. I extracted a merger tree of HII regions from the simulations to characterize the reionization process. I applied the technique in several cosmological simulations, where different ionizing source models were tested to investigate the impact of the source model on the reionization chrono-morphology. I also used the merger tree to characterize the past reionization history of MW type galaxies. I finally applied this methodology in Local Group simulations to quantify the reionization hystory of MW and M31.

L’utilisation du parallélisme des architectures actuelles dans le domaine du calcul hautes performances, oblige à recourir à différents langages parallèles. Ainsi, l’utilisation conjointe de MPI pour le parallélisme gros grain, à mémoire distribuée et OpenMP pour du parallélisme de thread, fait partie des pratiques de développement d’applications pour supercalculateurs. Des erreurs, liées à l’utilisation conjointe de ces langages de parallélisme, sont actuellement difficiles à détecter et cela limite l’écriture de codes, permettant des interactions plus poussées entre ces niveaux de parallélisme. Des outils ont été proposés afin de palier ce problème. Cependant, ces outils sont généralement focalisés sur un type de modèle et permettent une vérification dite statique (à la compilation) ou dynamique (à l’exécution). Pourtant une combinaison statique/- dynamique donnerait des informations plus pertinentes. En effet, le compilateur est en mesure de donner des informations relatives au comportement général du code, indépendamment du jeu d’entrée. C’est par exemple le cas des problèmes liés aux communications collectives du modèle MPI. Cette thèse a pour objectif de développer des analyses statiques/dynamiques permettant la vérification d’une application parallèle mélangeant plusieurs modèles de programmation, afin de diriger les développeurs vers un code parallèle multi-modèles correct et performant. La vérification se fait en deux étapes. Premièrement, de potentielles erreurs sont détectées lors de la phase de compilation. Ensuite, un test au runtime est ajouté pour savoir si le problème va réellement se produire. Grâce à ces analyses combinées, nous renvoyons des messages précis aux utilisateurs et évitons les situations de blocage. / Supercomputing plays an important role in several innovative fields, speeding up prototyping or validating scientific theories. However, supercomputers are evolving rapidly with now millions of processing units, posing the questions of their programmability. Despite the emergence of more widespread and functional parallel programming models, developing correct and effective parallel applications still remains a complex task. Although debugging solutions have emerged to address this issue, they often come with restrictions. However programming model evolutions stress the requirement for a convenient validation tool able to handle hybrid applications. Indeed as current scientific applications mainly rely on the Message Passing Interface (MPI) parallel programming model, new hardwares designed for Exascale with higher node-level parallelism clearly advocate for an MPI+X solutions with X a thread-based model such as OpenMP. But integrating two different programming models inside the same application can be error-prone leading to complex bugs - mostly detected unfortunately at runtime. In an MPI+X program not only the correctness of MPI should be ensured but also its interactions with the multi-threaded model, for example identical MPI collective operations cannot be performed by multiple nonsynchronized threads. This thesis aims at developing a combination of static and dynamic analysis to enable an early verification of hybrid HPC applications. The first pass statically verifies the thread level required by an MPI+OpenMP application and outlines execution paths leading to potential deadlocks. Thanks to this analysis, the code is selectively instrumented, displaying an error and synchronously interrupting all processes if the actual scheduling leads to a deadlock situation.

Afin de répondre aux besoins croissants de la simulation numérique et de rester à la pointe de la technologie, les supercalculateurs doivent d’être constamment améliorés. Ces améliorations peuvent être d’ordre matériel ou logiciel. Cela force les applications à s’adapter à un nouvel environnement de programmation au fil de son développement. Il devient alors nécessaire de se poser la question de la pérennité des applications et de leur portabilité d’une machine à une autre. L’utilisation de machines virtuelles peut être une première réponse à ce besoin de pérennisation en stabilisant les environnements de programmation. Grâce à la virtualisation, une application peut être développée au sein d’un environnement figé, sans être directement impactée par l’environnement présent sur une machine physique. Pour autant, l’abstraction supplémentaire induite par les machines virtuelles entraine en pratique une perte de performance. Nous proposons dans cette thèse un ensemble d’outils et de techniques afin de permettre l’utilisation de machines virtuelles en contexte HPC. Tout d’abord nous montrons qu’il est possible d’optimiser le fonctionnement d’un hyperviseur afin de répondre le plus fidèlement aux contraintes du HPC que sont : le placement des fils d’exécution et la localité mémoire des données. Puis en s’appuyant sur ce résultat, nous avons proposé un service de partitionnement des ressources d’un noeud de calcul par le biais des machines virtuelles. Enfin, pour étendre nos travaux à une utilisation pour des applications MPI, nous avons étudié les solutions et performances réseau d’une machine virtuelle. / To meet the growing needs of the digital simulation and remain at the forefront of technology, supercomputers must be constantly improved. These improvements can be hardware or software order. This forces the application to adapt to a new programming environment throughout its development. It then becomes necessary to raise the question of the sustainability of applications and portability from one machine to another. The use of virtual machines may be a first response to this need for sustaining stabilizing programming environments. With virtualization, applications can be developed in a fixed environment, without being directly impacted by the current environment on a physical machine. However, the additional abstraction induced by virtual machines in practice leads to a loss of performance. We propose in this thesis a set of tools and techniques to enable the use of virtual machines in HPC context. First we show that it is possible to optimize the operation of a hypervisor to respond accurately to the constraints of HPC that are : the placement of implementing son and memory data locality. Then, based on this, we have proposed a resource partitioning service from a compute node through virtual machines. Finally, to expand our work to use for MPI applications, we studied the network solutions and performance of a virtual machine.

Les travaux de thèse s'inscrivent dans le cadre du projet de recherche européen MAAXIMUS (More Affordable Aircraft through eXtended, Integrated and Mature nUmerical Sizing) et portent sur la simulation numérique de problèmes d'assemblages de composants en matériaux composites stratifiés. Ces assemblages sont sources de deux types de non-linéarités. D'une part, l'interface entre les pièce conduit au traitement de non-linéarités fortes (contact, frottement). D'autre part, dans les composants de l'assemblage, le comportement du matériau stratifié est complexe, du fait des nombreux phénomènes de dégradations interagissant entre eux. Ces deux aspects ont une influence forte sur la réponse globale de l'assemblage, ce qui implique la résolution de systèmes de très grandes tailles, nécessitant généralement l'utilisation de moyens de calcul parallèles.Le couplage entre ces deux problématiques nécessite donc l'utilisation d'algorithmes de calcul parallèle dédiés et robustes, à même de traiter de nombreuses non-linéarités très fortes. Pour cela, la méthode LATIN (pour LArge Time INcrement) présente de nombreux avantages, déjà mis en évidence dans le cas de calcul d'assemblages de pièces élastiques lors de travaux précédents. Le but de ces travaux est donc d'élargir le cadre de la méthode au cas des pièces au comportement endommageable et anélastique.Un dernier aspect, qui sera abordé au sein de ces travaux, traite des fortes variabilités des coefficients intervenant dans les lois non-linéaires. Par conséquent, il est nécessaire de pouvoir traiter un très grand nombre de problèmes affectés de valeurs de coefficients différents. Pour cela, la stratégie multiparamétrique, intimement liée à la méthode LATIN, doit être étendue au cas de comportements matériau non-linéaires. Elle sera alors appliquée au travers de plusieurs paramètres variables : coefficients de frottement, précharges des éléments de fixation, seuil d'endommagement des matériaux... / The presented work, within the framework of the European research project MAAXIMUS (More Affordable Aircraft through eXtended, Integrated and Mature nUmerical Sizing), is dedicated to the numerical simulation of assemblies with components made of laminated composites. These assemblies involve two types of high non-linearities. First ones are linked to the interfaces between parts (unilateral contact and friction). Second ones are linked to the constitutive material behaviour, from its initial properties to the complex evolution of degradations. These two non-linearities have a strong influence on the response of the assembly, which involves solving systems with a high number of degrees of freedom and generally requires the use of parallel computing resources.The coupling between the two sources of non-linearities requires dedicated and robust algorithms, able to run on parallel architectures and to deal with many very strong non-linearities. The efficiency of the LATIN method (LArge Time INcrement) has already been highlighted in the case of assemblies with elastic components. A first aim of this work is thus to extend the method to the case of damageable and anelastic components' behaviour.A second aim is to deal with the variability of the coefficients involved in the non-linear laws. Each set of parameters (friction coefficients, preload of fasteners, damage threshold of material laws...) requiring a given calculation, the multiparametric strategy of the LATIN method must be extended to the case of non-linear materials in order to efficiently reduce the computation time.

La simulation multi-agent représente une solution pertinente pour l’ingénierie et l’étude des systèmes complexes dans de nombreux domaines (vie artificielle, biologie, économie, etc.). Cependant, elle requiert parfois énormément de ressources de calcul, ce qui représente un verrou technologique majeur qui restreint les possibilités d'étude des modèles envisagés (passage à l’échelle, expressivité des modèles proposés, interaction temps réel, etc.).Parmi les technologies disponibles pour faire du calcul intensif (High Performance Computing, HPC), le GPGPU (General-Purpose computing on Graphics Processing Units) consiste à utiliser les architectures massivement parallèles des cartes graphiques (GPU) comme accélérateur de calcul. Cependant, alors que de nombreux domaines bénéficient des performances du GPGPU (météorologie, calculs d’aérodynamique, modélisation moléculaire, finance, etc.), celui-ci est peu utilisé dans le cadre de la simulation multi-agent. En fait, le GPGPU s'accompagne d’un contexte de développement très spécifique qui nécessite une transformation profonde et non triviale des modèles multi-agents. Ainsi, malgré l'existence de travaux pionniers qui démontrent l'intérêt du GPGPU, cette difficulté explique le faible engouement de la communauté multi-agent pour le GPGPU.Dans cette thèse, nous montrons que, parmi les travaux qui visent à faciliter l'usage du GPGPU dans un contexte agent, la plupart le font au travers d’une utilisation transparente de cette technologie. Cependant, cette approche nécessite d’abstraire un certain nombre de parties du modèle, ce qui limite fortement le champ d’application des solutions proposées. Pour pallier ce problème, et au contraire des solutions existantes, nous proposons d'utiliser une approche hybride (l'exécution de la simulation est partagée entre le processeur et la carte graphique) qui met l'accent sur l'accessibilité et la réutilisabilité grâce à une modélisation qui permet une utilisation directe et facilitée de la programmation GPU. Plus précisément, cette approche se base sur un principe de conception, appelé délégation GPU des perceptions agents, qui consiste à réifier une partie des calculs effectués dans le comportement des agents dans de nouvelles structures (e.g. dans l’environnement). Ceci afin de répartir la complexité du code et de modulariser son implémentation. L'étude de ce principe ainsi que les différentes expérimentations réalisées montre l'intérêt de cette approche tant du point de vue conceptuel que du point de vue des performances. C'est pourquoi nous proposons de généraliser cette approche sous la forme d'une méthodologie de modélisation et d'implémentation de simulations multi-agents spécifiquement adaptée à l'utilisation des architectures massivement parallèles. / Multi-Agent Based Simulations (MABS) represents a relevant solution for the engineering and the study of complex systems in numerous domains (artificial life, biology, economy, etc.). However, MABS sometimes require a lot of computational resources, which is a major constraint that restricts the possibilities of study for the considered models (scalability, real-time interaction, etc.).Among the available technologies for HPC (High Performance Computing), the GPGPU (General-Purpose computing on Graphics Processing Units) proposes to use the massively parallel architectures of graphics cards as computing accelerator. However, while many areas benefit from GPGPU performances (meteorology, molecular dynamics, finance, etc.). Multi-Agent Systems (MAS) and especially MABS hardly enjoy the benefits of this technology: GPGPU is very little used and only few works are interested in it. In fact, the GPGPU comes along with a very specific development context which requires a deep and not trivial transformation process for multi-agents models. So, despite the existence of works that demonstrate the interest of GPGPU, this difficulty explains the low popularity of GPGPU in the MAS community.In this thesis, we show that among the works which aim to ease the use of GPGPU in an agent context, most of them do it through a transparent use of this technology. However, this approach requires to abstract some parts of the models, what greatly limits the scope of the proposed solutions. To handle this issue, and in contrast to existing solutions, we propose to use a nhybrid approach (the execution of the simulation is shared between both the processor and graphics card) that focuses on accessibility and reusability through a modeling process that allows to use directly GPU programming while simplifying its use. More specifically, this approach is based on a design principle, called GPU delegation of agent perceptions, consists in making a clear separation between the agent behaviors, managed by the processor, and environmental dynamics, handled by the graphics card. So, one major idea underlying this principle is to identify agent computations which can be transformed in new structures (e.g. in the environment) in order to distribute the complexity of the code and modulate its implementation. The study of this principle and the different experiments conducted show the advantages of this approach from both a conceptual and performances point of view. Therefore, we propose to generalize this approach and define a comprehensive methodology relying on GPU delegation specifically adapted to the use of massively parallel architectures for MABS.

De plus en plus d'ordinateurs utilisent des architectures hybrides combinant des processeurs multi-cœurs (CPUs) et des accélérateurs matériels comme les GPUs (Graphics Processing Units). Ces plates-formes parallèles hybrides exigent de nouvelles stratégies d'ordonnancement adaptées. Cette thèse est consacrée à une caractérisation de ce nouveau type de problèmes d'ordonnancement. L'objectif le plus étudié dans ce travail est la minimisation du makespan, qui est un problème crucial pour atteindre le potentiel des nouvelles plates-formes en Calcul Haute Performance.Le problème central étudié dans ce travail est le problème d'ordonnancement efficace de n tâches séquentielles indépendantes sur une plateforme de m CPUs et k GPUs, où chaque tâche peut être exécutée soit sur un CPU ou sur un GPU, avec un makespan minimal. Ce problème est NP-difficiles, nous proposons donc des algorithmes d'approximation avec des garanties de performance allant de 2 à (2q + 1)/(2q) +1/(2qk), q> 0, et des complexités polynomiales. Il s'agit des premiers algorithmes génériques pour la planification sur des machines hybrides avec une garantie de performance et une fin pratique. Des variantes du problème central ont été étudiées : un cas particulier où toutes les tâches sont accélérées quand elles sont affectées à un GPU, avec un algorithme avec un ratio de 3/2, un cas où les préemptions sont autorisées sur CPU, mais pas sur GPU, le modèle des tâches malléables, avec un algorithme avec un ratio de 3/2. Enfin, le problème avec des tâches dépendantes a été étudié, avec un algorithme avec un ratio de 6. Certains des algorithmes ont été intégré dans l'ordonnanceur du système xKaapi. / More and more computers use hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like GPUs (Graphics Processing Units). These hybrid parallel platforms require new scheduling strategies. This work is devoted to a characterization of this new type of scheduling problems. The most studied objective in this work is the minimization of the makespan, which is a crucial problem for reaching the potential of new platforms in High Performance Computing. The core problem studied in this work is scheduling efficiently n independent sequential tasks with m CPUs and k GPUs, where each task of the application can be processed either on a CPU or on a GPU, with minimum makespan. This problem is NP-hard, therefore we propose approximation algorithms with performance ratios ranging from 2 to (2q+1)/(2q)+1/(2qk), q>0, and corresponding polynomial time complexities. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. Some variants of the core problem are studied: a special case where all the tasks are accelerated when assigned to a GPU, with a 3/2-approximation algorithm, a case where preemptions are allowed on CPUs, the same problem with malleable tasks, with an algorithm with a ratio of 3/2. Finally, we studied the problem with dependent tasks, providing a 6-approximation algorithm. Experiments based on realistic benchmarks have been conducted. Some algorithms have been integrated into the scheduler of the xKaapi runtime system for linear algebra kernels, and compared to the state-of-the-art algorithm HEFT.

En termes de prévention du risque associé aux séismes, la prédiction quantitative des phénomènes de propagation et d'amplification des ondes sismiques dans des structures géologiques complexes devient essentielle. Dans ce domaine, la simulation numérique est prépondérante et l'exploitation efficace des techniques de calcul haute performance permet d'envisager les modélisations à grande échelle nécessaires dans le domaine du risque sismique. Plusieurs évolutions récentes au niveau de l'architecture des machines parallèles nécessitent l'adaptation des algorithmes classiques utilisées pour la modélisation sismique. En effet, l'augmentation de la puissance des processeurs se traduit maintenant principalement par un nombre croissant de coeurs de calcul et les puces multicoeurs sont maintenant à la base de la majorité des architectures multiprocesseurs. Ce changement correspond également à une plus grande complexité au niveau de l'organisation physique de la mémoire qui s'articule généralement autour d'une architecture NUMA (Non Uniform Memory Access pour accès mémoire non uniforme)~de profondeur importante. Les contributions de cette thèse se situent à la fois au niveau algorithmique et numérique mais abordent également l'articulation avec les supports d'exécution optimisés pour les architectures multicoeurs. Les solutions retenues sont validées à grande échelle en considérant deux exemples de modélisation sismique. Le premier cas se situe dans la préfecture de Niigata-Chuetsu au Japon (événement du 16 juillet 2007) et repose sur la méthode des différences finies. Le deuxième exemple met en oeuvre la méthode des éléments finis. Un séisme hypothétique dans la région de Nice est modélisé en tenant compte du comportement non linéaire du sol.