AbstractMemory access is the bottleneck in the simulation of shared memory on a distributed memory model. We show that EREW, CREW, and CRCW PRAM models can be simulated work-optimally on a mesh-connected routing machinery that is coated with processors. The simulation uses a combination of well-known techniques such as randomized hashing, greedy routing, and parallel slackness.
The advantage of our mesh based simulation is the simple and scalable structure of the mesh combined with good performance. A theoretical analysis and practical experiments show that our simulation is economical and efficient in comparison with other proposed architectures, such as butterflies and hypercubes, for all feasible numbers of processors.
Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); C.2.1 [Computer-Communication Networks]: Network Architecture and Design; F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.3 [Probability and Statistics]
Additional Key Words and Phrases: PRAM, mesh, shared memory, simulation, work-optimal
Selected papers that cite this one
- Miltos D. Grammatikakis, D. Frank Hsu, and Jop F. Sibeyn. Packet routing in fixed-connection networks: A survey. Journal of Parallel and Distributed Computing, 54(2):77-132, 1 November 1998.
Selected references
- Anna R. Karlin and Eli Upfal. Parallel hashing -- an efficient implementation of shared memory (preliminary version). In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 160-168, Berkeley, California, 28-30 May 1986.
- Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 318-326, Victoria, British Columbia, Canada, 4-6 May 1992.
- Tom Leighton. Methods for message routing in parallel machines. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 77-96, Victoria, British Columbia, Canada, 4-6 May 1992.
- Kurt Mehlhorn and Uzi Vishkin. Randomized and deterministic simulations of prams by parallel machines with restricted granularity of parallel memories. Acta Informatica, 21:339-374, 1984.