finelybook
Parallel Scientific Computation: A Structured Approach Using BSP (Second Edition)
by 作者: Rob H. Bisseling
Publisher Finelybook 出版社: Oxford University Press
Publication date (UK): September 30,2020
pages 页数: 416 pages
ISBN-10 书号: 0198788355
ISBN-13 书号: 9780198788355
Publisher Finelybook 出版社: OUP Oxford; 2nd edition (30 Sept. 2020)
Language 语言: English
Book 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.
Slides
These class-tested slides are supplementary to the main text of the book. Each lecture corresponds to one section (or a few) of the book which takes about 45 min. It is given as a PDF file. The slides have been written in LaTeX/Beamer with most figures produced by TikZ or Gnuplot. If you are a teacher and want to use the slides,but would like to modify them,for instance to turn my jokes into better ones,then please send me an email and I will provide the sources. All lectures have been updated in 2020.
1.1 The Bulk Synchronous Parallel Model
1.3 Parallel Inner Product Computation
1.4 Starting with BSPlib
1.5-1.7 BSP Benchmarking
1.8 Sorting
1.9 Bulk Synchronous Message Passing: bspsort
1.10 Experimental Results for Samplesort on Cartesius
2.1-2.2 Sequential LU Decomposition
2.3 Parallel LU Decomposition
2.4 Two-phase Broadcasting
2.5 High-Performance LU Decomposition
2.6-2.7 Experiments with bsplu
3.1-3.2 Sequential Fast Fourier Transform
3.3 Sequential Nonrecursive FFT
3.4 Parallel Fast Fourier Transform
3.5 Weights for the FFT
3.6 Program bspfft
3.7 Experimental results for the FFT
4.1 Sequential Sparse Matrix-Vector Multiplication
4.2 Sparse Matrices and Their Data Structures
4.3 Parallel Sparse Matrix-Vector Multiplication
4.4 Cartesian Matrix Distribution
4.5 Mondriaan Sparse Matrix Distribution
4.6 Fine-Grain and Medium-Grain Matrix Distribution
4.7 Vector distribution
4.8 Random Sparse Matrices
4.9 Laplacian Matrices
4.10 Parallel algorithm for hybrid-BSP
4.11 Program bspmv
4.12 Experimental results on Cartesius
5.1-5.2 Sequential Graph Matching
5.3 Suitors and Sorting
5.4 Parallel Graph Matching
5.5 Correctness
5.6-5.7 Tie-breaking and Load Balancing
5.8 Further improvements
Lectures for sections 5.9 and 5.10 will be added here during Fall 2020
