The Bulk Synchronous Parallel model

The BSP model is a bridging model originally proposed by L. Valiant [1]. Intended to be employed for distributed-memory computing, the model assumes a BSP machine consists of p identical processors, which can execute r floating point operations per second. Each processor has access to its own local memory. These processors can communicate with each other through an all-to-all network, providing uniform point-to-point access times and bandwidth capacity:

A BSP algorithm consists of an arbitrary number of supersteps. During supersteps, no communication between processors may occur. All processors synchronise between supersteps: processors wait until every processor is done with the superstep, before executing the next superstep. Communication is performed in bulk during synchronisations. A schematic view of four processors is included below; the vertical axis corresponds to run-time, and only two supersteps are shown.

The time to synchronise all processors is modelled as l. The time between sending a data word from one processor to another is denoted by g, which is proportional to the inverse of the bandwidth. A BSP machine thus is completely modeled by the parameters (p,r,g,l), and using these parameters the execution time of any BSP algorithm can be completely characterised.

Using the model does not require the use of a BSP programming interface such as MulticoreBSP; BSP-style algorithms may be implemented in any parallel programming language. Specialised BSP libraries give designers a unified way for expressing algorithms, however, while the vendors of parallel computers can supply efficient BSP libraries.

[1] L. G. Valiant, A bridging model for parallel computation, Commun. ACM, 33(8), 1990; pp. 103–111.