Standard

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 journalArticlepeer-review

Harvard

Tiskin, A 1998, 'The bulk-synchronous parallel random access machine', Theoretical Computer Science, vol. 196, no. 1-2, pp. 109-130. https://doi.org/10.1016/S0304-3975(97)00197-7

APA

Vancouver

Author

Tiskin, Alexandre. / The bulk-synchronous parallel random access machine. In: Theoretical Computer Science. 1998 ; Vol. 196, No. 1-2. pp. 109-130.

BibTeX

@article{029026ed4e3346e58668ab4c3d49a3c2,
title = "The bulk-synchronous parallel random access machine",
abstract = "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. {\textcopyright} 1998 - Elsevier Science B.V. All rights reserved.",
keywords = "Automatic memory management, BSP algorithms, BSP computing, PRAM simulation, Shared memory simulation",
author = "Alexandre Tiskin",
year = "1998",
month = apr,
day = "6",
doi = "10.1016/S0304-3975(97)00197-7",
language = "English",
volume = "196",
pages = "109--130",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

RIS

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