Decomposable BSP: a bandwidth-latency model for parallel and hierarchical computation

This chapter describes the Decomposable Bulk Synchrounous Parallel (D-BSP) model of computation, as a framework for the design and the analysis of algorithms that can be executed efficiently on physical machines. A number of D-BSP algorithmic results are discussed for basic operations such as broadcast, prefix, sorting, routing, and shared memory simulation. An avenue is proposed to quantitatively define and analize the effectiveness of a model of computation M (the algorithmic model) in a context in which programs are actually executed on a different model M' (the machine model). The effectiveness of D-BSP is evaluated with respect to various processor networks, including multidimensional arrays. Finally, it is shown how the network locality exploited by D-BSP computation can be automatically translated into temporal locality of reference for the memory hierarchy.