Efficient PRAM Simulation on a Distributed Memory Machine
Title | Efficient PRAM Simulation on a Distributed Memory Machine |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Karp, R. M., Luby M., & der Heide F. Meyer auf |
Other Numbers | 828 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-040.pdf |
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 |