Les méthodes numériques adaptatives constituent un outil de choix pour assurer la pertinence et l'efficacité de la résolution numérique d'équations aux dérivées partielles. Le travail présenté dans ce mémoire porte sur la conception, l'implémentation, et la validation d'une telle méthode au sein d'une plate-forme industrielle de simulation en thermohydraulique. Du point de vue géométrique, la méthode proposée permet de prendre en compte tant le raffinement du maillage que son déraffinement, tout en garantissant la qualité des éléments qui le compose. Du point de vue numérique, nous utilisons le formalisme des éléments joints pour étendre la méthode des Volumes-Éléments Finis proposée par la plate-forme Trio-U et traiter convenablement les maillages non-conformes générés par la procédure d'adaptation. Enfin, l'implémentation proposée repose sur les concepts des méthodes de décomposition de domaine, afin d'en garantir le bon comportement dans un contexte d'exécution parallèle.

Cette thèse s'inscrit dans le cadre de la vérification automatique de programmes concurrents basée sur un modèle formel intermédiaire: les réseaux de Petri colorés de haut-niveau. Nous nous attachons à combattre le phénomène d'explosion combinatoire lié à l'exploration explicite de l'ensemble des entrelacements possibles du système. Pour cela, nous nous proposons de tirer profit de la quantité de mémoire et de la puissance de calcul offerte par un réseau local de machines travaillant de manière coopérative. Par le biais d'une analyse structurelle, nous cherchons à répartir efficacement le graphe d'accessibilité du système. Nous nous attachons ensuite à conserver l'efficacité des techniques visant à limiter l'explosion combinatoire dans cet environnement réparti en relâchant notamment les contraintes de cohérence sur l'exploration du graphe. Nous avons alors validé ces approches à l'aide d'un vérifieur réparti et multithreadé dans lequel nous avons implémenté nos algorithmes.

Sont présentés les différents travaux que j'ai pu effectuer: dans le domaine des automates cellulaires et de leur programmation, puis les travaux portant sur les fonctions Booléennes et leur complexité.

Depuis quelques années, les grappes équipées de processeurs graphiques GPUs sont devenues des outils très attrayants pour le calcul parallèle haute performance. Dans cette thèse, nous avons conçu des algorithmes itératifs parallèles pour la résolution de systèmes linéaires et non linéaires creux de très grandes tailles sur grappes de GPUs. Dans un premier temps, nous nous sommes focalisés sur la résolution de systèmes linéaires creux à l'aide des méthodes itératives CG et GMRES. Les expérimentations ont montré qu'une grappe de GPUs est plus performante que son homologue grappe de CPUs pour la résolution de systèmes linéaires de très grandes tailles. Ensuite, nous avons mis en oeuvre des algorithmes parallèles synchrones et asynchrones des méthodes itératives Richardson et de relaxation par blocs pour la résolution de systèmes non linéaires creux. Nous avons constaté que les meilleurs solutions développées pour les CPUs ne sont pas nécessairement bien adaptées aux GPUs. En effet, les simulations effectuées sur une grappe de GPUs ont montré que les algorithmes Richardson sont largement plus efficaces que ceux de relaxation par blocs. De plus, elles ont aussi montré que la puissance de calcul des GPUs permet de réduire le rapport entre le temps d'exécution et celui de communication, ce qui favorise l'utilisation des algorithmes asynchrones sur des grappes de GPUs. Enfin, nous nous sommes intéressés aux grappes géographiquement distantes pour la résolution de systèmes linéaires creux. Dans ce contexte, nous avons utilisé la méthode de multi-décomposition à deux niveaux avec GMRES parallèle adaptée aux grappes de GPUs. Celle-ci utilise des itérations synchrones pour résoudre localement les sous-systèmes linéaires et des itérations asynchrones pour résoudre la globalité du système linéaire.

Exprimer le parallélisme dans la programmation de manière simple et performante est un défi auquel l'informatique fait face, en raison de l'évolution actuelle des architectures matérielles. BSML est un langage permettant une programmation parallèle de haut niveau, structurée, qui participe à cette recherche. En s'appuyant sur le coeur du langage existant, cette thèse propose d'une part des extensions qui en font un langage plus général et plus simple (traits impératifs tels que références et exceptions, syntaxe spécifique...) tout en conservant et étendant sa sûreté (sémantiques formelles, système de types...) et d'autre part une méthodologie de développement d'applications parallèles certifiées

Afin de créer des productions toujours plus réalistes, les industries du jeu vidéo et du cinéma cherchent à générer des environnements de plus en plus larges et complexes. Cependant, la modélisation manuelle des objets 3D dans de tels décors se révèle très coûteuse. A l'inverse, les méthodes de génération procédurale permettent de créer facilement une grande variété d'objets, tels que les plantes et les bâtiments. La modélisation par règles de grammaire offre un outil de haut niveau pour décrire ces objets, mais utiliser correctement ces règles s'avère très souvent compliqué. De plus, aucune solution de modélisation basée grammaire ne supporte l'édition et la visualisation d'environnements massifs en temps interactif. Dans un tel scénario, les artistes doivent modifier les objets en dehors de la scène avant de voir le résultat intégré. Dans ces travaux de recherche, nous nous intéressons à la génération procédurale et au rendu d'environnements à grande échelle. Nous voulons aussi faciliter la tâche des artistes avec des outils intuitifs de contrôle de grammaires. Tout d'abord nous proposons un système permettant la génération procédurale en parallèle sur le GPU en temps interactif. Pour cela, nous adoptons une approche d'expansion indépendante par segment, permettant une amplification des données en parallèle. Nous étendons ce système pour générer des modèles basés sur une structure interne, tels que les toits. Nous présentons aussi une solution utilisant des contextes externes pour contrôler facilement les grammaires par le biais de surface ou de texture. Pour finir nous intégrons un système de niveaux de détails et des techniques d'optimisation permettant la génération, l'édition et la visualisation interactives d'environnements à grande échelle. Grâce à notre système il est possible de générer et d'afficher interactivement des scènes comprenant des milliers de bâtiments et d'arbres, représentant environ 2 teraoctets de données.

Dans le contexte du calcul scientique, l'équilibrage de la charge est un problème crucial qui conditionne la performance des simulations numériques parallèles. L'objectif est de répartir la charge de travail entre un nombre de processeurs donné, afin de minimiser le temps global d'exécution. Une stratégie populaire pour résoudre ce problème consiste à modéliser la simulation à l'aide d'un graphe et à appliquer des algorithmes de partitionnement. En outre, les simulations numériques tendent à se complexifier, notamment en mixant plusieurs codes représentant des physiques différentes ou des échelles différentes. On parle alors de couplage de codes multi-physiques ou multi-échelles. Dans ce contexte, le problème de l'équilibrage de charge devient également plus difficile, car il ne s'agit plus d'équilibrer chacun des codes séparément, mais l'ensemble de ces codes pris dans leur globalité. Dans ce travail, on propose de resoudre ce problème en utilisant le modèle de partitionnement à sommets fixes qui pourrait représenter efficacement les contraintes supplémentaires imposées par les codes couplés (co-partitionnement). Nous avons donc développé un algorithme direct de partitionnement de graphe qui gère des sommets fixes. L'algorithme a été implémenté dans le partitionneur Scotch et une série d'expériences ont été menées sur la collection des graphes DIMACS. Ensuite nous avons proposé trois algorithmes de co-partitionnement qui respectent les contraintes issues des codes couplés respectifs. Nous avons egalement validé nos algorithmes par une étude expérimentale en comparant nos méthodes aux strategies actuelles sur des cas artificiels ainsi que sur des codes réels couplés. / Load balancing is an important step conditioning the performance of parallel applications. The goal is to distribute roughly equal amounts of computational load across a number of processors, while minimising interprocessor communication. A common approach to model the problem is based on graph structures and graph partitioning algorithms. Moreover, new challenges involve the simulation of more complex physical phenomena, where different parts of the computational domain exhibit different physical behavior. Such simulations follow the paradigm of multi-physics or multi-scale modeling approaches. Combining such different models in massively parallel computations is still a challenge to reach high performance. Additionally, traditional load balancing algorithms are often inadequate, and more sophisticated solutions should be explored. In this thesis, we propose new graph partitioning algorithms that balance the load of such simulations, refered to as co-partitioning. We formulate this problem with the use of graph partitioning with initially fixed vertices which we believe represents efficiently the additional constraints of coupled simulations. We have therefore developed a direct algorithm for graph partitioning that manages successfully problems with fixed vertices. The algorithm is implemented inside Scotch partitioner and a series of experiments were carried out on the DIMACS graph collection. Moreover we proposed three copartitioning algorithms that respect the constraints of the respective coupled codes. We finally validated our algorithms by an experimental study comparing our methods with current strategies on artificial cases and on real-life coupled simulations.

Les systèmes sur puce sont constitués d'une partie matérielle (un circuit intégré) et d'une partie logicielle (un programme) qui utilise les ressources matérielles de la puce. La conséquence de cela est que le logiciel d'un système sur puce est intrinsèquement lié à sa partie matérielle. Les composants matériels d'accélération sont des facteurs clés de différenciation d'un produit à l'autre.Il est nécessaire de pouvoir simuler ces systèmes très tôt lors de leur conception; bien avant que la puce ne soit physiquement disponible, et même avant que la puce ne soit complètement spécifiée. Pour cela, un modèle du système sur puce est réalisé à l'aide du langage SystemC, au niveau d'abstraction TLM (Transaction Level Modeling). La partie matérielle d'un système sur puce est constituée de composants, qui s'exécutent en parallèle. Pour autant, la simulation avec le simulateur SystemC de référence est séquentielle. Ceci permet de garantir les bonnes propriétés des simulations SystemC, en particulier la reproductibilité et le confort d'écriture des modèles.Les travaux de cette thèse portent sur la simulation parallèle de modèles SystemC/TLM. L'objectif de l'exécution parallèle est d'accélérer les simulations dans un mode d'utilisation correspondant à la phase de développement, où il est primordial de disposer de simulations qui donnent rapidement un résultat. Afin de cerner le problème de performance remarqué sur des modèles complexes à STMicroelectronics, le premier travail de cette thèse a été d'analyser le profil d'exécution d'une étude de cas représentative de la complexité actuelle des platformes SystemC/TLM. Pour cette étude, nous avons développé un outil de collecte de traces et de visualisation. Les résultats de cette analyse ont indiqué que la lenteur d'exécution en simulation était due à la complexité des composants matériels d'accélération. L'étude de l'état de l'art en simulation parallèle de modèles SystemC nous a conduit à chercher d'autres pistes que celles actuellement existantes.Pour réaliser les composants matériels plus rapidement, et permettre d'augmenter la réutilisabilité de composants d'un projet à l'autre, le flot de conception HLS (High Level Synthesis) est utilisé, notamment à STMicroelectronics. Ce flot de conception permet, à partir de la description d'une fonction en C/C++, de générer un plan de composant matériel qui va réaliser la même fonction. La description des composants est découpée en sous-fonctions, individuellement plus simples. Afin d'obtenir de bonnes performances, les sous-fonctions sont assemblées en chaîne, à travers laquelle circulent les données à traiter. Il est indispensable de pouvoir réutiliser le code écrit pour la HLS dans les simulations SystemC/TLM@: cette situation deviendra de plus en plus fréquente, et il n'a pas assez de temps pour réécrire ces modèles dans ces projets courts.Nous avons développé une infrastructure de simulation parallèle permettant d'intégrer et de simuler efficacement des composants de traitement de données écrits pour la HLS. L'application de cette infrastructure à un exemple a permis d'accélérer l'exécution de la simulation d'un facteur 1.6 avec 4 processeurs. Au-delà de ce résultat, les conclusions principales de cette thèse sont que la simulation parallèle de modèles à haut niveau d'abstraction, en SystemC/TLM, passe par la combinaison de plusieurs techniques de parallélisation. Il est également important d'identifier les parties parallélisables dans des simulations industrielles, notamment pour les nouveaux défis que sont les simulations multi-physiques et l'internet des objets. / Systems on chip consists in a hardware part (an integrated circuit) and a software part (a program) that uses the hardware resources of the chip. Consequently, the embedded software is intrinsically connected to the chip hardware. Hardware acceleration components are key differentiation factors from one product to another.It is necessary to simulate systems on chip very early in the design flow; before the chip is physically available and even before its full specification. For such simulations, developers write a model of the system on chip in SystemC, at the TLM (Transaction Level Modeling) abstraction level. The hardware part of a chip consists in components that behave in parallel with each other. However, the reference SystemC simulator execute simulations sequentially. The sequential execution enables to keep good properties of SystemC simulations, namely reproducibility and ease of model writing.This thesis work address the parallel execution of SystemC/TLM simulations. The goal of parallel simulation is to speed up simulations, in the context of the model development, where it is important to quickly get results. In order to identify the performance problem of complex models at STMicroelectronics, the first step of this thesis was to analyse the execution profile of a case study, representative of the complexity of current platforms. For this study, we developed a trace recording and visualization tool. The results of this study indicated that the performance critical parts of the simulation are hardware acceleration components. Studying existing parallel simulation approaches led us to look for other parallel simulation techniques.To speed up the development of hardware acceleration components, and increase the reusability from one project to another, the HLS (High Level Synthesis) design flow is used, notably at STMicroelectronics. This design flow enables to generate a logically synthesizable model of a component, from a high level behavioral description in C/C++. This design flow also constraints the development: it is split in sub-functions, assembled in a pipeline. The code written for HLS must be re-used in SystemC/TLM models: this situation will become more and more frequent and there is no time to rewrite the models of such components within short delays.We developed a parallel simulation infrastructure enabling the integration and efficient simulation of hardware components written for HLS.We applied this infrastructure to an example platform, which resulted in speeding up the simulation. Beyond this result, one of the main conclusion of this thesis is that parallel simulation of abstract SystemC/TLM models will require to combine multiple parallelization techniques. Future research work can identify other types of potential parallelism in industrial models. This will become critical with the new challenges of simulation, as multi-physical simulations and internet of things.

Dans le cadre du projet PAJERO, nous présentons dans cette thèse une parallélisation externe d'un solveur de Programmation Par Contraintes (PPC) basée sur des méthodes de parallélisation de la search et Portfolio. Cela, afin d'améliorer la performance de la résolution des problèmes de satisfaction et d'optimisation sous contraintes. La parallélisation de la search que nous proposons est adaptée pour une exécution en mode opportuniste et déterministe, suivant les besoins des clients. Le principe consiste à partitionner à la demande l'arbre de recherche unique généré par une seule stratégie de recherche en un ensemble de sous-arbres, pour ensuite affecter chaque sous-arbre à un coeur de calcul. Une stratégie de recherche est un algorithme qui choisit pour chaque noeud dans l'arbre de recherche la variable à assigner et choisi également l'ordonnancement de la recherche. En PPC, il existe plusieurs stratégies de recherche, certaines sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmesde contraintes. Cependant la difficulté reste de choisir la bonne stratégie. Pour bénéficier de la variété des stratégies et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisationPortfolio consiste à exécuter en parallèle N stratégies de recherche, ensuite la première stratégie qui trouve une solution met fin à toutes les autres. La nouveauté que nous proposons dans la parallélisation Portfolio consiste à adapterl'ordonnancement des N stratégies entre elles afin de privilégier la stratégie la plus prometteuse. Cela en lui donnant plus de coeurs que les autres. Pour ceci nous appliquons soit une fonction d'estimation pour chaque stratégie afin de sélectionner la stratégie qui a le plus petit arbre de recherche, soit un algorithme d'apprentissage qui permet de prédire quelle est la meilleure stratégie suivant le résultat d'un apprentissage effectué sur des instances déjà résolues. Afin d'ordonnancer plusieurs applications de PPC, nous proposons également un nouveau système d'allocation de ressources basé sur une stratégie d'ordonnancement combinée avec un modèle économique. Les applications de PPC sont résolues avec des solveurs parallèles dans une infrastructure cloud computing. L'originalité du system d'allocation est qu'il détermine automatiquement le nombre de ressources à affecter pour chaque application suivant la classe économique du client. Les performances obtenues avec nos méthodes de parallélisation sont illustrées par la résolution des problèmes de contraintes en portant le solveur Google OR-Tools au-dessus de notre framework parallèle Bobpp / In the context of the PAJERO project, we propose in this thesis an external parallelization of a Constraint Programming (CP) solver, using both search and Portfolio parallelizations, in order to solve constraint satisfaction and optimization problems. In our work the search parallelization is adapted for deterministic and non-deterministic executions, according to the needs of the user. The principle is to partition the unique search tree generated by one search strategy into a set of sub-trees, then assign each sub-tree to one computing core. A search strategy herein means an algorithm to decide which variable is selected to be assigned in each node of the search tree, and decide also the scheduling of the search. In CP, several search strategies exist and each one could be better than others for solving a specific problem. The difficulty lies in how to choose the best strategy. To benefit from the variety of strategies and the availability of computationalresources, another parallelization exists called the Portfolio parallelization. The principle of this Portfolio parallelization is to execute N search strategies in parallel. The first strategy which find a solution stops the others. The noveltyof our work in the context of the Portfolio is to adapt the schedule of the N strategies in order to favour the most promising strategy, which is a candidate to find a solution first, by giving it more cores than others. The promising strategyis selected using two methods. The first method is to use an estimation function which select the strategy with the smallest search tree. The second method is to use a learning algorithm which automatically determines the number of cores thatwill be allocated to each strategy according to the previous experiment. We have also proposed a new resource allocation system based on a scheduling strategy used with an economic model in order to execute several PPC applications. Thisapplications are solved using parallel solvers in the cloud computing infrastructure. The originality of this system is that the number of resources allocated to each PPC application is determined automatically according the economic classesof the users. The performances obtained by our parallelization methods are illustrated by solving the CP problems using the Google OR-Tools solver on top of the parallel Bobpp framework.

Cette thèse étudie le processus de spéciation entre la lamproie fluviatile (Lampetra fluviatilis) et la lamproie de Planer (L. planeri). Les deux espèces présentent des stratégies d'histoire de vie extrêmement différentes : L. fluviatilis est parasite et anadrome alors que L. planeri n'est pas parasite et reste strictement dulcicole. Toutefois, leur degré d'isolement reproducteur et leur histoire de divergence demeurent méconnus. Ces questions ont été abordées par des approches expérimentales, de génomique de populations et de simulations démographiques. Des croisements expérimentaux ont révélé un faible isolement reproducteur, confirmé par des degrés variables de flux géniques dans les populations naturelles. Les analyses génétiques ont montré que les deux taxons représentaient probablement des écotypes avec un isolement reproducteur partiel suggérant que les barrières reproductives endogènes ne réduisaient que partiellement la migration efficace entre écotypes. L'importance du contexte géographique actuel et passé dans l'étude de la spéciation a aussi été mise en évidence par des analyses à l'échelle du génome. Ainsi, les populations isolées de L. planeri évoluent principalement sous l'effet de la dérive génétique et ont une diversité réduite. Les inférences démographiques ont suggéré que la divergence a été initiée en allopatrie puis suivie de contacts secondaires résultant en un parallélisme génomique partiel entre réplicas de paires de populations. Une hétérogénéité de la divergence génomique a démontré que les ilots génomiques de différenciation ne résultaient pas de l'action récente de la divergence écologique. En outre, nos résultats suggèrent un impact faible de la fragmentation anthropique des cours d'eau sur la diversité génétique des populations de L. planeri. Les populations résidentes possèdent une diversité génétique plus grande lorsque le flux de gènes avec L. fluviatilis dans les parties aval des cours d'eau. Globalement cette thèse a démontré que les paires d'écotypes parasites et non-parasites de lamproies représentent un excellent modèle d'étude de la spéciation et notamment de l'architecture génomique de la divergence. / This thesis investigates the process of speciation between the European lampreys Lampetra fluviatilis and L. planeri. The two species have drastically different life history strategies: L. fluviatilis is parasitic and anadromous while L. planeri is non-parasitic and strictly freshwater resident. Yet their level of reproductive isolation and history of divergence remain poorly understood. A multidisciplinary approach including experiments, population genomics analyses and historical reconstruction was undertaken to address these issues. Experimental crosses revealed a very low level of reproductive isolation, partially mirrored by variable levels of gene flow in wild populations. Genetic analyses revealed that the two taxa were best described as partially reproductively isolated ecotypes suggesting that endogenous genetic barriers partially reduced effective migration between ecotypes. Genome wide analyses showed the importance of the current and ancient geographical context of speciation. In particular, parapatric L. planeri populations diverged mostly through drift and displayed a reduced genetic diversity . Demographic inferences suggested that divergence have likely emerged in allopatry and then secondary contacts resulted in partial parallelism between replicate population pairs. A strong heterogeneity of divergence across the genome was revealed by sympatric populations suggesting that genomic islands of differentiation were not linked to ongoing ecological divergence. Further investigations showed that the genetic diversity of L. planeri populations was weakly affected by human-induced river fragmentation. Resident populations displayed a higher diversity when gene flow was possible with L. fluviatilis populations in downstream sections of rivers. Overall this thesis showed that parasitic and non-parasitic lamprey ecotypes represent a promising model for studying speciation and notably the genomic architecture of divergence.