Introduction to High Performance Scientific Computing

The Von Neumann architecture......Page 7
 Floating point units......Page 9
 Memory Hierarchies......Page 13
 Busses......Page 14
 Latency and Bandwidth......Page 15
 Caches......Page 16
 TLB and virtual memory......Page 22
 Multi-core chips......Page 23
 Cache coherence......Page 25
 Data reuse......Page 26
 Locality......Page 27
 Pipelining......Page 30
 Cache size......Page 32
 TLB......Page 33
 Cache associativity......Page 35
 Loop tiling......Page 36
 Case study: Matrix-vector product......Page 37
 Optimization strategies......Page 39
 Cache aware programming......Page 40
 Introduction......Page 41
 Parallel Computers Architectures......Page 42
 SIMD......Page 43
 MIMD / SPMD computers......Page 45
 Non-Uniform Memory Access......Page 46
 Logically and physically distributed memory......Page 47
 Data parallelism......Page 48
 Task-level parallelism......Page 49
 Thread parallelism......Page 51
 OpenMP......Page 54
 Message passing through MPI......Page 56
 Parallel languages......Page 63
 Latency hiding......Page 68
 Topologies......Page 69
 Some graph theory......Page 70
 Linear arrays and rings......Page 71
 Hypercubes......Page 72
 Switched networks......Page 75
 Theory......Page 78
 Amdahl's law......Page 79
 Scalability......Page 81
 GPU computing......Page 82
 Load balancing......Page 83
 Load balancing as graph problem......Page 84
 Distributed computing, grid computing, cloud computing......Page 85
 The TOP500 List......Page 87
 Integers......Page 88
 Some examples......Page 90
 Limitations......Page 91
 Normalized numbers and machine precision......Page 92
 The IEEE 754 standard for floating point numbers......Page 93
 Representation error......Page 94
 Addition......Page 95
 Subtraction......Page 96
 Examples......Page 97
 Programming languages......Page 99
 Complex numbers......Page 100
 Conclusions......Page 101
 Initial value problems......Page 102
 Error and stability......Page 103
 Finite difference approximation......Page 104
 General PDE theory......Page 108
 The Poisson equation......Page 109
 Discretization......Page 115
 Stability analysis......Page 118
 Elimination of unknowns......Page 120
 Linear algebra in computer arithmetic......Page 122
 Roundoff control during elimination......Page 123
 Influence of roundoff on eigenvalue computations......Page 124
 LU factorization......Page 125
 Uniqueness......Page 126
 Pivoting......Page 127
 Solving the system......Page 129
 Complexity......Page 130
 Block algorithms......Page 131
 Storage of sparse matrices......Page 133
 Sparse matrices and graph theory......Page 137
 LU factorizations of sparse matrices......Page 138
 Iterative methods......Page 141
 Convergence and error analysis......Page 143
 Computational form......Page 144
 Convergence of the method......Page 145
 Choice of K......Page 146
 Stopping tests......Page 148
 Theory of general iterative methods......Page 149
 Iterating by orthogonalization......Page 152
 Coupled recurrence form of iterative methods......Page 153
 The method of Conjugate Gradients......Page 154
 Derivation from minimization......Page 156
 Complexity......Page 157
 Further Reading......Page 159
 Asymptotics......Page 160
 Parallel dense matrix-vector product......Page 162
 Collective operations......Page 165
 Partitioning by rows......Page 167
 Two dimensional partitioning......Page 170
 Parallel sparse matrix-vector product......Page 173
 Parallel efficiency of the sparse matrix-vector product......Page 175
 Setup of the sparse matrix-vector product......Page 176
 Vector operations......Page 177
 Preconditioner construction, storage, and application......Page 178
 Parallelism in the preconditioner......Page 179
 Trouble both ways......Page 183
 Wavefronts......Page 184
 Recursive doubling......Page 185
 Approximating implicit by explicit operations, series expansion......Page 186
 Nested dissection......Page 188
 Block algorithms on multicore architectures......Page 192
 Molecular dynamics......Page 196
 Force Fields......Page 197
 Computing Short-Range Nonbonded Forces......Page 198
 Computing Long-Range Forces......Page 199
 Atom Decompositions......Page 201
 Force Decompositions......Page 202
 Spatial Decompositions......Page 205
 Neutral Territory Methods......Page 206
 Parallel Fast Fourier Transform......Page 207
 Parallel 1-D FFT......Page 208
 Parallel 3-D FFT......Page 209
 Integration for Molecular Dynamics......Page 210
 Integration by statistics......Page 214
Appendices......Page 215
 Theoretical background......Page 216
 Linear algebra......Page 217
 Complexity......Page 221
 Finite State Automatons......Page 222
 Partial Differential Equations......Page 223
 Taylor series......Page 225
 Graph theory......Page 227
 Practical tutorials......Page 230
 Good coding practices......Page 231
 LaTeX for scientific documentation......Page 243
 Unix intro......Page 256
 Compilers and libraries......Page 272
 Managing projects with Make......Page 276
 Source control......Page 288
 Debugging......Page 297
 Scientific Data Storage......Page 301
 Scientific Libraries......Page 309
 Plotting with GNUplot......Page 320
 Programming languages......Page 323
 Class project......Page 327
 Heat equation......Page 328
 Cache size......Page 330
 Cachelines......Page 332
 Cache associativity......Page 334
 TLB......Page 336
 Index and list of acronyms......Page 344