Simple, efficient shared memory simulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple, efficient shared memory simulations

Full text

Pdf (953 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 110 - 119

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Martin Dietzfelbinger
Friedhelm Meyer auf der Heide

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 15, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/165231.165246 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. J. Anderson, G. L. Miller. Optical communication for pointer based algorithms. Tech. Rep. CRI 88-14, Comp. Sci. Dept., Univ. of Southern California, Los Angeles, 1988.
	2	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]
	3	B. Bollob#s.Combinatorics. Cambridge University Press, 1986.
	4	J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143-154, 1979.
	5	Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
	6	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]
	7	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
	8	Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140906]
	9	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	10	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]
	11	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]
	12	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	13	D. J. Kleitman. Families of non-disjoint subsets. J. Combinatorial Theory, 1:153-155, 1966.
	14	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]
	15	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	16	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
	17	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]
	18	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
	19	Friedhelm Meyer auf der Heide, Hashing Strategies for Simulating Shared Memory on Distributed Memory Machines, Proceedings of the First Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, p.20-29, November 11-13, 1992
	20	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]
	21	A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their apphcations. In Proc. of the 30th IEEE Ann. Symp. on Foundations of Computer Science, pp. 20-25, 1989. (Revised Version).
	22	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]
	23	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]
	24	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	25	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

CITED BY 16

	Leslie Ann Goldberg , Philip D. Mackenzie , Mike Paterson , Aravind Srinivasan, Contention resolution with constant expected delay, Journal of the ACM (JACM), v.47 n.6, p.1048-1096, Nov. 2000
	Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States
	P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Journal of the ACM (JACM), v.45 n.2, p.324-378, March 1998
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.153-162, May 23-25, 1994, Montreal, Quebec, Canada
	Leslie Ann Goldberg , Mark Jerrum , Philip D. MacKenzie, An Ω(√ log log n) lower bound for routing in optical networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 27-29, 1994, Cape May, New Jersey, United States
	Volker Stemann, Parallel balanced allocations, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.261-269, June 24-26, 1996, Padua, Italy
	Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), v.50 n.4, p.568-589, July 2003
	Martin Dietzfelbinger, Gossiping and broadcasting versus computing functions in networks, Discrete Applied Mathematics, v.137 n.2, p.127-153, 1 March 2004
	Andrea Pietracaprina , Geppino Pucci , Jop F. Sibeyn, Constructive deterministic PRAM simulation on a mesh-connected computer, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.248-256, June 27-29, 1994, Cape May, New Jersey, United States
	Ville Leppänen , Martti Penttonen, Work-optimal simulation of PRAM models on meshes, Nordic Journal of Computing, v.2 n.1, p.51-69, March 1995
	Rina Panigrahy, Efficient hashing with lookups in two memory accesses, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Krishnaram Kenthapadi , Rina Panigrahy, Balanced allocation on graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.434-443, January 22-26, 2006, Miami, Florida
	Baruch Awerbuch , Christian Scheideler, Towards a scalable and robust DHT, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Julie Anne Cain , Peter Sanders , Nick Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.469-476, January 07-09, 2007, New Orleans, Louisiana