L’analyse de stabilité en régime transitoire du réseau de transport électrique permet de contrôler le bon retour au régime stationnaire du système soumis à une perturbation. Cette analyse systématique des systèmes de réseaux en développement permet notamment d’optimiser la production et la consommation de l’énergie électrique, et de protéger les équipements tels que les centrales électriques, les transformateurs, les lignes haute-tension, etc. Afin d’améliorer la stabilité, la robustesse et la viabilité de ces systèmes, la tendance est à l’interconnexion des réseaux de transport régionaux et nationaux, et ainsi, au développement et à l’analyse de systèmes toujours plus grands. Le problème de stabilité électrique peut être simulé numériquement grâce à l’intégration d’un système d’équations algébro-différentielles non-linéaire et raide. Lorsque le problème traité est très grand, la simulation numérique devient très coûteuse en temps de calcul et ralentit considérablement le travail des professionnels du secteur. Cette thèse a pour but de proposer, d’étudier, et de développer des méthodes innovantes de calcul parallèle pour la résolution des systèmes d’équations différentielles issus de la simulation de grands réseaux électriques tel que le réseau européen. Dans ce manuscrit, on livre une analyse des propriétés de ces systèmes assez spécifiques : creux, irréguliers, non-linéaires, raides et hétérogènes. On discute notamment de la structure particulière de ces systèmes qui rend attrayante l’application d’une méthode de décomposition de domaine. On étudie ainsi plusieurs méthodes de parallélisation en espace : la parallélisation fine de chaque opération coûteuse, la résolution du système non-linéaire par décomposition en sous-réseaux faiblement couplés, d’abord sur chaque étape d’intégration, puis par méthode de relaxation d’ondes. On aborde aussi la parallélisation en temps de type algorithme Pararéel ainsi qu’une méthode parallèle espace-temps bénéficiant des propriétés couplées des méthodes de relaxation d’ondes et de Pararéel. Dans ces travaux, nous proposons des méthodes assurant la convergence rapide des méthodes de décomposition de domaine quel que soit le nombre de sous-domaines et de processeurs employés. Nous introduisons pour cela des techniques de préconditionnement en espace adéquates afin d’améliorer la scalabilité des méthodes de parallélisation envisagées. / Power system transient stability analysis enables to control the return to equilibrium of the system subjected to a disturbance. This systematic analysis of developing transport networks allows to optimize the production and the consumption of electric power and to protect the equipments such as power plants, transformers, highvoltage lines and so on. In order to improve the stability, the robustness, and the sustainability of these systems, a worldwide trend is to interconnect regional and national transport networks. This leads to analyze ever larger systems. The power-stability problem can be numerically simulated owing to the integration of a differential-algebraic system which is nonlinear and stiff. When considering a very large problem, numerical simulation is very time consuming and significantly slows down the work of professionals. This thesis aims at studying innovative parallel computing methods for the resolution of differential systems arising from the transient stability analysis of large power systems such as the European Transport Network. In this manuscript, we first deliver an analysis of the properties of these rather specific systems: sparse, irregular, nonlinear, stiff, and heterogeneous. We discuss the particular structure of these systems making the application of a domain decomposition method interesting. Thus, we study several space parallelization methods: the fine parallelization of each costly tasks, the resolution of the nonlinear system by decomposition into weakly coupled subnetworks, first on each integration step separately, and then by waveform relaxation method. We also address the time parallelization with a Parareal-based algorithm and a space-time parallel method which benefits from the coupled properties of waveform relaxation and Parareal methods. In this work, we focus on methods which ensure a fast convergence of domain decomposition methods whatever the number of subdomains/processors used. In order to achieve such a goal, we introduce space preconditioning techniques to improve the scalability of the parallelization methods considered.

Les faisceaux d'ions, sont communément utilisés dans le cadre de l'étude des matériaux du nucléaire dans le but de reproduire, dans une certaine mesure, les différentes sources d'irradiations auxquelles sont soumis ces matériaux. L’interaction des ions avec la matière induit la formation de défauts cristallins le long du trajet de ces ions, associée à d'importantes déformations au sein de la zone irradiée. L'un des principaux enjeux de l'industrie électro-nucléaire consiste en l'encapsulation, à long terme, des déchets nucléaires. La zircone yttriée (YSZ) est un des matériaux qui pourrait être utilisé comme matrice inerte pour la transmutation des actinides. Par conséquent, la compréhension du comportement d’YSZ sous différentes conditions d'irradiations est d'une importance capitale.Cette thèse est décomposée en deux parties distinctes. Dans la première partie de ce travail, nous avons utilisé plusieurs techniques avancées de diffraction des rayons X (DRX) dans le but de caractériser les défauts et déformations au sein de la zone irradiée des cristaux étudiés. Les profils de déformations et de défauts ont été modélisés par des fonctions B-splines cubiques et les données DRX ont été simulées en utilisant la théorie dynamique de la diffraction couplée à un algorithme de recuit simulé généralisé. Cette démarche a été appliquée au cas des monocristaux d'YSZ irradiés par des ions Au 2+ dans une large gamme de températures et de fluences. Les résultats ont été comparés avec ceux de la spectroscopie de rétrodiffusion de Rutherford en mode canalisé (RBS/C) obtenus pour les mêmes échantillons.La deuxième partie est consacrée au développement d'un modèle spécifique pour calculer la distribution bidimensionnelle d'intensité diffractée par des monocristaux irradiés de grandes dimensions et présentant des distributions de défauts réalistes. Pour atteindre cet objectif, nous avons mis en œuvre une approche de calcul parallèle haute performance (basée à la fois sur l'utilisation de processeurs multi-cœurs et de processeurs graphiques) afin de réduire les durées de calcul. Cette approche a été utilisée pour modéliser les cartographies X de l'espace réciproque de monocristaux d’YSZ présentant des défauts de structure complexe. / Ion beams are commonly used in the framework of nuclear materials in order to reproduce, in a controlled way, the different sources of irradiation that these materials are submitted to. The interaction of ions with the material induces the formation of crystalline defects along the path of these ions,associated with high strains in the irradiated region. One of the main issues of the electro-nuclearindustry is the encapsulation of the long-term nuclear waste. Yttria stabilized zirconia (YSZ) is one of the materials that can be used as an inert matrix for the transmutation of actinides and therefore,understanding its behaviour under different conditions of irradiation is of utmost importance.This thesis is divided into two distinct parts. In the first part of this work, we have used advanced X-raydiffraction (XRD) techniques in order to characterize the strain and the damage levels within the irradiated region of the crystals. The strain and the damage profiles were modelled using B-splines functions and the XRD data were simulated using the dynamical theory of diffraction combined with a generalized simulated annealing algorithm. This approach was used to study YSZ single crystals irradiated with Au 2+ ions in a wide range of temperatures and fluences. The results were compared with the RBS/C results obtained for same samples.The second part of the thesis is devoted to the development of a specific model for calculating the two-dimensional XRD intensity from irradiated single crystals with realistic dimensions and defectdistributions. In order to achieve this goal, we have implemented high-performance parallel computing (both multi-processing and GPU-based) to accelerate the calculations. The approach was used to successfully model the reciprocal space maps of the YSZ single crystals which exhibit a complex defect structure.

Avec l’émergence du calcul haute-performance (HPC) et des applications Big Data, de nouvelles problématiques cruciales sont apparues. Parmi elles on trouve le problème du transfert de données, c’est-à-dire des communications entre machines, qui peut génerer des délais lors de gros calculs en plus d’avoir un impact sur la consommation énergétique. La réplication, que ce soit de tâches ou de fichiers, est un facteur qui accroît ces communications, tout en étant un outil quasi-indispensable pour améliorer le parallélisme du calcul et la résistance aux pannes. Dans cette thèse nous nous intéressons à la réplication de fichiers et à son impact sur les communications au travers de deux problèmes. Dans le premier, la multiplication de matrices en parallèle, le but est de limiter autant que possible ces réplications pour diminuer la quantité de données déplacées. Dans le second, l’ordonnancement de la phase « Map » de MapReduce, il existe une réplication initiale qu’il faut utiliser au mieux afin d’obtenir l’ordonnancement le plus rapide ou entraînant le moins de création de nouvelles copies. En plus de la réplication, nous nous intéressons aussi à la comparaison entre stratégies d’ordonnancement statiques (allocations faites en amont du calcul) et dynamiques (allocations faites pendant le calcul) sur ces deux problèmes avec pour objectif de créer des stratégies hybrides mélangeant les deux aspects. Pour le premier problème, le produit de matrices en parallèle, nous nous ramenons à un problème de partition de carré où l’équilibrage de charge est donné en entrée. Cet équilibrage donné, le but est de minimiser la somme des semi-paramètres des rectangles couvrant des zones ainsi créés. Ce problème a déjà été étudié par le passé et nous démontrons de nouveaux résultats. Nous proposons ainsi deux nouveaux algorithmes d’approximation, l’un fondé sur une stratégie récursive et l’autre sur l’usage d’une courbe fractale. Nous présentons également une modélisation alternative, fondée sur un problème similaire de partition de cube, dont nous prouvons la NP-complétude tout en fournissant deux algorithmes d’approximation. Pour finir, nous réalisons également une implémentation pratique du produit de matrices en utilisant nos stratégies d’allocation grâce à la librairie StarPU. Les résultats expérimentaux montrent une amélioration du temps de calcul ainsi qu’une diminution significative des transferts de données lorsqu’on utilise une stratégie statique d’allocation couplée à une technique de vol de tâches. Pour le second problème, l’ordonnancement de la phase « Map » de MapReduce, plusieurs copies des fichiers d’entrée sont distribuées parmi les processeurs disponibles. Le but ici est de faire en sorte que chaque tâche soit attribuée à un processeur possédant son fichier d’entrée tout en ayant le meilleur temps de calcul total. Une autre option étudiée est d’autoriser les tâches nonlocales (attribués à des processeurs ne possédant pas leurs fichiers d’entrée) mais d’en limiter le nombre. Dans cette thèse nous montrons premièrement qu’un algorithme glouton pour ce problème peut être modélisé par un processus de « balls-in-bins » avec choix, impliquant une surcharge (nombre de tâches supplémentaires par rapport à la moyenne) en O(mlogm) où m est le nombre de processeurs. Secondement, dans le cas où les tâches non-locales sont interdites, nous relions le problème à celui de l’orientation de graphes, ce qui permet d’obtenir des algorithmes optimaux et polynomiaux et l’existence d’une assignation presque parfaite avec forte probabilité. Dans le cas où les tâches non locales sont autorisées, nous proposons également des algorithmes polynomiaux et optimaux. Finalement, nous proposons un ensemble de simulations pour montrer l’efficacité de nos méthodes dans le cas de tâches faiblement hétérogènes. / The increasing importance of High Performance Computing (HPC) and Big Data applications creates new issues in parallel computing. One of them is communication, the data transferred from a processor to another. Such data movements have an impact on computational time, inducing delays and increase of energy consumption. If replication, of either tasks or files, generates communication, it is also an important tool to improve resiliency and parallelism. In this thesis, we focus on the impact of the replication of input files on the overall amount of communication. For this purpose, we concentrate on two practical problems. The first one is parallel matrix multiplication. In this problem, the goal is to induce as few replications as possible in order to decrease the amount of communication. The second problem is the scheduling of the “Map” phase in the MapReduce framework. In this case, replication is an input of the problem and this time the goal is to use it in the best possible way. In addition to the replication issue, this thesis also considers the comparison between static and dynamic approaches for scheduling. For consistency, static approaches compute schedules before starting the computation while dynamic approaches compute the schedules during the computation itself. In this thesis we design hybrid strategies in order to take advantage of the pros of both. First, we relate communication-avoiding matrix multiplication with a square partitioning problem, where load-balancing is given as an input. In this problem, the goal is to split a square into zones (whose areas depend on the relative speed of resources) while minimizing the sum of their half-perimeters. We improve the existing results in the literature for this problem with two additional approximation algorithms. In addition we also propose an alternative model using a cube partitioning problem. We prove the NP-completeness of the associated decision problem and we design two approximations algorithms. Finally, we implement the algorithms for both problems in order to provide a comparison of the schedules for matrix multiplication. For this purpose, we rely on the StarPU library. Second, in the Map phase of MapReduce scheduling case, the input files are replicated and distributed among the processors. For this problem we propose two metrics. In the first one, we forbid non-local tasks (a task that is processed on a processor that does not own its input files) and under this constraint, we aim at minimizing the makespan. In the second problem, we allow non-local tasks and we aim at minimizing them while minimizing makespan. For the theoretical study, we focus on tasks with homogeneous computation times. First, we relate a greedy algorithm on the makespan metric with a “ball-into-bins” process, proving that this algorithm produces solutions with expected overhead (the difference between the number of tasks on the most loaded processor and the number of tasks in a perfect distribution) equal to O(mlogm) where m denotes the number of processors. Second, we relate this scheduling problem (with forbidden non-local tasks) to a problem of graph orientation and therefore prove, with the results from the literature, that there exists, with high probability, a near-perfect assignment (whose overhead is at most 1). In addition, there are polynomial-time optimal algorithms. For the communication metric case, we provide new algorithms based on a graph model close to matching problems in bipartite graphs. We prove that these algorithms are optimal for both communication and makespan metrics. Finally, we provide simulations based on traces from a MapReduce cluster to test our strategies with realistic settings and prove that the algorithms we propose perform very well in the case of low or medium variance of the computation times of the different tasks of a job.

La modélisation des problèmes multi-domaine est abordée dans un cadre purement Eulérien. Un maillage unique, ne représentant plus la matière, est utilisé. Les différentes frontières et leur évolution sont décrites via des outils numériques tels que la méthode Level Set. Les caractéristiques locales de chaque sous domaines sont déterminées par des lois de mélange.Ce travail est une des premières tentations appliquant une approche Eulérienne pour modéliser de problèmes de grandes déformations. Dans un premier temps, la capacité de l'approche est testée afin de déterminer les développements nécessaires.Le frottement entre les différents objets est géré par un lubrifiant ajouté dans une couche limite. Combinée avec une technique d'identification, une nouvelle loi de mélange quadratique est introduite pour décrire la viscosité du lubrifiant. Des comparaisons ont été effectuées avec Forge® et les résultats sont trouvés satisfaisants. Pour traiter le contact entre les différents objets, un solveur directionnel a été développé. Malgré que les résultats soient intéressants, il reste le sujet de nouvelles améliorations. La scalabilité de l'approche dans un environnement massivement parallèle est testée aussi. Plusieurs recommandations ont été proposées pour s'assurer d'une performance optimale. La technique du maillage unique permet d'obtenir une très bonne scalabilité. L'efficacité du parallélisme ne dépend que de la partition d'un seul maillage (contrairement aux méthodes Lagrangiennes). La méthode proposée présente des capacités indéniables mais reste loin d'être complète. Des pistes d'amélioration sont proposées en conséquence. / Modeling of multi-domain problems is addressed in a Purely Eulerian framework. A single mesh is used all over the domain. The evolution of the different interacting bodies is described using numerical tools such as the Level Set method. The characteristics of the subdomains, considered as heterogeneities in the mesh, are determined using mixture laws.This work is one of the first attempts applying fully Eulerian Approach to Model large deformation problems. Therefore, the capacity of this approach is tested to determine necessary developments. The friction between the different objects is managed by adding a boundary layer implying the presence of a lubricant. Combined with an identification technique, a new quadratic mixture Law is introduced to determine the lubricant viscosity. Comparisons have been performed with Forge® and results were found satisfactory. To treat the contact problem between the different objects, a directional solver was developed. Despite the interesting results, it remains the topic of further improvements. The scalability of the approach in a massively parallel environment is tested as well. Several recommendations were proposed to ensure an optimal performance. The technique of a single mesh guarantees a very good scalability since the efficiency of parallelism depends of the partition of a single mesh (unlike the Lagrangian Methods). The proposed method presents undeniable capacities but remains far from being complete. Ideas for future Improvements are proposed accordingly.

Cette thèse est une contribution à la problématique de la simulation d'événements rares. A partir de l'étude des méthodes de Splitting, un nouveau cadre théorique est développé, indépendant de tout algorithme. Ce cadre, basé sur la définition d'un processus ponctuel associé à toute variable aléatoire réelle, permet de définir des estimateurs de probabilités, quantiles et moments sans aucune hypothèse sur la variable aléatoire. Le caractère artificiel du Splitting (sélection de seuils) disparaît et l'estimateur de la probabilité de dépasser un seuil est en fait un estimateur de la fonction de répartition jusqu'au seuil considéré. De plus, les estimateurs sont basés sur des processus ponctuels indépendants et identiquement distribués et permettent donc l'utilisation de machine de calcul massivement parallèle. Des algorithmes pratiques sont ainsi également proposés.Enfin l'utilisation de métamodèles est parfois nécessaire à cause d'un temps de calcul toujours trop important. Le cas de la modélisation par processus aléatoire est abordé. L'approche par processus ponctuel permet une estimation simplifiée de l'espérance et de la variance conditionnelles de la variable aléaoire résultante et définit un nouveau critère d'enrichissement SUR adapté aux événements rares / This thesis address the issue of extreme event simulation. From a original understanding of the Splitting methods, a new theoretical framework is proposed, regardless of any algorithm. This framework is based on a point process associated with any real-valued random variable and lets defined probability, quantile and moment estimators without any hypothesis on this random variable. The artificial selection of threshold in Splitting vanishes and the estimator of the probability of exceeding a threshold is indeed an estimator of the whole cumulative distribution function until the given threshold. These estimators are based on the simulation of independent and identically distributed replicas of the point process. So they allow for the use of massively parallel computer cluster. Suitable practical algorithms are thus proposed.Finally it can happen that these advanced statistics still require too much samples. In this context the computer code is considered as a random process with known distribution. The point process framework lets handle this additional source of uncertainty and estimate easily the conditional expectation and variance of the resulting random variable. It also defines new SUR enrichment criteria designed for extreme event probability estimation.

Ces travaux, initiés par le CNES (Centre National d’Etudes Spatiales) dans le cadre du programme de recherche ATAC (Aérodynamique Tuyères et Arrières-Corps), sont principalement consacrés au développement et à la validation de modèles numériques et physiques, pour la prédiction des charges latérales dans les moteurs-fusées. En effet, les systèmes propulsifs mettent en jeu des phénomènes physiques très complexes : mélange turbulent, compressibilité forte (interaction choc/turbulence, couplage de modes vorticité/entropie/acoustique), structures cohérentes et organisations tourbillonnaires dans le cas tridimensionnel, décollements massifs et instabilités à grande échelle. L’analyse de ces phénomènes nécessite le recourt à des modélisations de plus en plus fines basées sur des simulations numériques avancées. Pour faire face au coût prohibitif des simulations directes (ou simulations LES résolues) des couches limites, un nouveau modèle de paroi a été développé, en se basant sur les propriétés d’auto similarité des couches limites compressibles en tuyères supersoniques, et en utilisant des lois de renormalisation dérivées à partir d’une base de données tabulée. Ce modèle permet de prendre en compte la dynamique de l’écoulement tout en réduisant considérablement le nombre de points de calcul et le pas de temps requis pour les simulations LES. Les résultats de calcul mettent en évidence de nombreuses interactions complexes au sein de l’écoulement. En particulier, les interactions amont/aval (supersonique/subsonique),influençant fortement le décollement et la structure de chocs, à l’origine de l’apparition de pics énergétiques associés à des perturbations acoustiques conduisent à l’apparition,par rétroaction, de phénomènes d’instabilités convectives, couplées à des modes globaux dissymétriques en dynamique absolue. Ces phénomènes auto-entretenus sont synonymes d’efforts latéraux et sont représentatifs des expériences menées en laboratoire et sur bancs d’essai moteurs-fusées. En terme d’optimisation des calculs massivement parallèles, une méthode originale, appelée « Drop-Procs », a été développée dans le cadre des frontières immergées. Cette méthode, adaptée aux architectures de calculs intensifs Tier-0, permet une réduction notable du temps CPU (Central Processing Unit), allant jusqu’à 50%, et rendant ainsi ce type de simulations plus accessible à l’échelle industrielle. / This work, initiated by the CNES (Centre National d’Etudes Spatiales) in the ATAC research program (Aérodynamique Tuyères et Arrières-Corps), is devoted to the development and the validation of numerical and physical models for the prediction of side-loads in rocket engines. Indeed, propulsion systems involve complex physical phenomena : turbulent mixing, high compressibility (interaction shock / turbulence, coupling modes vorticity / entropy / acoustic), coherent structure, three-dimensional vortex organizations, massive detachment and large scale instabilities. The analysis of these phenomena requires the uses of advanced numerical simulations. To deal with the high cost of large-eddy simulations boundary layers, a new wall model, based on renormalization laws and a database, was developed. This model allows to take into account the dynamics of the flow while significantly reducing the number of calculation points and the time step required for LES simulations. Results show many complex interactions with in the flow. In particular, the upstream / downstream interactions (supersonic / subsonic), strongly influence the separation and the shock structure, causing the occurrence of energy peaks associated with acoustic disturbances and leading to the appearance of convective instability, coupled with global asymmetric modes. These self-sustained phenomena are synonymous of side-loads and are representative of laboratory experiments and rocket engine test benches. In terms of optimization of massively parallel computing, a new method, called "Drop-Procs", was developed as part of the immersed boundaries. This method is suitable for compute-intensive architectures Tier-0 and allows a significant reduction in CPU time (Central Processing Unit) consumption, up to 50%, making this type of simulation accessible for industrials.

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.

Les environnements de réalité virtuelle devenant de plus en plus complexes et de très grandes dimensions, un niveau d'interaction temps-réel devient impossible à garantir. En effet, de par leur complexité, due à une géométrie détaillée et aux propriétés physiques spécifiques, ces environnements large échelle engendrent un goulet d'étranglement calculatoire critique sur les algorithmes de simulation physique. Nous avons focalisé nos travaux sur la première étape de ces algorithmes qui concerne la détection de collision, car les problématiques font partie intégrante de ce goulet d'étranglement et leur complexité peut parfois se révéler quadratique dans certaines situations. Le profond bouleversement que subissent les architectures machines depuis quelques années ouvre une nouvelle voie pour réduire le goulet d'étranglement. La multiplication du nombre de cœurs offre ainsi la possibilité d'exécuter ces algorithmes en parallèle sur un même processeur. Dans le même temps, les cartes graphiques sont passées d'un statut de simple périphérique d'affichage graphique à celui de supercalculateur. Elles jouissent désormais d'une attention toute particulière de la part de la communauté traitant de la simulation physique. Afin de passer au large échelle et d'être générique sur la machine d'exécution, nous avons proposé des modèles unifiés et adaptatifs de correspondance entre les algorithmes de détection de collision et les architectures machines de type multi-coeur et multi-GPU. Nous avons ainsi défini des solutions innovantes et performantes permettant de réduire significativement le temps de calcul au sein d'environnements large échelle tout en assurant la pérennité des résultats. Nos modèles couvrent l'intégralité du pipeline de détection de collision en se focalisant aussi bien sur des algorithmes de bas ou de haut niveau. Nos modèles multi-coeur, GPU et multi-GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des techniques d'équilibrage de charge basées sur le vol de données. Notre solution hybride permet d'accroitre l'espace et le temps de calcul ainsi que le passage au large échelle. L'association de ces nouveaux algorithmes nous a permis de concevoir deux modèles d'adaptation algorithmique dynamique basés, ou non, sur des scénarios de pré-calcul hors-ligne. Enfin, il nous est apparu indispensable d'ajouter au pipeline de détection de collision une nouvelle dimension révélant la prise en compte des architectures pour une exécution optimale. Grâce à ce formalisme, nous avons proposé un nouveau pipeline de détection de collision offrant une granularité de parallélisme sur processeurs multi-coeur. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes.

Les automates cellulaires ont été introduits il y a une soixantaine d'années par von Neumann et Ulam qui cherchaient à définir les caractéristiques d'un système formel apte au calcul universel et à l'auto-reproduction. Leur utilité a été rapidement reconnue dans des domaines variés comme la physique et la biologie, pour modéliser des phénomènes complexes. En informatique, ils offrent un cadre privilégié pour l'étude du parallélisme massif. Leur description est simple et bien formalisée. Ils ont a la même puissance de calcul que les machines de Turing et de plus la richesse algorithmique propre aux machines parallèles tout en restant un modèle physiquement réaliste. Dans le cadre unificateur de la reconnaissance de langages, je m'intéresse aux questions de complexité sur les automates cellulaires, avec une attention particulière aux petites classes de complexité : calcul en temps réel (i.e. temps minimal) et en temps linéaire; en effet, c'est pour ces classes que l'apport du parallélisme est remarquable par rapport au mode séquentiel. Avec pour objectif de préciser les capacités de ce modèle et de mieux comprendre ce qu'est un calcul parallèle, trois tendances majeures se dégagent de mes travaux : l'étude des limites de ce modèle, la comparaison avec d'autres modèles de calcul et la question de l'influence de certains paramètres comme la dimension ou le voisinage sur ses capacités de reconnaissance.

L'informatique a changé profondément les aspects méthodologiques du processus de découverte dans les différents domaines du savoir. Les chercheurs ont à leur disposition aujourd'hui de nouvelles capacités qui permettent d'envisager la résolution de nouveaux problèmes. Les plates-formes parallèles et distribuées composées de ressources partagées entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offrent une puissance de calcul qui a été limitée jusqu'à présent aux projets scientifiques les plus grands (et les plus riches). Dans ce document qui regroupe les résultats obtenus pendant cette thèse, nous explorons quatre facettes différentes de la façon dont les organisations s'engagent dans une collaboration sur de plates-formes parallèles et distribuées. En utilisant des outils classiques de l'analyse combinatoire, de l'ordonnancement multi-objectif et de la théorie des jeux, nous avons montré comment calculer des ordonnancements avec un bon compromis entre les résultats obtenus par les participants et la performance globale de la plate-forme. En assurant des résultats justes et en garantissant des améliorations de performance pour les différents participants, nous pouvons créer une plate-forme efficace où chacun se sent toujours encouragé à collaborer et à partager ses ressources. Tout d'abord, nous étudions la collaboration entre organisations égoïstes. Nous montrons que le comportement égoïste entre les participants impose une borne inférieure sur le makespan global. Nous présentons des algorithmes qui font face à l'égoïsme des organisations et qui présentent des résultats équitables. La seconde étude porte sur la collaboration entre les organisations qui peuvent tolérer une dégradation limitée de leur performance si cela peut aider à améliorer le makespan global. Nous améliorons les bornes d'inapproximabilité connues sur ce problème et nous présentons de nouveaux algorithmes dont les garanties sont proches de l'ensemble de Pareto (qui regroupe les meilleures solutions possibles). La troisième forme de collaboration étudiée est celle entre des participants rationnels qui peuvent choisir la meilleure stratégie pour leur tâches. Nous présentons un modèle de jeu non coopératif pour le problème et nous montrons comment l'utilisation de "coordination mechanisms" permet la création d'équilibres approchés avec un prix de l'anarchie borné. Finalement, nous étudions la collaboration entre utilisateurs partageant un ensemble de ressources communes. Nous présentons une méthode qui énumère la frontière des solutions avec des meilleurs compromis pour les utilisateurs et sélectionne la solution qui apporte la meilleure performance globale.