Efficient schemes for parallel communication

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient schemes for parallel communication

Full text

Pdf (345 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing table of contents

Ottawa, Canada

Pages: 55 - 59

Year of Publication: 1982

ISBN:0-89791-081-8

Author

Eli Upfal

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 9

Additional Information:

abstract 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/800220.806682 What is a DOI?

ABSTRACT

A fundamental problem in the theory of parallel computation is to find an efficient interconnection pattern between N processors that minimizes the number of lines entering or leaving each processor while enabling fast communication between the processors. A family of Balanced communication schemes for connecting N processors with only a constant number of lines entering or leaving each processor is defined. It is proved that this network topology enables a fully distributed algorithm to route in parallel N packets each located in distinct processors to their distinct destinations in O(log2N) steps. Thus we give an optimal solution to the above problem.

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	D. Angluin and L. G. Valiant, Fast probabilistic algorithm for Hamiltonian circuits and matchings. J. of Comp. and Syst. Sci. (1979) 155-193.
	2	H. Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Ann. of Math. Stat. 23(1952) 493-507.
	3	W. Hoeffding. On the distribution of the number of successes in independent trails. Ann. of Math. Stat. 27 (1956) 713-721.
	4	G. M. Masson, G. C. Gingher and S. Nakamura. A sample of circuit switching networks. Computer. June 1979, 32-48.
	5	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]
	6	H. J. Siegel. Interconnection networks for SIMD machines. Computer. June 1979, 57-65.
	7	L. G. Valiant. A scheme for fast parallel communication. Report CSR-72-80, Computer Science Department, Edinburgh University, (1980).
	8	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

CITED BY 9

	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
	Oded Goldreich , Dror Sneh, On the complexity of global computation in the presence of link failures: the case of uni-directional faults, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.103-112, August 10-12, 1992, Vancouver, British Columbia, Canada
	B. Aiello , F. T. Leighton , B. Maggs , M. Newman, Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.55-64, July 02-06, 1990, Island of Crete, Greece
	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987
	Zvi Galil , Wolfgang J. Paul, An Efficient General-Purpose Parallel Computer, Journal of the ACM (JACM), v.30 n.2, p.360-387, April 1983
	Y.-D. Lyuu, Fast-fault-tolerant parallel communication and on-line maintenance using information dispersal, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.378-387, July 02-06, 1990, Island of Crete, Greece
	D. Mitra , R. A. Cieslak, Randomized parallel communications on an extension of the omega network, Journal of the ACM (JACM), v.34 n.4, p.802-824, Oct. 1987
	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
	Eli Shamir , Eli Upfal, N-processors graphs distributively achieve perfect matchings in O(log2N) beats, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.238-241, August 18-20, 1982, Ottawa, Canada