How to emulate shared memory
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 185-194
- https://doi.org/10.1109/sfcs.1987.32
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Deterministic Simulation of Idealized Parallel Computers on More Realistic OnesSIAM Journal on Computing, 1987
- Parallel hashing---an efficient implementation of shared memoryPublished by Association for Computing Machinery (ACM) ,1986
- “Hot spot” contention and combining in multistage interconnection networksIEEE Transactions on Computers, 1985
- Parallel Communication With Limited BuffersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- How To Share Memory In A Distributed SystemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- A probabilistic relation between desirable and feasible, models of parallel computationPublished by Association for Computing Machinery (ACM) ,1984
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential ProcessorsACM Transactions on Programming Languages and Systems, 1983
- Routing, merging and sorting on parallel models of computationPublished by Association for Computing Machinery (ACM) ,1982
- Efficient schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1982
- Universal schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1981