Conference graph

The Bulk Synchronous Parallel (BSP) abstract computer is a bridging model for designing parallel algorithms. It serves a purpose similar to the Parallel Random Access Machine (PRAM) model. BSP differs from PRAM by not taking communication and synchronization for granted. An important part of analysing a BSP algorithm rests on quantifying the synchronisation and communication needed.

The BSP model was developed by Leslie Valiant of Harvard University during the 1980s. The definitive article was published in 1990.

Between 1990 and 1992, Leslie Valiant and Bill McColl of Oxford University worked on ideas for a distributed memory BSP programming model, in Princeton and at Harvard. Between 1992 and 1997, McColl led a large research team at Oxford that developed various BSP programming libraries, languages and tools, and also numerous massively parallel BSP algorithms. With interest and momentum growing, in 1996 McColl then led a group from Oxford, Harvard, Florida, Princeton, Bell Labs, Columbia and Utrecht that developed and published the BSPlib Standard for BSP programming.

The model

A BSP computer consists of processors connected by a communication network. Each processor has a fast local memory, and may follow different threads of computation. A BSP computation proceeds in a series of global supersteps. A superstep consists of three components:

1. Concurrent computation: Several computations take place on every participating processor. Each process only uses values stored in the local memory of the processor. The computations are independent in the sense that they occur asynchronously of all the others.
2. Communication: The processes exchange data between themselves. This exchange takes the form of one-sided put and get calls, rather than two-sided send and receive calls.
3. Barrier synchronisation: When a process reaches this point (the barrier), it waits until all other processes have finished their communication actions.

The computation and communication actions do not have to be ordered in time. The barrier synchronization concludes the superstep: it has the function of ensuring that all one-sided communications are properly concluded. This global synchronization is not needed in models based on two-sided communication, since these synchronize processes implicitly.

The figure below shows this in a diagrammatic form. The processes are not regarded as having a particular linear order (from left to right or otherwise), and may be mapped to processors in any way.

A further aspect of the BSP model is that of overdecomposition of the problem and oversubscription of the processors: the problem is divided into more logical processes than there are physical processors, and processes are randomly assigned to processors. This strategy can be shown statistically to lead to almost perfectly load balancing, both of work and communication.

Communication

In many parallel programming systems, communications are considered at the level of individual actions: sending and receiving a message, memory to memory transfer, etc. This is difficult to work with, since there are many simultaneous communication actions in a parallel program, and their interactions are typically complex. In particular, it is difficult to say much about the time any single communication action will take to complete.

The BSP model considers communication actions en masse. This has the effect that an upper bound on the time taken to communicate a set of data can be given. BSP considers all communication actions of a superstep as one unit, and assumes all messages have a fixed size.

The maximum number of incoming or outgoing messages for a superstep is denoted by $h$. The ability of a communication network to deliver data is captured by a parameter $g$, defined such that it takes time $hg$ for a processor to deliver $h$ messages of size 1.

A message of length $m$ obviously takes longer to send than a message of size 1. However, the BSP model does not make a distinction between a message length of $m$ or $m$ messages of length 1. In either case the cost is said to be $mg$.

The parameter $g$ is dependent on the following factors:

• The protocols used to interact within the communication network.
• Buffer management by both the processors and the communication network.
• The routing strategy used in the network.
• The BSP runtime system.

A value for $g$ is, in practice, determined empirically for each parallel computer. Note that $g$ is not the normalised single-word delivery time, but the single-word delivery time under continuous traffic conditions.

Barriers

The one-sided communication of the BSP model requires a global barrier synchronization. Barriers are potentially costly, but have a number of attractions. They do not introduce the possibility of deadlock or livelock, since barriers do not create circular data dependencies. Therefore tools to detect and deal with them are unnecessary. Barriers also permit novel forms of fault tolerance.

The cost of barrier synchronization is influenced by a couple of issues:

1. The cost imposed by the variation in the completion time of the participating concurrent computations. Take the example where all but one of the processes have completed their work for this superstep, and are waiting for the last process, which still has a lot of work to complete. The best that an implementation can do is ensure that each process works on roughly the same problem size.
2. The cost of reaching a globally consistent state in all of the processors. This depends on the communication network, but also on whether there is special-purpose hardware available for synchronizing, and on the way in which interrupts are handled by processors.

The cost of a barrier synchronization is denoted by $l$. In practice, a value of $l$ is determined empirically.

The presence of barriers makes the BSP model mostly a theoretical one: on large computers barriers are expensive, and this is increasingly so on large scales. In fact, there is a large body of literature on removing synchronization points from existing algorithms.

The Cost of a BSP algorithm

The cost of a superstep is determined as the sum of three terms; the cost of the longest running local computation, the cost of global communication between the processors, and the cost of the barrier synchronisation at the end of the superstep. The cost of one superstep for $p$ processors:

$max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l$ where $w_{i}$ is the cost for the local computation in process $i$, and $h_{i}$ is the number of messages sent or received by process $i$. Note that homogeneous processors are assumed here. It is more common for the expression to be written as $w+hg+l$ where $w$ and $h$ are maxima. The cost of the algorithm then, is the sum of the costs of each superstep.

$W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl$ where $S$ is the number of supersteps.

$W$, $H$, and $S$ are usually modelled as functions, that vary with problem size. These three characteristics of a BSP algorithm are usually described in terms of asymptotic notation, e.g. $H\in O(n/p)$.

Extensions and uses

Interest in BSP has soared in recent years, with Google adopting it as a major technology for graph analytics at massive scale (Pregel). Also, with the next generation of Hadoop decoupling the MapReduce model from the rest of the Hadoop infrastructure, there is now some open source projects to add BSP and other high performance parallel programming models on top of Hadoop, such as Apache Hama and Apache Giraph.

BSP has been extended by many authors to address concerns about BSP's unsuitability for modelling specific architectures or computational paradigms. One example of this is the decomposable BSP model. The model has also been used in the creation of a number of new programming languages — including BSML (Bulk Synchronous Parallel ML) — and programming models — including BSPLib, Apache Hama, and Pregel.

See also

• Computer cluster
• Concurrent computing
• Concurrency
• Dataflow programming
• Grid computing
• Parallel computing
• ScientificPython
• LogP machine
• Automatic mutual exclusion
• Apache Hama

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

External links

• Collection of papers on BSP by Bill McColl and others. BSP Papers
• BSP topic on Quora. Bulk Synchronous Parallel Computing
• D.B. Skillicorn, Jonathan Hill, W. F. McColl, Questions and answers about BSP (1996)
• BSP Worldwide
• BSP related papers
• WWW Resources on BSP Computing
• 34 yrs old Fitter (General ) Anton from Iberville, has several passions including ceramics, property developers in singapore and vehicle racing. Has these days completed a trip to Monasteries of Haghpat and Sanahin.
  
  Also visit my web site; commercial real estate For Sale Bulk Synchronous Parallel ML (Nurse Manager Wesley Kamm from North York, usually spends time with hobbies and interests such as dogs, property developers in condo new launch singapore and baking. Finds the planet an motivating place having spent 9 weeks at City of Graz – Historic Centre and Schloss Eggenberg. official website)