Bulk synchronous parallel

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 analyzing a BSP algorithm rests on quantifying the synchronization and communication needed.

History

The BSP model was developed by Leslie Valiant of Harvard University during the 1980s. The definitive article[1] 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, 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 in 1996.

Valiant developed an extension to the BSP model in the 2000s, leading to the publication of the Multi-BSP model[2] in 2011.

In 2017, McColl developed a major new extension of the BSP model that provides fault tolerance and tail tolerance for large-scale parallel computations in AI, Analytics and HPC. [3]

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 via technologies like Pregel and MapReduce. Also, with the next generation of Hadoop decoupling the MapReduce model from the rest of the Hadoop infrastructure, there are now active open source projects to add explicit BSP programming, as well as other high performance parallel programming models, on top of Hadoop. Examples are Apache Hama[5] 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 and interfaces, such as Bulk Synchronous Parallel ML (BSML), BSPLib,[6] Apache Hama,[5] and Pregel.[7]

Notable implementations of the BSPLib standard are the Paderborn University BSP library[8] and the Oxford BSP Toolset by Jonathan Hill.[9] Modern implementations include BSPonMPI[10] (which simulates BSP on top of the Message Passing Interface), and MulticoreBSP[11][12] (a novel implementation targeting modern shared-memory architectures). MulticoreBSP for C is especially notable for its capability of starting nested BSP runs, thus allowing for explicit Multi-BSP programming.

References

  1. ^ Jump up to:ab c Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, Volume 33 Issue 8, Aug. 1990 [1]
  2. ^ Jump up to:ab Valiant, L. G. (2011). A bridging model for multi-core computing. Journal of Computer and System Sciences, 77(1), 154-166 [2]
  3. ^A Bridging Model for High Performance Cloud Computing by Bill McColl in 18th SIAM Conference on Parallel Processing for Scientific Computing (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973Archived 2019-12-11 at the Wayback Machine.
  4. ^Alpert, R., & Philbin, J. (1997). cBSP: Zero-cost synchronization in a modified BSP model. NEC Research Institute, 4 Independence Way, Princeton NJ, 8540, [3].
  5. ^ Jump up to:ab Apache Hama
  6. ^BSPlib
  7. ^Pregel
  8. ^The Paderborn University BSP (PUB) Library – Design, Implementation and Performance Heinz Nixdorf Institute, Department of Computer Science, University of Paderborn, Germany, technical report Archived 2001-06-05 at the Wayback Machine.
  9. ^Jonathan Hill: The Oxford BSP Toolset, 1998.
  10. ^Wijnand J. Suijlen: BSPonMPI, 2006.
  11. ^MulticoreBSP for C: a high-performance library for shared-memory parallel programming by A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen in International Journal of Parallel Programming, in press (2013), doi:10.1109/TPDS.2013.31.
  12. ^An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming by A. N. Yzelman & Rob H. Bisseling in Concurrency and Computation: Practice and Experience 24(5), pp. 533-553 (2012), doi:10.1002/cpe.1843.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library