Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks

Full text

Pdf (882 KB)

Source

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

San Diego, California, United States

Pages: 3 - 12

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Pablo E. Berman
Luis Gravano
Gustavo D. Pifarré
Jorge L. C. Sanz

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): 3, Downloads (12 Months): 24, Citation Count: 33

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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

	BCC+88	S. Borkar , R. Cohn , G. Cox , S. Gleason , T. Gross, Warp: an integrated solution of high-speed parallel computing, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.330-339, November 12-17, 1988, Orlando, Florida, United States
	BS91	K. Bolding and L. Snyder. Mesh and torus chaotic routing. UW CS91-04-04, University of Washington, 1991. To appear in the MIT/Brown Advanced Research in VLSI and Parallel Systems Conference, March 1992.
	CEDK91	F. Chong, E. Egozy, A. DeHon, and T. Knight. Multipath fault tolerance in multistage interconnection networks. Transit note #48~ MIT~ June 1991.
	CG92a	R. Cypher and L. Gravano. Adaptive deadlock-free packet routing in torus networks with minimal storage. RJ:8571 (77350), IBM Almaden Research Center, January 1992. To be presented in ICPP '92.
	CG92b	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 [doi>10.1145/135419.135425]
	DA90	W.J. Dally and H. Aoki. Adaptive Routing using Virtual Channels. Technical report, MIT, 1990.
	Dal90	William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
	DS86	W.J. Dally and C. L. Seitz. The Torus Routing Chip. Distributed Computing, pages 187-196, 1986.
	DS87	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	Dua91	J. Duato. Deadlock-free adaptive routing algorithms for multicomputers" Evaluation of a new algorithm. In Proceedings of the 3ra IEEE Symposium on Parallel and Distributed Processing. IEEE, December 1991.
	FGPS91	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 [doi>10.1145/125826.126141]
	FLBS91	S.A. Felperin, H. Laffitte, G. Buranits, and J.L.C. Sanz. Deadlock-free minimal packet routing in the torus network. TR:91-22, IBM Argentina, CRAAG, 1991.
	GPFS91	L. Gravano, G.D. Pifarr~, S. A. Felperin, and J.L.C. Sanz. Adaptive deadlock-free worm-hole routing with all minimal paths. TR:91-21, IBM Argentina, CRAAG, August 1991.
	Hil85	W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
	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]
	KS91	S. Konstantinidou , L. Snyder, Chaos router: architecture and performance, Proceedings of the 18th annual international symposium on Computer architecture, p.212-221, May 27-30, 1991, Toronto, Ontario, Canada
	KU91	S. Konstantinidou and E. Upfal. Experimental comparison of multistage interconnection networks. RJ:8451 (76459), IBM Almaden Research Center, November 1991.
	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]
	LLK+91	D. Lenoski, 3. Laudon, Garachorloo K., A. Gupta, W. Weber, and J. Hennessy. Overview and status of the dash multiprocessor. In International Sympos,um on Shared Memory Multiprocesszng. Tokyo, Japan, 1991.
	LM89	T. Leighton and B. Maggs. Expanders might be practical" Fast algorithms for routing around faults on multibutterflies. In IEEE, editor, 30th Annual Symposium on Foundations of Computer Science, pages 384-389, October 1989.
	NS87	John Y. Ngai , Charles L. Seitz, A Framework for Adaptive Routing, California Institute of Technology, Pasadena, CA, 1987
	PGFS91	Gustavo D. Pifarré , Luis Gravano , Sergio A. Felperin , Jorge L. C. Sanz, Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.278-290, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113405]
	Ran85	A.G. Ranade. How to emulate shared memory. In Foundations of Computer Science, 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
	RU91	P. Raghavan and E. Upfal. A theory of wormhole routing in parallel computers. Technical report, IBM Research, December 1991.
	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]
	Val88	L.G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoreiical Compuier Science. North-Holland, 1988.

CITED BY 33

	Loren Schwiebert, Deadlock-free oblivious wormhole routing with cyclic dependencies, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.149-158, June 23-25, 1997, Newport, Rhode Island, United States
	Swaminathan Ramany , Derek Eager, Quantifying achievable routing performance in multiprocessor interconnection networks, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.270-271, May 1996
	Patrick T. Gaughan , Sudhakar Yalamanchili, A Family of Fault-Tolerant Routing Protocols for Direct Multiprocessor Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.482-497, May 1995
	Dianne R. Kumar , Walid A. Najjar , Pradip K. Srimani, A New Adaptive Hardware Tree-Based Multicast Routing in K-Ary N-Cubes, IEEE Transactions on Computers, v.50 n.7, p.647-659, July 2001
	Yu-Chee Tseng , Sandeep K. S. Gupta, All-to-All Personalized Communication in a Wormhole-Routed Torus, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.498-505, May 1996
	Denvil Smith, A flit level simulator for wormhole routing, Proceedings of the 38th annual on Southeast regional conference, April 07-08, 2000, Clemson, South Carolina
	Loren Schwiebert , D. N. Jayasimha, A universal proof technique for deadlock-free routing in interconnection networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.175-184, June 24-26, 1995, Santa Barbara, California, 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
	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
	Loren Schwiebert, Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependencies, IEEE Transactions on Computers, v.50 n.9, p.865-876, September 2001
	Patrick T. Gaughan , Binh V. Dao , Sudhakar Yalamanchili , David E. Schimmel, Distributed, Deadlock-Free Routing in Faulty, Pipelined, Direct Interconnection Networks, IEEE Transactions on Computers, v.45 n.6, p.651-665, June 1996
	Federico Silla , José Duato, High-Performance Routing in Networks of Workstations with Irregular Topology, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.699-719, July 2000
	Yu-Chee Tseng , Sze-Yao Ni , Jang-Ping Sheu, Toward Optimal Complete Exchange on Wormhole-Routed Tori, IEEE Transactions on Computers, v.48 n.10, p.1065-1082, October 1999
	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
	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
	José Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1055-1067, October 1995
	José Duato, A Theory of Deadlock-Free Adaptive Multicast Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.976-987, September 1995
	Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, Journal of the ACM (JACM), v.42 n.1, p.91-123, Jan. 1995
	Swaminathan Ramany , Derek Eager, The interaction between virtual channel flow control and adaptive routing in wormhole networks, Proceedings of the 8th international conference on Supercomputing, p.136-145, July 11-15, 1994, Manchester, England
	Fabrizio Petrini , Marco Vanneschi, Minimal adaptive routing with limited injection on Toroidal k-ary n-cubes, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.23-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	Susan Hinrichs , Corey Kosak , David R. O'Hallaron , Thomas M. Stricker , Riichiro Take, An architecture for optimal all-to-all personalized communication, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.310-319, June 27-29, 1994, Cape May, New Jersey, United States
	Rajendra V. Boppana , Suresh Chalasani, A comparison of adaptive wormhole routing algorithms, ACM SIGARCH Computer Architecture News, v.21 n.2, p.351-360, May 1993
	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
	Rajendra V. Boppana , Suresh Chalasani, A Framework for Designing Deadlock-Free Wormhole Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.7 n.2, p.169-183, February 1996
	Andrew A. Chien, A Cost and Speed Model for k-ary n-Cube Wormhole Routers, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.150-162, February 1998
	Jae H. Kim , Ziqiang Liu , Andrew A. Chien, Compressionless Routing: A Framework for Adaptive and Fault-Tolerant Routing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.3, p.229-244, March 1997
	K. V. Anjan , Timothy Mark Pinkston, An efficient, fully adaptive deadlock recovery scheme: DISHA, ACM SIGARCH Computer Architecture News, v.23 n.2, p.201-210, May 1995
	Eric Fleury , Pierre Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.626-638, July 1998
	Dimiter Avresky , Natcho Natchev, Dynamic Reconfiguration in Computer Clusters with Irregular Topologies in the Presence of Multiple Node and Link Failures, IEEE Transactions on Computers, v.54 n.5, p.603-615, May 2005
	G. Campobello , G. Patané , M. Russo, Hardware for multiconnected networks: a case study, Information Sciences—Informatics and Computer Science: An International Journal, v.158 n.1, p.173-188, January 2004
	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
	Philip K. McKinley , Hong Xu , Lionel M. Ni , Abdol-Hossein Esfahanian, Unicast-Based Multicast Communication in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1252-1265, 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