Parallel algorithm for the hybrid BSP model

Modern paralllel computers are often organised as a set of nodes, each of which contains a number of cores. Communication and synchronisation within a node is much cheaper than between nodes. The memory is distributed across the nodes, each node having its own memory, but the cores within a node share the memory of that node. Thus, the architecture is a hybrid distributed/shared-memory parallel computer.

The BSP model can be generalised to reflect this architecture, while still keeping much of its simplicity. The result is the hybrid-BSP model, which has two levels in its memory hierarchy. A hybrid-BSP algorithm performs local supersteps (within a node) and global supersteps, each with associated BSP costs.

This video explains the hybrid-BSP model and shows how to use it for parallel sparse matrix-vector multiplication (SpMV). The video also shows how to partition the sparse matrix in two phases, trying to minimise communications cost within a node and between nodes, and tailored to the relative communication costs per data word.

This video corresponds to Section 4.10 of the book Parallel Scientific Computation: A Structured Approach Using BSP, Second Edition, by Rob H. Bisseling, Oxford University Press, 2020.

An expanded set of slides, solutions to the homework questions, and software accompanying the book can all be found on my personal book page: