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

La thèse porte sur deux enjeux importants de sécurité. Le premier concerne l’amélioration de la sécurité des systèmes Linux présents dans le calcul intensif et le second la protection des postes de travail Windows. Elle propose une méthode commune pour l’observation des appels système et la répartition d’observateurs afin de renforcer la sécurité et mesurer les performances obtenues. Elle vise des observateurs du type moniteur de référence afin de garantir de la confidentialité et de l’intégrité. Une solution utilisant une méthode de calcul intensif est mise en oeuvre pour réduire les surcoûts de communication entre les deux moniteurs de référence SELinux et PIGA. L’évaluation des performances montre les surcoûts engendrés par les moniteurs répartis et analyse la faisabilité pour les différents noeuds d’environnements de calcul intensif. Concernant la sécurité des postes de travail, un moniteur de référence est proposé pour Windows. Il repose sur les meilleures protections obligatoires issues des systèmes Linux et simplifie l’administration. Nous présentons une utilisation de ce nouveau moniteur pour analyser le fonctionnement de logiciels malveillants. L’analyse permet une protection avancée qui contrôle l’ensemble du scénario d’attaque de façon optimiste. Ainsi, la sécurité est renforcée sans nuire aux activités légitimes. / This thesis deals with two major issues in the computer security field. The first is enhancing the security of Linux systems for scientific computation, the second is the protection of Windows workstations. In order to strengthen the security and measure the performances, we offer a common method for the distributed observation of system calls. It relies on reference monitors to ensure confidentiality and integrity. Our solution uses specific high performance computing technologies to lower the communication latencies between the SELinux and PIGA monitors. Benchmarks study the integration of these distributed monitors in the scientific computation. Regarding workstation security, we propose a new reference monitor implementing state of the art protection models from Linux and simplifying administration. We present how to use our monitor to analyze the behavior of malware. This analysis enables an advanced protection to prevent attack scenarii in an optimistic manner. Thus, security is enforced while allowing legitimate activities.

Ce travail s'inscrit dans le contexte des techniques de renforcement des sols, permettant d'améliorer les performances mécaniques de terrains de qualité médiocre. Parmi ces techniques, l'utilisation d'inclusions souples prenant la forme de colonnes ou de tranchées croisées connaît une diffusion croissante. Même si les aspects relatifs à leur procédé de construction sont aujourd'hui bien maîtrisés, les méthodes de dimensionnement de ces ouvrages en sols renforcés restent à améliorer. Dans cette thèse, nous proposons d'utiliser la méthode d'homogénéisation afin d'analyser le comportement global des ouvrages en sols renforcés, dans le cadre de la théorie de l'élasticité (propriétés de rigidité) aussi bien que dans celle du calcul à la rupture (propriétés de résistance). Tenant compte de la périodicité géométrique des différentes configurations de renforcement, nous déterminons le comportement des sols renforcés tout d'abord au niveau local puis à l'échelle de l'ouvrage. Pour évaluer les capacités de résistance des ouvrages en sols renforcés, les approches statique et cinématique du calcul à la rupture sont mises en œuvre analytiquement ou numériquement selon la nature du matériau de renforcement utilisé. Par des formulations numériques innovantes adaptées à cette théorie, nous parvenons notamment à évaluer les domaines de résistance macroscopiques des sols renforcés par colonnes ou tranchées croisées, qui peuvent ensuite être pris en compte dans le comportement à la rupture des ouvrages en sols renforcés. Deux exemples d'application de cette procédure, relatifs au problème de capacité portante d'une semelle de fondation reposant sur un sol renforcé d'une part et à l'analyse de la stabilité d'un remblai d'autre part, sont effectués / This work takes place in the context of soil reinforcement techniques, aimed at improving the mechanical performances of poor quality grounds. Among these techniques, the use of soft inclusions taking the form of columns or cross trenches has known important developments. Even if the aspects relative to their construction process are presently well mastered, the design methods of such reinforced soil structures still remain to be greatly improved. The present work advocates the use of the homogenization method for assessing the global behavior of reinforced soil structures, both in the context of linear elasticity (stiffness properties) and in the framework of yield design (strength properties). Taking into account the geometrical periodicity of the various reinforcement configurations, we thus determine the behavior of the reinforced soils first locally and then at the global scale. To assess the strength capacities of reinforced soil structures, the static and kinematic approaches of the yield design theory are performed analytically or numerically depending on the kind of reinforcing material which is used. Adopting innovative numerical formulations dedicated to this theory, we can notably evaluate the macroscopic strength domains of column as well as cross trench reinforced soils which can then be introduced in the yield design of reinforced soil structures. Two illustrative applications of this procedure are performed relating to the bearing capacity problem of a reinforced soil shallow foundation on the one hand, the stability analysis of an embankment on the other hand

Les méthodes en simulation numérique dans le domaine de l’ingénierie pétrolière nécessitent la résolution de systèmes linéaires creux de grande taille et non structurés. La performance des méthodes itératives utilisées pour résoudre ces systèmes représente un enjeu majeur afin de permettre de tester de nombreux scénario.Dans ces travaux, nous présentons une manière d'implémenter des méthodes itératives parallèles au dessus d’un support exécutif à base de tâches. Afin de simplifier le développement des méthodes tout en gardant un contrôle fin sur la gestion du parallélisme, nous avons proposé une API permettant d’exprimer implicitement les dépendances entre tâches : la sémantique de l'API reste séquentielle et le parallélisme est implicite.Nous avons étendu le support exécutif HARTS pour enregistrer une trace d'exécution afin de mieux exploiter les architectures NUMA, tout comme de prendre en compte un placement des tâches et des données calculé au niveau de l’API. Nous avons porté et évalué l'API sur les processeurs many-coeurs KNL en considérant les différents types de mémoires de l’architecture. Cela nous a amené à optimiser le calcul du SpMV qui limite la performance de nos applications.L'ensemble de ce travail a été évalué sur des méthodes itératives et en particulier l’une de type décomposition de domaine. Nous montrons alors la pertinence de notre API, qui nous permet d’atteindre de très bon niveaux de performances aussi bien sur architecture multi-coeurs que many-coeurs. / Numerical methods in reservoir engineering simulations lead to the resolution of unstructured, large and sparse linear systems. The performances of iterative methods employed in simulator to solve these systems are crucial in order to consider many more scenarios.In this work, we present a way to implement efficient parallel iterative methods on top of a task-based runtime system. It enables to simplify the development of methods while keeping control on parallelism management. We propose a linear algebra API which aims to implicitly express task dependencies: the semantic is sequential while the parallelism is implicit.We have extended the HARTS runtime system to monitor executions to better exploit NUMA architectures. Moreover, we implement a scheduling policy which exploits data locality for task placement. We have extended the API for KNL many-core systems while considering the various memory banks available. This work has led to the optimization of the SpMV kernel, one of the most time consuming operation in iterative methods.This work has been evaluated on iterative methods, and particularly on one method coming from domain decomposition. Hence, we demonstrate that the API enables to reach good performances on both multi-core and many-core architectures.

Ces travaux de thèse s’intéressent aux outils de simulation rapide de la fabrication d’un pneumatique. L'objectif est de prédire le mouvement et la position des éléments constitutifs du pneumatique, lors de leur mise en conformation, en prenant en compte les déformations induites par les actions mécaniques associées. Ces travaux s’appuient sur la mise en place d’un algorithme visant à modéliser le gonflement d’un outillage et la mise en place d’un modèle de déformation d’un système de formes géométriques aux caractéristiques mécaniques différentes. L'algorithme de gonflement de l’outillage se base sur la théorie des membranes inextensibles et son industrialisation est validée pour des dimensions standards de pneumatiques. La méthode Masse-Ressort est retenue pour réaliser la déformation de formes géométriques afin d’obtenir des résultats de déformation en temps réel. Dans ces travaux, cette méthode est adaptée aux matériaux d’un pneumatique à partir de travaux de caractérisations géométrique et mécanique validés par comparaison aux Éléments Finis. En conclusion, la modélisation développée permet une description à chaque étape du procédé de fabrication. / This thesis deals with fast simulation tools used to manufacture of a tire. The goal is to predict the displacement and position of the components of a tire taking into account the deformations induced by the associated mechanical actions. This work is based on the implementation of an algorithm for modeling the inflation of a tool and the development of a deformation model in order to compute the deformation of geometric shapes taking into account different mechanical properties. The algorithm to model the inflation of the tool is based on the theory of inextensible membranes and its industrialization is validated for standard sizes of tires. Mass-Spring method is used to achieve the deformation of geometric shapes in order to compute deformation in real time. In this work, this method is suitable for materials of a tire from geometric and mechanical characterizations validated by comparison with FEM. To conclude, the developed modelization allows a description for each step of the manufacturing process.

La microcirculation cérébrale joue un rôle clé dans la physiologie cérébrale. Lors de maladies dégénératives comme celle d’Alzheimer, la détérioration des réseaux microvasculaires (e.g. occlusions et baisse de densité vasculaires) limite l’afflux sanguin vers le cortex. La réduction associée de l’apport en oxygène et nutriments risque de provoquer la mort de neurones. En complément des techniques d’imagerie médicale, la modélisation est un outil précieux pour comprendre l’impact de telles variations structurelles sur l’écoulement sanguin et les transferts de masse. Dans la microcirculation cérébrale, le lit capillaire contient les plus petits vaisseaux (diamètre de 1-10 μm) et présente une structure maillée, au sein du tissu cérébral. C’est le lieu principal des échanges moléculaires entre le sang et les neurones. Le lit capillaire est alimenté et drainé par les arbres artériolaires et veinulaires (diamètre de 10-100 μm). Depuis quelques décennies, les approches “réseau” ont significativement amélioré notre compréhension de l’écoulement sanguin, du transport de masse et des mécanismes de régulation dans la microcirculation cérébrale humaine. Cependant, d’un point de vue numérique, la densité des capillaires limite ces approches à des volumes relativement petits (<100 mm3). Cette contrainte empêche leur application à des échelles cliniques, puisque les techniques d’imagerie médicale permettent d’acquérir des volumes bien plus importants (∼100 cm3), avec une résolution de 1-10 mm. Pour réduire ce coût numérique, nous présentons une approche hybride pour la modélisation de l’écoulement dans laquelle les capillaires sont remplacés par un milieu continu. Cette substitution a du sens puisque le lit capillaire est dense et homogène à partir d’une longueur de coupure de ∼50 μm. Dans ce continuum, l’écoulement est caractérisé par des propriétés effectives (e.g. perméabilité) à l’échelle d’un volume représentatif plus grand. De plus, le continuum est discrétisé par la méthode des volumes finis sur un maillage grossier, ce qui induit un gain numérique important. Les arbres artério- et veinulaires ne peuvent être homogénéisés à cause de leur structure quasi-fractale. Nous appliquons donc une approche “réseau” standard dans les vaisseaux les plus larges. La principale difficulté de l’approche hybride est de développer un modèle de couplage aux points où les vaisseaux artério- et veinulaires sont connectés au continuum. En effet, de forts gradients de pression apparaissent à proximité de ces points, et doivent être homogénéisés proprement à l’échelle du continuum. Ce genre de couplage multi-échelle n’a jamais été introduit dans le contexte de la microcirculation cérébrale. Nous nous inspirons ici du "modèle de puits" développé par Peaceman pour l’ingénierie pétrolière, en utilisant des solutions analytiques du champ des pressions dans le voisinage des points de couplage. Les équations obtenues forment un unique système linéaire à résoudre pour l’ensemble du domaine d’étude. Nous validons l’approche hybride par comparaison avec une approche “réseau” classique, pour des architectures synthétiques simples qui n’impliquent qu’un ou deux couplages, et pour des structures plus complexes qui impliquent des arbres artério- et veinulaires anatomiques avec un grand nombre de couplages. Nous montrons que cette approche est fiable, puisque les erreurs relatives en pression sont faibles (<6 %). Cela ouvre la voie à une complexification du modèle (e.g. hématocrite non uniforme). Dans une perspective de simulations à grande échelle et d’extension au transport de masse, l’approche hybride a été implémentée dans un code C++ conçu pour le calcul haute performance. Ce code a été entièrement parallélisé en utilisant les standards MPI et des librairies spécialisées (e.g. PETSc). Ce travail faisant partie d’un projet plus large impliquant plusieurs collaborateurs, une attention particulière a été portée à l’établissement de stratégies d’implémentation efficaces. / The brain microcirculation plays a key role in cerebral physiology and neuronal activation. In the case of degenerative diseases such as Alzheimer’s, severe deterioration of the microvascular networks (e.g. vascular occlusions) limit blood flow, thus oxygen and nutrients supply, to the cortex, eventually resulting in neurons death. In addition to functional neuroimaging, modelling is a valuable tool to investigate the impact of structural variations of the microvasculature on blood flow and mass transfers. In the brain microcirculation, the capillary bed contains the smallest vessels (1-10 μm in diameter) and presents a mesh-like structure embedded in the cerebral tissue. This is the main place of molecular exchange between blood and neurons. The capillary bed is fed and drained by larger arteriolar and venular tree-like vessels (10-100 μm in diameter). For the last decades, standard network approaches have significantly advanced our understanding of blood flow, mass transport and regulation mechanisms in the human brain microcirculation. By averaging flow equations over the vascular cross-sections, such approaches yield a one-dimensional model that involves much fewer variables compared to a full three-dimensional resolution of the flow. However, because of the high density of capillaries, such approaches are still computationally limited to relatively small volumes (<100 mm3). This constraint prevents applications at clinically relevant scales, since standard imaging techniques only yield much larger volumes (∼100 cm3), with a resolution of 1-10 mm3. To get around this computational cost, we present a hybrid approach for blood flow modelling where the capillaries are replaced by a continuous medium. This substitution makes sense since the capillary bed is dense and space-filling over a cut-off length of ∼50 μm. In this continuum, blood flow is characterized by effective properties (e.g. permeability) at the scale of a much larger representative volume. Furthermore, the domain is discretized on a coarse grid using the finite volume method, inducing an important computational gain. The arteriolar and venular trees cannot be homogenized because of their quasi-fractal structure, thus the network approach is used to model blood flow in the larger vessels. The main difficulty of the hybrid approach is to develop a proper coupling model at the points where arteriolar or venular vessels are connected to the continuum. Indeed, high pressure gradients build up at capillary-scale in the vicinity of the coupling points, and must be properly described at the continuum-scale. Such multiscale coupling has never been discussed in the context of brain microcirculation. Taking inspiration from the Peaceman “well model” developed for petroleum engineering, our coupling model relies on to use analytical solutions of the pressure field in the neighbourhood of the coupling points. The resulting equations yield a single linear system to solve for both the network part and the continuum (strong coupling). The accuracy of the hybrid model is evaluated by comparison with a classical network approach, for both very simple synthetic architectures involving no more than two couplings, and more complex ones, with anatomical arteriolar and venular trees displaying a large number of couplings. We show that the present approach is very accurate, since relative pressure errors are lower than 6 %. This lays the goundwork for introducing additional levels of complexity in the future (e.g. non uniform hematocrit). In the perspective of large-scale simulations and extension to mass transport, the hybrid approach has been implemented in a C++ code designed for High Performance Computing. It has been fully parallelized using Message Passing Interface standards and specialized libraries (e.g. PETSc). Since the present work is part of a larger project involving several collaborators, special care has been taken in developing efficient coding strategies.

Les travaux de ce doctorat concernent le développement de méthodes itératives pour la résolution de systèmes linéaires creux de grande taille comportant de nombreux seconds membres. L’application visée est la résolution d’un problème inverse en géophysique visant à reconstruire la vitesse de propagation des ondes dans le sous-sol terrestre. Lorsque de nombreuses sources émettrices sont utilisées, ce problème inverse nécessite la résolution de systèmes linéaires complexes non symétriques non hermitiens comportant des milliers de seconds membres. Dans le cas tridimensionnel ces systèmes linéaires sont reconnus comme difficiles à résoudre plus particulièrement lorsque des fréquences élevées sont considérées. Le principal objectif de cette thèse est donc d’étendre les développements existants concernant les méthodes de Krylov par bloc. Nous étudions plus particulièrement les techniques de déflation dans le cas multiples seconds membres et recyclage de sous-espace dans le cas simple second membre. Des gains substantiels sont obtenus en terme de temps de calcul par rapport aux méthodes existantes sur des applications réalistes dans un environnement parallèle distribué. / This PhD thesis concerns the development of flexible Krylov subspace iterative solvers for the solution of large sparse linear systems of equations with multiple right-hand sides. Our target application is the solution of the acoustic full waveform inversion problem in geophysics associated with the phenomena of wave propagation through an heterogeneous model simulating the subsurface of Earth. When multiple wave sources are being used, this problem gives raise to large sparse complex non-Hermitian and nonsymmetric linear systems with thousands of right-hand sides. Specially in the three-dimensional case and at high frequencies, this problem is known to be difficult. The purpose of this thesis is to develop a flexible block Krylov iterative method which extends and improves techniques already available in the current literature to the multiple right-hand sides scenario. We exploit the relations between each right-hand side to accelerate the convergence of the overall iterative method. We study both block deflation and single right-hand side subspace recycling techniques obtaining substantial gains in terms of computational time when compared to other strategies published in the literature, on realistic applications performed in a parallel environment.

Les travaux présentés ici concernent le domaine de la localisation de véhicule par vision artificielle. Dans ce contexte, la trajectoire d’une caméra et la structure3D de la scène filmée sont estimées par une méthode d’odométrie visuelle monoculaire basée sur l’ajustement de faisceaux local. Les contributions de cette thèse sont plusieurs améliorations de cette méthode. L’incertitude associée à la position estimée n’est pas fournie par la méthode d’ajustement de faisceaux local. C’est pourtant une information indispensable pour pouvoir utiliser cette position, notamment dans un système de fusion multi-sensoriel. Une étude de la propagation d’incertitude pour cette méthode d’odométrie visuelle a donc été effectuée pour obtenir un calcul d’incertitude temps réel et représentant l’erreur de manière absolue (dans le repère du début de la trajectoire). Sur de longues séquences (plusieurs kilomètres), les méthodes monoculaires de localisation sont connues pour présenter des dérives importantes dues principalement à la dérive du facteur d’échelle (non observable). Pour réduire cette dérive et améliorer la qualité de la position fournie, deux méthodes de fusion ont été développées. Ces deux améliorations permettent de rendre cette méthode monoculaire exploitable dans le cadre automobile sur de grandes distances tout en conservant les critères de temps réel nécessaire dans ce type d’application. De plus, notre approche montre l’intérêt de disposer des incertitudes et ainsi de tirer parti de l’information fournie par d’autres capteurs. / The present work is about localisation of vehicle using computer vision methods. In this context, the camera trajectory and the 3D structure of the scene is estimated by a monocular visual odometry method based on local bundle adjustment. This thesis contributions are some improvements of this method. The uncertainty of the estimated position was not provided by the local bundle adjustment method. Indeed, this uncertainty is crucial in a multi-sensorial fusion system to use optimally the estimated position. A study of the uncertainty propagation in this visual odometry method has been done and an uncertainty calculus method has been designed to comply with real time performance. By the way, monocular visual localisation methods are known to have serious drift issues on long trajectories (some kilometers). This error mainly comes from bad propagation of the scale factor. To limit this drift and improve the quality of the given position, we proposed two data fusion methods between an odometer and the visual method. Finally, the two improvements presented here allow us to use visual localisation method in real urban environment on long trajectories under real time constraints.

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és composées de ressources partagés entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offre 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 mon doctorat, 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 obtenu 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 encourager à 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. / Computer science is deeply changing methodological aspects of the discovery process in different areas of knowledge. Researchers have at their disposal new capabilities that can create novel research opportunities. Parallel and distributed platforms composed of resources shared between different participants can make these new capabilities accessible to every researcher at every level, delivering computational power that was restricted before to bigger (and wealthy) scientific projects. This work explores four different facets of the rules that govern how organizations engage in collaboration on modern parallel and distributed platforms. Using classical combinatorial tools, multi-objective scheduling and game-theory, we showed how to compute schedules with good trade-offs between the results got by the participants and the global performance of the platform. By ensuring fair results and guaranteeing performance improvements for the participants, we can create an efficient platform where everyone always feels encouraged to collaborate and to share its resources. First, we study the collaboration between selfish organizations. We show how the selfish behavior between the participants imposes a lower bound on the global makespan. We present algorithms that cope with the selfishness of the organizations and that achieve good fairness in practice. The second study is about collaboration between organizations that can tolerate a limited degradation on their performance if this can help ameliorate the global makespan. We improve the existing inapproximation bounds for this problem and present new algorithms whose guarantees are close to the Pareto set. The third form of collaboration studied is between rational participants that can independently choose the best strategy for their jobs. We present a non-cooperative game-theoretic model for the problem and show how coordination mechanisms allow the creation of approximate pure equilibria with bounded price of anarchy. Finally, we study collaboration between users sharing a set of common resources. We present a method that enumerates the frontier of best compromise solutions for the users and selects the solution that brings the best value for the global performance function.

Cette thèse porte sur les techniques d'analyse formelle de systèmes hybrides à dynamiques continues non linéaire. Ses contributions portent sur les algorithmes d'atteignabilité et sur les problèmatiques liées à la representation des ensembles atteignables. This thesis deals with formal analysis of hybrid system with non linear continous dynamic. It contributes to the fields of reachability analysis algorithm and the set representation. / In this thesis, we presented our contributions to the formal analysis of dynamical systems. We focused on the problem of efficiently computing an accurate approximation of the reachable sets under nonlinear dynamics given by differential equations. Our aim was also to design scalable methods which can handle large systems. The first contribution of this thesis concerns the dynamic hybridization technique for a large class of nonlinear systems. We focused on the hybridization domain construction such that the linear interpolation realized in this domain ensures a desired error between the original system trajectories and those computed with the approximated system. We propose a construction method which tends to maximize the domain volume which reduce the number of creation of new domains during the analysis. The second research direction that we followed concerns a subclass of nonlinear dynamical systems which are the polynomial systems. Our results for the reachability analysis of these systems are based on the Bernstein expansion properties. We approximate an initial reachability computation (which requires solving polynomial optimization problems) with an accurate over-approximation (which requires solving linear optimization problems). The last theoretical contribution concerns the reachability analysis of linear systems with polyhedral input which often result from approximation of nonlinear systems. We proposed a technique to refine