Questions and Answers about BSP

Article type: Research Article

Authors: Skillicorn, D.B. | Hill, Jonathan M.D. | McColl, W.F.

Affiliations: Department of Computing and Information Science, Queen's University, Kingston, Canada; E-mail: skill@qucis.queensu.ca | Computing Laboratory, University of Oxford, Oxford, UK; E-mail: {Jonathan.Hill,Bill.McColl}@comlab.ox.ac.uk

Abstract: Bulk Synchronous Parallelism (BSP) is a parallel programming model that abstracts from low-level program structures in favour of supersteps. A superstep consists of a set of independent local computations, followed by a global communication phase and a barrier synchronisation. Structuring programs in this way enables their costs to be accurately determined from a few simple architectural parameters, namely the permeability of the communication network to uniformly-random traffic and the time to synchronise. Although permutation routing and barrier synch ronisations are widely regarded as inherently expensive, this is not the case. As a result, the structure imposed by BSP does not reduce performance, while bringing considerable benefits for application building. This paper answers the most common questions we are asked about BSP and justifies its claim to be a major step forward in parallel programming.

Journal: Scientific Programming, vol. 6, no. 3, pp. 249-274, 1997