Efficient PRAM Simulation on a Distributed Memory Machine

TitleEfficient PRAM Simulation on a Distributed Memory Machine
Publication TypeTechnical Report
Year of Publication1993
AuthorsKarp, R. M., Luby M., & der Heide F. Meyer auf
Other Numbers828

We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. The delay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of an m processor PRAM on a n processor DMM will necessarily have delay at least m/n. A randomized simulation is called time-processor optimal if the delay is O(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delay O(loglog(n)log*(n). The best previous simulations use a simpler scheme based on hashing and have much larger delay.

Bibliographic Notes

ICSI Technical Report TR-93-040

Abbreviated Authors

R. M. Karp, M. Luby, and F. M. auf der Heide

ICSI Publication Type

Technical Report