A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer

Full text

Pdf (1.15 MB)

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: 300 - 309

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Leslie Ann Goldberg
Mark Jerrum
Tom Leighton
Satish Rao

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): 2, Downloads (12 Months): 15, Citation Count: 6

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.166108 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.

	AM 88	R. }. Anderson and G. L. Miller, Optical Communication for Pointer Based Algorithms, Technical Report CRI 88-14, Computer Science Department, University of Southern California, Los Angeles, CA 90089-0782 USA, 1988.
	Bol 88	B. Bollobds, Martingales, Isoperimetric Inequalities and Random Graphs, in Combinatorics (eds A. ttajnal, L. Lov~sz, and V. T. S6s), Colloq. Math. Soc. Jdnos Bolyai 52 (North Holland 1988) 113-139.
	Col 88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	GT 92	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]
	GV 92	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.1-18, July 08-10, 1992
	GM 91	Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States
	MV 91	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]
	McC 92	W. F. McColl. General Purpose Parallel Computing, pre-print (1992).
	McD 89	C. McDiarmid, On the Method of Bounded Differences, Surveys in Combinatorics, London Math. Soc. Lecture Notes Series 141 (Cambridge Univ. Press, 1989) 148-188.
	MP 75	David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975 [doi>10.1145/321879.321882]
	Rao 92	S. B. Rao, Properties of an Interconnection Architecture Based on Wavelength Division Multiplexing, Technical Report TR-92-009-3-0054-2, NEC Research Institute, 4 Independence Way, Princeton, NJ 08540 USA, 1992.
	Val 90	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

CITED BY 6

	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
	Dannie Durand , Ravi Jain , David Tseytlin, Applying randomized edge coloring algorithms to distributed communication: an experimental study, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.264-274, June 24-26, 1995, Santa Barbara, California, 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
	Dannie Durand , Ravi Jain , David Tseytlin, Parallel I/O scheduling using randomized, distributed edge coloring algorithms, Journal of Parallel and Distributed Computing, v.63 n.6, p.611-618, June 2003
	Sanguthevar Rajasekaran , Sartaj Sahni, Sorting, Selection, and Routing on the Array with Reconfigurable Optical Buses, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1123-1132, November 1997