Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer

TitleConstructive Deterministic PRAM Simulation on a Mesh-Connected Computer
Publication TypeTechnical Report
Year of Publication1993
AuthorsPietracaprina, A., Pucci G., & Sibeyn J. Frederik
Other Numbers847

The PRAM model of computation consists of a collection of sequential RAM machines accessing a shared memory in lock-step fashion. The PRAM is a very high-level abstraction of a parallel computer, and its direct realization in hardware is beyond reach of the current (or even foreseeable) technology. In this paper we present a deterministic simulation scheme to emulate PRAM computation on a mesh-connected computer, a feasible machine where each processor has its own memory module and is connected to at most four other processors via point-to-point links. In order to achieve a good worst-case performance, any deterministic simulation scheme has to replicate each variable in a number of copies. Such copies are stored in the local memory modules according to a Memory Organization Scheme (MOS), which is known to all the processors. A variable is then accessed by routing packets to its copies. All deterministic schemes in the literature make use of a MOS whose existence is proved via the probabilistic method, but that cannot be efficiently constructed. We introduce a new constructive MOS, and show how to employ it to simulate an n-processor PRAM on an n-node mesh-connected computer. Our simulation achieves almost optimal slowdown for small memories. This is the first constructive deterministic PRAM simulation on a bounded-degree network

Bibliographic Notes

ICSI Technical Report TR-93-059

Abbreviated Authors

A. Pietracaprina, G. Pucci, and J. F. Sibeyn

ICSI Publication Type

Technical Report