L'interprétation des expériences de relaxométrie RMN nécessite une modélisation précise des interactions entre le noyau étudié et son environnement. Pour un noyau quadrupolaire, l'interaction entre le gradient du champ électrique (EFG) émis par l'environnement avec le quadruple électrostatique du noyau est prépondérante. Notre travail a porté sur le développement du calcul des temps de relaxation RMN pour ces noyaux par simulation moléculaire. Nous nous sommes intéressés à la relaxation d'ions mono-atomiques en phase condensée à travers deux systèmes simples et réalistes : des solutions aqueuses d'électrolytes et des verres de silicate de sodium. L'EFG dé aux électrons de l'ion est obtenu en calculant la réponse du nuage électronique grâce à des calculs quantiques combinés à une récente méthode pour reconstruire la contribution des électrons de cœur. L'EFG dû à l'environnement est obtenu à partir d'une simulation moléculaire où les interactions sont décrites par un champ de force polarisable nouvellement développé. Les temps de relaxation obtenus en combinant ces deux contributions reproduisent correctement les résultats expérimentaux. Les simulations moléculaires nous permettent aussi d'extraire les mécanismes microscopiques. Pour les ions dans l'eau à dilution infinie, nous avons étudié les propriétés statistiques et dynamiques des fluctuations de l'EFG. Nous avons montré en particulier le rôle fondamental des fluctuations de densité de l'eau dans la première sphère de solvatation de l'ion. Cette thèse ouvre la voie à une meilleur compréhension des processus de relaxation RMN des ions mono-atomiques quadrupolaires dans des systèmes simples ou complexes. / Interpreting NMR relaxometry experiments requires an accurate modeling of interactions between the nucleus under study and its environment. For a quadrupolar nucleus, the interaction between the electric field gradient (EFG) arising from the environment and the electrostatic quadrupole of the nucleus is preponderant. The present work deals with a new method to compute NMR relaxation times for such nuclei with molecular simulations. We consider the relaxation of monoatomic ions in condensed matter through two simple and realistic systems: aqueous electrolytes and sodosilicate glasses. The EFG due to electrons around the ion is obtained by computing the electronic response with quantum calculation combined with a new method to obtain the contribution of core electrons. The EFG due to the environment is obtained from a molecular simulation where interactions are described using a recently developed polarisable force field. NMR relaxation times obtained by combining both these contributions compare well with experimental data. Molecular simulations allow us to highlight the microscopic mechanisms. For ions in water at infinite dilution, we studied the statistical and dynamical properties of EFG fluctuations. We notably demonstrated the primary role of water density fluctuations in the first solvation shell around the ion. This thesis opens the way for a better understanding of the mechanism behind the NMR relaxation of monoatomic and quadrupolar ions in simple and complex systems.

L'ensemble de ce travail est dédié à l'étude de certaines propriétés concernant les processus de sauts d-dimensionnels X = (Xt) dont le générateur est donné par Lψ(x) = 1/2 ∑ aᵤᵥ(x)∂²ψ(x)/∂xᵤ∂xᵥ + g(x)∇ψ(x) + ∫ (ψ(x + c(z, x)) − ψ(x))γ(z, x)µ(dz) où µ est de masse totale infinie. Si γ ne dépendait pas de x, nous nous trouverions dans une situation classique où le processus X pourrait être représenté comme une solution d'une équation stochastique comportant une mesure ponctuelle de Poisson de mesure d'intensité γ(z)µ(dz) ; lorsque γ dépend de x, on peut s'en représenter l'heuristique en imaginant le processus comme la trajectoire d'une particule, la loi des sauts pouvant alors dépendre de la position de la particule. Dans la première partie, nous donnons des conditions pour obtenir l'existence et l'unicité de tels processus. Ensuite, nous considérons ce type de processus comme une généralisation des PDMP ; nous montrons qu'ils peuvent être vus comme une limite d'une suite (Xᵣ(t)) de PDMP standards pour lesquels l'intensité des sauts tend vers l'infini quand r tend vers l'infini, suivant deux régimes : un lent et un rapide qui, en supposant que les processus en question sont centrés et normalisés convenablement, produit une composante de diffusion à la limite. Finalement, on prouve la récurrence au sens de Harris de X en utilisant un schéma régénératif entièrement basé sur les sauts du processus. De plus, nous dégageons des conditions explicites par rapport aux coefficients du processus qui nous permettent de contrôler la vitesse de convergence vers l'équilibre en terme d'inégalités de déviation pour des fonctionnelles additives intégrables. Dans la seconde partie, nous considérons à nouveau le même type de processus X = (Xt(x)) partant du point x. Utilisant une approche basé sur un Calcul de Malliavin fini-dimensionnel, nous étudions la régularité jointe de ce processus dans le sens suivant : on fixe b≥1 et p>1, K un ensemble compact de Rᵈ, et nous donnons des conditions suffisantes pour avoir P(Xt(x)∈dy)=pt(x,y)dy avec (x,y)↦pt(x,y) appartenant à Wᵇᵖ(K×Rᵈ) / This work is dedicated to the study of some properties concerning the d-dimensional jump type diffusion X = (Xt) with infinitesimal generator given by Lψ(x) = 1/2 ∑ aᵤᵥ(x)∂²ψ(x)/∂xᵤ∂xᵥ + g(x)∇ψ(x) + ∫ (ψ(x + c(z, x)) − ψ(x))γ(z, x)µ(dz) where µ is of infinite total mass. If γ did not depend on x, we would be in a classical situation where the process X could be represented as the solution of a stochastic equation driven by a Poisson point measure with intensity measure γ(z)µ(dz) ; when γ depends on x, we may have the heuristic idea that, if we were to imagine the process as a trajectory of a particle, the law of the jumps may depend on the position of the particle. In the first part, we give some conditions to obtain existence and uniqueness of such processes. Then, we consider this type of processes as a generalization of Piecewise Deterministic Markov Processes (PDMP) ; we show that they can be seen as a limit of a sequence (Xᵣ(t)) of standard PDMP's for which the intensity of the jumps tends to infinity as r tends to infinity, following two regimes: a slow one, which leads to a jump component with finite variation, and a rapid one which, supposing that the processes at hand are centered and renormalized in a convenient way, produces the diffusion component in the limit. Finally, we prove Harris recurrence of X using a regeneration scheme which is entirely based on the jumps of the process. Moreover we state explicit conditions in terms of the coefficients of the process allowing to control the speed of convergence to equilibrium in terms of deviation inequalities for integrable additive functionals. In the second part, we consider again the same type of process X = (Xt(x)) starting from x. Using an approach based on a finite dimensional Malliavin Calculus, we study the joint regularity of this process in the following sense : we fix b≥1 and p>1, K a compact set of Rᵈ, and we give sufficient conditions in order to have P(Xt(x)∈dy)=pt(x,y)dy with (x,y)↦pt(x,y) in Wᵇᵖ(K×Rᵈ)

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.

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.

De ce fait, le premier objectif de notre travail consiste à proposer des générateurs de nombres aléatoires appropriés pour des architectures parallèles et massivement parallèles de clusters de CPUs/GPUs. Nous testerons le gain en temps de calcul et l'énergie consommée lors de l'implémentation du cas linéaire du pricing européen. Le deuxième objectif est de reformuler le problème non-linéaire du pricing américain pour que l'on puisse avoir des gains de parallélisation semblables à ceux obtenus pour les problèmes linéaires. La méthode proposée fondée sur le calcul de Malliavin est aussi plus avantageuse du point de vue du praticien au delà même de l'intérêt intrinsèque lié à la possibilité d'une bonne parallélisation. Toujours dans l'objectif de proposer des algorithmes parallèles, le dernier point est l'étude de l'unicité de la solution de certains cas linéaires inverses en finance. Cette unicité aide en effet à avoir des algorithmes simples fondés sur Monte Carlo / Handling multidimensional parabolic linear, nonlinear and linear inverse problems is the main objective of this work. It is the multidimensional word that makes virtually inevitable the use of simulation methods based on Monte Carlo. This word also makes necessary the use of parallel architectures. Indeed, the problems dealing with a large number of assets are major resources consumers, and only parallelization is able to reduce their execution times. Consequently, the first goal of our work is to propose "appropriate" random number generators to parallel and massively parallel architecture implemented on CPUs/GPUs cluster. We quantify the speedup and the energy consumption of the parallel execution of a European pricing. The second objective is to reformulate the nonlinear problem of pricing American options in order to get the same parallelization gains as those obtained for linear problems. In addition to its parallelization suitability, the proposed method based on Malliavin calculus has other practical advantages. Continuing with parallel algorithms, the last point of this work is dedicated to the uniqueness of the solution of some linear inverse problems in finance. This theoretical study enables the use of simple methods based on Monte Carlo

En France, environ 9,8% de la population souffre de lithiase urinaire. Nous proposons, ici, une nouvelle approche afin de caractériser ces matériaux et d'obtenir une meilleure compréhension de leur formation. Les médecins utilisent principalement des techniques FTIR pour déterminer les principales phases présentes dans une calcification pathologique donnée. Les méthodes de RMN semblent appropriées pour déterminer plus précisément la composition de ces calcifications pathologiques. Très peu d'analyses RMN de calculs rénaux et d'analogues synthétiques ont été réalisées à ce jour.Premièrement, les trois phases d'oxalate de calcium ont été synthétisées (CaC2O4?nH2O avec n = 1, 2, 3) en mettant en ¿uvre des protocoles originaux. L'analyse des spectres 1H, 13C CPMAS et 43Ca MAS à ultra-haut champ magnétique en abondance naturelle permet une identification précise des différentes phases et peut être interprétée en tenant compte du nombre d'inéquivalents des sites cristallographiques. L'hydroxyapatite a été étudiée en parallèle car pouvant également apparaître lors de lithiase urinaire.Enfin, nous montrons les résultats obtenus à partir de DNP MAS à 100 K sur les échantillons synthétiques. L'affinité de la combinaison biradical/solvant reste un facteur limitant pour les matériaux hétérogènes tels que ceux qui sont analysés dans cette étude. Nous devons être en mesure de trouver une combinaison appropriée pour les matériaux multi-composants complexes afin d'obtenir un gain équivalent sur tous les signaux. Finalement, il est démontré qu'il est possible de transposer l'approche méthodologique présentée ci-dessus à l'étude des calculs rénaux. / In France, about 9.8% of the population suffer from urolithiasis. The treatment of kidney stones, composed of 72% of hydrated calcium oxalates (CaC2O4∙nH2O) with n = 1, 2, 3, represents almost 900 million euros in annual spending and it is therefore necessary to understand the in vivo formation of these stones. Here we propose a new approach in order to characterize kidney stones and have a greater understanding of their formation. Physicians primarily use FTIR techniques to determine the major phases present in a given pathological calcification. NMR methods appears suitable to determine more accurately the composition of these pathological calcifications. Very few NMR analyzes of kidney stones and synthetic analogues were conducted to date. In a first step, the three phases of calcium oxalate were synthesized by implementing original protocols. Analysis of the 1H, 13C CP MAS and MAS 43Ca ultra-high magnetic field spectra at natural abundance allow precise identification of the different phases and can be interpreted by taking into account the number of inequivalent crystallographic sites. The hydroxyapatite was studied in parallel as it may also appear in urolithiase. Finally, we show results obtained from DNP MAS at 100 K on the synthetic samples. The affinity of the biradical/solvent combination remains a limiting factor for heterogeneous materials such as those analyzed in this study. We have to be able to find a suitable combination for complex multi-component materials and to obtain an equivalent gain on all signals. In a last step, it is demonstrated that it is possible to transpose the methodological approach presented above to the study of kidney stones.

Cette thèse s'intéresse à l'étude et au développement de méthodes de pistage mono et multicible en contexte Track-Before-Detect (TBD) par filtrage particulaire. Contrairement à l'approche classique qui effectue un seuillage préalable sur les données avant le pistage, l'approche TBD considère directement les données brutes afin de réaliser conjointement la détection et le pistage des différentes cibles. Il existe plusieurs solutions à ce problème, néanmoins cette thèse se restreint au cadre bayésien des Modèles de Markov Cachés pour lesquels le problème TBD peut être résolu à l'aide d'approximations particulaires. Dans un premier temps, nous nous intéressons à des méthodes particulaires monocibles existantes pour lesquels nous proposons différentes lois instrumentales permettant l'amélioration des performances en détection et estimation. Puis nous proposons une approche alternative du problème monocible fondée sur les temps d'apparition et de disparition de la cible; cette approche permet notamment un gain significatif au niveau du temps de calcul. Dans un second temps, nous nous intéressons au calcul de la vraisemblance en TBD -- nécessaire au bon fonctionnement des filtres particulaires -- rendu difficile par la présence des paramètres d'amplitudes des cibles qui sont inconnus et fluctuants au cours du temps. En particulier, nous étendons les travaux de Rutten et al. pour le calcul de la vraisemblance au modèle de fluctuations Swerling et au cas multicible. Enfin, nous traitons le problème multicible en contexte TBD. Nous montrons qu'en tenant compte de la structure particulière de la vraisemblance quand les cibles sont éloignées, il est possible de développer une solution multicible permettant d'utiliser, dans cette situation, un seule filtre par cible. Nous développons également un filtre TBD multicible complet permettant l'apparition et la disparition des cibles ainsi que les croisements. / This thesis deals with the study and the development of mono and multitarget tracking methods in a Track-Before-Detect (TBD) context with particle filters. Contrary to the classic approach that performs before the tracking stage a pre-detection and extraction step, the TBD approach directly works on raw data in order to jointly perform detection and tracking. Several solutions to this problem exist, however this thesis is restricted to the particular Hidden Markov Models considered in the Bayesian framework for which the TBD problem can be solved using particle filter approximations.Initially, we consider existing monotarget particle solutions and we propose several instrumental densities that allow to improve the performance both in detection and in estimation. Then, we propose an alternative approach of the monotarget TBD problem based on the target appearance and disappearance times. This new approach, in particular, allows to gain in terms of computational resources. Secondly, we investigate the calculation of the measurement likelihood in a TBD context -- necessary for the derivation of the particle filters -- that is difficult due to the presence of the target amplitude parameters that are unknown and fluctuate over time. In particular, we extend the work of Rutten et al. for the likelihood calculation to several Swerling models and to the multitarget case. Lastly, we consider the multitarget TBD problem. By taking advantage of the specific structure of the likelihood when targets are far apart from each other, we show that it is possible to develop a particle solution that considers only a particle filter per target. Moreover, we develop a whole multitarget TBD solution able to manage the target appearances and disappearances and also the crossing between targets.

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.

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.

Cette thèse traite de problématique de dimensionnement d'un système technique complexe. L'objectif est de proposer et d'outiller un processus de conception selon lequel le dimensionnement statique de l'architecture initiale d'un système satisfait dès le début les exigences statiques et dynamiques sans nécessité de redimensionnement. Ainsi, nous avons proposé une nouvelle démarche de conception dans laquelle la prise en compte des exigences statiques et dynamiques est effectuée de maniéré simultanée et globale dans la phase de conception préliminaire. Cette démarche se base sur les exigences pour déterminer les solutions admissibles et utilise des méthodes de résolution ensemblistes telles que la méthode de calcul par intervalle et la méthode de propagation par contraintes. En effet, les variables de conception sont exprimées par intervalles et les exigences statiques et dynamiques sont implémentées dans un même modèle NCSP. Les exigences dynamiques sont plus difficiles à intégrer. Il s'agit des exigences fonctionnelles du système, de la résonance et des critères de stabilité, de commandabilité et de transmittance. Dans un premier temps, nous avons réussi à intégrer le comportement dynamique d'un système technique sous forme d'équation différentielle ordinaire par intervalles et dans un deuxième temps, nous avons traduit les exigences dynamiques sous forme de contraintes algébriques définies par un ensemble d'équations et inéquations. La solution générée représente les valeurs admissibles des variables de conception satisfaisant simultanément les exigences statiques et dynamiques imposées. Ce couplage entre le dimensionnement statique et dynamique dans l'approche de conception proposée permet d'éviter le sur-dimensionnement puisque les exigences dynamiques interviennent dans le choix des coefficients de sécurité, et d'éviter les boucles de redimensionnement en cas d'échec ce qui permet de gagner en temps de calcul et de réduire le coût de conception. La démarche de conception proposée est validée par application sur le cas de dimensionnement d'un système de suspension active MacPherson. / This thesis deals with design problems of a complex technical system. The objective is to find a design process which the static design of the initial architecture of a system meets from the first static and dynamic requirements with no need to resize it. Thus, we propose a new design approach which the consideration of static and dynamic requirements is done simultaneously and globally in the preliminary design phase. This approach is based on the requirements to determine admissible solutions and uses set-based methods such as interval computation and constraint propagation. Indeed, the design variables are expressed by intervals and the static and dynamic requirements are implemented in a NCSP model. The dynamic requirements are more difficult to integrate. They represent the functional requirements of the system, the resonance and stability criteria, controllability and transmittance. On the one hand, we succeed to integrate the dynamic behavior of a technical system in the form of ordinary differential equation by intervals. On the other hand, we formalize the dynamic requirements in the form of algebraic constraints defined by a set of equations and inequalities. The generated solution is the set of acceptable values of design variables satisfying simultaneously static and dynamic requirements. This coupling between the static and dynamic sizing steps in the proposed design approach avoids over- sizing of the system as the dynamic requirements involved in the choice of safety factors. Il also avoid resizing loops in case of failure, which saves significant computation time and reduce the cost of design. The proposed design approach is applied on the sizing of a MacPherson active suspension system.