SCIENTIFIC COMPUTING: AN INTRODUCTION WITH PARALLEL COMPUTING

By EMILY HERNANDEZ

CONTENTS BASIC ISSUES MEMORY MEMORY SYSTEMS CACHE DESIGNS PIPELINES, INSTRUCTION SCHEDULING, AND LOOP UNROLLING MULTIPLE PROCESSORS AND PROCESSES NETWORKS APPLICATIONS LINEAR ALGEBRA LAPACK AND THE BLAS TYPICAL PERFORMANCE NUMBERS FOR THE BLAS SOLVING SYSTEMS OF EQUATIONS WITH LAPACK LINEAR ALGEBRA: SPARSE MATRICES, ITERATIVE METHODS STATIONARY ITERATIONS JACOBI ITERATION GAUSS–SEIDEL (GS) ITERATION SUCCESSIVE AND SYMMETRIC SUCCESSIVE OVERRELAXATION KRYLOV SUBSPACE METHODS THE GENERALIZED MINIMAL RESIDUAL METHOD (GMRES) THE CONJUGATE GRADIENT (CG) METHOD PARALLELIZATION THE SPARSE MATRIX VECTOR PRODUCT PRECONDITIONING AND PARALLEL PRECONDITIONING FAST FOURIER TRANSFORM (FFT) SYMMETRIES MONTE CARLO (MC) METHODS RANDOM NUMBERS AND INDEPENDENT STREAMS UNIFORM DISTRIBUTIONS NON-UNIFORM DISTRIBUTIONS SIMD, SINGLE INSTRUCTION MULTIPLE DATA INTRODUCTION DATA DEPENDENCIES AND LOOP UNROLLING PIPELINING AND SEGMENTATION MORE ABOUT DEPENDENCIES, SCATTER/GATHER OPERATIONS CRAY SV-1 HARDWARE LONG MEMORY LATENCIES AND SHORT VECTOR LENGTHS PENTIUM 4 AND MOTOROLA G-4 ARCHITECTURES PENTIUM 4 ARCHITECTURE MOTOROLA G-4 ARCHITECTURE BRANCHING AND CONDITIONAL EXECUTION REDUCTION OPERATIONS, SEARCHING SOME BASIC LINEAR ALGEBRA EXAMPLES MATRIX MULTIPLY SGEFA: THE LINPACK BENCHMARK RECURRENCE FORMULAE, POLYNOMIAL EVALUATION POLYNOMIAL EVALUATION A SINGLE TRIDIAGONAL SYSTEM SOLVING TRIDIAGONAL SYSTEMS BY CYCLIC REDUCTION ANOTHER EXAMPLE OF NON-UNIT STRIDES TO ACHIEVE PARALLELISM SOME EXAMPLES FROM INTEL SSE AND MOTOROLA ALTIVEC ISAMAX ON INTEL USING SSE FFT ON SSE AND ALTIVEC SHARED MEMORY PARALLELISM HP9000 SUPERDOME MACHINE CRAY X1 MACHINE NEC SX-6 MACHINE OPENMP STANDARD SHARED MEMORY VERSIONS OF THE BLAS AND LAPACK BASIC OPERATIONS WITH VECTORS BASIC VECTOR OPERATIONS WITH OPENMP OPENMP MATRIX VECTOR MULTIPLICATION THE MATRIX–VECTOR MULTIPLICATION WITH OPENMP SHARED MEMORY VERSION OF SGEFA SHARED MEMORY VERSION OF FFT OVERVIEW OF OPENMP COMMANDS 4 10 USING LIBRARIES MIMD, MULTIPLE INSTRUCTION, MULTIPLE DATA MPI COMMANDS AND EXAMPLES MATRIX AND VECTOR OPERATIONS WITH PBLAS AND BLACS DISTRIBUTION OF VECTORS CYCLIC VECTOR DISTRIBUTION BLOCK DISTRIBUTION OF VECTORS BLOCK–CYCLIC DISTRIBUTION OF VECTORS DISTRIBUTION OF MATRICES TWO-DIMENSIONAL BLOCK–CYCLIC MATRIX DISTRIBUTION MATRIX–VECTOR MULTIPLY REVISITED MATRIX–VECTOR MULTIPLICATION WITH MPI MATRIX–VECTOR MULTIPLY WITH PBLAS SCALAPACK MPI TWO-DIMENSIONAL FFT EXAMPLE MPI THREE-DIMENSIONAL FFT EXAMPLE 5 10 MPI MONTE CARLO (MC) INTEGRATION EXAMPLE 5 11 PETSC MATRICES AND VECTORS KRYLOV SUBSPACE METHODS AND PRECONDITIONERS 5 12 SOME NUMERICAL EXPERIMENTS WITH A PETSC CODE