Richard M. Karp
Michael Luby
Friedhelm Meyer auf der Heide
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: Θ(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and Θ(log(n)) in the case where the simulation preserves the processor-time product.
- 1.H. Bast and T. Hagerup. Fast and reliable parallel hashing. In Proc. of the 3rd Ann. A CM Syrup. on Parallel Algorithms and Architectures, pages 50- 61, 1991. Google Scholar
Digital Library
- 2.B. BollobAs. Random Graphs. Academic Press, London, 1985.Google Scholar
- 3.J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143- 154, 1979.Google ScholarCross Ref
- 4.M. Dietzfelbinger and F. Meyer auf der Heide. How to distribute a dictionary in a complete network. In Proc. of the 22nd Ann. ACM Symp. on Theory of Computing, pages 117-127, 1990. Google ScholarDigital Library
- 5.M. Dietzfelbinger and F. Meyer auf der tleide. A new universal class of hash functions and dynamic hashing in real time. In M. S. Paterson, editor, Proceedings of 17th ICALP, pages 6-19. Springer, 1990. Lecture Notes in Computer Science 443. Google ScholarDigital Library
- 6.A. Karlin and E. Upfal. Parallel hashing- an efficient implementation of shared memory. In Proc. of the 18th Ann. ACM Syrup. on Theory of Computing, pages 160-168, 1986. Google ScholarDigital Library
- 7.C. P. Krusknl, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci., 71:95-132, 1990. Google ScholarDigital Library
- 8.Y. Matias and U. Vishkin. Converting high probability into nearly-constant time- with applications to parallel hashing. In Proc. of the 23rd Ann. A CM Syrup. on Theory of Computing, pages 307-816, 1991. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 10.K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica, 21:339-374, 1984. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 13.E. Upfal. Efficient schemes for parallel communication. J. Assoc. Comput. Mach., 31(3):507-517, 1984. Google ScholarDigital Library
- 14.L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, chapter 18, pages 943-971. Elsevier, Amsterdam, 1990. Google ScholarDigital Library
Index Terms
- Efficient PRAM simulation on a distributed memory machine
Recommendations
Work-Time Optimal k-Merge Algorithms on the PRAM
For 2 k n, the k-merge problem is to merge a collection of k sorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of ...
PRAM Processor Allocation: A Hidden Bottleneck in Sublogarithmic Algorithms
The problem of dynamic processor allocation in PRAMs (programmable random-access memories) is discussed, and differentiated from that of static allocation. The version of the PRAM considered, also called the CREW model is a parallel computer with global ...
Comments