Parallel hashing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel hashing: an efficient implementation of shared memory

Full text

Pdf (1.28 MB)

Source

Journal of the ACM (JACM) archive
Volume 35 , Issue 4 (October 1988) table of contents

Pages: 876 - 892

Year of Publication: 1988

ISSN:0004-5411

Authors

Anna R. Karlin	Stanford Univ., Stanford, CA
Eli Upfal	IBM Almaden Research Center, Almaden, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 31, Citation Count: 11

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/48014.350550 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	Helmut Alt , Torben Hagerup , Kurt Mehlhorn , Franco P. Perparata, Deterministic simulation of idealized parallel computers on more realistic ones, SIAM Journal on Computing, v.16 n.5, p.808-835, Oct. 1987 [doi>10.1137/0216053]
	2	ANGLUIN, O., AND VALIANT, L. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 12, 6 (1979), 155-193.
	3	AWERBUCH, B., ISRAELI, A., AND SHILOACH, Y. Efficient simulation of PRAM by Ultracomputer. Preprint, Technion, Haifa, Israel. 1983.
	4	CARTER, L., AND WEGMAN, M. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2 (1979), 143-154.
	5	CHERNOFF, H. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Ann. Math. Statistics 23 (1952), 493-507.
	6	FELLER, W. An Introduction to Probability Theory and Its Applications. Vol. I, 3rd ed. Wiley, New York, 1967.
	7	HOEFFDING, W. On the distribution of the number of successes in independent trials. Ann. Math. Statistics 27 (I956), 713-721.
	8	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]
	9	MEHLHORN, K., AND VISHKIN, U. Randomized and deterministic simulation of PRAMs by parallel machines with restricted granularity of parallel memories. In Proceedings of the 9th Workshop on Graph Theoretic Concepts in Computer Science. Fachbereich Mathematic, Universit~it Osnabruck, Osnabruck, Austria, June 1983.
	10	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]
	11	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]
	12	Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
	13	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]
	14	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]
	15	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]
	16	VALIANT, L. A scheme for fast parallel communication. SlAM J. Comput. 11, 2 (1982), 350-361.
	17	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]
	18	YAO, A.C. A probabilistic computation: Towards a unified measure of complexity. In Proceedings of thp 18th AnmJn} {~t~. ic;'~,nr}ntion~ of Comp~tar .~ian,~a IlZl:71~ Nlow Vnrlc 1077 nn 99'9_997

CITED BY 11

	Andreas Geyer-Schulz , Johann Mitlöhner , Alfred Taudes, An APL-simulator of non-Von Neumann computer architectures, ACM SIGAPL APL Quote Quad, v.20 n.4, p.140-148, July 1990
	A. Z. Broder , A. R. Karlin , P. Raghavan , E. Upfal, Trading space for time in undirected s-t connectivity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.543-549, May 14-17, 1989, Seattle, Washington, United States
	K. Herley, Space-efficient representations of shared data for parallel computers, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.407-416, July 02-06, 1990, Island of Crete, Greece
	B. H. H. Juurlink , H. A. G. Wijshoff, Experiences with a model for parallel computation, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.87-96, August 15-18, 1993, Ithaca, New York, United States
	A. Pietracaprina , F. P. Preparata, A practical constructive scheme for deterministic shared-memory access, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.100-109, June 30-July 02, 1993, Velen, Germany
	Martti Forsell, A parallel computer as a NOC region, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990
	Guy E. Blelloch , Phillip B. Gibbons , S. Harsha Vardhan, Combinable memory-block transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Keqin Li , Yi Pan , Si Qing Zheng, Efficient Deterministic and Probabilistic Simulations of PRAMs on Linear Arrays with Reconfigurable Pipelined Bus Systems, The Journal of Supercomputing, v.15 n.2, p.163-181, Feb.1.2000
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993