Parallel Scientific Computation: A Structured Approach Using BSP

Description

Building upon the wide-ranging success of the first edition, Parallel Scientific Computation presents a single unified approach to using a range of parallel computers, from a small desktop computer to a massively parallel computer. The author explains how to use the bulk synchronous parallel (BSP) model to design and implement parallel algorithms in the areas of scientific computing and big data, and provides a full treatment of core problems in these areas, starting from a high-level problem description, via a sequential solution algorithm to a parallel solution algorithm and an actual parallel program written in BSPlib. Every chapter of the book contains a theoretical section and a practical section presenting a parallel program and numerical experiments on a modern parallel computer to put the theoretical predictions and cost analysis to the test. Every chapter also presents extensive bibliographical notes with additional discussions and pointers to relevant literature, and numerous exercises which are suitable as graduate student projects. The second edition provides new material relevant for big-data science such as sorting and graph algorithms, and it provides a BSP approach towards new hardware developments such as hierarchical architectures with both shared and distributed memory. A single, simple hybrid BSP system suffices to handle both types of parallelism efficiently, and there is no need to master two systems, as often happens in alternative approaches. Furthermore, the second edition brings all algorithms used up to date, and it includes new material on high-performance linear system solving by LU decomposition, and improved data partitioning for sparse matrix computations. The book is accompanied by a software package BSPedupack, freely available online from the author's homepage, which contains all programs of the book and a set of test driver programs. This package written in C can be run using modern BSPlib implementations such as MulticoreBSP for C or BSPonMPI. Cover Parallel Scientific Computation: A Structured Approach Using BSP Copyright PREFACE ACKNOWLEDGEMENTS ABOUT THE AUTHOR CONTENTS 1 Introduction 1.1 Parallel computing is everywhere 1.2 The BSPmodel 1.3 BSP algorithm for inner product computation 1.4 Starting with BSPlib: example program bspinprod 1.5 BSP benchmarking 1.6 Example programbspbench 1.7 Benchmark results 1.8 Sorting 1.9 Example function bspsort 1.10 Experimental results for samplesort on a Cartesius node 1.11 Bibliographic notes 1.11.1 BSP-related models of parallel computation 1.11.2 BSP libraries 1.11.3 The non-BSP world: message passing and threads 1.11.4 Benchmarking 1.11.5 Sorting 1.12 exercises 2 LU decomposition 2.1 The problem 2.2 Sequential LU decomposition 2.3 Basic parallel algorithm 2.4 Two-phase broadcasting and other improvements 2.5 High-performance LU decomposition 2.6 Example function bsplu 2.7 Experimental results on the Cori supercomputer 2.8 Bibliographic notes 2.8.1 Matrix distributions 2.8.2 Collective communication 2.8.3 Parallel matrix computations 2.9 exercises 3 The fast Fourier transform 3.1 The problem 3.2 Sequential recursive fast Fourier transform 3.3 Sequential nonrecursive algorithm 3.4 Parallel algorithm 3.5 Weight reduction 3.6 Example function bspfft 3.7 Experimental results on the Cartesius supercomputer 3.8 Bibliographic notes 3.8.1 Sequential FFT algorithms 3.8.2 Parallel FFT algorithms 3.8.3 Applications 3.9 exercises 4 Sparse matrix–vector multiplication 4.1 The problem 4.2 Sparsematrices and their data structures 4.3 Parallel algorithm 4.4 Cartesianmatrix distribution 4.5 Mondriaan distribution for general sparsematrices 4.6 Fine-grain and medium-grainmatrix distribution 4.7 Vector distribution 4.8 Random sparsematrices 4.9 Laplacian matrices 4.10 Parallel algorithm for hybrid-BSP 4.11 Example function bspmv 4.12 Experimental results on the Cartesius supercomputer 4.13 Bibliographic notes 4.13.1 Sparse matrix computations 4.13.2 Parallel sparse matrix–vector multiplication algorithms 4.13.3 Partitioning methods 4.14 exercises 5 Graph matching 5.1 The problem 5.2 Sequential algorithm 5.3 Suitors and sorting 5.4 Parallel algorithm 5.5 Correctness 5.6 Tie-breaking 5.7 Load balancing 5.8 Further improvements 5.9 Example function bspmatch 5.10 Experimental results on the Cartesius supercomputer 5.11 Bibliographic notes 5.11.1 Sequential graph matching 5.11.2 Parallel graph matching 5.11.3 GraphBLAS 5.12 exercises APPENDIX A: AUXILIARY BSPEDUPACK FUNCTIONS A.1 Header file bspedupack.h A.2 Utility file bspedupack.c APPENDIX B: A QUICK REFERENCE GUIDE TO BSPLIB REFERENCES INDEX