The bulk-synchronous parallel random access machineReport as inadecuate




The bulk-synchronous parallel random access machine - Download this document for free, or read online. Document in PDF available to download.

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 http://www.elsevier.com/open-access/userlicense/1.0/

Bibliographic Details

Publisher: Elsevier

Publisher Website: https://www.elsevier.com/

Host: Theoretical Computer Sciencesee more from them

Publication Website: http://www.journals.elsevier.com/theoretical-computer-science/

Issue Date: 1998-04

Copyright Date: 1998

pages:109–130Identifiers

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

Relationships





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

Source: https://ora.ox.ac.uk/objects/uuid:903deacc-aadc-4cba-9c76-bb738742b5ee



DOWNLOAD PDF




Related documents