Cloud computing systems, like MapReduce and Pregel, provide a scalable and fault tolerant environment for running computations at massive scale. However, these systems are designed primarily for data intensive computational tasks, while a large class of problems in scientific computing and business analytics are computationally intensive (i.e., they require a lot of CPU in addition to I/O). In this thesis, we investigate the use of cloud computing systems, in particular MapReduce, for computationally intensive problems, focusing on two classic problems that arise in scienti c computing and also in analytics: maximum clique and matrix inversion. The key contribution that enables us to e ectively use MapReduce to solve the maximum clique problem on dense graphs is a recursive partitioning method that partitions the graph into several subgraphs of similar size and running time complexity. After partitioning, the maximum cliques of the di erent partitions can be computed independently, and the computation is sped up using a branch and bound method. Our experiments show that our approach leads to good scalability, which is unachievable by other partitioning methods since they result in partitions of di erent sizes and hence lead to load imbalance. Our method is more scalable than an MPI algorithm, and is simpler and more fault tolerant. For the matrix inversion problem, we show that a recursive block LU decomposition allows us to e ectively compute in parallel both the lower triangular (L) and upper triangular (U) matrices using MapReduce. After computing the L and U matrices, their inverses are computed using MapReduce. The inverse of the original matrix, which is the product of the inverses of the L and U matrices, is also obtained using MapReduce. Our technique is the rst matrix inversion technique that uses MapReduce. We show experimentally that our technique has good scalability, and it is simpler and more fault tolerant than MPI implementations such as ScaLAPACK.

This thesis develops methods to identify periodic solutions to the n-body problem by representing gravitational orbits with Fourier series. To find periodic orbits, a minimization function was developed that compares the second derivative of the Fourier series with Newtonian gravitation acceleration and modifies the Fourier coefficients until the orbits match. Software was developed to minimize the function and identify the orbits using gradient descent and quadratic curves. A Newtonian gravitational simulator was developed to read the initial orbit data and numerically simulate the orbits with accurate motion integration, allowing for comparison to the Fourier series orbits and investigation of their stability. The orbits found with the programs correlate with orbits from literature, and a number remain stable when simulated. / February 2016

Le calcul scientifique sur processeurs graphiques (GPU) est en plein essor depuis un certain temps, en particulier dans le domaine de l'apprentissage machine. Cette thèse présente les efforts pour établir une structure de données de table au multidimensionnel de manière efficace sur GPU. Nous commençons par faire une revue de ce qui est actuellement similaire dans le domaine et des désavantages d'avoir une multitude d'approches. Nous nous intéresserons particulièrement aux calculs fait à partir du langage Python. Nous décrirons des techniques intéressantes telles que la réduction d'ordre et le calcul asynchrone automatique. Pour terminer nous présenterons l'utilisation du module développé dans le cadre de cette thèse. / Scientific computing on GPU (graphical processing units) is on the rise, specifically in machine learning. This thesis presents the implementation of an efficient multidimensional array on the GPU. We will begin by a review of what currently implements similar functionality and the disadvantage of a fragmented approach. We will focus on packages that have a Python interface. We will explain techniques to optimize execution such as order reduction and automatic asynchronous computations. Finally, we will present the functionality of the module developed for this thesis. / Le code source de la libraire développée accompagne ce dépôt dans l'état où il était à ce moment. Il est possible de trouver une version plus à jour sur github (http://github.com/abergeron).

Cloud computing systems, like MapReduce and Pregel, provide a scalable and fault tolerant environment for running computations at massive scale. However, these systems are designed primarily for data intensive computational tasks, while a large class of problems in scientific computing and business analytics are computationally intensive (i.e., they require a lot of CPU in addition to I/O). In this thesis, we investigate the use of cloud computing systems, in particular MapReduce, for computationally intensive problems, focusing on two classic problems that arise in scienti c computing and also in analytics: maximum clique and matrix inversion. The key contribution that enables us to e ectively use MapReduce to solve the maximum clique problem on dense graphs is a recursive partitioning method that partitions the graph into several subgraphs of similar size and running time complexity. After partitioning, the maximum cliques of the di erent partitions can be computed independently, and the computation is sped up using a branch and bound method. Our experiments show that our approach leads to good scalability, which is unachievable by other partitioning methods since they result in partitions of di erent sizes and hence lead to load imbalance. Our method is more scalable than an MPI algorithm, and is simpler and more fault tolerant. For the matrix inversion problem, we show that a recursive block LU decomposition allows us to e ectively compute in parallel both the lower triangular (L) and upper triangular (U) matrices using MapReduce. After computing the L and U matrices, their inverses are computed using MapReduce. The inverse of the original matrix, which is the product of the inverses of the L and U matrices, is also obtained using MapReduce. Our technique is the rst matrix inversion technique that uses MapReduce. We show experimentally that our technique has good scalability, and it is simpler and more fault tolerant than MPI implementations such as ScaLAPACK.

In the context of software engineering for image processing (IP), we consider the notion of reusability of algorithms. In many software tools, an algorithm's implementation often depends on the type of processed data. In a broad definition, discrete digital images may have various forms : classical 2D images, 3D volumes, non-regular graphs, cell complexes, and so on : thus leading to a combinatorial explosion of the theoretical number of implementations. Generic programming (GP) is a framework suited to the development of reusable software tools. We present a programming paradigm based on GP designed for the creation of scientific software such as IP tools. This approach combines the benefits of reusability, expressive power, extensibility, and efficiency. We then propose a software architecture for IP using this programming paradigm based on a generic IP library. The foundations of this framework define essential IP concepts, enabling the development of algorithms compatible with many image types. We finally present a strategy to build high-level tools on top of this library, such as bridges to dynamic languages or graphical user interfaces. This mechanism has been designed to preserve the genericity and efficiency of the underlying software tools, while making them simpler to use and more flexible

Computer simulations are an indispensable tool for scientists to gain new insights about nature. Simulations of natural phenomena are usually large, and limited by the available computer resources. By using the computer resources more efficiently, larger and more detailed simulations can be performed, and more information can be extracted to help advance human knowledge. The topic of this thesis is how to make best use of modern computers for scientific computations. The challenge here is the high level of parallelism that is required to fully utilize the multicore processors in these systems. Starting from the basics, the primitives for synchronizing between threads are investigated. Hardware transactional memory is a new construct for this, which is evaluated for a new use of importance for scientific software: atomic updates of floating point values. The evaluation includes experiments on real hardware and comparisons against standard methods. Higher level programming models for shared memory parallelism are then considered. The state of the art for efficient use of multicore systems is dynamically scheduled task-based systems, where tasks can depend on data. In such systems, the software is divided up into many small tasks that are scheduled asynchronously according to their data dependencies. This enables a high level of parallelism, and avoids global barriers. A new system for managing task dependencies is developed in this thesis, based on data versioning. The system is implemented as a reusable software library, and shown to be as efficient or more efficient than other shared-memory task-based systems in experimental comparisons. The developed runtime system is then extended to distributed memory machines, and used for implementing a parallel version of a software for global climate simulations. By running the optimized and parallelized version on eight servers, an equally sized problem can be solved over 100 times faster than in the original sequential version. The parallel version also allowed significantly larger problems to be solved, previously unreachable due to memory constraints. / UPMARC / eSSENCE

A precise simulation requires a large amount of input data such as geometrical descriptions of the crystal structure, the external forces and loads, and quantitative properties of the material. Although some powerful applications already exist for research purposes, they are not widely used in education due to complex structure and unintuitive operation. To cater to the generic user base, a front-end application for material simulation software is introduced. With a graphic interface, it provides a more efficient way to conduct the simulation and to educate students who want to enlarge knowledge in relevant fields. We first discuss how we explore the solution for the front-end application and how to develop it on top of the material simulation software developed by mechanical engineering lab from Georgia Tech Lorraine. The user interface design, the functionality and the whole user experience are primary factors determining the product success or failure. This material simulation software helps researchers resolve the motion and the interactions of a large ensemble of dislocations for single or multi-layered 3D materials. However, the algorithm it utilizes is not well optimized and parallelized, so its performance of speedup cannot scale when using more CPUs in the cluster. This problem leads to the second topic on scientific computing, so in this thesis we offer different approaches that attempt to improve the parallelization and optimize the scalability.

Depuis plusieurs décennies, afin de réduire la consommation énergétique des processeurs, les constructeurs fabriquent des ordinateurs de plus en plus parallèles.Dans le même temps, l'écart de fréquence entre les processeurs et la mémoire a significativement augmenté.Pour compenser cet écart, les processeurs modernes embarquent une hiérarchie de caches complexe.Développer un programme efficace sur de telles machines est une tâche complexe.Par conséquent, l'analyse de performance est devenue une étape majeure lors du développement d'applications requérant des performances.La plupart des outils d'analyse de performances se concentrent sur le point de vue du processeur.Ces outils voient la mémoire comme une entité monolithique et sont donc incapable de comprendre comment elle est accédée.Cependant, la mémoire est une ressource critique et les schémas d'accès à cette dernière peuvent impacter les performances de manière significative.Quelques outils permettant l'analyse de performances mémoire existent, cependant ils sont basé sur un échantillon age à large grain.Par conséquent, ces outils se concentrent sur une petite partie de l’Exécution et manquent le comportement global de l'application.De plus, l'échantillonnage à large granularité ne permet pas de collecter des schémas d'accès.Dans cette thèse, nous proposons deux outils différences pour analyser le comportement mémoire d'une application.Le premier outil est conçu spécifiquement pour pour les machines NUMA (Not Uniform Memory Accesses) et fournit plusieurs visualisations du schéma global de partage de chaque structure de données entre les flux d’ExécutionLe deuxième outil collecte des traces mémoires a grain fin avec information temporelles.Nous proposons de visualiser ces traces soit à l'aide d'un outil générique de gestion de traces soit en utilisant une approche programmatique basé sur R.De plus nous évaluons ces deux outils en les comparant a des outils existant de trace mémoire en terme de performances, précision et de complétude. / Since a few decades, to reduce energy consumption, processor vendors builds more and more parallel computers.At the same time, the gap between processors and memory frequency increased significantly.To mitigate this gap, processors embed a complex hierarchical caches architectureWriting efficient code for such computers is a complex task.Therefore, performance analysis has became an important step of the development of applications seeking for performances.Most existing performance analysis tools focuses on the point of view of the processor.Theses tools see the main memory as a monolithic entity and thus are not able to understand how it is accessed.However, memory is a common bottleneck in High Performances Computing, and the pattern of memory accesses can impact significantly the performances.There are a few tools to analyze memory performances, however theses tools are based on a coarse grain sampling.Consequently, they focus on a small part of the execution missing the global memory behavior.Furthermore, these coarse grain sampling are not able to collect memory accesses patterns.In this thesis we propose two different tools to analyze the memory behavior of an application.The first tool is designed specifically for Not Uniform Memory Accesses machines and provides some visualizations of the global sharing pattern inside each data structure between the threads.The second one collects fine grain memory traces with temporal information.We can visualize theses traces either with a generic trace management framework or with a programmatic exploration using R.Furthermore we evaluate both of these tools, comparing them with state of the art memory analysis tools in terms of performances, precision and completeness.

Les modèles mathématiques ont pour but de décrire le comportement d'un système. Bien souvent, cette description est imparfaite, notamment en raison des incertitudes sur les paramètres qui définissent le modèle. Dans le contexte de la modélisation des fluides géophysiques, ces paramètres peuvent être par exemple la géométrie du domaine, l'état initial, le forçage par le vent, ou les coefficients de frottement ou de viscosité. L'objet de l'analyse de sensibilité est de mesurer l'impact de l'incertitude attachée à chaque paramètre d'entrée sur la solution du modèle, et, plus particulièrement, identifier les paramètres (ou groupes de paramètres) og sensibles fg. Parmi les différentes méthodes d'analyse de sensibilité, nous privilégierons la méthode reposant sur le calcul des indices de sensibilité de Sobol. Le calcul numérique de ces indices de Sobol nécessite l'obtention des solutions numériques du modèle pour un grand nombre d'instances des paramètres d'entrée. Cependant, dans de nombreux contextes, dont celui des modèles géophysiques, chaque lancement du modèle peut nécessiter un temps de calcul important, ce qui rend inenvisageable, ou tout au moins peu pratique, d'effectuer le nombre de lancements suffisant pour estimer les indices de Sobol avec la précision désirée. Ceci amène à remplacer le modèle initial par un emph{métamodèle} (aussi appelé emph{surface de réponse} ou emph{modèle de substitution}). Il s'agit d'un modèle approchant le modèle numérique de départ, qui nécessite un temps de calcul par lancement nettement diminué par rapport au modèle original. Cette thèse se centre sur l'utilisation d'un métamodèle dans le cadre du calcul des indices de Sobol, plus particulièrement sur la quantification de l'impact du remplacement du modèle par un métamodèle en terme d'erreur d'estimation des indices de Sobol. Nous nous intéressons également à une méthode de construction d'un métamodèle efficace et rigoureux pouvant être utilisé dans le contexte géophysique. / Mathematical models seldom represent perfectly the reality of studied systems, due to, for instance, uncertainties on the parameters that define the system. In the context of geophysical fluids modelling, these parameters can be, e.g., the domain geometry, the initial state, the wind stress, the friction or viscosity coefficients. Sensitivity analysis aims at measuring the impact of each input parameter uncertainty on the model solution and, more specifically, to identify the ``sensitive'' parameters (or groups of parameters). Amongst the sensitivity analysis methods, we will focus on the Sobol indices method. The numerical computation of these indices require numerical solutions of the model for a large number of parameters' instances. However, many models (such as typical geophysical fluid models) require a large amount of computational time just to perform one run. In these cases, it is impossible (or at least not practical) to perform the number of runs required to estimate Sobol indices with the required precision. This leads to the replacement of the initial model by a emph{metamodel} (also called emph{response surface} or emph{surrogate model}), which is a model that approximates the original model, while having a significantly smaller time per run, compared to the original model. This thesis focuses on the use of metamodel to compute Sobol indices. More specifically, our main topic is the quantification of the metamodeling impact, in terms of Sobol indices estimation error. We also consider a method of metamodeling which leads to an efficient and rigorous metamodel, which can be used in the geophysical context.

A computação em nuvem tem recebido um grande destaque, ao propor um novo e eficiente mecanismo para disponibilizar recursos computacionais. Dos investimentos cada vez maiores nessa plataforma, inclusive pela academia, surge a oportunidade de compartilhar estes recursos computacionais entre diferentes instituições. As grades computacionais são um mecanismo bem estabelecido para o compartilhamento de alguns tipos de recursos computacionais. Através do entendimento de como isso é feito nestas estruturas, esse trabalho avalia as soluções existentes e propõe um arquitetura alternativa que permite a criação das federações de nuvens computacionais. / Cloud computing is a new model to provide computing resources. The growing interest and investments on this platform creates an opportunity to share this resources across different institutions. The grid computing is the standard way of achieving this. Using grid as reference, this work survey current technologies and present an alternative design to allow the development of academic cloud computing federations.