The bulk-synchronous parallel random access machine
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...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
1998
|
| Subjects: |
| _version_ | 1797081917097508864 |
|---|---|
| author | Tiskin, A |
| author_facet | Tiskin, A |
| author_sort | Tiskin, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:20:48Z |
| format | Journal article |
| id | oxford-uuid:903deacc-aadc-4cba-9c76-bb738742b5ee |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:20:48Z |
| publishDate | 1998 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:903deacc-aadc-4cba-9c76-bb738742b5ee2022-03-26T23:10:25ZThe bulk-synchronous parallel random access machineJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:903deacc-aadc-4cba-9c76-bb738742b5eeApplications and algorithmsComputingEnglishOxford University Research Archive - ValetElsevier1998Tiskin, AThe 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. |
| spellingShingle | Applications and algorithms Computing Tiskin, A The bulk-synchronous parallel random access machine |
| title | The bulk-synchronous parallel random access machine |
| title_full | The bulk-synchronous parallel random access machine |
| title_fullStr | The bulk-synchronous parallel random access machine |
| title_full_unstemmed | The bulk-synchronous parallel random access machine |
| title_short | The bulk-synchronous parallel random access machine |
| title_sort | bulk synchronous parallel random access machine |
| topic | Applications and algorithms Computing |
| work_keys_str_mv | AT tiskina thebulksynchronousparallelrandomaccessmachine AT tiskina bulksynchronousparallelrandomaccessmachine |