Constructive deterministic PRAM simulation on a mesh-connected computer

ABSTRACT

We present a constructive deterministic simulation of a PRAM with n processors and m = n &agr; shared variables, 1 < &agr; ≤ 2, on an n-node mesh-connected computer where each node hosts a processor and a memory module. At the core of the simulation is a Hierarchical Memory Organization Scheme (HMOS) that governs the distribution of the PRAM variables (each replicated into a number of copies) among the modules. The HMOS consists of a cascade of explicit bipartite graphs whose expansion properties, combined with suitable access and routing protocols, yield a time performance that, for &agr; < 3/2, is close to the Wn bound imposed by the network's diameter, and that, for &agr; ≥ 3/2, is a function of &agr; never exceeding On^5/8 .

REFERENCES

• AHMP87: Helmut Alt , Torben Hagerup , Kurt Mehlhorn , Franco P. Perparata, Deterministic simulation of idealized parallel computers on more realistic ones, SIAM Journal on Computing, v.16 n.5, p.808-835, Oct. 1987 [doi>10.1137/0216053]
• BP92: Franco P. Preparata , Gianfranco Bilardi, Horizons of Parallel Computation, Proceedings of the International Conference on Future Tendencies in Computer Science, Control and Applied Mathematics, p.155-174, December 08-11, 1992
• DM93: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• Hal86: M. Hall Jr. Combinatorial Theory. John Wiley & Sons, New York NY, second edition, 1986.
• HB88: Kieran T. Herley , Gianfranco Bilardi, Deterministic Simulations of PRAMs on Bounded Degree Networks, Cornell University, Ithaca, NY, 1988
• Her89: K.T. Herley. Efficient simulations of small shared memories on bounded degree networks. Proc. of the 30th IEEE Syrup. on Foundations of Comp. So., pages 390-395# 1989.
• Her90: K. Herley, Space-efficient representations of shared data for parallel computers, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.407-416, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97708]
• KLM92: Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
• KSS94: Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
• LPP90: F. Luccio, A. Pietracaprina, and G. Pucci. A new scheme for the deterministic simulation of PRAMs in VLSI. Algorithmica, 5:529-544, 1990.
• MV84: Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
• PP93a: Andrea Pietracaprina , Franco P. Preparata, On O(sqrt(n))-Worst-Case-Time Solution to the Granularity Problem, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.110-119, February 25-27, 1993
• PP93b: A. Pietracaprina , F. P. Preparata, A practical constructive scheme for deterministic shared-memory access, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.100-109, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165245]
• Ran91: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• SK94: Jop F. Sibeyn , Michael Kaufmann, Deterministic 1-k Routing on Meshes, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.237-248, February 24-26, 1994
• Tho79: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• UW87: Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory, Verification