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.
Author(s): Ronald W. Shonkwiler, Lew Lefton
Series: Cambridge Texts in Applied Mathematics
Edition: 1
Publisher: Cambridge University Press
Year: 2006
Language: English
Pages: 306
Cover......Page 1
Half-title......Page 3
Series-title......Page 5
Title......Page 7
Copyright......Page 8
Contents......Page 9
Preface......Page 13
Acknowlegments......Page 17
PART I Machines and Computation......Page 19
1 Introduction – The Nature of High-Performance Computation......Page 21
1.1 Computing Hardware Has Undergone Vast Improvement......Page 22
The von Neumann Computer......Page 23
Operation of a von Neumann Computer: c = a + b Walk-Through......Page 25
Parallel Computing Hardware – Flynn’s Classification......Page 26
Operation of a Vector Computer – Assembly-Line Processing......Page 27
Hockney’s Formulas......Page 29
The “Jiffy-Lube” Model......Page 32
1.4 Classification of Distributed Memory Computers......Page 34
Communication Links and Delays......Page 35
Mesh......Page 36
LAN......Page 37
1.5 Amdahl’s Law and Profiling......Page 38
Exercises......Page 41
Programming Exercises......Page 44
A Directed Acyclic Graph Defines a Computation......Page 45
A Schedule......Page 49
Speedup and Efficiency......Page 50
Reduction......Page 51
Recursive Doubling......Page 52
Matrix Powers......Page 54
2.3 Data Dependencies......Page 55
Induction Variable......Page 56
Forward Dependency......Page 57
Run-Time Break......Page 58
Exercises......Page 59
3 Machine Implementations......Page 62
The Fork Operation......Page 63
Barriers......Page 65
Mutexes......Page 66
3.2 Threads Programming......Page 68
Mutexes, Barriers, and Condition Variables......Page 69
Condition Variables......Page 73
3.3 Java Threads......Page 74
Two Styles of Threaded Programming......Page 75
Every Object Has a Mutex......Page 77
Condition Variables Are Keyed to wait() and notify()......Page 79
3.4 SGI Threads and OpenMP......Page 81
DOACROSS Style Parallelization......Page 82
Introduction to Message Passing......Page 85
Nonblocking Communications and Other Features of MPI......Page 92
Matrix Product Source Code in C......Page 95
Writing Vector Code......Page 98
Chaining......Page 100
Instruction Buffering......Page 101
Vector Dependencies......Page 102
ABC test......Page 103
Programming Aids......Page 104
3.7 Quantum Computation Qubits......Page 107
Superposition of States – Quantum Reality......Page 109
Adding More Qubits......Page 110
Entanglement......Page 111
Quantum Computation......Page 112
Shor’s Algorithm to Break an RSA Code in Polynomial Time......Page 114
Exercises......Page 115
Programming Exercises......Page 116
PART II Linear Systems......Page 119
4 Building Blocks – Floating Point Numbers and Basic Linear Algebra......Page 121
4.1 Floating Point Numbers and Numerical Error......Page 122
Floating Point Numbers......Page 123
Density of Floating Point Numbers and Round-off Error......Page 126
Subtracting Numbers About the Same Size......Page 128
Condition......Page 129
Scalar–Vector Product......Page 131
Sum of n Matrices, Each m × m......Page 132
Matrix–Vector multiply......Page 133
Matrix–Matrix Multiply, i jk-Forms......Page 135
Inner-Product Model, Forms i jk and jik......Page 136
Middle-Product Model, Forms ikj and jki......Page 137
4.4 Operations with Banded Matrices......Page 138
Banded Matrix–Vector Product by Diagonals......Page 139
Tridiagonal Matrix–Matrix Product......Page 140
Exercises......Page 142
Programming Exercises......Page 143
5.1 Triangular Systems......Page 144
Lower Triangular Systems – Forward Substitution......Page 145
Looping Notation......Page 148
Upper-Triangular Systems – Back Substitution......Page 149
Parallel Considerations for Triangular Systems......Page 150
A Surprising Matrix Solution......Page 151
5.2 Gaussian Elimination......Page 152
Elementary Row Operations......Page 153
Gaussian Elimination – LU Decomposition......Page 154
Row Interchanges......Page 158
Pivoting......Page 164
Total Pivoting......Page 166
5.3 i jk-Forms for LU Decomposition......Page 168
ki j-Form......Page 169
jki-Form......Page 170
jik-Form......Page 172
5.4 Bordering Algorithm for LU Decomposition......Page 173
5.5 Algorithm for Matrix Inversion in log2n Time......Page 174
Exercises......Page 176
Programming Exercises......Page 179
6.1 Tridiagonal Systems – Thompson’s Algorithm......Page 180
6.2 Tridiagonal Systems – Odd–Even Reduction......Page 181
Parallel Considerations......Page 183
6.3 Symmetric Systems – Cholesky Decomposition......Page 184
Exercises......Page 188
Programming Exercises......Page 189
7.1 Error and Residual – Matrix Norms......Page 190
The Size of Vectors and Matrices......Page 192
Condition Number......Page 194
Step-by-Step Error in the Elimination Process......Page 197
7.2 Givens Rotations......Page 198
Parallel Implementation......Page 200
Orthogonal Basis......Page 201
Exercises......Page 202
Programming Exercises......Page 203
8.1 Jacobi Iteration or the Method of Simultaneous Displacements......Page 204
8.2 Gauss–Seidel Iteration or the Method of Successive Displacements......Page 207
8.3 Fixed-Point Iteration......Page 209
8.4 Relaxation Methods......Page 211
8.5 Application to Poisson’s Equation......Page 212
8.6 Parallelizing Gauss–Seidel Iteration......Page 216
8.7 Conjugate Gradient Method......Page 218
Exercises......Page 222
Programming Exercises......Page 223
9.1 Eigenvalues and Eigenvectors......Page 224
9.2 The Power Method......Page 227
9.3 Jordan Cannonical Form......Page 228
9.4 Extensions of the Power Method......Page 233
9.6 The QR Method for Eigenvalues......Page 235
Convergence Properties of the QR Method......Page 238
9.7 Householder Transformations......Page 239
QR Via Reflections......Page 242
9.8 Hessenberg Form......Page 244
Exercises......Page 245
Programming Exercises......Page 246
PART III Monte Carlo Methods......Page 249
10.1 Quadrature (Numerical Integration)......Page 251
Sample Mean Estimator......Page 253
Output Analysis......Page 254
Central Limit Theorem......Page 255
Parallelizing Quadrature......Page 257
Exercises......Page 260
Programming Exercises......Page 261
11.1 Monte Carlo Methods for Optimization......Page 262
Retention and Acceleration......Page 264
11.2 IIP Parallel Search......Page 267
11.3 Simulated Annealing......Page 269
Cooling Schedules......Page 270
Application of SA to the Traveling Salesman Problem......Page 271
11.4 Genetic Algorithms......Page 273
A GA for the Permanent Problem......Page 275
11.5 Iterated Improvement Plus Random Restart......Page 276
Programming Exercises......Page 280
Appendix: Programming Examples......Page 283
MPI Examples......Page 285
Fork Example......Page 288
LAN Example......Page 293
Threads Example......Page 298
SGI Example......Page 300
References......Page 303
Index......Page 304
