Introduction to Parallel Computing

In the last few years, courses on parallel computation have been developed and offered in many institutions in the UK, Europe and US as a recognition of the growing significance of this topic in mathematics and computer science. There is a clear need for texts that meet the needs of studentsand lecturers and this book, based on the author's lecture at ETH Zurich, is an ideal practical student guide to scientific computing on parallel computers working up from a hardware instruction level, to shared memory machines, and finally to distributed memory machines.Aimed at advanced undergraduate and graduate students in applied mathematics, computer science, and engineering, subjects covered include linear algebra, fast Fourier transform, and Monte-Carlo simulations, including examples in C and, in some cases, Fortran. This book is also ideal forpractitioners and programmers.

List of Figures

xv

List of Tables

xvii

1 BASIC ISSUES

1

(17)

1.1 Memory

1

(4)

1.2 Memory systems

5

(10)

1.2.1 Cache designs

5

(3)

1.2.2 Pipelines, instruction scheduling, and loop unrolling

8

(7)

1.3 Multiple processors and processes

15

(1)

1.4 Networks

15

(3)

2 APPLICATIONS

18

(67)

2.1 Linear algebra

18

(3)

2.2 LAPALK and the BLAS

21

(7)

2.2.1 Typical performance numbers for the BLAS

22

(1)

2.2.2 Solving systems of equations with LAPALK

23

(5)

2.3 Linear algebra: sparse matrices, iterative methods

28

(21)

2.3.1 Stationary iterations

29

(1)

2.3.2 Jacobi iteration

30

(1)

2.3.3 Gauss-Seidel (GS) iteration

31

(1)

2.3.4 Successive and symmetric successive overrelaxation

31

(3)

2.3.5 Krylov subspace methods

34

(1)

2.3.6 The generalized minimal residual method (GMRES)

34

(2)

2.3.7 The conjugate gradient (CG) method

36

(3)

2.3.8 Parallelization

39

(1)

2.3.9 The sparse matrix vector product

39

(3)

2.3.10 Preconditioning and parallel preconditioning

42

(7)

2.4 Fast Fourier Transform (FFT)

49

(8)

2.4.1 Symmetries

55

(2)

2.5 Monte Carlo (MC) methods

57

(28)

2.5.1 Random numbers and independent streams

58

(2)

2.5.2 Uniform distributions

60

(4)

2.5.3 Non-uniform distributions

64

(21)

3 SIMD, SINGLE INSTRUCTION MULTIPLE DATA

85

(51)

3.1 Introduction

85

(1)

3.2 Data dependencies and loop unrolling

86

(19)

3.2.1 Pipelining and segmentation

89

(2)

3.2.2 More about dependencies, scatter/gather operations

91

(1)

3.2.3 Cray SV-1 hardware

92

(4)

3.2.4 Long memory latencies and short vector lengths

96

(1)

3.2.5 Pentium 4 and Motorola G-4 architectures

97

(1)

3.2.6 Pentium 4 architecture

97

(4)

3.2.7 Motorola G-4 architecture

101

(1)

3.2.8 Branching and conditional execution

102

(3)

3.3 Reduction operations, searching

105

(1)

3.4 Some basic linear algebra examples

106

(4)

3.4.1 Matrix multiply

106

(1)

3.4.2 SGEFA: The Linpack benchmark

107

(3)

3.5 Recurrence formulae, polynomial evaluation

110

(16)

3.5.1 Polynomial evaluation

110

(2)

3.5.2 A single tridiagonal system

112

(2)

3.5.3 Solving tridiagonal systems by cyclic reduction.

114

(3)

3.5.4 Another example of non-unit strides to achieve parallelism

117

(5)

3.5.5 Some examples from Intel SSE and Motorola Altivec

122

(1)

3.5.6 SDOT on G-4

123

(1)

3.5.7 ISAMAX on Intel using SSE

124

(2)

3.6 FFT on SSE and Altivec

126

(10)

4 SHARED MEMORY PARALLELISM

136

(20)

4.1 Introduction

136

(1)

4.2 HP9000 Superdome machine

136

(1)

4.3 Cray X1 machine

137

(2)

4.4 NEC SX-6 machine

139

(1)

4.5 OpenMP standard

140

(1)

4.6 Shared memory versions of the BLAS and LAPACK

141

(1)

4.7 Basic operations with vectors

142

(4)

4.7.1 Basic vector operations with OpenMP

143

(3)

4.8 OpenMP matrix vector multiplication

146

(6)

4.8.1 The matrix-vector multiplication with OpenMP

147

(2)

4.8.2 Shared memory version of SGEFA

149

(2)

4.8.3 Shared memory version of FFT

151

(1)

4.9 Overview of OpenMP commands

152

(1)

4.10 Using Libraries

153

(3)

5 MIMD, MULTIPLE INSTRUCTION, MULTIPLE DATA

156

(45)

5.1 MPI commands and examples

158

(3)

5.2 Matrix and vector operations with PBLAS and BLACS

161

(4)

5.3 Distribution of vectors

165

(5)

5.3.1 Cyclic vector distribution

165

(3)

5.3.2 Block distribution of vectors

168

(1)

5.3.3 Block-cyclic distribution of vectors

169

(1)

5.4 Distribution of matrices

170

(1)

5.4.1 Two-dimensional block-cyclic matrix distribution

170

(1)

5.5 Basic operations with vectors

171

(1)

5.6 Matrix-vector multiply revisited

172

(5)

5.6.1 Matrix-vector multiplication with MPI

172

(1)

5.6.2 Matrix-vector multiply with PBLAS

173

(4)

5.7 ScaLAPACK

177

(3)

5.8 MPI two-dimensional FFT example

180

(4)

5.9 MPI three-dimensional FFT example

184

(3)

5.10 MPI Monte Carlo (MC) integration example

187

(3)

5.11 PETSc

190

(4)

5.11.1 Matrices and vectors

191

(2)

5.11.2 Krylov subspace methods and preconditioners

193

(1)

5.12 Some numerical experiments with a PETSc code

194

(7)

APPENDIX A SSE INTRINSICS FOR FLOATING POINT

201

(10)

A.1 Conventions and notation

201

(1)

A.2 Boolean and logical intrinsics

201

(1)

A.3 Load/store operation intrinsics

202

(3)

A.4 Vector comparisons

205

(1)

A.5 Low order scalar in vector comparisons

206

(1)

A.6 Integer valued low order scalar in vector comparisons

206

(1)

A.7 Integer/floating point vector conversions

206

(1)

A.8 Arithmetic function intrinsics

207

(4)

APPENDIX B ALTIVEC INTRINSICS FOR FLOATING POINT

211

(7)

B.1 Mask generating vector comparisons

211

(1)

B.2 Conversion, utility, and approximation functions

212

(1)

B.3 Vector logical operations and permutations

213

(1)

B.4 Load and store operations

214

(1)

B.5 Full precision arithmetic functions on vector operands

215

(1)

B.6 Collective comparisons

216

(2)

APPENDIX C OPENMP COMMANDS

218

(2)

APPENDIX D SUMMARY OF MPI COMMANDS

220

(15)

D.1 Point to point commands

220

(6)

D.2 Collective communications

226

(8)

D.3 Timers, initialization, and miscellaneous

234

(1)

APPENDIX E FORTRAN AND C COMMUNICATION

235

(5)

APPENDIX F GLOSSARY OF TERMS

240

(5)

APPENDIX G NOTATIONS AND SYMBOLS

245

(1)

References

246

(9)

Index

255

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Introduction to Parallel Computing

Summary

Table of Contents

Supplemental Materials