A probabilistic relation between desirable and feasible, models of parallel computation

ABSTRACT

We present a powerful probabilistic technique for simulating strong models of synchronized parallel computation by weaker ones. The technique is demonstrated by an algorithm simulating an n processor PRAM, with an arbitrary large shared memory, by an n processor ULRTACOMPUTER (a set of n processors communicating through a bounded degree network, and sharing no common memory). We prove that if a program required t PRAM steps, our simulation algorithm executes it on the ULTRACOMPUTER within O(tlog2n) steps with overwhelming probability.

REFERENCES

• 1: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• 2: B. Awerbuch, A. Israeli and Y. Shiloach. Efficient simulation of pram by ultracomputer. Preprint, Technion, Haifa, Israel. 1983.
• 3: P. Billinsley. Probability and Measure. John Wiley and Sons, Inc., 1979.
• 4: H. Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Ann. of Math. Stat. 23 (1952) 493-507
• 5: Zvi Galil , Wolfgang J. Paul, An Efficient General-Purpose Parallel Computer, Journal of the ACM (JACM), v.30 n.2, p.360-387, April 1983 [doi>10.1145/322374.322382]
• 6: F.P. Preparata, J. Vuillemin. The cube-connected-cycles: A versatile network for parallel computation. 20 IEEE Symp. on Foundation of Computer Science. (1979) 140-147.
• 7: M.O. Rabin. Probabilistic algorithms, Algorithm and Complexity, J.F. Taub, ed., Academic Press, NY 1976.
• 8: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 9: R. Solovay and V. Strassen, Fast Monte-Carlo test for primality. SIAM J. of Computing 6 (1977) 84-85.
• 10: U. Vishkin. A parallel-design distributed-implementation general-purpose computer. Preprint, Courant Institute, New York University. 1983.
• 11: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
• 12: L. G. Valiant. A scheme for fast parallel communication. SIAM J. of Computing 11 (1982) 350-361.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory