INTRODUCTION TO PARALLEL COMPUTING
1 BASIC ISSUES 1 11 Memory 1 12 Memory systems 5 121 Cache designs 5 122 Pipelines, instruction scheduling, and loop unrolling 8 13 Multiple processors and processes 15 14 Networks 15 2 APPLICATIONS 18 21 Linear algebra 18 22 LAPACK and the BLAS 21 221 Typical performance numbers for the BLAS 22 222 Solving systems of equations with LAPACK 23 23 Linear algebra: sparse matrices, iterative methods 28 231 Stationary iterations 29 232 Jacobi iteration 30 233 Gauss–Seidel (GS) iteration 31 234 Successive and symmetric successive overrelaxation 31 235 Krylov subspace methods 34 236 The generalized minimal residual method (GMRES) 34 237 The conjugate gradient (CG) method 36 238 Parallelization 39 239 The sparse matrix vector product 39 2310 Preconditioning and parallel preconditioning 42 24 Fast Fourier Transform (FFT) 49 241 Symmetries 55 25 Monte Carlo (MC) methods 57 251 Random numbers and independent streams 58 252 Uniform distributions 60 253 Non-uniform distributions 64 3 SIMD, SINGLE INSTRUCTION MULTIPLE DATA 85 31 Introduction 85 32 Data dependencies and loop unrolling 86 321 Pipelining and segmentation 89 322 More about dependencies, scatter/gather operations 91 323 Cray SV-1 hardware 92 324 Long memory latencies and short vector lengths 96 325 Pentium 4 and Motorola G-4 architectures 97 326 Pentium 4 architecture 97 327 Motorola G-4 architecture 101 328 Branching and conditional execution 102 33 Reduction operations, searching 105 34 Some basic linear algebra examples 106 341 Matrix multiply 106 342 SGEFA: The Linpack benchmark 107 35 Recurrence formulae, polynomial evaluation 110 351 Polynomial evaluation 110 352 A single tridiagonal system 112 353 Solving tridiagonal systems by cyclic reduction 114 354 Another example of non-unit strides to achieve parallelism 117 355 Some examples from Intel SSE and Motorola Altivec 122 356 SDOT on G-4 123 357 ISAMAX on Intel using SSE 124 36 FFT on SSE and Altivec 126 4 SHARED MEMORY PARALLELISM 136 41 Introduction 136 42 HP9000 Superdome machine 136 43 Cray X1 machine 137 44 NEC SX-6 machine 139 45 OpenMP standard 140 46 Shared memory versions of the BLAS and LAPACK 141 47 Basic operations with vectors 142 471 Basic vector operations with OpenMP 143 48 OpenMP matrix vector multiplication 146 481 The matrix–vector multiplication with OpenMP 147 482 Shared memory version of SGEFA 149 483 Shared memory version of FFT 151 49 Overview of OpenMP commands 152 410 Using Libraries 153 5 MIMD, MULTIPLE INSTRUCTION, MULTIPLE DATA 156 51 MPI commands and examples 158 52 Matrix and vector operations with PBLAS and BLACS 161 53 Distribution of vectors 165 531 Cyclic vector distribution 165 532 Block distribution of vectors 168 533 Block–cyclic distribution of vectors 169 54 Distribution of matrices 170 541 Two-dimensional block–cyclic matrix distribution 170 55 Basic operations with vectors 171 56 Matrix–vector multiply revisited 172 561 Matrix–vector multiplication with MPI 172 562 Matrix–vector multiply with PBLAS 173 57 ScaLAPACK 177 58 MPI two-dimensional FFT example 180 59 MPI three-dimensional FFT example 184 510 MPI Monte Carlo (MC) integration example 187 511 PETSc 190 5111 Matrices and vectors 191 5112 Krylov subspace methods and preconditioners 193 512 Some numerical experiments with a PETSc code 194