THÈSE
187 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

THÈSE

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
187 Pages
English

Description

oN D’ORDRE 2623
THÈSE
présenté en vue de l’obtention du titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
Spécialité: Mathématiques, Informatique et Télécommunications
par
Azzam HAIDAR
CERFACS
Sur l’extensibilité parallèle de solveurs linéaires hybrides pour des
problèmes tridimensionels de grandes tailles
On the parallel scalability of hybrid linear solvers for large 3D problems
Thèse présentée le 23 Juin 2008 à Toulouse devant le jury composé de:
Fréderic Nataf Directeur de Recherche CNRS, Lab Jacques Louis Lions France Rapporteur
Ray Tuminaro Chercheur senior, Sandia National Laboratories USA Rapporteur
Iain Duff Directeur de Recherche RAL et CERFACS Royaume Uni Examinateur
Luc Giraud Professeur, INPT ENSEEIHT France Directeur
Stéphane Lanteri Directeur de Recherche INRIA France Examinateur
Gérard Meurant Directeur de Recherche CEA France Examinateur
Jean Roman Professeur, ENSEIRB INRIA France Examinateur
Thèse préparée au Cerfacs, Report Ref:TH/PA/08/93 Résumé
La résolution de très grands systèmes linéaires creux est une composante de base algorithmique
fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per
formante de ces systèmes passe par la conception, le développement et l’utilisation d’algorithmes
parallèles performants. Dans nos travaux, nous nous intéressons au développement et l’évaluation
d’une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine
sans recouvrement. ...

Subjects

Informations

Published by
Reads 97
Language English
Document size 5 MB

Exrait

oN D’ORDRE 2623 THÈSE présenté en vue de l’obtention du titre de DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Spécialité: Mathématiques, Informatique et Télécommunications par Azzam HAIDAR CERFACS Sur l’extensibilité parallèle de solveurs linéaires hybrides pour des problèmes tridimensionels de grandes tailles On the parallel scalability of hybrid linear solvers for large 3D problems Thèse présentée le 23 Juin 2008 à Toulouse devant le jury composé de: Fréderic Nataf Directeur de Recherche CNRS, Lab Jacques Louis Lions France Rapporteur Ray Tuminaro Chercheur senior, Sandia National Laboratories USA Rapporteur Iain Duff Directeur de Recherche RAL et CERFACS Royaume Uni Examinateur Luc Giraud Professeur, INPT ENSEEIHT France Directeur Stéphane Lanteri Directeur de Recherche INRIA France Examinateur Gérard Meurant Directeur de Recherche CEA France Examinateur Jean Roman Professeur, ENSEIRB INRIA France Examinateur Thèse préparée au Cerfacs, Report Ref:TH/PA/08/93 Résumé La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per formante de ces systèmes passe par la conception, le développement et l’utilisation d’algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l’évaluation d’une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l’utilisation des machines mas sivement parallèles à plusieurs milliers de processeurs. L’étude systématique de l’extensibilité et l’efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d’un point de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d’inconnues pour des problèmes réels 3D. Mots-clés: Décomposition de domaines, Méthodes itératives, Méthodes directes, Méthodes hy brides, Complément de Schur, Systèmes linéaires denses et creux, Méthodes de Krylov, GMRES, Flexible GMRES, CG, Calcul haute performace, Deux niveaux de parallèlisme, Calcul parallèle distribué, Calcul sientifique, Simulation numériques de grande taille, Techniques de précondition nement, Préconditionneur de type Schwarz additive. Abstract Large scalescientific applicationsandindustrial simulationsarenowadaysfully integratedin many engineering areas. They involve the solution of large sparse linear systems. The use of large high performance computers is mandatory to solve these problems. The main topic of this research work was the study of a numerical technique that had attractive features for an efficient solution of large scale linear systems on large massively parallel platforms. The goal is to develop a high performance hybrid direct/iterative approach for solving large 3D problems. We focus specifically onthe associateddomaindecompositiontechniquesforthe parallelsolutionoflargelinearsystems. We have investigated several algebraic preconditioning techniques, discussed their numerical be haviours, their parallel implementations and scalabilities. We have compared their performances on a set of 3D grand challenge problems. Keywords: Domaindecomposition, Iterativemethods, Direct methods, Hybrid methods, Schur complements Linear systems, Krylov methods, GMRES, flexible GMRES, CG, High performance computing, Two levels of parallelism, Distributed computing, Scientific computing, Large scale numerical simulations, Preconditioning techniques, Additive Schwarz preconditioner. Remerciements C’est une habitude saine que de rendre mérite, avec mon enthousiasme le plus vif et le plus sincère à tous ceux qui à leur manière ont contribué mener ce travail à bien. Je désire alors ex primer ma profonde gratitude : Envers Luc GIRAUD, pour avoir accepté de me diriger patiemment, mais aussi spécialement pour m’avoir accordé sa confiance en me laissant toute liberté dans mes initiatives, tout en étant suffisamment attentif pour que je ne m’égare pas sur des pistes peu prometteuses. Mais également pour sa disponibilité et sa générosité exceptionnelles, il s’est montré très disponible pour toutes mes questions et problèmes à résoudre. Pour sa gentillesse, il a pris le temps de lire, relire et corriger soigneusement cette thèse. J’ai pu profiter des ses compétences scientifiques, de ses con seils pertinents et précieux. Par son charisme, son dynamisme et sa passion exceptionnelle pour la recherche, il m’a beaucoup appris pour évoluer dans le monde de la recherche et de l’industrie. Envers le directeur de l’équipe algorithme parallèle Iain DUFF, je tiens à lui exprimer ma très vive reconnaissance. Monsieur j’ai eu l’honneur de travailler ces trois années au sein de votre équipe. Cette expérience professionnelle me sera très bénéfique en ce qui concerne mes projets d’avenir. Je tiens à vous remercier pour toutes vos remarques toujours pertinentes et vos idées attentives. A Serge GRATTON, et Xavier VASSEUR, je tiens à vous adresser mes sincères remerciements pour vos encouragements généreux et vos suggestions judicieuses : ils m’ont été précieux. Vous vous êtes montrés très disponibles pour toutes mes discussions vous m’avez aidé avec grande gen tillesse ce qui m’a permis de m’ouvrir à d’autres horizons. A l’assistancede plusieurs personnesde l’équipe MUMPS. Particulièrementje tiens à remercier Jean Yves L’EXCELLENT et Patrick AMESTOY pour leur support et leurs aides très précieuses de tous moments. Vous avez pris le temps de développer et de débuguer de nouvelles fonctionnal ités qui m’ont été très bénéfiques. Aux membresdu Jury qui m’ont honoré en acceptant d’évaluer mon travailet d’être présent ici aujourd’hui. Chacund’eux mérite un remerciementparticulierpourm’avoiraccordéson attention. UnsincèreremerciementàFrédericNATAFetRayTUMINAROquim’ontfaitl’honneurd’accepté la charge d’être rapporteurs. Je leur suis reconnaissant pour le temps qu’ils ont consacré à la lec ture de ce manuscrit et pour l’intérêt qu’ils ont montré pour mon travail. J’aimerais remercier sincèrement Iain DUFF qui m’a fait l’honneur de présider mon jury, qui m’a beaucoup encouragé etinspiré. AussibienégalementLucGIRAUDquim’amotivéetquim’aconsidérablementsoutenu durant toutes mes recherches de thèse. Je désire aussi remercier vivement Stéphane LANTERI pour ces conseils amicaux ainsi que ses discussions importantes et son accueil passionnant lors de mon séjour dans son équipe à l’INRIA Sophia Antipolis. Je désire aussi remercier très vivement Gérard MEURANT pour toutes ses remarques scientifiques, ses suggestions et ses conseils judi cieux qu’il m’a souvent transmis grâce à son caractère chaleureux : ils m’ont été très précieux. Il n’a jamais manqué une occasion pour m’encourager. Enfin je tiens à remercier profondément Jean ROMAN pour avoir accepté de participer à ce jury, ainsi que pour ses conversationsenrichissantes lors de mes visites à l’INRIA Bordeaux. Egalement je tiens à remercier toutes les personnes qui ont assisté à cette soutenance de thèse. C’est un grand privilège d’effectuer sa thèse au CERFACS, j’exprime ma très vive reconnais sance à Jean Claude ANDRE le directeur du laboratoire. Monsieur, le CERFACS est un bon en droitdeconvivialitéetj’aieul’honneurd’effectuermathèseauseindevotrelaboratoire. Heureuse ment que l’équipe CSG du CERFACS était là pour m’aider à me dépatouiller avec les expériences etpourvenirmesauverlorsquej’étaisperduaufinfonddestracasinformatiques. Mercipourvotre délicatesse et votre attention. Merci également au travail et à la gentillesse de l’administration, Brigitte, Chantal, Dominique, Lydia, Michèle, et Nicole. Egalement une pensée pour tous ceux avec qui j’ai partagé les moments qui font la vie d’un étudiant, les discussions dans les couloirs. Un remerciement particulier aux membres de l’équipe ALGO avec qui j’ai partagé de très beaux moments chaleureux, les déjeuners (départ à 12h30 tapante !), les pauses café/thé, les sudokus, les affaires de logiques du “le Monde”, les sorties, je glisse un remerciement amical à cette joyeuse bande. To the Samcef project, especially to Stéphane PRALET, who provided us with the structural mechanics problems support, for the help he gave me among this work, and for kindly developing special functionality allowing me to use the samcef code, for his advice and numerous suggestions. To all the members of the Consortium Seiscope project with whom I had fruitful discussion and who, provides me the seismic applications that enables me to progress in my work: Florent SOURBIER, Jean VIRIEUX, Romain BROSSIER and StÂťephane OPERTO. To the INRIA NACHOS team. I must thank Stéphane LANTERI who opened me the door of an enriching collaboration, who interest in my work and who gave me constructive advice. To Masha SOSONKINA and Layne WATSON whose deserve grateful thanks for providing me with an huge amount of simulations hours on the Virginia Tech supercomputer, and for many helpful discussions and advices. Un grand grand Merci également a toutes celles et ceux qui ont participé directement ou indi rectement à ce travail. Tous celles et ceux qui m’ont témoigné leur amitié, qui m’ont apporté leur aide,quim’ontaccompagnépendantcetteaventureetquejenepeuxciterici,vousêtesnombreux... Cette aventure de m’est pas propre, enfin, c’est quand même l’aboutissement de toute une scolarité, je voudrais remercier chaleureusement ma petite maman à qui je dois beaucoup et qui a toujours été une fervente supportrice avecmes deux sœurset mon frère. Kamil, un grand merci du cœur a toi mon père, pour m’avoir donné l’envie d’être heureux et pour m’avoir toujours soutenu dans mes choix. Et tout le reste de ma famille, Merci pour votre soutien, vos encouragements et votre présence dans les moments difficiles. Je vous témoigne ici toute ma reconnaissance et tout mon amour. Contents I Solving large linear systems on large parallel platforms 3 1 Introduction 11 2 Some basics on hybrid linear solvers 15 2.1 Some roots in domain decomposition methods . . . . . . . . . . . . . . . . . . . . . 15 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.2 A brief overview of overlapping domain decomposition . . . . . . . . . . . . 17 2.1.2.1 Additive Schwarz preconditioners . . . . . . . . . . . . . . . . . . 17 2.1.2.2 Restricted additive Schwarz preconditioner . . . . . . . . . . . . . 18 2.1.3 A brief overview of non overlapping domain decomposition . . . . . . . . . 18 2.1.3.1 The Neumann Dirichlet preconditioner . . . . . . . . . . . . . . . 19 2.1.3.2 The Neumann Neumann preconditioner . . . . . . . . . . . . . . . 20 2.2 Some background on Krylov subspace methods . . . . . . . . . . . . . . . . . . . . 20 2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 The unsymmetric problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 The symmetric positive definite problems . . . . . . . . . . . . . . . . . . . 24 2.2.4 Stopping criterion: a central component . . . . . . . . . . . . . . . . . . . . 25 3 An additive Schwarz preconditioner for Schur complement 29 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Algebraic description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Sparse algebraic Additive Schwarz preconditioner . . . . . . . . . . . . . . . . . . . 31 3.4 Mixed precision Additive Schwarz preconditioner . . . . . . . . . . . . . . . . . . . 31 3.5 Two level preconditioner with a coarse space correction. . . . . . . . . . . . . . . . 36 3.6 Scaling the Schur complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Design of parallel distributed implementation 41 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Classical parallel implementations of domain decomposition method . . . . . . . . 41 4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.2 Local solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.3 Local preconditioner and coarse grid implementations . . . . . . . . . . . . 43 4.2.4 Parallelizing iterative solvers . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 Two level parallelization strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.1 Motivations for multi level parallelism . . . . . . . . . . . . . . . . . . . . . 45 4.3.2 Parallel Blacs environments . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3.3 Multi level of task and data parallelism . . . . . . . . . . . . . . . . . . . . 47 4.3.4 Mixing 2-levels of parallelism and domain decomposition techniques . . . . 49 ii CONTENTS II Study of parallel scalability on large 3D model problems 53 5 Numerical investigations on diffusion equations 59 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Experimental environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3 Numerical performance behaviour. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3.1 Influence of the sparsification threshold . . . . . . . . . . . . . . . . . . . . 61 5.3.2 Influence of the mixed arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4 Parallel numerical scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.4.1 Parallel speedup experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.4.2 Numerical scalability study on massively parallel platforms . . . . . . . . . 67 5.4.2.1 Effect of the sparsification dropping threshold on the performance 67 5.4.2.2 Effect of the mixed arithmetic on the performance . . . . . . . . . 68 5.4.3 Parallel performance scalability on massively parallel platforms . . . . . . . 70 5.4.4 Influence of the coarse component correction . . . . . . . . . . . . . . . . . 75 5.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6 Numerical investigations on convection-diffusion equations 81 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2 Experimental environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.3 Numerical performance behaviour. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.3.1 Influence of the sparsification threshold . . . . . . . . . . . . . . . . . . . . 84 6.3.2 Influence of the mixed arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3.3 Effect of the Péclet number . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.4 Parallel numerical scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.4.1 Numerical scalability on massively parallel platforms . . . . . . . . . . . . . 89 6.4.2 Parallel performance scalability on massively parallel platforms . . . . . . . 90 6.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 III Study of parallel scalability on large real application problems 101 7 Preliminary investigations on structural mechanics problems 107 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2 Experimental framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2.1 Model problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.2.2 Parallel platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.3 Partitioning strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.4 Indefinite symmetric linear systems in structural mechanics . . . . . . . . . . . . . 113 7.4.1 Numerical behaviour of the sparsification . . . . . . . . . . . . . . . . . . . 113 7.4.2 Parallel performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.4.2.1 Numerical scalability on parallel platforms . . . . . . . . . . . . . 115 7.4.2.2 Parallel performance scalability. . . . . . . . . . . . . . . . . . . . 117 7.5 Symmetric positive definite linear systems in structural mechanics . . . . . . . . . 127 7.5.1 Numerical behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.5.1.1 Influence of the sparsification threshold . . . . . . . . . . . . . . . 127 7.5.1.2 Influence of the mixed arithmetic . . . . . . . . . . . . . . . . . . 128 7.5.2 Parallel performance experiments . . . . . . . . . . . . . . . . . . . . . . . . 128 7.5.2.1 Numerical scalability . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.5.2.2 Parallel performance scalability. . . . . . . . . . . . . . . . . . . . 130 7.6 Exploiting 2-levels of parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.6.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 CONTENTS iii 7.6.2 Numerical benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7.6.3 Parallel performance benefits . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7.7 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8 Preliminary investigations in seismic modelling 143 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 8.2 Experimental framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8.2.1 The 2D Marmousi II model . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8.2.2 The 3D Overthrust model: SEG/EAGE . . . . . . . . . . . . . . . . . . . 146 8.3 Numerical accuracy analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.4 Parallel performance investigations on 2D problems . . . . . . . . . . . . . . . . . 147 8.5 Parallel performance investigations on 3D problems . . . . . . . . . . . . . . . . . 153 8.6 Parallel efficiency of the 2-level parallel implementation . . . . . . . . . . . . . . . 154 8.6.1 Numerical benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 8.6.2 Parallel performance benefits . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.7 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 IV Further performance study and applications 163 9 Conclusion and future work 165 Acknowledgments 169 Bibliography 171