finance and industry. For example, it enables us, thanks to efficient algorithms adapted to current computers, to
simulate, without the help of models or experimentations, the deflection of beams in bending, the sound level in a theater room or a fluid flowing around an aircraft wing.
This book presents the scientific computing techniques applied to parallel computing for the numerical simulation of large-scale problems; these problems result from systems modeled by partial differential equations. Computing concepts will be tackled via examples.
Implementation and programming techniques resulting from the finite element method will be presented for direct solvers, iterative solvers and domain decomposition methods, along with an introduction to MPI and OpenMP.
Autorentext
Frédéric Magoulès is Professor at Ecole Centrale Paris in France and Honorary Professor at the University of Pecs in Hungary. His research focuses on parallel computing and numerical linear algebra.
François-Xavier Roux is Professor at Université Pierre et Marie Curie and an Engineer at ONERA, in France. His research focuses on parallel computing and numerical analysis.
Guillaume Houzeaux is Team Leader at the Barcelona Supercomputing Center in Spain. His research focuses on high performance computational mechanics.
Zusammenfassung
Parallel Scientific Computing
Scientific computing has become an indispensable tool in numerous fields, such as physics, mechanics, biology, finance and industry. For example, it enables us, thanks to efficient algorithms adapted to current computers, to simulate, without the help of models or experimentations, the deflection of beams in bending, the sound level in a theater room or a fluid flowing around an aircraft wing.
This book presents the scientific computing techniques applied to parallel computing for the numerical simulation of large-scale problems; these problems result from systems modeled by partial differential equations. Computing concepts will be tackled via examples.
Implementation and programming techniques resulting from the finite element method will be presented for direct solvers, iterative solvers and domain decomposition methods, along with an introduction to MPI and OpenMP.
Inhalt
Preface xi
Introduction xv
Chapter 1. Computer Architectures 1
1.1. Different types of parallelism 1
1.1.1. Overlap, concurrency and parallelism 1
1.1.2. Temporal and spatial parallelism for arithmetic logic units 4
1.1.3. Parallelism and memory 6
1.2. Memory architecture 7
1.2.1. Interleaved multi-bank memory 7
1.2.2. Memory hierarchy 8
1.2.3. Distributed memory 13
1.3. Hybrid architecture 14
1.3.1. Graphics-type accelerators 14
1.3.2. Hybrid computers 16
Chapter 2. Parallelization and Programming Models 17
2.1. Parallelization 17
2.2. Performance criteria 19
2.2.1. Degree of parallelism 19
2.2.2. Load balancing 21
2.2.3. Granularity 21
2.2.4. Scalability 22
2.3. Data parallelism 25
2.3.1. Loop tasks 25
2.3.2. Dependencies 26
2.3.3. Examples of dependence 27
2.3.4. Reduction operations 30
2.3.5. Nested loops 31
2.3.6. OpenMP 34
2.4. Vectorization: a case study 37
2.4.1. Vector computers and vectorization 37
2.4.2. Dependence 38
2.4.3. Reduction operations 39
2.4.4. Pipeline operations 41
2.5. Message-passing 43
2.5.1. Message-passing programming 43
2.5.2. Parallel environment management 44
2.5.3. Point-to-point communications 45
2.5.4. Collective communications 46
2.6. Performance analysis 49
Chapter 3. Parallel Algorithm Concepts 53
3.1. Parallel algorithms for recurrences 54
3.1.1. The principles of reduction methods 54
3.1.2. Overhead and stability of reduction methods 55
3.1.3. Cyclic reduction 57
3.2. Data locality and distribution: product of matrices 58
3.2.1. Row and column algorithms 58
3.2.2. Block algorithms 60
3.2.3. Distributed algorithms 64
3.2.4. Implementation 66
Chapter 4. Basics of Numerical Matrix Analysis 71
4.1. Review of basic notions of linear algebra 71
4.1.1. Vector spaces, scalar products and orthogonal projection 71
4.1.2. Linear applications and matrices 74
4.2. Properties of matrices 79
4.2.1. Matrices, eigenvalues and eigenvectors 79
4.2.2. Norms of a matrix 80
4.2.3. Basis change 83
4.2.4. Conditioning of a matrix 85
Chapter 5. Sparse Matrices 93
5.1. Origins of sparse matrices 93
5.2. Parallel formation of sparse matrices: shared memory 98
5.3. Parallel formation by block of sparse matrices: distributed memory 99
5.3.1. Parallelization by sets of vertices 99
5.3.2. Parallelization by sets of elements 101
5.3.3. Comparison: sets of vertices and elements 101
Chapter 6. Solving Linear Systems 105
6.1. Direct methods 105
6.2. Iterative methods 106
Chapter 7. LU Methods for Solving Linear Systems 109
7.1. Principle of LU decomposition 109
7.2. Gauss factorization 113
7.3. GaussJordan factorization 115
7.3.1. Row pivoting 118
7.4. Crout and Cholesky factorizations for symmetric matrices 121
Chapter 8. Parallelization of LU Methods for Dense Matrices 125
8.1. Block factorization 125
8.2. Implementation of block factorization in a message-passing environment 130
8.3. Parallelization of forward and backward substitutions 135
Chapter 9. LU Methods for Sparse Matrices 139
9.1. Structure of factorized matrices 139
9.2. Symbolic factorization and renumbering 142
9.3. Elimination trees 147
9.4. Elimination trees ...