|
|||||
|
|
Towards a single model of efficient computation in real parallel machines |
|
| Authors: | Pilar de la Torre Clyde P Kruskal |
| Affiliation: | a Department of Computer Science, University of New Hampshire, Durham, NH 03824, USA b Department of Computer Science, University of Maryland, College Park, MD 20742, USA |
| Abstract: | We propose a model of parallel computation, the YPRAM, that allows general parallel algorithms to be designed for a wide class of parallel models. The basic model captures locality among processors, which is measured as a function of two parameters; latency and bandwidth. We design YPRAM algorithms for solving several fundamental problems: parallel prefix, sorting, sorting numbers from a bounded range, and list ranking. We show that our model predicts, reasonably accurately, the actual known performances of several basic parallel models — PRAM, hypercube, mesh and tree — when solving these problems. |
| Keywords: | Models of parallel computation parallel algorithms efficient parallel algorithms PRAM parallel processing processor networks latency bandwidth YPRAM |
| 本文献已被 ScienceDirect 等数据库收录！ | |