L'assimilation variationnelle de données 4D-Var est une technique très utilisée en géophysique, notamment en météorologie et océanographie. Elle consiste à estimer des paramètres d'un modèle numérique direct, en minimisant une fonction de coût mesurant l'écart entre les sorties du modèle et les mesures observées. La minimisation, qui est basée sur une méthode de gradient, nécessite le calcul du modèle adjoint (produit de la transposée de la matrice jacobienne avec le vecteur dérivé de la fonction de coût aux points d'observation). Lors de la mise en œuvre de l'AD 4D-Var, il faut faire face à des problèmes d'implémentation informatique complexes, notamment concernant le modèle adjoint, la parallélisation du code et la gestion efficace de la mémoire. Afin d'aider au développement d'applications d'AD 4D-Var, le logiciel YAO qui a été développé au LOCEAN, propose de modéliser le modèle direct sous la forme d'un graphe de flot de calcul appelé graphe modulaire. Les modules représentent des unités de calcul et les arcs décrivent les transferts des données entre ces modules. YAO est doté de directives de description qui permettent à un utilisateur de décrire son modèle direct, ce qui lui permet de générer ensuite le graphe modulaire associé à ce modèle. Deux algorithmes, le premier de type propagation sur le graphe et le second de type rétropropagation sur le graphe permettent, respectivement, de calculer les sorties du modèle direct ainsi que celles de son modèle adjoint. YAO génère alors le code du modèle direct et de son adjoint. En plus, il permet d'implémenter divers scénarios pour la mise en œuvre de sessions d'assimilation.Au cours de cette thèse, un travail de recherche en informatique a été entrepris dans le cadre du logiciel YAO. Nous avons d'abord formalisé d'une manière plus générale les spécifications deYAO. Par la suite, des algorithmes permettant l'automatisation de certaines tâches importantes ont été proposés tels que la génération automatique d'un parcours "optimal" de l'ordre des calculs et la parallélisation automatique en mémoire partagée du code généré en utilisant des directives OpenMP. L'objectif à moyen terme, des résultats de cette thèse, est d'établir les bases permettant de faire évoluer YAO vers une plateforme générale et opérationnelle pour l'assimilation de données 4D-Var, capable de traiter des applications réelles et de grandes tailles.

Os workflows científicos emergiram como uma abstração básica para estruturar experimentos científicos baseados em simulações computacionais. Em muitas situações, estes workflows são intensivos, seja computacionalmente seja quanto em relação à manipulação de dados, exigindo a execução em ambientes de processamento de alto desempenho. Entretanto, paralelizar a execução de workflows científicos requer programação trabalhosa, de modo ad hoc e em baixo nível de abstração, o que torna difícil a exploração das oportunidades de otimização. Visando a abordar o problema de otimizar a execução paralela de workflows científicos, esta tese propõe uma abordagem algébrica para especificar o workflow, bem como um modelo de execução que, juntos, possibilitam a otimização automática da execução paralela de workflows científicos. A tese apresenta uma avaliação ampla da abordagem usando tanto experimentos reais quanto dados sintéticos. Os experimentos foram avaliados no Chiron, um motor de execução de workflows desenvolvido para apoiar a execução paralela de workflows científicos. Os experimentos apresentaram resultados excelentes de paralelização na execução de workflows e evidenciaram, com a abordagem algébrica, diversas possibilidades de otimização de desempenho quando comparados a execuções paralelas de workflow de modo ad hoc.

Les méthodes de dynamique moléculaire (MD pour Molecular Dynamics en anglais) sont utilisées pour simuler des systèmes volumineux et complexes. Cependant, la simulation de ce type de systèmes sur de longues échelles temporelles demeure un problème coûteux en temps de calcul. L'étape la plus coûteuse des méthodes de MD étant la mise à jour des forces entre les particules. La simulation de particules restreintes de façon adaptative (ARMD pour Adaptively Restrained Molecular Dynamics en anglais) est une nouvelle approche permettant d'accélérer le processus de simulation en réduisant le nombre de calculs de forces effectués à chaque pas de temps. La méthode ARMD fait varier l'état des degrés de liberté en position en les activants ou en les désactivants de façon adaptative au cours de la simulation. Du fait, que le calcul des forces dépend majoritairement de la distance entre les atomes, ce calcul peut être évité entre deux particules dont les degrés de liberté en position sont désactivés. En revanche, le calcul des forces pour les particules actives (i.e. celles dont les degrés de liberté en position sont actifs) est effectué. Afin d'exploiter au mieux l'adaptabilité de la méthode ARMD, nous avons conçu de nouveaux algorithmes permettant de calculer et de mettre à jour les forces de façon plus efficace. Nous avons développé des algorithmes permettant de construire et de mettre à jour des listes de voisinage de manière incrémentale. En particulier, nous avons travaillé sur un algorithme de mise à jour incrémentale des forces en un seul passage deux fois plus rapide que l'ancien algorithme également incrémental mais qui nécessitait deux passages. Les méthodes proposées ont été implémentées et validées dans le simulateur de MD appelé LAMMPS, mais elles peuvent s'appliquer à n'importe quel autre simulateur de MD. Nous avons validé nos algorithmes pour différents exemples sur les ensembles NVE et NVT. Dans l'ensemble NVE, la méthode ARMD permet à l'utilisateur de jouer sur le précision pour accélérer la vitesse de la simulation. Dans l'ensemble NVT, elle permet de mesurer des grandeurs statistiques plus rapidement. Finalement, nous présentons des algorithmes parallèles pour la mise à jour incrémentale en un seul passage permettant d'utiliser la méthode ARMD avec le standard Message Passage Interface (MPI). / Molecular Dynamics (MD) is often used to simulate large and complex systems. Although, simulating such complex systems for the experimental time scales are still computationally challenging. In fact, the most computationally extensive step in MD is the computation of forces between particles. Adaptively Restrained Molecular Dynamics (ARMD) is a recently introduced particles simulation method that switches positional degrees of freedom on and off during simulation. Since force computations mainly depend upon the inter-atomic distances, the force computation between particles with positional degrees of freedom off~(restrained particles) can be avoided. Forces involving active particles (particles with positional degrees of freedom on) are computed.In order to take advantage of adaptability of ARMD, we designed novel algorithms to compute and update forces efficiently. We designed algorithms not only to construct neighbor lists, but also to update them incrementally. Additionally, we designed single-pass incremental force update algorithm that is almost two times faster than previously designed two-pass incremental algorithm. These proposed algorithms are implemented and validated in the LAMMPS MD simulator, however, these algorithms can be applied to other MD simulators. We assessed our algorithms on different and diverse benchmarks in both microcanonical ensemble (NVE) and canonical (NVT) ensembles. In the NVE ensemble, ARMD allows users to trade between precision and speed while, in the NVT ensemble, it makes it possible to compute statistical averages faster. In Last, we introduce parallel algorithms for single-pass incremental force computations to take advantage of adaptive restraints using the Message Passage Interface (MPI) standard.

Dans cette thèse, nous nous intéressons à des noeuds critiques du calcul du risque de contrepartie, la valorisation rapide des produits dérivées et de leurs sensibilités. Nous proposons plusieurs méthodes mathématiques et informatiques pour répondre à cette problématique. Nous contribuons à quatre domaines différents: une extension de la méthode Vibrato et l'application des méthodes multilevel Monte Carlo pour le calcul des grecques à ordre élevé n>1 avec une technique de différentiation automatique. La troisième contribution concerne l'évaluation des produits Américain, ici nous nous servons d'un schéma pararéel pour l'accélération du processus de valorisation et nous faisons également une application pour la résolution d'une équation différentielle stochastique rétrograde. La quatrième contribution est la conception d'un moteur de calcul performant à architecture parallèle. / In this thesis, we will focus on the critical node of the computation of counterparty credit risk, the fast evaluation of financial derivatives and their sensitivities. We propose several mathematical and computer-based methods to address this issue. We have contributed to four areas: an extension of the Vibrato method and an application of the weighted multilevel Monte Carlo for the computation of the greeks for high order derivatives n>1 with automatic differentiation. The third contribution concerns the evaluation of American style option, here we use a parareal scheme to speed up the assessing process and we made an application for solving backward stochastic differential equations. The last contribution is the conception of an efficient computation engine for financial derivatives with a parallel architecture.

Depuis plusieurs années, le nombre de cœurs de calcul dans les processeurs ne cesse d'augmenter à chaque nouvelle génération. Les processeurs multi-cœurs sont maintenant très fréquents mais le développement de logiciels séquentiels reste une pratique très courante. Pour palier à ce problème, des outils de parallélisation automatique ont été proposés mais ils ne sont pas encore prêts pour une utilisation à grande échelle. Nous proposons d'étendre les outils existants dans trois directions différentes. Premièrement, on peut remarquer que le code source de certains programmes n'est pas disponible. Nous proposons donc un système de parallélisation statique de code binaire qui permet de paralléliser un application séquentielle déjà compilée. Ensuite, on peut s'apercevoir que la performance d'un programme dépend du contexte d'exécution dans lequel il s'exécute. Nous présentons donc un système qui permet de sélectionner une version d'un programme parmi plusieurs afin d'exploiter au mieux les particularités du contexte d'exécution courant. Enfin, étant donné que certains programmes sont difficiles à analyser statiquement, nous proposons un système de parallélisation spéculative permettant d'appliquer dynamiquement des transformations de code complexes sur ces programmes. Ces trois systèmes utilisent le modèles polyédrique comme une boîte à outil permettant d'analyser, de transformer ou de paralléliser les programmes. En travaillant à différentes phases de la vie des programmes, ils forment une approche globale qui étend les techniques de parallélisation existantes.

Dans cette thèse nous étudions l'accélération des rayons cosmiques (RC), ces particules très énergétiques qui emplissent l'univers. Il est admis que les RC galactiques sont produits par accélération diffusive par onde de choc dans les restes de supernovae. La théorie linéaire explique la formation de spectres en loi de puissance, mais elle doit être modifiée du fait de la rétroaction des RC. Nous nous concentrons sur l'accélération répétée par chocs successifs, qui durcit les spectres, et qui dépend du transport des rayons cosmiques entre les chocs.<br />Pour cette étude nous avons développé un outil numérique qui couple l'évolution hydrodynamique du plasma et le transport cinétique des RC. Nous l'avons validé grâce à des résultats déjà connus. Pour résoudre toutes les échelles induites par la dépendance en énergie du coefficient de diffusion des RC nous avons implémenté une technique de grille adaptative. Pour réduire le temps de calcul nous avons aussi parallélisé notre code, dans la dimension d'énergie. Cela nous permet de présenter les premières simulations de l'accélération non-linéaire par chocs multiples. <br />Nous appliquons notre outil aux superbulles, les vastes structures chaudes et peu denses entourant les associations OB, car c'est probablement là que la plupart des supernovae explose en fait -- ce qui induit des modifications substantielles du modèle standard de production des RC galactiques. Plus précisément nous avons commencé à explorer les effets de chocs multiples, par une étude du rôle de RC pré-existants en amont d'une onde de choc. Pour finir nous passons en revue l'émission haute énergie des superbulles dans l'optique d'une production efficace de RC.

La physique actuelle cherche, à côté des expériences, à vérifier et déduire les lois de la nature en simulant les modèles physiques sur d'énormes ordinateurs. Cette thèse explore comment accélérer ces simulations en améliorant les programmes qui les font tourner. L'application de référence est la chromodynamique quantique sur réseaux (LQCD pour "Lattice Quantum Chromodynamics"), une branche de la théorie quantique des champs, tournant sur le plus récent des supercalculateurs d'IBM, le Blue Gene/Q.Dans un premier temps, on améliore le code source de tmLQCD, un programme de LQCD, dont l'opération clef pour la performance est un stencil à 8 points en dimension 4. On étudie deux stratégies d'optimisation différentes: la première se donne comme priorité d'améliorer la localité spatiale et temporelle; la seconde utilise le préchargement matériel de flux de données. Sur le Blue Gene/Q, la première stratégie permet d'atteindre 20% de la performance crête théorique. La seconde, avec jusqu'à 54% de la performance crête est bien meilleure mais utilise 4 fois plus de mémoire car elle stocke les résultats dans l'ordre où les utilise le stencil suivant, ce qui requiert de dupliquer des données. Les autres techniques exploitées sont la programmation directe du système de communication (appelé MUSPI chez IBM), un mécanisme allégé de gestion des threads, le préchargement explicite de certaines données (à l'aide de l'instruction dcbt) et la vectorisation manuelle (en utilisant les instructions SIMD de largeur 4; appelé QPX par IBM). Le préchargement de liste et la mémoire transactionnelle - deux nouveaux mécanismes du Blue Gene/Q - n'améliorent pas les performances.Dans un second temps, on présente la réalisation d'une extension appelé Molly au compilateur LLVM, pour optimiser automatiquement le programme, et plus précisément la distribution des données et des calculs entre les nœuds d'un cluster tel que le Blue Gene/Q. Molly représente les tableaux par des polyèdres entiers et utilise l'extension existante Polly qui représente les boucles et les instructions par des polyèdres. Partant de la spécification de la distribution des données et de l'emplacement des calculs, Molly ajoute le code qui gère les flots de données entre les nœuds de calcul. Molly peut aussi permuter l'ordre des données en mémoire. La tâche principale de Molly est d'agréger les données dans des ensembles qui sont envoyés dans le même tampon au même destinataire, pour éviter l'overhead des transferts trop petits. Nous présentons un algorithme qui minimise le nombre de transferts pour des boucles non-paramétrées, basé sur les antichaînes du flot des données. De plus, nous implémentons une heuristique qui tient compte de la manière dont le programmeur a écrit son code. Les primitives de communication asynchrone sont insérées juste après que les données soient disponibles - respectivement juste avant qu'elles soient utilisées. Une bibliothèque runtime implémente ces primitives en utilisant MPI. Molly gère la distribution pour tout code représentable dans le modèle polyédrique, mais fonctionne mieux pour du code à stencil tel LQCD. Compilé avec Molly, le code LQCD atteint 2,5% de la performance crête. L'écart de performance est surtout dû au fait que les autres optimisations ne sont pas faites, par exemple la vectorisation. Les versions futures de Molly pourraient aussi gérer efficacement les codes non à stencil et exploiter les autres optimisations qui ont rendu le code LQCD optimisé à la main si rapide. / Motivated by modern day physics which in addition to experiments also tries to verify and deduce laws of nature by simulating the state-of-the-art physical models using oversized computers, this thesis explores means of accelerating such simulations by improving the simulation programs they run. The primary focus is Lattice Quantum Chromodynamics (QCD), a branch of quantum field theory, running on IBM newest supercomputer, the Blue Gene/Q.In a first approach, the source code of tmLQCD, a Lattice QCD program, is improved to run faster on the Blue Gene machine. Its most performance-relevant operation is a 8-point stencil in 4 dimensional space. Two different optimization strategies are perused: One with the priority of improving spatial and temporal locality, and a second making use of the hardware's data stream prefetcher. On Blue Gene/Q the first strategy reaches up to 20% of the peak theoretical floating point operation performance of that machine. The second strategy with up to 54% of peak is much faster at the cost of using 4 times more memory by storing the data in the order they will be used in the next stencil operation, duplicating data where necessary.Other techniques exploited are direct programming of the messaging hardware (called MUSPI by IBM), a low-overhead work distribution mechanism for threads, explicit data prefetching of data (using dcbt instruction) and manual vectorization (using QPX; width-4 SIMD instructions). Hardware-based list prefetching and transactional memory - both distinct and novel features of the Blue Gene/Q system -- did not improve the program's performance.The second approach is the newly-written LLVM compiler extension called Molly which optimizes the program itself, specifically the distribution of data and work between the nodes of a cluster machine such as Blue Gene/Q. Molly represents arrays using integer polyhedra and uses another already existing compiler extension Polly which represents statements and loops using polyhedra. When Molly knows how data is distributed among the nodes and where statements are executed, it adds code that manages the data flow between the nodes. Molly can also permute the order of data in memory. Molly's main task is to cluster data into sets that are sent to the same target into the same buffer because single transfers involve a massive overhead. We present an algorithm that minimizes the number of transfers for unparametrized loops using anti-chains of data flows. In addition, we implement a heuristic that takes into account how the programmer wrote the code. Asynchronous communication primitives are inserted right after the data is available respectively just before it is used. A runtime library implements these primitives using MPI.Molly manages to distribute any code that is representable by the polyhedral model, but does so best for stencils codes such as Lattice QCD. Compiled using Molly, the Lattice QCD stencil reaches 2.5% of the theoretical peak performance. The performance gap is mostly because all the other optimizations are missing, such as vectorization. Future versions of Molly may also effectively handle non-stencil codes and use make use of all the optimizations that make the manually optimized Lattice QCD stencil so fast.

Dans cette thèse nous présentons une approche générale et robuste pour la décomposition des jeux décrits en Game Description Language (GDL). Dans le domaine du General Game Playing (GGP), les joueurs peuvent significativement diminuer le coût de l'exploration d'un jeu s'ils disposent d'une version décomposée de celui-ci. Les travaux existants sur la décomposition des jeux s'appuient sur la structure syntaxique des règles, sur des habitudes d'écriture du GDL ou sur le coûteux calcul de la forme normale disjonctive des règles. Nous proposons une méthode plus générale pour décomposer les jeux solitaires ou multijoueurs. Dans un premier temps nous envisageons une approche fondée sur l'analyse logique des règles. Celle-ci nécessite l'utilisation d'heuristiques, qui en limitent la robustesse, et le coûteux calcul de la forme normale disjonctive des règles. Une seconde approche plus efficace est fondée sur la collecte d'informations durant des simulations (playouts). Cette dernière permet la détection des liens de causalité entre les actions et les fluents d'un jeu. Elle est capable de traiter les différents types de jeux composés et de prendre en charge certains cas difficiles comme les jeux à actions composées et les jeux en série. Nous avons testé notre approche sur un panel de 597 jeux GGP. Pour 70% des jeux, la décomposition nécessite moins d'une minute en faisant 5k playouts. Nous montrons de 87% d'entre eux peuvent être correctement décomposés après seulement 1k playouts. Nous ébauchons également une approche originale pour jouer avec ces jeux décomposés. Les tests préliminaires sur quelques jeux solitaires sont prometteurs. / This PhD thesis presents a robust and general approach for the decomposition of games described in Game Description Language (GDL). In the General Game Playing framework (GGP), players can drastically decrease game search cost if they hold a decomposed version of the game. Previous works on decomposition rely on syntactical structures and writing habits of the GDL, or on the disjunctive normal form of the rules, which is very costly to compute. We offer an approach to decompose single or multi-player games. First, we consider an approach based on logical rule analysis. This requires the use of heuristics, which limit its robustness, and the costly calculation of the disjunctive normal form of the rules. A second more efficient approach is based on information gathering during simulations of the game (playouts). The latter allows the detection of causal links between actions. It can handle the different classes of compound games and can process some difficult cases like synchrounous parallel games with compound moves and serial games. We tested our program on 597 games. Given 5k playouts, 70% of the games are decomposed in less than one minute. We demonstrate that for 87% of the games, 1k playouts are sufficient to obtain a correct decomposition. We also sketch an original approach to play with these decomposed games. Preliminary tests on some one-player games are promising. Another contribution of this thesis is the evaluation of the MPPA architecture for the parallelization of a GGP player (LeJoueur of Jean-Noël Vittaut).

L’efficacité énergétique devient un domaine de recherche incontournable dans la communauté scientifique vu son importance dans la lutte contre les crises énergétiques actuelles et futures. L'analyse des performances énergétiques, pour les procédés industriels, nécessite la connaissance des grandeurs physiques impliquées dans les équilibres de masse et d'énergie. D’où la problématique : comment choisir les points de mesure sur un site industriel de façon à trouver les valeurs de tous les indicateurs énergétiques sans avoir des redondances de mesure (respect des contraintes économiques), et en conservant un niveau de précision des résultats ? La première partie présente la formulation du problème d’instrumentation ayant pour but de garantir une observabilité minimale du système en faveur des variables clés. Ce problème est combinatoire. Une méthode de validation des différentes combinaisons de capteurs a été introduite. Elle est basée sur l’interprétation structurelle de la matrice représentant le procédé. Le verrou de long temps de calcul lors du traitement des procédés de moyenne et grande taille a été levé. Des méthodes séquentielles ont été développées pour trouver un ensemble de schémas de capteurs pouvant être employés, en moins de 1% du temps de calcul initialement requis. La deuxième partie traite le choix du schéma d’instrumentation optimal. Le verrou de propagation des incertitudes dans un problème de taille variable a été levé. Une modélisation du procédé basée sur des paramètres binaires a été proposée pour automatiser les calculs, et évaluer les incertitudes des schémas trouvés. Enfin la méthodologie complète a été appliquée sur un cas industriel et les résultats ont été présentés. / Energy efficiency is becoming an essential research area in the scientific community given its importance in the fight against current and future energy crises. The analysis of the energy performances of the industrial processes requires the determination of the quantities involved in the mass and energy balances. Hence: how to choose the placement of the measurement points in an industrial site to find the values of all the energy indicators, without engendering an excess of unnecessary information due to redundancies (reducing measurements costs) and while respecting an accepted level of accuracy of the results ? The first part presents the formulation of the instrumentation problem which aims to guaranteeing a minimal observability of the system in favor of the key variables. This problem is combinatory. A method of validation of the different sensors combinations has been introduced. It is based on the structural interpretation of the matrix representing the process. The issue of long computing times while addressing medium and large processes was tackled. Sequential methods were developed to find a set of different sensor networks to be used satisfying the observability requirements, in less than 1% of the initial required computation time. The second part deals with the choice of the optimal instrumentation scheme. The difficulty of uncertainty propagation in a problem of variable size was addressed. To automate the evaluation of the uncertainty for all the found sensor networks, the proposed method suggested modeling the process based on binary parameters. Finally, the complete methodology is applied to an industrial case and the results were presented.

La complexification de la modélisation multi-physique conduit d’une part à devoir simuler des systèmes d’équations différentielles ordinaires et d’équations différentielles algébriques de plus en plus grands en nombre d’inconnues et sur des temps de simulation longs. D’autre part l’évolution des architectures de calcul parallèle nécessite d’autres voies de parallélisation que la décomposition de système en sous-systèmes. Dans ce travail, nous proposons de concevoir des méthodes de décomposition de domaine pour la résolution d’EDO en temps. Nous reformulons le problème à valeur initiale en un problème aux valeurs frontières sur l’intervalle de temps symétrisé, sous l’hypothèse de réversibilité du flot. Nous développons deux méthodes, la première apparentée à une méthode de complément de Schur, la seconde basée sur une méthode de type Schwarz dont nous montrons la convergence pouvant être accélérée par la méthode d’Aitken dans le cadre linéaire. Afin d’accélérer la convergence de cette dernière dans le cadre non-linéaire, nous introduisons les techniques d’extrapolation et d’accélération de la convergence des suites non-linéaires. Nous montrons les avantages et les limites de ces techniques. Les résultats obtenus nous conduisent à développer l’accélération de la méthode de type Schwarz par une méthode de Newton. Enfin nous nous intéressons à l’étude de conditions de raccord non-linéaires adaptées à la décomposition de domaine de problèmes non-linéaires. Nous nous servons du formalisme hamiltonien à ports, issu du domaine de l’automatique, pour déduire les conditions de raccord dans le cadre l’équation de Saint-Venant et de l’équation de la chaleur non-linéaire. Après une étude analytique de la convergence de la DDM associée à ces conditions de transmission, nous proposons et étudions une formulation de Lagrangien augmenté sous l’hypothèse de séparabilité de la contrainte. / Complexification of multi-physics modeling leads to have to simulate systems of ordinary differential equations and algebraic differential equations with increasingly large numbers of unknowns and over large times of simulation. In addition the evolution of parallel computing architectures requires other ways of parallelization than the decomposition of system in subsystems. In this work, we propose to design domain decomposition methods in time for the resolution of EDO. We reformulate the initial value problem in a boundary values problem on the symmetrized time interval, under the assumption of reversibility of the flow. We develop two methods, the first connected with a Schur complement method, the second based on a Schwarz type method for which we show convergence, being able to be accelerated by the Aitken method within the linear framework. In order to accelerate the convergence of the latter within the non-linear framework, we introduce the techniques of extrapolation and of acceleration of the convergence of non-linear sequences. We show the advantages and the limits of these techniques. The obtained results lead us to develop the acceleration of the method of the type Schwarz by a Newton method. Finally we investigate non-linear matching conditions adapted to the domain decomposition of nonlinear problems. We make use of the port-Hamiltonian formalism, resulting from the control field, to deduce the matching conditions in the framework of the shallow-water equation and the non-linear heat equation. After an analytical study of the convergence of the DDM associated with these conditions of transmission, we propose and study a formulation of augmented Lagrangian under the assumption of separability of the constraint.