Research output: Contribution to journal › Article › peer-review
The bulk-synchronous parallel random access machine. / Tiskin, Alexandre.
In: Theoretical Computer Science, Vol. 196, No. 1-2, 06.04.1998, p. 109-130.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - The bulk-synchronous parallel random access machine
AU - Tiskin, Alexandre
PY - 1998/4/6
Y1 - 1998/4/6
N2 - 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 shared-memory 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. © 1998 - Elsevier Science B.V. All rights reserved.
AB - 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 shared-memory 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. © 1998 - Elsevier Science B.V. All rights reserved.
KW - Automatic memory management
KW - BSP algorithms
KW - BSP computing
KW - PRAM simulation
KW - Shared memory simulation
UR - http://www.scopus.com/inward/record.url?scp=0346098076&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(97)00197-7
DO - 10.1016/S0304-3975(97)00197-7
M3 - Article
AN - SCOPUS:0346098076
VL - 196
SP - 109
EP - 130
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -
ID: 127713365