Abstract: This book explains the use of the bulk synchronous parallel (BSP) model and the BSPlib communication library in parallel algorithm design and parallel programming. The main topics treated in the book are central to the area of scientific computation: solving dense linear systems by Gaussian elimination, computing fast Fourier transforms, and solving sparse linear systems by iterative methods based on sparse matrix-vector multiplication. Each topic is treated in depth, starting from the problem formulation and a sequential algorithm, through a parallel algorithm and its cost analysis, to a complete parallel program written in C and BSPlib, and experimental results obtained using this program on a parallel computer. Throughout the book, emphasis is placed on analyzing the cost of the parallel algorithms developed, expressed in three terms: computation cost, communication cost, and synchronization cost. The book contains five example programs written in BSPlib, which illustrate the methods taught. These programs are freely available as the package BSPedupack. An appendix on the message-passing interface (MPI) discusses how to program in a structured, bulk synchronous parallel style using the MPI communication library, and presents MPI equivalents of all the programs in the book.

Keywords: bulk synchronous parallel, communication, fast Fourier transform, linear system, message-passing interface, parallel algorithm, parallel programming, sparse matrix-vector multiplication