N o D'ORDRE

Frédéric Nataf

Description

Niveau: Supérieur, Doctorat, Bac+8
N o 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

• cerfacs


• large linear


• calcul parallèle


• krylov methods


• méthodes de krylov


• extensibilité parallèle de solveurs linéaires


• systèmes linéaires


• directeur de la recherche

Sujets

• Institut national polytechnique de Toulouse
• Lanteri
• Giraud
• Toulouse
• Vasseur
• Gratton
• Parallélisme (informatique)

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 juin 2008
• Nombre de lectures: 50
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

o N 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 large3D problems

Thèse présentée le 23 Juin 2008 à Toulouse devant le jury composé de:

Fréderic Nataf Ray Tuminaro

Iain Duff Luc Giraud Stéphane Lanteri Gérard Meurant Jean Roman

Directeur de Recherche CNRS, Lab Jacques-Louis Lions Chercheur senior, Sandia National Laboratories

Directeur de Recherche RAL et CERFACS Professeur, INPT-ENSEEIHT Directeur de Recherche INRIA Directeur de Recherche CEA Professeur, ENSEIRB-INRIA

Thèse préparée au C ERFACS , Report Ref:TH/PA/08/93

France USA

Royaume-Uni France France France France

Rapporteur Rapporteur

Examinateur Directeur Examinateur Examinateur Examinateur

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 te chniques 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 al gé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 pou r 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-scale scientific applications and industrial simulations are nowadays fully integrated in 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 perfor- mance hybrid direct/iterative approach for solving large 3D problems. We focus specifically on the associated domain decomposition techniques for the parallel solution of large linear systems. 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: Domain decomposition, Iterative methods, 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 nu- merical simulations, Preconditioning techniques, Additive Schwarz preconditioner.

Remerciements

C'est une habitude saine que de rendre mérite, avec mon entho usiasme le plus vif et le plus sincère à tous ceux qui à leur manière ont contribué mener ce travail à bien. Je désire alors exprimer 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 piste s 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éten ces scientifiques, de ses conseils perti- nents 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 recher che et de l'industrie.

Envers le directeur de l'équipe algorithme parallèle Iain D UFF, je tiens à lui exprimer ma très vive reconnaissance. Monsieur j'ai eu l'honneur de travail ler 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'assistance de plusieurs personnes de l'équipe MUMPS. Pa rticulièrement je 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 fonctionnalités qui m'ont été très bénéfiques.

Aux membres du Jury qui m'ont honoré en acceptant d'évaluer m on travail et d'être présent ici aujourd'hui. Chacun d'eux mérite un remerciement parti culier pour m'avoir accordé son atten- tion. Un sincère remerciement à Fréderic NATAF et Ray TUMINARO qui m'ont fait l'honneur d'accepté la charge d'être rapporteurs. Je leur suis reconn aissant pour le temps qu'ils ont consacré à la lecture 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é et inspiré. Aussi bien également Luc GIRAUD qui m'a motivé et qu i m'a considérablement soutenu 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ési re aussi remercier très vivement Gérard MEURANT pour toutes ses remarques scientifiques, ses suggestions et ses conseils judicieux 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 à remer cier profondément Jean ROMAN pour avoir accepté de participer à ce jury, ainsi que pour ses conversations enrichissantes lors de mes visites à l'INRIA Bordeaux. Egalement je tiens à remercier t outes 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 endroit de convivialité et j'ai eu l'honneur d'effectuer ma thèse au sein de votre laboratoire. Heureusement

que l'équipe CSG du CERFACS était là pour m'aider à me dépatou iller avec les expériences et pour venir me sauver lorsque j'étais perdu au fin fond des tracas in formatiques. Merci pour votre déli- catesse 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 SOUR- BIER, Jean VIRIEUX, Romain BROSSIER and StÂt'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, qui m'ont accompagné pendant cette aventure et que je n e peux citer ici, vous êtes nombreux...

Cette aventure de m'est pas propre, enfin, c'est quand même l' aboutissement de toute une scolar- ité, je voudrais remercier chaleureusement ma petite maman à qui je dois beaucoup et qui a toujours été une fervente supportrice avec mes deux sœurs et 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 po ur 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

1

2

3

4

Solving large linear systems on large parallel platforms

Introduction

Some basics on hybrid linear solvers 2.1 Some roots in domain decomposition methods. . . . . . . . . . . . . . . . . . . . . 2.1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 2.1.2 A brief overview of overlapping domain decomposition. . . . . . . . . . .. 2.1.2.1 Additive Schwarz preconditioners. . . . . . . . . . . . . . . . .. 2.1.2.2 Restricted additive Schwarz preconditioner. . . .. . . . . . . . . 2.1.3 A brief overview of non-overlapping domain decomposition. . . . . . . . . 2.1.3.1 The Neumann-Dirichlet preconditioner . . . . . . . . . . . . . . . 2.1.3.2 The Neumann-Neumann preconditioner . . . . . . . . . . . . . . 2.2 Some background on Krylov subspace methods. . . . .. . . . . . . . . . . . . . . 2.2.1 Introduction. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 The unsymmetric problems. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 The symmetric positive definite problems. . . . . . . . . . . . . . . . . . . 2.2.4 Stopping criterion: a central component.. . . . . . . . . . . . . . . . . . .

An additive Schwarz preconditioner for Schur complement 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Algebraic description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Sparse algebraic Additive Schwarz preconditioner . . . . . . . . . . . . . . . . . . . 3.4 Mixed precision Additive Schwarz preconditioner . . . . . . . . . . . . . . . . . . . 3.5 Two-level preconditioner with a coarse space correction . . . . . . . . . . . . . . . . 3.6 Scaling the Schur complement. . . . . . . . . . . . . . . . . . . . .. . . . . . . .

Design of parallel distributed implementation 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Classical parallel implementations of domain decomposition method. . . . .. . . . 4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Local solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Local preconditioner and coarse grid implementations . . . . . . . . . . . . 4.2.4 Parallelizing iterative solvers . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Two-level parallelization strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Motivations for multi-level parallelism . . . . . . . . . . . . . . . . . . . . . 4.3.2 Parallel B LACS . . . . . . . . . . . . . . . . . . . . . . . .environments . 4.3.3 Multi-level of task and data parallelism . . . . . . . . . . . . . . . . . . . . 4.3.4 Mixing2-levels. . . .of parallelism and domain decomposition techniques

3

11

15 15 15 17 17 18 18 19 20 20 20 21 24 25

29 29 29 31 32 36 39

41 41 41 41 42 43 43 45 45 47 47 49

ii

II

5

6

III

7

Study of parallel scalability on large3Dmodel problems

CONTENTS

Numerical investigations on diffusion equations 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Experimental environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Numerical performance behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Influence of the sparsification threshold . . . . . . . . . . . . . . . . . . . . 5.3.2 Influence of the mixed arithmetic . . . . . . . . . . . . . . . . . . . . . . . 5.4 Parallel numerical scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Parallel speedup experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Numerical scalability study on massively parallel platforms . . . . . . . . . 5.4.2.1 Effect of the sparsification dropping threshold on the performance 5.4.2.2 Effect of the mixed arithmetic on the performance . . . . . . . . . 5.4.3 Parallel performance scalability on massively parallel platforms . . . . . . . 5.4.4 Influence of the coarse component correction . . . . . . . . . . . . . . . . . 5.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numerical investigations on convection-diffusion equations 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Experimental environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Numerical performance behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Influence of the sparsification threshold . . . . . . . . . . . . . . . . . . . . 6.3.2 Influence of the mixed arithmetic . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 Effect of the Péclet number. . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Parallel numerical scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 Numerical scalability on massively parallel platforms . . . . . . . . . . . . . 6.4.2 Parallel performance scalability on massively parallel platforms . . . . . . . 6.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Study of parallel scalability on large real application problems

Preliminary investigations on structural mechanics problems 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Experimental framework . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Model problems . . . . . . . . . . . . . . . . . . . . . . 7.2.2 Parallel platforms . . . . . . . . . . . . . . . . . . . . . . 7.3 Partitioning strategies . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Indefinite symmetric linear systems in structural mechanics . . . . 7.4.1 Numerical behaviour of the sparsification . . . . . . . . . 7.4.2 Parallel performance . . . . . . . . . . . . . . . . . . . . 7.4.2.1 Numerical scalability on parallel platforms . . . 7.4.2.2 Parallel performance scalability . . . . . . . . . 7.5 Symmetric positive definite linear systems in structural mechanics 7.5.1 Numerical behaviour . . . . . . . . . . . . . . . . . . . . 7.5.1.1 Influence of the sparsification threshold . . . . . 7.5.1.2 Influence of the mixed arithmetic . . . . . . . . 7.5.2 Parallel performance experiments . . . . . . . . . . . . . 7.5.2.1 Numerical scalability . . . . . . . . . . . . . . 7.5.2.2 Parallel performance scalability . . . . . . . . . 7.6 Exploiting2-levels. . . . . . . . . . . . . . . . . .of parallelism 7.6.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

53

59 59 59 60 61 63 66 66 67 67 68 70 75 80

81 81 81 84 84 86 88 89 89 90 97

101

. . . . . . . . . . . . . . . . . . .

107 107 107 107 110 111 113 113 115 115 117 127 127 127 128 128 129 130 133 133

CONTENTS

8

IV

9

7.7

7.6.2 Numerical benefits . . . . . . . . . . . . . . . . 7.6.3 Parallel performance benefits . . . . . . . . . . . Concluding remarks . . . . . . . . . . . . . . . . . . . .

iii

. . . . . . . . . . . . . . . 134 . . . . . . . . . . . . . . . 134 . . . . . . . . . . . . . . . 136

Preliminary investigations in seismic modelling 143 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 8.2 Experimental framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8.2.1 The 2DMarmousi II model . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8.2.2 The 3DOverthrust 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 3Dproblems . . . . . . . . . . . . . . . . . 153 8.6 Parallel efficiency of the2-level parallelimplementation . . . . . . . . . . . . . . . 154 8.6.1 Numerical benefits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 8.6.2 Parallel performance benefits . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.7 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

Further performance study and applications

Conclusion and future work

Acknowledgments

Bibliography

163

165

169

171