An introduction to parallel and vector scientific computing

Ronald W. Shonkwiler, Lew Lefton052186478X, 9780521864787, 0521683378, 9780521683371

In this text, students of applied mathematics, science and engineering are introduced to fundamental ways of thinking about the broad context of parallelism. The authors begin by giving the reader a deeper understanding of the issues through a general examination of timing, data dependencies, and communication. These ideas are implemented with respect to shared memory, parallel and vector processing, and distributed memory cluster computing. Threads, OpenMP, and MPI are covered, along with code examples in Fortran, C, and Java. The principles of parallel computation are applied throughout as the authors cover traditional topics in a first course in scientific computing. Building on the fundamentals of floating point representation and numerical error, a thorough treatment of numerical linear algebra and eigenvector/eigenvalue problems is provided. By studying how these algorithms parallelize, the reader is able to explore parallelism inherent in other computations, such as Monte Carlo methods.

---

Table of contents :
Cover……Page 1
Half-title……Page 2
Series-title……Page 3
Title……Page 4
Copyright……Page 5
Contents……Page 6
Preface……Page 10
Acknowlegments……Page 14
PART I Machines and Computation……Page 16
1 Introduction – The Nature of High-Performance Computation……Page 18
1.1 Computing Hardware Has Undergone Vast Improvement……Page 19
The von Neumann Computer……Page 20
Operation of a von Neumann Computer: c = a + b Walk-Through……Page 22
Parallel Computing Hardware – Flynn’s Classification……Page 23
Operation of a Vector Computer – Assembly-Line Processing……Page 24
Hockney’s Formulas……Page 26
The “Jiffy-Lube” Model……Page 29
1.4 Classification of Distributed Memory Computers……Page 31
Communication Links and Delays……Page 32
Mesh……Page 33
LAN……Page 34
1.5 Amdahl’s Law and Profiling……Page 35
Exercises……Page 38
Programming Exercises……Page 41
A Directed Acyclic Graph Defines a Computation……Page 42
A Schedule……Page 46
Speedup and Efficiency……Page 47
Reduction……Page 48
Recursive Doubling……Page 49
Matrix Powers……Page 51
2.3 Data Dependencies……Page 52
Induction Variable……Page 53
Forward Dependency……Page 54
Run-Time Break……Page 55
Exercises……Page 56
3 Machine Implementations……Page 59
The Fork Operation……Page 60
Barriers……Page 62
Mutexes……Page 63
3.2 Threads Programming……Page 65
Mutexes, Barriers, and Condition Variables……Page 66
Condition Variables……Page 70
3.3 Java Threads……Page 71
Two Styles of Threaded Programming……Page 72
Every Object Has a Mutex……Page 74
Condition Variables Are Keyed to wait() and notify()……Page 76
3.4 SGI Threads and OpenMP……Page 78
DOACROSS Style Parallelization……Page 79
Introduction to Message Passing……Page 82
Nonblocking Communications and Other Features of MPI……Page 89
Matrix Product Source Code in C……Page 92
Writing Vector Code……Page 95
Chaining……Page 97
Instruction Buffering……Page 98
Vector Dependencies……Page 99
ABC test……Page 100
Programming Aids……Page 101
3.7 Quantum Computation Qubits……Page 104
Superposition of States – Quantum Reality……Page 106
Adding More Qubits……Page 107
Entanglement……Page 108
Quantum Computation……Page 109
Shor’s Algorithm to Break an RSA Code in Polynomial Time……Page 111
Exercises……Page 112
Programming Exercises……Page 113
PART II Linear Systems……Page 116
4 Building Blocks – Floating Point Numbers and Basic Linear Algebra……Page 118
4.1 Floating Point Numbers and Numerical Error……Page 119
Floating Point Numbers……Page 120
Density of Floating Point Numbers and Round-off Error……Page 123
Subtracting Numbers About the Same Size……Page 125
Condition……Page 126
Scalar–Vector Product……Page 128
Sum of n Matrices, Each m × m……Page 129
Matrix–Vector multiply……Page 130
Matrix–Matrix Multiply, i jk-Forms……Page 132
Inner-Product Model, Forms i jk and jik……Page 133
Middle-Product Model, Forms ikj and jki……Page 134
4.4 Operations with Banded Matrices……Page 135
Banded Matrix–Vector Product by Diagonals……Page 136
Tridiagonal Matrix–Matrix Product……Page 137
Exercises……Page 139
Programming Exercises……Page 140
5.1 Triangular Systems……Page 141
Lower Triangular Systems – Forward Substitution……Page 142
Looping Notation……Page 145
Upper-Triangular Systems – Back Substitution……Page 146
Parallel Considerations for Triangular Systems……Page 147
A Surprising Matrix Solution……Page 148
5.2 Gaussian Elimination……Page 149
Elementary Row Operations……Page 150
Gaussian Elimination – LU Decomposition……Page 151
Row Interchanges……Page 155
Pivoting……Page 161
Total Pivoting……Page 163
5.3 i jk-Forms for LU Decomposition……Page 165
ki j-Form……Page 166
jki-Form……Page 167
jik-Form……Page 169
5.4 Bordering Algorithm for LU Decomposition……Page 170
5.5 Algorithm for Matrix Inversion in log2n Time……Page 171
Exercises……Page 173
Programming Exercises……Page 176
6.1 Tridiagonal Systems – Thompson’s Algorithm……Page 177
6.2 Tridiagonal Systems – Odd–Even Reduction……Page 178
Parallel Considerations……Page 180
6.3 Symmetric Systems – Cholesky Decomposition……Page 181
Exercises……Page 185
Programming Exercises……Page 186
7.1 Error and Residual – Matrix Norms……Page 187
The Size of Vectors and Matrices……Page 189
Condition Number……Page 191
Step-by-Step Error in the Elimination Process……Page 194
7.2 Givens Rotations……Page 195
Parallel Implementation……Page 197
Orthogonal Basis……Page 198
Exercises……Page 199
Programming Exercises……Page 200
8.1 Jacobi Iteration or the Method of Simultaneous Displacements……Page 201
8.2 Gauss–Seidel Iteration or the Method of Successive Displacements……Page 204
8.3 Fixed-Point Iteration……Page 206
8.4 Relaxation Methods……Page 208
8.5 Application to Poisson’s Equation……Page 209
8.6 Parallelizing Gauss–Seidel Iteration……Page 213
8.7 Conjugate Gradient Method……Page 215
Exercises……Page 219
Programming Exercises……Page 220
9.1 Eigenvalues and Eigenvectors……Page 221
9.2 The Power Method……Page 224
9.3 Jordan Cannonical Form……Page 225
9.4 Extensions of the Power Method……Page 230
9.6 The QR Method for Eigenvalues……Page 232
Convergence Properties of the QR Method……Page 235
9.7 Householder Transformations……Page 236
QR Via Reflections……Page 239
9.8 Hessenberg Form……Page 241
Exercises……Page 242
Programming Exercises……Page 243
PART III Monte Carlo Methods……Page 246
10.1 Quadrature (Numerical Integration)……Page 248
Sample Mean Estimator……Page 250
Output Analysis……Page 251
Central Limit Theorem……Page 252
Parallelizing Quadrature……Page 254
Exercises……Page 257
Programming Exercises……Page 258
11.1 Monte Carlo Methods for Optimization……Page 259
Retention and Acceleration……Page 261
11.2 IIP Parallel Search……Page 264
11.3 Simulated Annealing……Page 266
Cooling Schedules……Page 267
Application of SA to the Traveling Salesman Problem……Page 268
11.4 Genetic Algorithms……Page 270
A GA for the Permanent Problem……Page 272
11.5 Iterated Improvement Plus Random Restart……Page 273
Programming Exercises……Page 277
Appendix: Programming Examples……Page 280
MPI Examples……Page 282
Fork Example……Page 285
LAN Example……Page 290
Threads Example……Page 295
SGI Example……Page 297
References……Page 300
Index……Page 301