You are here: Community Papers

Papers

This page aims to give a overview of papers dealing on the Bulk Synchronous Parallel (BSP) model, as well as BSP programming, with respect to shared-memory (multicore) computing. If you find any work missing, please contact us.

The MulticoreBSP library

The MulticoreBSP library is introduced by A. N. Yzelman and Rob H. Bisseling in early 2011 [1]; this was done by detailing the implementation of a sparse matrix dense vector multiplication. Experiments show the scalability of this algorithm, as well as that of a dense LU decomposition and a fast Fourier transform. These experiments have been performed on various architectures: the Sun UltraSparc T2, the Intel Core 2 Q6600, and the AMD Phenom II 945e, thus further stressing the interoperability of MulticoreBSP.

To show BSP programming has a place in high-performance computing, following years saw the development of MulticoreBSP for C. An introductory paper by Yzelman et al. [6] was released in 2013. The sparse matrix–vector multiplication method included with the paper often exceeds performance of other then-current state-of-the-art methods [6]. The C library remains fully backwards compatible with earlier work [3], and supports nested BSP runs as required by applications using the updated Multi-BSP model [5].

Previous work

MulticoreBSP relies heavily on previous work, most notably on the initial proposal of the BSP model by L. Valiant [2], and the Oxford BSPlib library by J. Hill et al. [3], providing application of this model on distributed-memory supercomputers. Furthermore, the book by R. Bisseling [4] provides much of the initial applications programmed in MulticoreBSP.

Related work
  • Valiant [5] updates the BSP model to better account for hierarchical systems, including multicore systems, and models memory size constraints as well.

Bibliography

  • [1] A. N. Yzelman and Rob H. Bisseling, An Object-Oriented Bulk Synchronous Parallel Library for Multicore Programming, Concurrency and Computation: Practice and Experience 24(5), 2012; pp. 533-553. (citation)
  • [2] L. G. Valiant, A bridging model for parallel computation, Communications of the ACM, Volume 33, Issue 8, 1990; pp. 103--111.
  • [3] Jonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, Satish B. Rao, Torsten Suel, Thanasis Tsantilas, and Rob Bisseling, BSPlib: The BSP Programming Library, Parallel Computing, Volume 24, Issue 14, 1998; pp. 1947--1980.
  • [4] Rob H. Bisseling, Parallel Scientific Computation: A Structured Approach using BSP and MPI, Oxford University Press, 2004.
  • [5] L. G. Valiant, A bridging model for multi-core computing. Algorithms - ESA 2008, Lecture Notes in Computer Science, Volume 5193, Springer, 2008; pp. 13--28.
  • [6] A. N. Yzelman, R. H. Bisseling, D. Roose, and K. Meerbergen, MulticoreBSP for C: a high-performance library for shared-memory parallel programming, Technical report TW 624, KU Leuven, 2013; pre-print version (accepted for publication). (citation)