Parallel hashing—an efficient implementation of shared memory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel hashing—an efficient implementation of shared memory

Full text

Pdf (834 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 160 - 168

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

A R Karlin	Computer Science Department, Stanford University
E Upfal	IBM Almaden Research Center, Almaden, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 35, Citation Count: 18

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/12130.12146 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.

	AHMP	H. Alt, T. Hagerup, K. Mehlhorn and F.P. Preparata, "Simulation of idealized parallel computers on more realistic ones." Preliminary Report
	AIS	B. Awerbuch, A. Israeli and Y. Shiloach, "Efficient simulation of PRAM by Ultracomputer." Preprint, Technion, Haifa, Israel. 1983.
	CW	L. Carter and M. Wegman. "Universal classes of Hash Functions." JCSS 18, No. 2, (1979) 143-154.
	Ch	H. Chernoff. "A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations." .Ann. of Math. Star. 23, (1952) 493-507.
	Ho	W. Hoeffding. "On the distribution of the number of successes in independent trials." Ann. of Math. Star. 27 (1956)713-721.
	Ku	David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
	MV	K. Mehlhorn and U Vishkin. "Randomized and deterministic simulation of PRAMs by parallel machines with restricted granularity of parallel memories." Ninth Workshop on Graph Theoretic Concepts in Computer Science, Fachbereich Mathematic, Universitat Osnabruck, June 1983.
	RV	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983 [doi>10.1145/800061.808727]
	Sc	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]
	Vi	Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]
	U1	Eli Upfal, A probabilistic relation between desirable and feasible, models of parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.258-265, December 1984 [doi>10.1145/800057.808689]
	U2	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]
	UW	E. Upfal and A. Wigderson. "How to share memory in a distributed system." Proc. of 25th IEEE FOCS (1984) 171-180.
	Va	L. Valiant. "A scheme for fast parallel communication," SIAM J. on Computing 11, No. 2, (1982) 350-361.

CITED BY 18

	P. Selinger, Chickens and eggs—the interrelationship of systems and theory, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.250-253, March 23-25, 1987, San Diego, California, United States
	D. Peleg , E. Upfal, Constructing disjoint paths on expander graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.264-273, January 1987, New York, New York, United States
	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
	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
	J. Reif , S. Sen, Randomized algorithms for binary search and load balancing with geometric applications, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.327-339, July 02-06, 1990, Island of Crete, Greece
	D. Greenberg , S. Bhatt, Routing multiple paths in hypercubes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.45-54, July 02-06, 1990, Island of Crete, Greece
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for memory bank contention and delay in high-bandwidth multiprocessors, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.84-94, June 24-26, 1995, Santa Barbara, California, United States
	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
	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	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
	Shaibal Roy, Semantic complexity of classes of relational queries and query independent data partitioning, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.259-267, May 29-31, 1991, Denver, Colorado, United States
	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
	J. Gil , F. Meyer auf der Heide , A. Wigderson, Not all keys can be hashed in constant time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.244-253, May 13-17, 1990, Baltimore, Maryland, United States
	M. Dietzfelbinger , F. Meyer auf der Heide, An optimal parallel dictionary, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.360-368, June 18-21, 1989, Santa Fe, New Mexico, United States
	S. W. Hornick , F. P. Preparata, Deterministic P-RAM simulation with constant redundancy, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.103-109, June 18-21, 1989, Santa Fe, New Mexico, United States
	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States
	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States