Trade-offs between communication throughput and parallel time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Trade-offs between communication throughput and parallel time

Full text

Pdf (994 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 372 - 381

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Yishay Mansour	Dept. of Computer Science, Tel Aviv University, Tel Aviv, Israel
Noam Nisan	Dept. of Computer Science, Hebrew University, Jerusalem, Israel
Uzi Vishkin	University of Maryland Institute for Advanced Computers Studies and Department of Electrical Engineering, College Park, MD and Dept. of Computer Science, Tel Aviv University, Tel Aviv, Israel

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): 12, Citation Count: 9

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

	AKP91	F. Abolhassan, J. Keller and W. Paul. On the cost-effectiveness and realization of the theoretical PRAM model, technical report 09/91, FB Informatik, universitat des saarlandes. 1991.
	Abr86	K. Abrahamson. Time-space tradeoffs for branching programs constructed with those for straight line programs. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, pages 402-409, October 1986.
	Aza92	Yossi Azar, Lower bounds for threshold and symmetric functions in parallel computation, SIAM Journal on Computing, v.21 n.2, p.329-338, April 1992 [doi>10.1137/0221024]
	B74	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	BC82	A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Cornput., 1(2):287-297, 1982.
	Bea89	P. Beame, A general sequential time-space tradeoff for finding unique elements, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.197-203, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73026]
	CKP+93	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	Hel80	M.E. Hellman. A cryptanalytic time-memory tradeoff. IEEE Trans. Infor. Theor., 26:401- 406, 1980.
	HS86	W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
	J-92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	Lei92	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]
	LY86	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 [doi>10.1145/12130.12148]
	MNT90	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
	MV84	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
	SV-82	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	Val77	L. Valiant. Graph theoretic arguments in lowlevel complexity, technical report CS 13-77, University of Edinburgh, UK. 1977.
	VW85	U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. SIAM J. Computin9, 14,2:303--314, 1985.
	Yao90	A. C.-C. Yao, Coherent functions and program checkers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.84-94, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100226]
	Yes84	Y. Yesha. A time-space tradeoff for matrix multiplication and the discrete Fourier transform on a general sequential random access computer. J. Comp. and Syst. Sci., 29:183-197, 1984.

CITED BY 9

	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France
	Adnan Agbaria , Yosi Ben-Asher , Ilan Newman, Communication-processor tradeoffs in limited resources PRAM, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.74-82, June 27-30, 1999, Saint Malo, France
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States
	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, 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
	Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, United States
	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States