The bulk-synchronous parallel random access machine

Journal article

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. Originally, BSP was defined as a distributed memory model. Shared-memory style BSP programming had to be provided by PRAM simulation. However, this approach destroys data locality and therefore may prove inefficient for many practical problems. In this paper we present a new BSP-type model, called BSPRAM, which reconciles sharedmemory style programming with efficient exploitation of data locality. BSPRAM can be optimally simulated by BSP for a broad range of algorithms. We identify some characteristic properties of such algorithms: obliviousness, slackness, granularity. Finally, we illustrate these concepts by presenting BSPRAM algorithms for butterfly dag computation, cube dag computation, dense matrix multiplication and sorting.

Authors: Tiskin, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science More from this journal
• Volume: 196
• Issue: 1-2
• Pages: 109–130
• Publication date: 1998-04-01
• Edition: Publisher's version
• ISSN: 0304-3975
• Language: English
• Keywords: BSP algorithms; PRAM simulation; BSP computing; automatic memory management; shared memory simulation
• Subjects: Computing; Applications and algorithms