Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks

Full text

Pdf (1.08 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 278 - 290

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Gustavo D. Pifarré	ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California
Luis Gravano	ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California
Sergio A. Felperin	ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California
Jorge L. C. Sanz	Computer Science Dept., IBM Almaden Research Center, San, José, California., Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 15

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

	BGSS89	Y. Birk, P.B. Gibbons, D. Soroker, a, ld J.L.C. Sanz. A simple lnechanisn~ for efticient barrier synchronization in MIMD machines. RJ 7078 (67141) Computer Science, IBM Almaden Research Center, October 1989.
	BH82	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 [doi>10.1145/800070.802209]
	DS86a	W. Dally and C. Seitz. Deadlock-fi'ee routing in multiprocessor interconnection network. 5206:TR:86, Computer Science Det)a.rtlnellt, California Institute of Technology, i986.
	DS86b	W.J. Dally alld C. L. Seitz. The Torus Routing Chip. Distributed Computing, (1):187- 196, 1986.
	FCS90	M.L. Fulghaxn, R. Cyplmr, and J.L.C. Sanz. A comparison of SIMD hypercube routi~lg strategies. RJ 7722 (71587), IBM Almaden Research Center, 1990.
	Gel81	D. Gelernter. A DAG-based a.lgorithnl for prevention of store-and-forward deadlock in packet networks. IEEE Transactions on Compuiers, c-30:709-715, October 1981.
	GPS91	L. Gravano, G.D. PifarrS, and J.L.C. Sanz. Adaptive Worm-hole Routing in Tori and Itypercubes. T R:91-10, IBM Argentina- CRAAG, March 199i.
	Gun81	K.D. Gunther. Prevention of deadlocks in packet-switched data transport system. IEEE Trausaclions on Co~nmunications, com-29(4), April 1981.
	Hil85	D. ttillis. The Connection Machinc. The MIT Press, 1985.
	KK79	P. Kermani and L. Kleinrock. Virtual Cut- Through: A new computer communication switching technique. Compuier Networks, (3):267-286, 1979.
	Kon90	Smaragda Konstantinidou, Adaptive, minimal routing in hypercubes, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.139-153, March 1990, Boston, Massachusetts, United States
	KS90	S. Konstantinidou , L. Snyder, The chaos router: a practical application of randomization in network routing, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.21-30, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97452]
	Lei90	F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
	LH91	Daniel H. Linder , Jim C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, IEEE Transactions on Computers, v.40 n.1, p.2-12, January 1991 [doi>10.1109/12.67315]
	LM89	T. Leighton and B. Maggs. Expanders might be practical: Fast algorithms for routing around faults on lnultib~ltterflies. In IEEE, editor, 30th AT~nual ,5'y~posium on Foundations of Co~.pulcr ,_.C;ciencc, pages 384--389, October 1989.
	LMR88	T, Leighton, B. Ma.ggs, and S. I{3o. Universal packet routing algoritlLn~s. 1988.
	MS80	P.M. Merlin and P..I. Schweitzer. Deadlock avoidance in store-and-forward networks. 1: Store-and-forward deadlock. IEEE Transaclions on CoT~muntcatiou.s, 28(3), March 1980.
	Ni90	L.M. Ni. Comlnunication Issues in Multicolnputers. In Proceedings of the First Work- .shop on Parallel Processing, Tai'wan, 1990.
	Ni91	I~.M. Ni, February 1991. Personal Colnmunication.
	NS	John Y. Ngai , Charles L. Seitz, A Framework for Adaptive Routing, California Institute of Technology, Pasadena, CA, 1987
	PFGS91	G.D. Pifa.rr~, S.A. Felperin, L. Gra.vano, and J.L.C. Sanz. New techniques for combination, adaptivity, deadlock-fi'eedom and synchronization in massively parallel routing. In Preparation, 1991.
	PGFS91	G.D. Pifarr6, L. Gravauo, S.A. Felperin, and J.L.C. Sanz. Fully-Adaptive Mini~ml Deadlock-Free Pa.cket I'/outing in Ilypercubes, Meshes, and Other Networks. Technical report, IBM Alnm.den Research Center, 1991.
	Pip84	N. Pippenger. Parallel colnmunication with limited buffers. In Foundal.iol~.s of Computer Science, pages 127- 136, 1984.
	Ran85	A.G. Ranade. {low to e~nulate shared memory. In Foundations of Com pulcr Scicuce, pages 185- 194, 1985.
	RBJ88	Abhiram G. Ranade , Sandeep N. Bhatt , Lennart S. Johnsson, The fluent abstract machine, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.71-93, January 1988, Cambridge, Massachusetts, United States
	Upf89	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
	Val82	L.G. Valiant. Optinlality of a two-phase strategy for ro~lting in interconnection networks. March 1982.
	Val88	L.G. Valiant. General purpose parallel archit, ectures. In J. van Leeuwen, editor, Handbook of Theoretical Co~putcr Science. Nortl~-Ilolland, 1988.

CITED BY 15

	Robert Cypher , Luis Gravano, Requirements for deadlock-free, adaptive packet routing, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.25-33, August 10-12, 1992, Vancouver, British Columbia, Canada
	S. N. Bhatt , G. Pucci , A. Ranade , A. L. Rosenberg, Scattering and Gathering Messages in Networks of Processors, IEEE Transactions on Computers, v.42 n.8, p.938-949, August 1993
	Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States
	S. A. Felperin , L. Gravano , G. D. Pifarré , J. L. C. Sanz, Fully-adaptive routing: packet switching performance and wormhole algorithms, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.654-663, November 18-22, 1991, Albuquerque, New Mexico, United States
	Ambrose K. Laing , Robert Cypher, Deadlock-free routing in arbitrary networks via the flattest common supersequence method, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.55-66, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Robert Cypher , Smaragda Konstantinidou, Bounds on the efficiency of message-passing protocols for parallel computers, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.173-181, June 30-July 02, 1993, Velen, Germany
	Smaragda Konstantinidou , Lawrence Snyder, The Chaos Router, IEEE Transactions on Computers, v.43 n.12, p.1386-1397, December 1994
	Jean-Claude Bermond , Miriam Di Ianni , Michele Flammini , Stéphane Pérennès, Deadlock prevention by acyclic orientations, Discrete Applied Mathematics, v.129 n.1, p.31-47, 15 June 2003
	Luis Gravano , Gustavo D. Pifarré , Pablo E. Berman , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1233-1251, December 1994
	Robert Cypher , Luis Gravano, Storage-Efficient, Deadlock-Free Packet Routing Algorithms for Torus Networks, IEEE Transactions on Computers, v.43 n.12, p.1376-1385, December 1994
	G. D. Pifarré , L. Gravano , S. A. Felperin , J. L. C. Sanz, Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.247-263, March 1994
	Gustavo D. Pifarré , Luis Gravano , Gustavo Denicolay , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing in the Hypercube Network, IEEE Transactions on Parallel and Distributed Systems, v.5 n.11, p.1121-1139, November 1994
	José Duato, A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.841-854, August 1996
	Kevin Bolding , Melanie Fulgham , Lawrence Snyder, The Case for Chaotic Adaptive Routing, IEEE Transactions on Computers, v.46 n.12, p.1281-1292, December 1997