The bulk-synchronous parallel random access machineReportar como inadecuado

The bulk-synchronous parallel random access machine - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Alexandre Tiskin, (1998-04). The bulk-synchronous parallel random access machine. Theoretical Computer Science, 196 (1-2), 109–130.Citable link to this page:


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 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.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's version Funder: European Strategic Programme of Research and Development in Information Technology   Notes:Copyright 1998 Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at

Bibliographic Details

Publisher: Elsevier

Publisher Website:

Host: Theoretical Computer Sciencesee more from them

Publication Website:

Issue Date: 1998-04

Copyright Date: 1998


Issn: 0304-3975

Urn: uuid:903deacc-aadc-4cba-9c76-bb738742b5ee Item Description

Type: Article: post-print;

Language: en

Version: Publisher's versionKeywords: BSP computing automatic memory management PRAM simulation shared memory simulation BSP algorithmsSubjects: Applications and algorithms Computing Tiny URL: ora:10760


Autor: Alexandre Tiskin - institutionUniversity of Oxford facultyMathematical, Physical and Life Sciences Division - Department of Compu



Documentos relacionados