Efficient PRAM simulation on a distributed memory machine

Abstract

We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The algorithm is based on hashing and uses a novel simulation scheme. The best previous simulations use a simpler scheme based on hashing and have much larger expected delay: Θ(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and Θ(log(n)) in the case where the simulation preserves the processor-time product.