Cette thèse se concentre sur la résolution de systèmes linéaires creux dans le contexte d’applications massivement parallèles. Ce type de problèmes s’exprime sous la forme AX=B, où A est une matrice creuse d’ordre n x n, i.e. qui possède un nombre d’entrées nulles suffisamment élevé pour pouvoir être exploité, et B et X sont respectivement la matrice de seconds membres et la matrice de solution de taille n x nrhs. Cette résolution par des méthodes dites directes est effectuée grâce à une étape de factorisation qui réduit A en deux matrices triangulaires inférieure et supérieure L et U, suivie de deux résolutions triangulaires pour calculer la solution.Nous nous intéressons à ces résolutions avec une attention particulière apportée à la première, LY=B. Dans beaucoup d’applications, B possède un grand nombre de colonnes (nrhs >> 1) transformant la phase de résolution en un goulot d’étranglement. Elle possède souvent aussi une structure creuse, donnant l’opportunité de réduire la complexité de cette étape.Cette étude aborde sous des angles complémentaires la résolution triangulaire de systèmes linéaires avec seconds membres multiples et creux. Nous étudions dans un premier temps la complexité asymptotique de cette étape dans différents contextes (2D, 3D, facteurs compressés ou non). Nous considérons ensuite l’exploitation de cette structure et présentons de nouvelles approches s’appuyant sur une modélisation du problème par des graphes qui permettent d’atteindre efficacement le nombre minimal d’opérations. Enfin, nous donnons une interprétation concrète de son exploitation sur une application d’électromagnétisme pour la géophysique. Nous adaptons aussi des algorithmes parallèles aux spécificités de la phase de résolution.Nous concluons en combinant l'ensemble des résultats précédents et en discutant des perspectives de ce travail. / We consider direct methods to solve sparse linear systems AX = B, where A is a sparse matrix of size n x n with a symmetric structure and X and B are respectively the solution and right-hand side matrices of size n x nrhs. A is usually factorized and decomposed in the form LU, where L and U are respectively a lower and an upper triangular matrix. Then, the solve phase is applied through two triangular resolutions, named respectively the forward and backward substitutions.For some applications, the very large number of right-hand sides (RHS) in B, nrhs >> 1, makes the solve phase the computational bottleneck. However, B is often sparse and its structure exhibits specific characteristics that may be efficiently exploited to reduce this cost. We propose in this thesis to study the impact of the exploitation of this structural sparsity during the solve phase going through its theoretical aspects down to its actual implications on real-life applications.First, we investigate the asymptotic complexity, in the big-O sense, of the forward substitution when exploiting the RHS sparsity in order to assess its efficiency when increasing the problem size. In particular, we study on 2D and 3D regular problems the asymptotic complexity both for traditional full-rank unstructured solvers and for the case when low-rank approximation is exploited. Next, we extend state-of-the-art algorithms on the exploitation of RHS sparsity, and also propose an original approach converging toward the optimal number of operations while preserving performance. Finally, we show the impact of the exploitation of sparsity in a real-life electromagnetism application in geophysics that requires the solution of sparse systems of linear equations with a large number of sparse right-hand sides. We also adapt the parallel algorithms that were designed for the factorization to solve-oriented algorithms.We validate and combine the previous improvements using the parallel solver MUMPS, conclude on the contributions of this thesis and give some perspectives.

La méthode des éléments frontières pour l’équation des ondes (BEM) est utilisée en acoustique eten électromagnétisme pour simuler la propagation d’une onde avec une discrétisation en temps(TD). Elle permet d’obtenir un résultat pour plusieurs fréquences à partir d’une seule résolution.Dans cette thèse, nous nous intéressons à l’implémentation efficace d’un simulateur TD-BEM sousdifférents angles. Nous décrivons le contexte de notre étude et la formulation utilisée qui s’exprimesous la forme d’un système linéaire composé de plusieurs matrices d’interactions/convolutions.Ce système est naturellement calculé en utilisant l’opérateur matrice/vecteur creux (SpMV). Nousavons travaillé sur la limite du SpMV en étudiant la permutation des matrices et le comportementde notre implémentation aidé par la vectorisation sur CPU et avec une approche par bloc surGPU. Nous montrons que cet opérateur n’est pas approprié pour notre problème et nous proposonsde changer l’ordre de calcul afin d’obtenir une matrice avec une structure particulière.Cette nouvelle structure est appelée une matrice tranche et se calcule à l’aide d’un opérateur spécifique.Nous décrivons des implémentations optimisées sur architectures modernes du calculhaute-performance. Le simulateur résultant est parallélisé avec une approche hybride (mémoirespartagées/distribuées) sur des noeuds hétérogènes, et se base sur une nouvelle heuristique pouréquilibrer le travail entre les processeurs. Cette approche matricielle a une complexité quadratiquesi bien que nous avons étudié son accélération par la méthode des multipoles rapides (FMM). Nousavons tout d’abord travaillé sur la parallélisation de l’algorithme de la FMM en utilisant différentsparadigmes et nous montrons comment les moteurs d’exécution sont adaptés pour relâcher le potentielde la FMM. Enfin, nous présentons des résultats préliminaires d’un simulateur TD-BEMaccéléré par FMM . / The time-domain BEM for the wave equation in acoustics and electromagnetism is used to simulatethe propagation of a wave with a discretization in time. It allows to obtain several frequencydomainresults with one solve. In this thesis, we investigate the implementation of an efficientTD-BEM solver using different approaches. We describe the context of our study and the TD-BEMformulation expressed as a sparse linear system composed of multiple interaction/convolutionmatrices. This system is naturally computed using the sparse matrix-vector product (SpMV). Wework on the limits of the SpMV kernel by looking at the matrix reordering and the behavior of ourSpMV kernels using vectorization (SIMD) on CPUs and an advanced blocking-layout on NvidiaGPUs. We show that this operator is not appropriate for our problem, and we then propose toreorder the original computation to get a special matrix structure. This new structure is called aslice matrix and is computed with a custom matrix/vector product operator. We present an optimizedimplementation of this operator on CPUs and Nvidia GPUs for which we describe advancedblocking schemes. The resulting solver is parallelized with a hybrid strategy above heterogeneousnodes and relies on a new heuristic to balance the work among the processing units. Due tothe quadratic complexity of this matrix approach, we study the use of the fast multipole method(FMM) for our time-domain BEM solver. We investigate the parallelization of the general FMMalgorithm using several paradigms in both shared and distributed memory, and we explain howmodern runtime systems are well-suited to express the FMM computation. Finally, we investigatethe implementation and the parametrization of an FMM kernel specific to our TD-BEM, and weprovide preliminary results.

Dans le contexte de cette thèse, nous nous focalisons sur des algorithmes pour l’algèbre linéaire numérique, plus précisément sur la résolution de grands systèmes linéaires creux. Nous mettons au point des méthodes de parallélisation pour le solveur linéaire hybride MaPHyS. Premièrement nous considerons l'aproche MPI+threads. Dans MaPHyS, le premier niveau de parallélisme consiste au traitement indépendant des sous-domaines. Le second niveau est exploité grâce à l’utilisation de noyaux multithreadés denses et creux au sein des sous-domaines. Une telle implémentation correspond bien à la structure hiérarchique des supercalculateurs modernes et permet un compromis entre les performances numériques et parallèles du solveur. Nous démontrons la flexibilité de notre implémentation parallèle sur un ensemble de cas tests. Deuxièmement nous considérons un approche plus innovante, où les algorithmes sont décrits comme des ensembles de tâches avec des inter-dépendances, i.e., un graphe de tâches orienté sans cycle (DAG). Nous illustrons d’abord comment une première parallélisation à base de tâches peut être obtenue en composant des librairies à base de tâches au sein des processus MPI illustrer par un prototype d’implémentation préliminaire de notre solveur hybride. Nous montrons ensuite comment une approche à base de tâches abstrayant entièrement le matériel peut exploiter avec succès une large gamme d’architectures matérielles. À cet effet, nous avons implanté une version à base de tâches de l’algorithme du Gradient Conjugué et nous montrons que l’approche proposée permet d’atteindre une très haute performance sur des architectures multi-GPU, multicoeur ainsi qu’hétérogène. / In the context of this thesis, our focus is on numerical linear algebra, more precisely on solution of large sparse systems of linear equations. We focus on designing efficient parallel implementations of MaPHyS, an hybrid linear solver based on domain decomposition techniques. First we investigate the MPI+threads approach. In MaPHyS, the first level of parallelism arises from the independent treatment of the various subdomains. The second level is exploited thanks to the use of multi-threaded dense and sparse linear algebra kernels involved at the subdomain level. Such an hybrid implementation of an hybrid linear solver suitably matches the hierarchical structure of modern supercomputers and enables a trade-off between the numerical and parallel performances of the solver. We demonstrate the flexibility of our parallel implementation on a set of test examples. Secondly, we follow a more disruptive approach where the algorithms are described as sets of tasks with data inter-dependencies that leads to a directed acyclic graph (DAG) representation. The tasks are handled by a runtime system. We illustrate how a first task-based parallel implementation can be obtained by composing task-based parallel libraries within MPI processes throught a preliminary prototype implementation of our hybrid solver. We then show how a task-based approach fully abstracting the hardware architecture can successfully exploit a wide range of modern hardware architectures. We implemented a full task-based Conjugate Gradient algorithm and showed that the proposed approach leads to very high performance on multi-GPU, multicore and heterogeneous architectures.

Les orages tropicaux jouent un rôle incertain dans le transport de l'air troposphérique dans la stratosphère limitant notre capacité à prévoir le climat futur. Le transport par les orages pourrait en effet être sous-estimé dans les modèles de climat aux résolutions trop grossières. L'efficacité de ce transport est analysée à partir de simulations numériques de l'orage Hector the Convector jusqu'à une résolution de 100 m, la plus fine jamais utilisée pour un cas de convection très profonde. Les percées nuageuses, qui avaient été observées à son sommet à 18 km d'altitude, sont reproduites et l'hydratation nette de la stratosphère est quantifiée. La contribution des orages tropicaux au flux d'eau de la troposphère à la stratosphère est ainsi estimée à près de 20 %. La quasi-convergence aux résolutions de 200 m et 100 m suggère que de telles résolutions sont nécessaires pour représenter correctement les ascendances. L'analyse individuelle des ascendances indique que les deux plus grandes contribuent à plus de 90 % du flux de masse vers la basse stratosphère. Elles sont plus larges, plus puissantes et contiennent plus d'eau que les plus grandes ascendances une heure avant et une heure après, et leur cœur convectif apparaît très peu dilué. L'alimentation en surface par des lignes de convergence intensifiées par des poches froides et la faible dilution des deux plus grandes ascendances sont déterminantes dans l'apparition de la convection très profonde. L'analyse isentropique de la circulation générale dans Hector confirme le flux de masse calculé par l'analyse des ascendances. Elle le corrige dans les basses couches en prenant en compte les flux turbulents, et en haute troposphère en filtrant les ondes de gravité. Elle met en évidence l'importance du dégagement de chaleur latente dû à la congélation dans les plus grandes ascendances pendant la phase de percée en stratosphère. / The tropical thunderstorms play an uncertain role in the transport of tropospheric air into the stratosphere, limiting our capability to predict the future climate. The transport by the thunderstorms may be underestimated by the climate models, due to their coarse resolutions. The efficiency of this transport is analysed using numerical simulations of the thunderstorm Hector the Convector with resolutions down to 100 m, the finest ever used for a case of very deep convection. The overshoots, that were observed at its top at 18 km altitude, are captured and the net hydration of the stratosphere is quantified. The contribution of the tropical thunderstorms to the water flux from the troposphere to the stratosphere is then estimated to about 20 %. The almost convergence at 200 m and 100 m suggests that such resolutions are necessary to correctly represent the updafts. The individual analysis of the updrafts indicates that the two tallest contribute beyond 90 % of the mass flux into the stratosphere. They are larger, more vigorous and contain more water than the tallest updrafts one hour before and one hour after, and their convective core was weakly diluted. The supply from the surface by the convergence lines, intensified by the cold pools, and the weak dilution of the two tallest updrafts are determinant for the development of very deep convection. The isentropic analysis of the overturning inside Hector confirms the mass flux computed with the updrafts analysis. It corrects the estimate in the lower troposphere by taking into account the turbulent flux, and in the upper troposphere by filtering out the gravity waves. It highlights the importance of the latent heating due to freezing in the two tallest updrafts during the phase of overshoot in the stratosphere.

Lors de la rentrée atmosphérique nous sommes amenés à modéliser trois phénomènes physiques différents. Tout d'abord, l'écoulement autour du véhicule entrant dans l'atmosphère est hypersonique,il est caractérisé par la présence d'un choc fort et provoque un fort échauffement du véhicule. Nous modélisons l'écoulement par les équations de Navier-Stokes compressibles et l'échauffement du véhicule au moyen de la thermique anisotrope. De plus le véhicule est protégé par un bouclier thermique siège de réactions chimiques que l'on nomme communément ablation.Dans le premier chapitre de cette thèse nous présentons le schéma numérique de diffusion CCLAD (Cell-Centered LAgrangian Diffusion) que nous utilisons pour résoudre la thermique anisotrope. Nous présentons l'extension en trois dimensions de ce schéma ainsi que sa parallélisation.Nous continuons le manuscrit en abordant l'extension de ce schéma à une équation de diffusion tensorielle. Cette équation est obtenue en supprimant les termes convectifs de l'équation de quantité de mouvement des équations de Navier-Stokes. Nous verrons qu'une pénalisation doit être introduite afin de pouvoir inverser la loi constitutive et ainsi appliquer la méthodologie CCLAD. Nous présentons les propriétés numériques du schéma ainsi obtenu et effectuons des validations numériques.Dans le dernier chapitre, nous présentons un schéma numérique de type Volumes Finis permettant de résoudre les équations de Navier-Stokes sur des maillages non-structurés obtenu en réutilisant les deux schémas de diffusion présentés précédemment. / When studying the problem of atmospheric reentry we need to model three different physical phenomenons. First, the ow around the atmospheric reentry vehicle is hypersonic, it is characterized by the presence of a strong shock which leads to a rapid heating of the vehicle. We model the ow using the compressible Navier-Stokes equations and the heating of the vehicle is modeled with the anisotropic heat transfer equation. Furthermore the vehicle is protected by an heat shield, where thermochemical reactions, commonly named ablation, occurs.In the first chapter of this thesis we introduce the numerical diffusion scheme CCLAD (Cell-Centered LAgrangian Diffusion) that we use to solve the anisotropic heat diffusion. We develop its non trivial extension to three-dimensional geometries and present its parallelization. We continue this thesis by the presentation of the extension of this scheme to tensorial diffusion. This equation is obtained by suppressing the convective terms of the momentum equation of the Navier-Stokes equations. We show that we need to introduce a penalization term in order to be able to invert the constitutive law. The invertibility of the constitutive law allows us to apply the CCLAD methodology to this equation straightforwardly. We present the numerical properties of this scheme and show numerical validations.In the last chapter, we present a Finite Volume scheme on unstructured grids that solves the compressible Navier-Stokes equations. This numerical scheme is mainly obtained by gathering the contributions of the two diffusion schemes we developed in the previous chapters.

- Betriebsbereitschaft zum Jahreswechsel 2009/10 - Abschaltung der Klimaanlage - HRSK-Wartungsarbeiten - Frühwarnsystem im Datennetz der TU Dresden - Erfolgreicher Workshop zu TIMaCS - Scan2Mail auf öffentlichen Druck-Kopierern - ZIH präsentierte sich auf der SC09 in Portland - ESMTB-Präsidium erstmalig in Dresden - Veranstaltungen

- HRSK-Wartungsarbeiten - Erweiterung Virtuelle Firewalls im Datennnetz - Neuer Ablauf bei der Software-Beschaffung - FutureGrid: Testumgebungen im Grid-Computing - Bildanalyse-Marathon auf den Hochleistungsrechnern - ZIH Performance Cafe - D-Grid All-Hands-Meeting 2010 in Dresden - AUTOMATA 2010 und SOLSTICE 2010 - Veranstaltungen

- Wartung und Erweiterung WLAN - Neue virtuelle Firewalls im Datennetz - Neue Nutzerverzeichnisse für HRSK geplant - Günstige Microsoft-Lizenzen - VI-HPS Tuning Workshop in Amsterdam - EuroPar-Workshop PROPER 2010 - COLMOT 2010 am MPI-PKS in Dresden - Neue ZIH-Publikationen - Veranstaltungen

- Änderung der Password Policy im ZIH - Erhöhung der Sicherheit im Datennetz der TUD - Inbetriebnahme des neuen Web-Clusters - Neuer IBM IDataPlex HPC-Cluster - Neues HFSP-Projekt 'Biologische Wachstumsregulation' - ZIH auf der Lustre User Group - OUTPUT.DD: Innovationsforum 'Software Saxony' - Veranstaltungen

- Projekt ParMa erfolgreich abgeschlossen - Erweiterung des VPN-Dienstes - Notebook-Ausleihe am ZIH - Neuer Sonderforschungsbereich bewilligt - ZIH auf der ISC'10 - Lange Nacht der Wissenschaften - Neue ZIH-Publikationen - Veranstaltungen