Abstract
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. Thedelay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of anm processor PRAM on ann processor DMM will necessarily have delay at leastm/n. A randomized simulation is calledtime-processor optimal if the delay isO(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delayO(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: Θ (log(n)/log log(n)) for the simulation of an n processor PRAM on ann processor DMM, and Θ(log(n)) in the case where the simulation is time-processor optimal.
Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon and J. H. Spencer.The Probabilistic Method. Wiley, New York, 1991.
H. Bast and T. Hagerup. Fast and reliable parallel hashing.Proc. 3rd Ann. ACM Symp. on Parallel Algorithms and Architectures, pages 50–61, 1991.
B. Bollobás.Random Graphs. Academic Press, London, 1985.
J. L. Carter and M. N. Wegman. Universal classes of hash functions.J. Comput. System Sci., 18:143–154, 1979.
B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. Efficient simulations between concurrent-read concurrent-write PRAM models.Proc. MFCS '88, pages 231–239, 1988.
B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. New simulations between CRCW PRAMs.Proc. MFCS '89, pages 95–104, 1989.
M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. Technical Report 77, Universität-GH Paderborn, FB Mathematik-Informatik, Jan. 1991. (Revised version of paper with same title that appeared inProc. 24thIEEE FOCS, pages 524–531, 1988.) To appear inSIAM J. Comput.
M. Dietzfelbinger and F. Meyer auf der Heide. How to distribute a hash table in a complete network.Proc. 22nd Ann. ACM Symp. on Theory of Computing, pages 117–127, 1990.
M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In M. S. Paterson, editor,Proc. 17th ICALP, pages 6–19, 1990. Lecture Notes in Computer Science, Vol. 443. Springer-Verlag, Berlin.
F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation.SIAM J. Comput., 17:606–627, June 1988.
F. E. Fich, P. L. Ragde, and A. Wigderson. Simulations among concurrent-write PRAMs.Algorithmica, 3:43–51, 1988.
J. Gil and Y. Matias. Fast hashing on a PRAM-designing by expectation.Proc. SODA '91, pages 271–280, 1991.
J. Gil and Y. Matias. Leaders election without a conflict resolution rule—fast and efficient randomized simulations among CRCW PRAMs.Proc. LATIN '92, pages 204–218, 1992.
J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms.Proc. FOCS '91, pages 698–710, Oct. 1991.
A. Karlin and E. Upfal. Parallel hashing—an efficient implementation of shared memory.Proc. 18th Ann. ACM Symp. on Theory of Computing, pages 160–168, 1986.
C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms.Theoret. Comput. Sci., 71:95–132, 1990.
Y. Matias and U. Vishkin. Converting high probability into nearly-constant time—with applications to parallel hashing.Proc. 23rd Ann. ACM Symp. on Theory of Computing, pages 307–316, 1991.
C. McDiarmid. On the method of bounded differences. In J. Siemons, editor,Surveys in Combinatorics, pages 148–188. London Mathematical Society Lecture Note Series, Vol. 141. Cambridge University Press, Cambridge, 1989.
K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories.Ada Inform., 21:339–374, 1984.
A. G. Ranade. How to emulate shared memory.Proc. 28th IEEE Ann. Symp. on Foundations of Computer Science, pages 185–194, 1987.
A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications.Proc. 30th IEEE Ann. Symp. on Foundations of Computer Science, pages 20–25, 1989. Revised Version.
E. Upfal. Efficient schemes for parallel communication.J. Assoc. Comput. Mach., 31(3):507–517, 1984.
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.
Author information
Authors and Affiliations
Additional information
Communicated by M. Luby.
Research partially supported by NSF/DARPA Grant CCR-9005448. Work was done while at the University of California at Berkeley and the International Computer Science Institute, Berkeley, CA.
Research partially supported by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT BR Grant EC-US 030.
Part of work was done during a visit at the International Computer Science Institute at Berkeley; supported in part by DFG-Forschergruppe “Effiziente Nutzung massiv paralleler Systeme, Teilprojekt 4,” and by the Esprit Basic Research Action Nr. 7141 (ALCOM II).
Rights and permissions
About this article
Cite this article
Karp, R.M., Luby, M. & Meyer auf der Heide, F. Efficient PRAM simulation on a distributed memory machine. Algorithmica 16, 517–542 (1996). https://doi.org/10.1007/BF01940878
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01940878