Dans cette thèse, nous présentons notre travail de recherche dans le domaine du calcul haute performance en mécanique des fluides (CFD) pour architectures de type cluster et cloud. De manière générale, nous nous proposons de développer un solveur efficace, appelé ADAPT, pour la résolution de problèmes de CFD selon une vue classique correspondant à des développements en MPI et selon une vue qui nous amène à représenter ADAPT comme un graphe de tâches destinées à être ordonnancées sur une plateforme de type cloud computing. Comme première contribution, nous proposons une parallélisation de l’équation de diffusion-convection couplée àun système linéaire en 2D et en 3D à l’aide de MPI. Une parallélisation à deux niveaux est utilisée dans notre implémentation pour exploiter au mieux les capacités des machines multi-coeurs. Nous obtenons une distribution équilibrée de la charge de calcul en utilisant la décomposition du domaine à l’aide de METIS, ainsi qu’une résolution pertinente de notre système linéaire creux de très grande taille en utilisant le solveur parallèle MUMPS (Solveur MUltifrontal Massivement Parallèle). Notre deuxième contribution illustre comment imaginer la plateforme ADAPT, telle que représentée dans la premièrecontribution, comme un service. Nous transformons le framework ADAPT (en fait, une partie du framework)en DAG (Direct Acyclic Graph) pour le voir comme un workflow scientifique. Ensuite, nous introduisons de nouvelles politiques à l’intérieur du moteur de workflow RedisDG, afin de planifier les tâches du DAG, de manière opportuniste.Nous introduisons dans RedisDG la possibilité de travailler avec des machines dynamiques (elles peuvent quitter ou entrer dans le système de calcul comme elles veulent) et une approche multi-critères pour décider de la “meilleure”machine à choisir afin d’exécuter une tâche. Des expériences sont menées sur le workflow ADAPT pour illustrer l’efficacité de l’ordonnancement et des décisions d’ordonnancement dans le nouveau RedisDG. / In this thesis, we present our research work in the field of high performance computing in fluid mechanics (CFD) for cluster and cloud architectures. In general, we propose to develop an efficient solver, called ADAPT, for problemsolving of CFDs in a classic view corresponding to developments in MPI and in a view that leads us to represent ADAPT as a graph of tasks intended to be ordered on a cloud computing platform. As a first contribution, we propose a parallelization of the diffusion-convection equation coupled to a linear systemin 2D and 3D using MPI. A two-level parallelization is used in our a implementation to take advantage of thecurrent distributed multicore machines. A balanced distribution of the computational load is obtained by using the decomposition of the domain using METIS, as well as a relevant resolution of our very large linear system using the parallel solver MUMPS (Massive Parallel MUltifrontal Solver). Our second contribution illustrates how to imagine the ADAPT framework, as depicted in the first contribution, as a Service. We transform the framework (in fact, a part of the framework) as a DAG (Direct Acyclic Graph) in order to see it as a scientific workflow. Then we introduce new policies inside the RedisDG workflow engine, in order to schedule tasks of the DAG, in an opportunistic manner. We introduce into RedisDG the possibility to work with dynamic workers (they can leave or enter into the computing system as they want) and a multi-criteria approach to decide on the “best” worker to choose to execute a task. Experiments are conducted on the ADAPT workflow to exemplify howfine is the scheduling and the scheduling decisions into the new RedisDG.

Pas de résumé / Pas de résumé

Les systèmes polynomiaux sous forme triangulaire, notamment les chaînes régulières et en particulier les ensembles triangulaires (de Lazard), sont des structures de données simples, permettant d'envisager des calculs modulaires (par spécialisation des coefficients, puis remontée via un opérateur de Newton-Hensel), de "résoudre'' les systèmes de polynômes (méthodes de "triangulations'') et de représenter des tours d'extensions de corps pour calculer avec les nombres algébriques. Dans ces trois domaines, les méthodes et résultats nouveaux apportés, notamment sur le plan de la complexité, étendent le champs d'application des ensembles triangulaires, et leur impact face à d'autres méthodes de manipulation des équations polynomiales, surtout les bases de Gröbner. Tout d'abord la complexité en espace des coefficients n'est qu'en croissance quadratique en fonction de données géometriques naturelles. Conséquence directe en est un opérateur de Newton (triangulaire) requérant moins d'étapes de remontée, et donc des méthodes modulaires plus encourageantes. Il en est ainsi pour la décomposition équiprojetable, premier algorithme de triangulation des systèmes basé sur une méthode modulaire, et pour le problème du changement d'ordres monomiaux en dimension positive, dans des cas assez particuliers toutefois pour une première approche. Par ailleurs, calculer modulo un ensemble triangulaire en suivant le modèle de l'évaluation dynamique, se voit doté, 20 ans après sa création, d'un premier résultat de complexité satisfaisant.

Dans ce travail de thèse une étude théorique et pratique du résultant résiduel est proposée. Ce résultant résiduel fournit une condition nécessaire et suffisante pour qu'un système algébrique possède des solutions sur une variété résiduelle obtenue par éclatement. Des méthodes effectives pour calculer ce résultant résiduel ainsi que son degré sont proposées, les résultats les plus précis étant obtenus lorsque le lieu que l'on éclate est une intersection complète ou encore une intersection complète locale projective Cohen-Macaulay de codimension deux. Un algorithme pour résoudre le problème d'implicitisation dans le cas ou la paramétrisation possède des points base localement intersection complète est explicité à l'aide du résultant résiduel. On montre également comment ce résultant résiduel permet d'obtenir la forme de Chow des points isolés d'un système algébrique. Enfin le dernier chapitre de cette thèse présente une définition et une première étude du résultant déterminantal qui donne une condition nécessaire et suffisante pour qu'une matrice générique soit de rang inférieur ou égal à un entier positif donné.

Le calcul numérique du champ électrique ou magnétique intervient aussi bien dans la mise au point d'outils de communication performants que dans les problèmes de compatibilité électromagnétique des systèmes électriques ou de modélisation de l'interaction champ-vivant. Ce calcul est fréquemment fondé sur la discrétisation des équations de Maxwell par la méthode des éléments finis d'arête. Il conduit alors à la résolution d'un système linéaire creux mais généralement de grande taille.<br /><br />L'objectif de ce travail est de proposer une méthode multiniveau algébrique pour la résolution des systèmes linéaires issus d'une discrétisation par la méthode des éléments finis d'arête. En effet, les méthodes itératives multiniveau construisent des algorithmes qui s'avèrent être les plus performants pour certaines classes l'équations aux dérivées partielles. Ces méthodes s'appuient, dans leur version géométrique, sur une hiérarchie de maillages emboîtés. Cependant pour des applications réalistes cette hiérarchie ne peut pas toujours être construite et il faut définir algébriquement les différents niveaux.<br /><br />La stratégie algébrique de définition des niveaux grossiers que nous proposons repose sur la construction de fonctions grossières nodales et d'arête vérifiant une contrainte de compatibilité. En outre, les fonctions grossières d'arête doivent minimiser une fonctionnelle d'énergie. Ce problème de minimisation avec contrainte est résolu par deux techniques : l'une utilise les multiplicateurs de Lagrange, l'autre s'appuie sur la résolution d'une suite de problèmes de flot dans un graphe. Des expériences numériques illustrent les performances de différentes versions de notre méthode.

Cette thèse est en majeure partie dédiée au calcul rapide de remontée p-adique par des algorithmes détendus. Dans une première partie, nous présentons le cadre général des algorithmes détendus et de leur application au calcul de p-adiques récursifs. Pour appliquer ce cadre à la remontée p-adique de divers systèmes d'équations, il reste à transformer ces équations implicites en équations récursives. Ainsi, la seconde partie traite des systèmes d'équations linéaires, éventuellement différentiels. La remontée de résolutions de systèmes polynomiaux se trouve en troisième partie. Dans tous les cas, les nouveaux algorithmes détendus sont comparés, en théorie comme en pratique, aux algorithmes existants. En quatrième partie, nous étudions l'algèbre de décomposition universelle d'un polynôme. Nous développons un algorithme rapide pour calculer une représentation adéquate de cette algèbre et l'utilisons pour manipuler efficacement les éléments de l'algèbre. Finalement, nous montrons en annexe que la recherche d'invariants fondamentaux d'algèbres d'invariants sous un groupe fini peut se faire directement modulo p, facilitant ainsi leur calcul.

Ce travail est divisé en deux axes de recherches. Le premier axe concerne l'étude de quelques systèmes d'équations aux dérivées partielles non linéaires issus de la modélisation macroscopique des composants semi-conducteurs. Le deuxième axe de recherche est consacré à l'étude de quelques problèmes d'identification. Nous nous intéressons en particulier à deux types de problèmes d'identification. Le premier concerne la reconstruction des données sur le bord pour des problèmes elliptiques. Le deuxième type de problèmes auquel nous nous sommes intéressés est celui de l'identification des frontières dans des problèmes gouvernés par des équations elliptiques.

Un problème fondamental en géométrie algorithmique est celui du calcul de la topologie d'une courbe plane donnée par son équation implicite. Ce problème peut être vu comme celui du calcul d'un graphe qui approche la courbe et qui possède la même topologie que cette dernière. Une étape importante dans les algorithmes calculant la topologie d'une courbe plane concerne le calcul des points singuliers et points extrêmes (en x) de celle-ci. Ce problème se ramène naturellement à celui de la résolution de systèmes bivariés définis par la courbe et ses dérivées par rapport aux variables qui la définissent. Cette thèse porte sur l'étude, l'élaboration et l'implantation d'algorithmes robustes et efficaces pour la résolution de systèmes définis par des polynômes en deux variables à coefficients entiers. Plus précisément, nous nous somme intéressé au calcul d'une Représentation Univariée Rationnelle des solutions. Une telle représentation est constitué d'un polynôme univarié et de deux fonctions rationnelles qui envois les racines du polynôme univarié sur les coordonnées des points solutions du système. Nous présentons dans un premier temps un algorithme théorique pour calculer la RUR d'un système bivarié qui améliore la meilleure borne de complexité connue d'un facteur d^2, ou d désigne le degré des polynômes de départ, et qui permet d'obtenir une nouvelle borne sur la taille des polynômes de cette RUR. Dans un second temps, nous présentons un algorithme de calcul de RUR efficace en pratique. Cet algorithme, basé sur des choix aléatoires et sur l'utilisation du calcul multi-modulaire est probabiliste. Nous en présentons une première version Monte-Carlo, puis nous montrons comment tester la correction du résultat ce qui fourni un algorithme Las-Vegas. Cet algorithme est efficace à la fois en théorie et en pratique à en juger par l'analyse de complexité en moyenne et les nombreux testes effectués.

L’évolution courante des machines montre une croissance importante dans le nombre et l’hétérogénéité des unités de calcul. Les développeurs doivent alors trouver des alternatives aux modèles de programmation habituels permettant de produire des codes de calcul à la fois performants et portables. PaStiX est un solveur parallèle de système linéaire creux par méthodes directe. Il utilise un ordonnanceur de tâche dynamique pour être efficaces sur les machines modernes multi-coeurs à mémoires hiérarchiques. Dans cette thèse, nous étudions les bénéfices et les limites que peut nous apporter le remplacement de l’ordonnanceur interne, très spécialisé, du solveur PaStiX par deux systèmes d’exécution génériques : PaRSEC et StarPU. Pour cela l’algorithme doit être décrit sous la forme d’un graphe de tâches qui est fournit aux systèmes d’exécution qui peuvent alors calculer une exécution optimisée de celui-ci pour maximiser l’efficacité de l’algorithme sur la machine de calcul visée. Une étude comparativedes performances de PaStiX utilisant ordonnanceur interne, PaRSEC, et StarPU a été menée sur différentes machines et est présentée ici. L’analyse met en évidence les performances comparables des versions utilisant les systèmes d’exécution par rapport à l’ordonnanceur embarqué optimisé pour PaStiX. De plus ces implémentations permettent d’obtenir une accélération notable sur les machines hétérogènes en utilisant lesaccélérateurs tout en masquant la complexité de leur utilisation au développeur. Dans cette thèse nous étudions également la possibilité d’obtenir un solveur distribué de système linéaire creux par méthodes directes efficace sur les machines parallèles hétérogènes en utilisant les systèmes d’exécution à base de tâche. Afin de pouvoir utiliser ces travaux de manière efficace dans des codes parallèles de simulations, nous présentons également une interface distribuée, orientée éléments finis, permettant d’obtenir un assemblage optimisé de la matrice distribuée tout en masquant la complexité liée à la distribution des données à l’utilisateur. / The ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of computing resources. The pressure to maintain reasonable levels of performance and portability forces application developers to leave the traditional programming paradigms and explore alternative solutions. PaStiX is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical manycore architectures. In this thesis, we study the benefits and the limits of replacing the highly specialized internal scheduler of the PaStiX solver by two generic runtime systems: PaRSEC and StarPU. Thus, we have to describe the factorization algorithm as a tasks graph that we provide to the runtime system. Then it can decide how to process and optimize the graph traversal in order to maximize the algorithm efficiency for thetargeted hardware platform. A comparative study of the performance of the PaStiX solver on top of its original internal scheduler, PaRSEC, and StarPU frameworks is performed. The analysis highlights that these generic task-based runtimes achieve comparable results to the application-optimized embedded scheduler on homogeneous platforms. Furthermore, they are able to significantly speed up the solver on heterogeneous environments by taking advantage of the accelerators while hiding the complexity of their efficient manipulation from the programmer. In this thesis, we also study the possibilities to build a distributed sparse linear solver on top of task-based runtime systems to target heterogeneous clusters. To permit an efficient and easy usage of these developments in parallel simulations, we also present an optimized distributed interfaceaiming at hiding the complexity of the construction of a distributed matrix to the user.

Nous nous intéressons à la résolution en parallèle de système d’équations linéaires creux et de large taille. Le calcul de la solution d’un tel type de système requiert un grand espace mémoire et une grande puissance de calcul. Il existe deux principales méthodes de résolution de systèmes linéaires. Soit la méthode est directe et de ce fait est rapide et précise, mais consomme beaucoup de mémoire. Soit elle est itérative, économe en mémoire, mais assez lente à atteindre une solution de qualité suffisante. Notre travail consiste à combiner ces deux techniques pour créer un solveur hybride efficient en consommation mémoire tout en étant rapide et robuste. Nous essayons ensuite d’améliorer ce solveur en introduisant une nouvelle méthode pseudo directe qui contourne certains inconvénients de la méthode précédente. Dans les premiers chapitres nous examinons les méthodes de projections par lignes, en particulier la méthode Cimmino en bloc, certains de leurs aspects numériques et comment ils affectent la convergence. Ensuite, nous analyserons l’accélération de ces techniques avec la méthode des gradients conjugués et comment cette accélération peut être améliorée avec une version en bloc du gradient conjugué. Nous regarderons ensuite comment le partitionnement du système linéaire affecte lui aussi la convergence et comment nous pouvons améliorer sa qualité. Finalement, nous examinerons l’implantation en parallèle du solveur hybride, ses performances ainsi que les améliorations possible. Les deux derniers chapitres introduisent une amélioration à ce solveur hybride, en améliorant les propriétés numériques du système linéaire, de sorte à avoir une convergence en une seule itération et donc un solveur pseudo direct. Nous commençons par examiner les propriétés numériques du système résultants, analyser la solution parallèle et comment elle se comporte face au solveur hybride et face à un solveur direct. Finalement, nous introduisons de possible amélioration au solveur pseudo direct. Ce travail a permis d’implanter un solveur hybride "ABCD solver" (Augmented Block Cimmino Distributed solver) qui peut soit fonctionner en mode itératif ou en mode pseudo direct. / We are interested in solving large sparse systems of linear equations in parallel. Computing the solution of such systems requires a large amount of memory and computational power. The two main ways to obtain the solution are direct and iterative approaches. The former achieves this goal fast but with a large memory footprint while the latter is memory friendly but can be slow to converge. In this work we try first to combine both approaches to create a hybrid solver that can be memory efficient while being fast. Then we discuss a novel approach that creates a pseudo-direct solver that compensates for the drawback of the earlier approach. In the first chapters we take a look at row projection techniques, especially the block Cimmino method and examine some of their numerical aspects and how they affect the convergence. We then discuss the acceleration of convergence using conjugate gradients and show that a block version improves the convergence. Next, we see how partitioning the linear system affects the convergence and show how to improve its quality. We finish by discussing the parallel implementation of the hybrid solver, discussing its performance and seeing how it can be improved. The last two chapters focus on an improvement to this hybrid solver. We try to improve the numerical properties of the linear system so that we converge in a single iteration which results in a pseudo-direct solver. We first discuss the numerical properties of the new system, see how it works in parallel and see how it performs versus the iterative version and versus a direct solver. We finally consider some possible improvements to the solver. This work led to the implementation of a hybrid solver, our "ABCD solver" (Augmented Block Cimmino Distributed solver), that can either work in a fully iterative mode or in a pseudo-direct mode.