Bounds on the time for parallel RAM's to compute simple functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounds on the time for parallel RAM's to compute simple functions

Full text

Pdf (192 KB)

Source

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

San Francisco, California, United States

Pages: 231 - 233

Year of Publication: 1982

ISBN:0-89791-070-2

Authors

Stephen Cook
Cynthia Dwork

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): 19, Citation Count: 14

Additional Information:

abstract references cited by 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/800070.802196 What is a DOI?

ABSTRACT

We prove that a parallel RAM with no write conflicts allowed requires -&-Ohgr;(log n) steps to compute the Boolean or of n bits stored in the first n global memory cells. We first argue that this result is subtler than it appears, and in fact the -&-ldquo;obvious-&-rdquo; lower bound of log2n steps can be beaten.

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	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	2	Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]

CITED BY 14

	Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada
	M Li , Y Yesha, New lower bounds for parallel computation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.177-187, May 28-30, 1986, Berkeley, California, United States
	Rüdiger Reischuk, Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions, Journal of the ACM (JACM), v.34 n.1, p.163-178, Jan. 1987
	Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984
	Cynthia Dwork , Dale Skeen, The inherent cost of nonblocking commitment, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.1-11, August 17-19, 1983, Montreal, Quebec, Canada
	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States
	Marc Snir, On parallel searching (Extended Abstract), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.242-253, August 18-20, 1982, Ottawa, Canada
	Ming Li , Yaacov Yesha, New lower bounds for parallel computation, Journal of the ACM (JACM), v.36 n.3, p.671-680, July 1989
	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
	L. Fava Lindon , S. G. Akl, An Optimal Implementation of Broadcasting with Selective Reduction, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.256-269, March 1993
	Alon Itai, Parallel arithmetic with concurrent writes, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.293-299, August 1985, Minaki, Ontario, Canada
	A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States
	Ashok K. Chandra , Steven Fortune , Richard Lipton, Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.52-60, December 1983
	R. Miller , Q. F. Stout, Efficient Parallel Convex Hull Algorithms, IEEE Transactions on Computers, v.37 n.12, p.1605-1618, December 1988

Collaborative Colleagues:

Stephen Cook: colleagues

Cynthia Dwork: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player