Les infrastructures de cloud fournissent une grande variété de ressources de calcul à la demande avec différents compromis coût-performance. Cela donne aux utilisateurs des nombreuses opportunités pour exécuter leurs applications ayant des besoins complexes en ressources, à partir d’un grand nombre de serveurs avec des interconnexions à faible latence jusqu’à des dispositifs spécialisés comme des GPUs et des FPGAs. Les besoins des utilisateurs concernant l’exécution de leurs applications peuvent varier entre une exécution la plus rapide possible, la plus chère ou un compromis entre les deux. Cependant, le choix du nombre et du type des ressources à utiliser pour obtenir le compromis coût-performance que les utilisateurs exigent constitue un défi majeur. Cette thèse propose trois contributions avec l’objectif de fournir des bons compromis coût-performance pour l’exécution des applications sur des plates-formes hétérogènes. Elles suivent deux directions : un bon usage des ressources et un bon choix des ressources. Nous proposons comme première contribution une méthode de partage pour des accélérateurs de type FPGA dans l’objectif de maximiser leur utilisation. Dans une seconde contribution, nous proposons des méthodes de profilage pour la modélisation de la demande en ressources des applications. Enfin, nous démontrons comment ces technologies peuvent être intégrées dans une plate-forme de cloud hétérogène. / Cloud infrastructures provide on-demand access to a large variety of computing devices with different performance and cost. This creates many opportunities for cloud users to run applications having complex resource requirements, starting from large numbers of servers with low-latency interconnects, to specialized devices such as GPUs and FPGAs. User expectations regarding the execution of applications may vary between the fastest possible execution, the cheapest execution or any trade-off between the two extremes. However, enabling cloud users to easily make performance-cost trade-offs is not a trivial exercise and choosing the right amount and type of resources to run applications accordingto user expectations is very difficult. This thesis proposes three contributions to enable performance-cost trade-offs for application execution in heterogeneous clouds by following two directions: make good use of resources and make good choice of resources. We propose as a first contribution a method to share FPGA-based accelerators in cloud infrastructures having the objective to improve their utilization. As a second contribution we propose profiling methods to automate the selection of heterogeneous resources for executing applications under user objectives. Finally, we demonstrate how these technologies can be implemented and exploited in heterogeneous cloud platforms.

Cette thèse porte sur la notion de certification locale, un sujet central en décision distribuée, un domaine du calcul distribué. Le mécanisme de la décision distribuée consiste, pour les nœuds d'un réseau, à décider de manière distribuée si le réseau est dans une configuration correcte ou non, selon un certain prédicat. Cette décision est dite locale, car les nœuds du réseau ne peuvent communiquer qu'avec leurs voisins. Après avoir communiqué, chaque nœud prend une décision, exprimant si le réseau est correct ou non localement, c'est-à-dire correct étant donné l'information partielle récoltée jusque-là. Le réseau est déclaré correct globalement s'il est déclaré correct localement par tous les nœuds.Du fait de la contrainte de localité, peu de prédicats peuvent être vérifiés de cette manière. La certification locale est un moyen de contourner cette difficulté, et permet de décider tous les prédicats. C'est un mécanisme qui consiste à étiqueter les nœuds du réseau avec ce que l'on appelle des certificats, qui peuvent être vérifiés localement par un algorithme distribué. Un schéma de certification locale est correct si seuls les réseaux dans une configuration correcte peuvent être certifiés. L'idée de la certification locale est non seulement séduisante d'un point de vue théorique, comme une forme de non-déterminisme distribué, mais c'est surtout un concept très utile pour l'étude des algorithmes tolérants aux pannes, où une étape-clé consiste à vérifier l'état du réseau en se basant sur des informations stockées par les nœuds.Cette thèse porte sur quatre aspects de la certification locale : la sensibilité aux erreurs, l'uniformité, la redondance et l'interactivité. L'étude de ces quatre sujets est motivée par une question essentielle : comment réduire les ressources nécessaires à la certification et/ou permettre une meilleure tolérance aux pannes? Pour aborder cette question, il est nécessaire de comprendre le mécanisme de certification en profondeur. Dans cette optique, dans cette thèse, nous apportons des réponses aux questions suivantes. À quel point les certificats doivent-ils être redondants, pour assurer une certification correcte? Les schémas de certification classiques sont-ils robustes à un changement de la condition de correction? Le fait d'introduire de l'interactivité dans le processus change-t-il la complexité de la certification? / This dissertation is about local certification, a central topic in distributed decision, a subfield of distributed computing. The distributed decision mechanism consists, for the nodes of a network, in deciding in a distributed manner whether the network is in a proper configuration or not, with respect to some fixed predicate. This decision is said to be local because the nodes of the network can communicate only with their neighbours. After communication, every node outputs a decision, stating whether the network is locally correct, that is, correct given the partial information gathered so far by this node. The network is declared to be globally correct, if and only if, it is declared to be locally correct by every node.Most predicates cannot be verified by this type of computation, due to the locality constraint. Local certification is a mechanism that enables to circumvent this difficulty, and to check any property. It consists in providing the nodes of the network with labels, called certificates, that can be verified locally by a distributed algorithm. A local certification scheme is correct if only the networks that satisfy the predicate can be certified. In addition to its theoretical appeal, as a form of distributed non-determinism, the concept of local certification is especially relevant in the study of fault-tolerant distributed algorithms, where a key step consists in checking the status of the network, based on information stored at the nodes.This dissertation deals with four aspects of local certification: error-sensitivity, uniformity, redundancy, and interactivity. The study of these four topics is motivated by the same essential question: How to reduce the resources needed for certification, and/or ensure a better fault-tolerance? In order to tackle this question we have to understand fundamental properties of certification. In particular, in this dissertation we answer questions such as: How redundant the certificates need to be for a proper certification? Are the classic certification protocols robust to a strengthening of the acceptance condition? and, How does introducing interactivity in the process changes the complexity of certification?

Une large classe de méthodes numériques possède une propriété d’échelonnabilité connue comme étant la loi d’Amdahl. Elle constitue l’inconvénient majeur limitatif du calcul parallèle, en ce sens qu’elle établit une borne supérieure sur le nombre d’unités de traitement parallèles qui peuvent être utilisées pour accélérer un calcul. Des activités de recherche sont donc largement conduites à la fois sur les plans mathématiques et informatiques, pour repousser cette limite afin d’être en mesure de tirer le maximum des machines parallèles. Les méthodes de décomposition de domaine introduisent une approche naturelle et optimale pour résoudre de larges problèmes numériques de façon distribuée. Elles consistent en la division du domaine géométrique sur lequel une équation est définie, puis le traitement itératif de chaque sous-domaine, séparément, tout en assurant la continuité de la solution et de sa dérivée sur leur interface de jointure. Dans le présent travail, nous étudions la suppression de la limite d’accélération en appliquant des itérations asynchrones dans différents cadres de décomposition, à la fois de domaines spatiaux et temporels. Nous couvrons plusieurs aspects du développement d’algorithmes asynchrones, de l’analyse théorique de convergence à la mise en oeuvre effective. Nous aboutissons ainsi à des méthodes asynchrones efficaces pour la décomposition de domaine, ainsi qu’à une nouvelle bibliothèque de communication pour l’expérimentation asynchrone rapide d’applications scientifiques existantes. / An important class of numerical methods features a scalability property well known as the Amdahl’s law, which constitutes the main limiting drawback of parallel computing, as it establishes an upper bound on the number of parallel processing units that can be used to speed a computation up. Extensive research activities are therefore conducted on both mathematical and computer science aspects to increase this bound, in order to be able to squeeze the most out of parallel machines. Domain decomposition methods introduce a natural and optimal approach to solve large numerical problems in a distributed way. They consist in dividing the geometrical domain on which an equation is defined, then iteratively processing each sub-domain separately, while ensuring the continuity of the solution and of its derivative across the junction interface between them. In the present work, we investigate the removal of the scalability bound by the application of the asynchronous iterations theory in various decomposition frameworks, both for space and time domains. We cover various aspects of the development of asynchronous iterative algorithms, from theoretical convergence analysis to effective parallel implementation. Efficient asynchronous domain decomposition methods are thus successfully designed, as well as a new communication library for the quick asynchronous experimentation of existing scientific applications.

Le système de simulation et d'avis précoce d'alerte est un outil puissant pour la surveillance de la qualité de l'eau de la rivière Mudan, une rivière importante dans les régions froides du nord-est de la Chine et qui se jette finalement dans la rivière de l'Amour en Russie. Ainsi la qualité de l'eau dans la rivière Mudan est une préoccupation importante non seulement au niveau local et régional,mais aussi au niveau international. L'objectif de cette étude est de créer un système de simulation et d'avis précoce d'alerte pour que la distribution spatio-temporelle de la qualité de l'eau durant les périodes de couverture glaciaire et d'eaux libres soit simulée et visualisée précisément et afin que l'on puisse appréhender la variation spatiale de polluants sur le cours de rivière. La thèse est structurée en 7 chapitres. Dans le premier chapitre nous décrivons le contexte de l'étude et faisons un état de lieu des recherches actuelles. Dans le chapitre Il, la comparaison des modèles principaux disponibles pour l'évaluation de la qualité de l'eau est réaliser ainsi que le choix du meilleur modèle comme base pour créer le système de modélisation. Dans le chapitre Ill, la construction du modèle,les conditions limites requises et les paramètres pour le modèle ont été vérifiés et étalonnés. Une procédure de simulation distribuée est conçue dans le chapitre IV pour améliorer l'efficacité de la simulation. Le chapitre V concerne la programmation et la réalisation la de simulation distribuée et le chapitre VI les techniques fondamentales pour mettre en œuvre le système. Le chapitre VII est la conclusion. Il y a trois points innovants dans ce travail: un modèle bidimensionnel de dynamique de fluides de l'environnement pour la rivière Mudan, une méthode efficace du calcul distribué et un prototype de système de simulation et d'avis précoce d'alerte qui peuvent largement améliorer la capacité de surveillance et de gestion de la qualité de l'eau de la rivière Mudan ou d'autres rivières similaires. / Simulation and Early Warning System (SEWS) is a powerful tool for river water quality monitoring. Mudan River, an important river in northeastern cold regions of China, can run out of China into Russia. Thus, the water quality of Mudan River is highly concerned not only locally andregionally but also internationally. Objective of this study is to establish an excellent SEWS of water quality so that the spatio-temporal distribution of water quality in both open-water and ice-covered periods can be accurately simulated and visualized to understand the spatial variation of pollutants along the river course. The dissertation is structured into 7 chapters, chapter 1 outlines the background of the study and reviews the current progress. Chapter Il compares the main available models for evaluating river water quality so that a better model can be selected as the basis to establish a modeling system for Mudan River. Chapter Ill establishes the model, the required boundary conditions and parameters for the model were verified and calibrated. Chapter IV, a distributed simulation procedure was designed to increase the simulation efficiency. Chapter V discusses more about the programing and operational issues of the distributed simulation. Chapter VI is about the core techniques to implement the system. Chapter VII is the conclusion of the study to summarize the key points and innovations of the study. The study has the following three points as innovation : a two-dimensional environmental fluid dynamics model for Mudan River, an efficient distributed model computational method and a prototype of SEWS, which can greatly improve the capability of monitoring and management of water quality in Mudan River and other similar rivers.

Les performances des outils numériques de simulation électromagnétique de structures complexes, i.e., échelles multiples, sont souvent limitées par les ressources informatiques disponibles. De nombreux méso-centres, fermes et grilles de calcul, se créent actuellement sur les campus universitaires. Utilisant ces ressources informatiques mutualisées, ce travail de thèse s'attache à évaluer les potentialités du concept de grille de calcul (Grid Computing) pour la simulation électromagnétique de structures multi-échelles. Les outils numériques de simulation électromagnétique n'étant pas conçus pour être utilisés dans un environnement distribué, la première étape consistait donc à les modifier afin de les déployer sur une grille de calcul. Une analyse approfondie a ensuite été menée pour évaluer les performances des outils de simulation ainsi déployés sur l'infrastructure informatique. Des nouvelles approches pour le calcul électromagnétique distribué avec ces outils sont présentées et validées. En particulier, ces approches permettent la réalisation de simulation électromagnétique de structures à échelles multiples en un temps record et avec une souplesse d'utilisation.

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille par des méthodes directes de factorisation. Dans ce contexte, la taille de la matrice des facteurs constitue un des facteurs limitants principaux pour l'utilisation de méthodes directes de résolution. Nous supposons donc que la matrice des facteurs est de trop grande taille pour être rangée dans la mémoire principale du multiprocesseur et qu'elle a donc été écrite sur les disques locaux (hors-mémoire : OOC) d'une machine multiprocesseurs durant l'étape de factorisation. Nous nous intéressons à l'étude et au développement de techniques efficaces pour la phase de résolution après une factorization multifrontale creuse. La phase de résolution, souvent négligée dans les travaux sur les méthodes directes de résolution directe creuse, constitue alors un point critique de la performance de nombreuses applications scientifiques, souvent même plus critique que l'étape de factorisation. Cette thèse se compose de deux parties. Dans la première partie nous nous proposons des algorithmes pour améliorer la performance de la résolution hors-mémoire. Dans la deuxième partie nous pousuivons ce travail en montrant comment exploiter la nature creuse des seconds membres pour réduire le volume de données accédées en mémoire. Dans la première partie de cette thèse nous introduisons deux approches de lecture des données sur le disque dur. Nous montrons ensuite que dans un environnement parallèle le séquencement des tâches peut fortement influencer la performance. Nous prouvons qu'un ordonnancement contraint des tâches peut être introduit; qu'il n'introduit pas d'interblocage entre processus et qu'il permet d'améliorer les performances. Nous conduisons nos expériences sur des problèmes industriels de grande taille (plus de 8 Millions d'inconnues) et utilisons une version hors-mémoire d'un code multifrontal creux appelé MUMPS (solveur multifrontal parallèle). Dans la deuxième partie de ce travail nous nous intéressons au cas de seconds membres creux multiples. Ce problème apparaît dans des applications en electromagnétisme et en assimilation de données et résulte du besoin de calculer l'espace propre d'une matrice fortement déficiente, du calcul d'éléments de l'inverse de la matrice associée aux équations normales pour les moindres carrés linéaires ou encore du traitement de matrices fortement réductibles en programmation linéaire. Nous décrivons un algorithme efficace de réduction du volume d'Entrées/Sorties sur le disque lors d'une résolution hors-mémoire. Plus généralement nous montrons comment le caractère creux des seconds -membres peut être exploité pour réduire le nombre d'opérations et le nombre d'accès à la mémoire lors de l'étape de résolution. Le travail présenté dans cette thèse a été partiellement financé par le projet SOLSTICE de l'ANR (ANR-06-CIS6-010). / We consider the solution of very large systems of linear equations with direct multifrontal methods. In this context the size of the factors is an important limitation for the use of sparse direct solvers. We will thus assume that the factors have been written on the local disks of our target multiprocessor machine during parallel factorization. Our main focus is the study and the design of efficient approaches for the forward and backward substitution phases after a sparse multifrontal factorization. These phases involve sparse triangular solution and have often been neglected in previous works on sparse direct factorization. In many applications, however, the time for the solution can be the main bottleneck for the performance. This thesis consists of two parts. The focus of the first part is on optimizing the out-of-core performance of the solution phase. The focus of the second part is to further improve the performance by exploiting the sparsity of the right-hand side vectors. In the first part, we describe and compare two approaches to access data from the hard disk. We then show that in a parallel environment the task scheduling can strongly influence the performance. We prove that a constraint ordering of the tasks is possible; it does not introduce any deadlock and it improves the performance. Experiments on large real test problems (more than 8 million unknowns) using an out-of-core version of a sparse multifrontal code called MUMPS (MUltifrontal Massively Parallel Solver) are used to analyse the behaviour of our algorithms. In the second part, we are interested in applications with sparse multiple right-hand sides, particularly those with single nonzero entries. The motivating applications arise in electromagnetism and data assimilation. In such applications, we need either to compute the null space of a highly rank deficient matrix or to compute entries in the inverse of a matrix associated with the normal equations of linear least-squares problems. We cast both of these problems as linear systems with multiple right-hand side vectors, each containing a single nonzero entry. We describe, implement and comment on efficient algorithms to reduce the input-output cost during an outof- core execution. We show how the sparsity of the right-hand side can be exploited to limit both the number of operations and the amount of data accessed. The work presented in this thesis has been partially supported by SOLSTICE ANR project (ANR-06-CIS6-010).

Les performances des outils numériques de simulation électromagnétique de structures complexes, i.e., échelles multiples, sont souvent limitées par les ressources informatiques disponibles. De nombreux méso-centres, fermes et grilles de calcul, se créent actuellement sur les campus universitaires. Utilisant ces ressources informatiques mutualisées, ce travail de thèse s'attache à évaluer les potentialités du concept de grille de calcul (Grid Computing) pour la simulation électromagnétique de structures multi-échelles. Les outils numériques de simulation électromagnétique n'étant pas conçus pour être utilisés dans un environnement distribué, la première étape consistait donc à les modifier afin de les déployer sur une grille de calcul. Une analyse approfondie a ensuite été menée pour évaluer les performances des outils de simulation ainsi déployés sur l'infrastructure informatique. Des nouvelles approches pour le calcul électromagnétique distribué avec ces outils sont présentées et validées. En particulier, ces approches permettent la réalisation de simulation électromagnétique de structures à échelles multiples en un temps record et avec une souplesse d'utilisation. / The numerical electromagnetic tools for complex structures simulation, i.e. multi-scale, are often limited by available computation resources. Nowadays, Grid computing has emerged as an important new field, based on shared distributed computing resources of Universities and laboratories. Using these shared resources, this study is focusing on grid computing potential for electromagnetic simulation of multi-scale structure. Since the numerical simulations tools codes are not initially written for distributed environment, the first step consists to adapt and deploy them in Grid computing environment. A performance study is then realized in order to evaluate the efficiency of execution on the test-bed infrastructure. New approaches for distributing the electromagnetic computations on the grid are presented and validated. These approaches allow a very remarkable simulation time reduction for multi-scale structures and friendly-user interfaces

L'estimation de mouvement est une opération clé pour la compression vidéo, mais implique une complexité de calcul conséquente, accrue par le contexte de la haute définition et l'évolution des standards de compression vidéo. Jusqu'à 60% de la charge de calcul d'un encodeur vidéo H.264 est dédiée à cette opération. L'adéquation entre les algorithmes et les architectures multicomposants est étudiée dans ce nouveau contexte, avec un cadre méthodologique.<br />Un état de l'art des différentes méthodes d'estimation de mouvement et des architectures matérielles existantes est tout d'abord présenté. Les algorithmes de mise en correspondance de blocs HME et EPZS apparaissent comme les plus performants pour notre étude. La méthode de développement utilisée, ainsi que l'implantation et l'optimisation d'estimateurs de mouvement sur DSP sont ensuite présentés. Un nouvel algorithme d'estimation de mouvement est conçu : HDS. Des implantations parallèles sur plates-formes hétérogènes sont enfin proposées.