How to emulate shared memory

摘要

We present a simple algorithm for emulating an N-processor CROW PRAM on an N-ode butterfly. Each step of the PRAM is emulated in time O(log N) with high probability, using FIFO queues of size O(1) at each node. The only use of randomization is in selecting a hash function to distribute the shared address space of the PRAM onto the nodes of the butterfly. The routing itself is both deterministic and oblivious, and messages are combined without the use of associative memories or explicit sorting. As a corollary we improve the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock. Besides being optimal, our algorithm has the advantage of extreme simplicity and is readily suited for use in practice.