Efficient PRAM simulation on a distributed memory machine

ABSTRACT

We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The algorithm is based on hashing and uses a novel simulation scheme. The best previous simulations use a simpler scheme based on hashing and have much larger expected delay: &THgr;(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and &THgr;(log(n)) in the case where the simulation preserves the processor-time product.

REFERENCES

• 1: Holger Bast , Torben Hagerup, Fast and reliable parallel hashing, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.50-61, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113384]
• 2: B. BollobAs. Random Graphs. Academic Press, London, 1985.
• 3: J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143- 154, 1979.
• 4: M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100229]
• 5: M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
• 6: A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
• 7: Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
• 8: Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
• 9: C. MeDiarmid. On the method of bounded differenees. In J. Siemons, editor, Surveys in Uombinatorics, 1989, pages 148-188. Cambridge University Press, 1989. London Math. Soc. Lecture Note Series 141.
• 10: 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
• 11: A. G. Ranade. How to emulate shared memory. In Proc. of the 28th IEEE Ann. Syrup. on Foundations of Computer Science, pages 185-194, 1987.
• 12: A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proc. of the $Oth IEEE Ann. Syrup. on Foundations of Computer Science, pages 20-25, 1989. Revised Version.
• 13: 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]
• 14: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance, Theory