language: en

Efficient PRAM Simulation on a Distributed Memory Machine

Richard M. Karp
University of California at Berkeley and International Computer Science Institute,
Berkeley, CA
Michael Luby
International Computer Science Institute,
Berkeley, CA
and UC Berkeley
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute and Computer Science Department,
University of Paderborn,
Germany
TR-93-040 August 1993

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: fi(log(n)= loglog(n)) for the simulation of an n processor PRAM on an n processor DMM, and fi(log(n)) in the case where the simulation is time-processor optimal.

[Research partially supported by NSF/DARPA Grant CCR-9005448 Research partially supported by NSF operating grant CCR-9016468 and by grant No. 89-00312 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel. Part of work was done during a visit at the International Computer Science Institute at Berkeley; supported in part by DFG-Forschergruppe "Effiziente Nutzung massiv paralleler Systeme, Teilprojekt 4", and by the Esprit Basic Research Action Nr. 7141 (ALCOM II).]