Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Full text

Pdf (1.73 MB)

Source

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

Dallas, Texas, United States

Pages: 378 - 388

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Richard Cole	Courant Institute, New York University, New York, NY
Bruce M. Maggs	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Friedhelm Meyer auf der Heide	Department of Mathematics and Computer Science, and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany
Michael Mitzenmacher	Digital Systems Research Center, Palo Alto, CA
Andréa W. Richa	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Klaus Schröder	Department of Mathematics and Computer Science, and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany
Ramesh K. Sitaraman	Department of Computer Science, University of Massachusetts, Amherst, MA
Berthold Vöcking	Department of Mathematics and Computer Science, and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 5

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/276698.276790 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	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	2	Sanjeev Arora , F. T. Leighton , Bruce M. Maggs, On-line Algorithms for Path Selectionin a Nonblocking Network, SIAM Journal on Computing, v.25 n.3, p.600-625, June 1996 [doi>10.1137/S0097539791221499]
	3	J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. Online machine scheduling vfith applications to load balancing and virtual circuit routing. In Prec. 25th Annual ACM Symposium on Theory of Computing, pages 240--249, November 1994.
	4	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
	5	L. A. Bassalygo and M. S. Pinsker. Complexity of an optimum nonblocking switching network without reconnections. Problems of lnformation Transmission, 9:64-66, 1974.
	6	K. Batcher. Sorting networks and their applications. In Proceedings of the AFIP$ Spring Joint Computing Conference, volume 32, pages 307-314, 1968.
	7	Butterfly'r~f Parallel Processor Overview. BBN Report No. 6148, Version i, Cambridge, MA, March 1986.
	8	B. Beizer. The analysis and synthesis of signal switching net. works. In Proceedings of the S37nposium on Mathematical Theory of Automata, pages 563-576, Brooklyn, NY, 1962. Brooklyn Polytechnic Institute.
	9	V. E. Beneg. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal, 43:1641-I 656, July 1964.
	10	Richard J. Cole , Bruce M. Maggs , Ramesh K. Sitaraman, On the benefit of supporting virtual channels in wormhole routers, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.131-141, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237517]
	11	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
	12	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
	13	Sergio A. Felperin , Prabhakar Raghavan , Eli Upfal, An Experimental Study of Wormhole Routing in Parallel Computers, Proceedings of the First Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, p.156-165, November 11-13, 1992
	14	Juan A. Garay , Inder S. Gopal, Call preemption in communication networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.1043-1050, May 1992, Florence, Italy
	15	A. Gottlieb. An overview of the NYU Ultracomputer Project. in .1.. J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 25-95. Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1987.
	16	Ikeno. A limit on crosspoint number. IRE Trans. on lnfo. Theoo: 5, pages 187-196, 1959.
	17	R. Karp, M. Luby, and F. Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algoritlvnica 16, pages 245-28 I, 1996.
	18	R.R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 221-230. IEEE Computer Society Press, October 1988.
	19	C.P. Kruskal and M. Snir. The performance of multistage in.. terconnection networks for multiprocessors. IEEE Transactions on Computers, C-32(12):1091-I098, December 1983.
	20	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	21	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]
	22	F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992 [doi>10.1109/12.142684]
	23	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	24	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129728]
	25	E Meyer aut'der Heide and B. Vficking. A packet routing protocol for arbitrary ned, or 'ks. In Proceedings of the I2th Symposium on Theoretical Aspects of Computer Science, pages 291-302, March 1995.
	26	M. Mitzenmacher, Load balancing and density dependent jump Markov processes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.213, October 14-16, 1996
	27	Friedhelm Meyer auf der Heide , Christian Scheideler , Volker Stemann, Exploiting storage redundancy to speed up randomized shared memory simulations, Theoretical Computer Science, v.162 n.2, p.245-281, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00032-1]
	28	T. Nakata, S. Matsushita, N. Tanabe, N. Kajihara, H. Onozuka, ~: Asano, and N. Koike. Parallel programming on Cenju: A multiprocessor system for modular circuit simulation. NEC Research & Development, 32(3):421-429, July 1991.
	29	G.F. Pfister, W. C. Branfiey D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. MeAulift~, E. A. Melton, V. A. Norton, and J. Weiss. An introduction to the IBM Research Parallel Processor Prototype (RP3). In J. J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 123-140. Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1987.
	30	D. Nassimi and S. Sahni. Parallel algorithms to set up the Beneg permutation network. IEEE Transactions on Comput. ers, C-31(2):148-154, Feb, 1982.
	31	N. Pippenger. Parallel communication with limited buft~r~. In Proceedings of the 25th Annual Symposittm on Foundations of Computer Science, pages 127-136. IEEE Computer Society Press, October 1984.
	32	Nicholas Pippenger, Self-routing superconcentrators, Journal of Computer and System Sciences, v.52 n.1, p.53-60, Feb. 1996 [doi>10.1006/jcss.1996.0005]
	33	S. Plotldn. Competitive routing in ATM networks. IEEEJottr nal on Selected Areas in Communication, pages 1128-1136, August 1995.
	34	A. G. Ranade. Constrained randomization for parallel communication. Technical Report YALEU/DCS/TR-511, Department of Computer Science, Yale University, New Haven, CT, 1987.
	35	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	36	A. Ranade, S. Schleimer, and D. S. Wilkerson. Nearly tight bounds for wormhole routing, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
	37	Reza Rooholamini , Vladimir Cherkassky , Mark Garver, Finding the right ATM switch for the market, Computer, v.27 n.4, p.16-28, April 1994 [doi>10.1109/2.274995]
	38	J. Turner and N. Yamanaka. Architectural Choices in Large Scale ATM Switches. Technical Report WUCS-97-21. Department of Computer Science, Washington University St. Louis, MO. 1997.
	39	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]
	40	Eli Upfal, An O(log N) deterministic packet-routing scheme, Journal of the ACM (JACM), v.39 n.1, p.55-70, Jan. 1992 [doi>10.1145/147508.147517]
	41	L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350-361, May 1982.
	42	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]
	43	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

CITED BY 5

	Petra Berenbrink , Artur Czumaj , Tom Friedetzky , Nikita D. Vvedenskaya, Infinite parallel job allocation (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.99-108, July 09-13, 2000, Bar Harbor, Maine, United States
	Berthold Vöcking, How asymmetry helps load balancing, Journal of the ACM (JACM), v.50 n.4, p.568-589, July 2003
	Krishnaram Kenthapadi , Rina Panigrahy, Balanced allocation on graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.434-443, January 22-26, 2006, Miami, Florida
	Brian D. Alleyne , Isaac D. Scherson, On Evil Twin Networks and the Value of Limited Randomized Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.9, p.910-925, September 2000
	Volker Strumpen , Arvind Krishnamurthy, A collision model for randomized routing in fat-tree networks, Journal of Parallel and Distributed Computing, v.65 n.9, p.1007-1021, September 2005