How to emulate shared memory
Abhiram Ranade · Annual Symposium on Foundations of Computer Science · 1987
We present a simple algorithm for emulating an N processor CRCW PRAM on an N node 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 [8] 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.
Cited by 219 works. doi:10.1109/sfcs.1987.32
Authors
References
- Universal Schemes for Parallel Communication
- “Hot spot” contention and combining in multistage interconnection networks
- Routing, merging and sorting on parallel models of computation
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
- A logarithmic time sort for linear size networks
- Parallel Communication With Limited Buffers
- A logarithmic time sort for linear size networks
- Randomized parallel communication (Preliminary Version)
- Efficient schemes for parallel communication
- Parallel hashing---an efficient implementation of shared memory