Parallel Scientific Computation: A Structured Approach using BSP and MPI

✍ Scribed by Rob H. Bisseling

• Publisher: Oxford University Press, USA
• Year: 2004
• Tongue: English
• Leaves: 324
• Category: Library

✦ Synopsis

Based on the author's extensive development, this is the first text explaining how to use BSPlib, the bulk synchronous parallel library, which is freely available for use in parallel programming. Aimed at graduate students and researchers in mathematics, physics and computer science, the main topics treated in the book are core in the area of scientific computation and many additional topics are treated in numerous exercises. An appendix on the message-passing interface (MPI) discusses how to program using the MPI communication library. MPI equivalents of all the programs are also presented. The main topics treated in the book are core in the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems, by iterative methods. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its analysis to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Additional topics treated in the exercises include: data compression, random number generation, cryptography, eigensystem solving, 3D and Strassen Matrix multiplication, wavelets and image compression, fast cosine transform, decimals of pi, simulated annealing and molecular dynamics. This book contains five small but complete example programs written in BSPlib which illustrates the methods taught. The appendix on MPI discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library. It presents MPI equivalents of all the programs in the book. The complete programs of the book and their driver programs are freely available online in packages called BSPedupack and MPIedupack.

✦ Table of Contents

0198529392......Page 1
Contents......Page 18
1.1 Wanted: a gentle parallel programming model......Page 20
1.2 The BSP model......Page 22
1.3 BSP algorithm for inner product computation......Page 28
1.4 Starting with BSPlib: example program bspinprod......Page 32
1.5 BSP benchmarking......Page 43
1.6 Example program bspbench......Page 46
1.7 Benchmark results......Page 50
1.8.1 BSP-related models of parallel computation......Page 57
1.8.2 BSP libraries......Page 59
1.8.3 The non-BSP world: message passing......Page 61
1.8.4 Benchmarking......Page 62
1.9 Exercises......Page 63
2.1 The problem......Page 69
2.2 Sequential LU decomposition......Page 70
2.3 Basic parallel algorithm......Page 76
2.4 Two-phase broadcasting and other improvements......Page 83
2.5 Example function bsplu......Page 91
2.6 Experimental results on a Cray T3E......Page 98
2.7.1 Matrix distributions......Page 104
2.7.3 Parallel matrix computations......Page 106
2.8 Exercises......Page 107
3.1 The problem......Page 119
3.2 Sequential recursive fast Fourier transform......Page 122
3.3 Sequential nonrecursive algorithm......Page 124
3.4 Parallel algorithm......Page 132
3.5 Weight reduction......Page 139
3.6 Example function bspfft......Page 146
3.7 Experimental results on an SGI Origin 3800......Page 155
3.8.1 Sequential FFT algorithms......Page 164
3.8.2 Parallel FFT algorithms with log[sub(2)]p or more supersteps......Page 166
3.8.3 Parallel FFT algorithms with O(1) supersteps......Page 167
3.8.4 Applications......Page 170
3.9 Exercises......Page 171
4.1 The problem......Page 182
4.2 Sparse matrices and their data structures......Page 186
4.3 Parallel algorithm......Page 192
4.4 Cartesian distribution......Page 198
4.5 Mondriaan distribution for general sparse matrices......Page 205
4.6 Vector distribution......Page 216
4.7 Random sparse matrices......Page 222
4.8 Laplacian matrices......Page 229
4.9 Remainder of BSPlib: example function bspmv......Page 241
4.10 Experimental results on a Beowulf cluster......Page 250
4.11.1 Sparse matrix computations......Page 254
4.11.2 Parallel sparse matrix–vector multiplication algorithms......Page 256
4.11.3 Parallel iterative solvers for linear systems......Page 258
4.11.4 Partitioning methods......Page 259
4.12 Exercises......Page 262
A.2 Utility file bspedupack.c......Page 270
B: A quick reference guide to BSPlib......Page 273
C.1 The message-passing interface......Page 275
C.2.1 Program mpiinprod......Page 277
C.2.2 Program mpibench......Page 280
C.2.3 Function mpilu......Page 284
C.2.4 Function mpifft......Page 289
C.2.5 Function mpimv......Page 292
C.3 Performance comparison on an SGI Origin 3800......Page 297
C.4 Where BSP meets MPI......Page 299
References......Page 302
B......Page 318
D......Page 319
G......Page 320
M......Page 321
N......Page 322
R......Page 323
W......Page 324