A universal proof technique for deadlock-free routing in interconnection networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A universal proof technique for deadlock-free routing in interconnection networks

Full text

Pdf (1.17 MB)

Source

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

Santa Barbara, California, United States

Pages: 175 - 184

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Loren Schwiebert	Department of Computer and Information Science, The Ohio State University, Columbus, OH
D. N. Jayasimha	Department of Computer and Information Science, The Ohio State University, Columbus, OH

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
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): 6, Downloads (12 Months): 27, 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/215399.215440 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	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 [doi>10.1145/140901.140902]
	2	Y. M. Boura and C. R. Das. A Class of Partially Adaptive Routing Algorithms for n_dimensional Meshes. In international Conference on Parallel Processing, volume III, pages 175-182, 1993.
	3	A. A. Chien. A Cost and Speed Model for k-ary n-cube Wormhole Routers. In Hot Interconnects '93, August 1993.
	4	R. Cypher and L. Gravano. Adaptive, Deadlock-Free Packet Routing in Torus Networks with Minimal Storage. In international Conference on Parallel Processing, volume III, pages 204-211, 1992.
	5	Robert Cypher , Luis Gravano, Requirements for Deadlock-Free, Adaptive PacketRouting, SIAM Journal on Computing, v.23 n.6, p.1266-1274, Dec. 1994 [doi>10.1137/S0097539792231830]
	6	W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
	7	W. J. Dally , H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.466-475, April 1993 [doi>10.1109/71.219761]
	8	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]
	9	J. Duato, On the design of deadlock-free adaptive routing algorithms for multicomputers: design methodologies, Proceedings on Parallel architectures and languages Europe : volume I: parallel architectures and algorithms: volume I: parallel architectures and algorithms, p.390-405, June 1991, Eindhoven, The Netherlands
	10	J. Duato. A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks. Technical report, Universidad Politecnica de Valencia, 1993.
	11	José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
	12	J. Duato. A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks. In International Conference on Parallel Processing, volume I, pages 142-149, 1994.
	13	Patrick T. Gaughan , Sudhakar Yalamanchili, Adaptive routing protocols for hypercube interconnection networks, Computer, v.26 n.5, p.12-23, May 1993 [doi>10.1109/2.211888]
	14	C. Glass and L. M. Ni. Maximally Fully Adaptive Routing in 2D Meshes. In International Conference on Parallel Processing, volume I, pages 101-104, 1992.
	15	Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Proceedings of the 19th annual international symposium on Computer architecture, p.278-287, May 19-21, 1992, Queensland, Australia
	16	Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Journal of the ACM (JACM), v.41 n.5, p.874-902, Sept. 1994 [doi>10.1145/185675.185682]
	17	I. S. Gopal. Prevention of Store-and-Forward Deadlock in Computer Networks. IEEE Transactions on Communications, COM-33(12): 1258-1264, December 1985.
	18	Luis Gravano , Gustavo D. Pifarré , Gustavo Denicolay , Jorge L. C. Sanz, Adaptive Deadlock-Free Worrnhole Routing in Hypercubes, Proceedings of the 6th International Parallel Processing Symposium, p.512-515, March 01, 1992
	19	K. D. Gtinther. Prevention of Deadlocks in Packet- Switched Data Transport Systems. IEEE Transactions on Communications, COM-29(4):512-524, April 1981o
	20	R Kermani and L. Kleinrock. Virtual Cut-Through: A New Computer Communication Switching Technique. Computer Networks, 3(4):267-286, September 1979.
	21	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
	22	X. Lin, R K. McKinley, and L. M. Ni. The Message Flow Model for Routing in Wormhole-Routed Networks. In International Conference on Parallel Processing, volume I, pages 294-297, 1993.
	23	J. May, D. N. Jayasimha, and K. Patel. Comparison of Multiplexing Schemes for Wormhole-Routed Distributed Memory Multiprocessors. In 1st International Workshop on Parallel Processing, pages 211- 215, 1994.
	24	J. Y. Ngai , C. L. Setiz, A framework for adaptive routing in multicomputer networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.1-9, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72936]
	25	Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
	26	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 [doi>10.1109/71.277792]
	27	L. Schwiebert , D. N. Jayasimha, Optimal fully adaptive wormhole routing for meshes, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.782-791, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169835]
	28	Loren Schwiebert , D. N. Jayasimha, A necessary and sufficient condition for deadlock-free wormhole routing, Journal of Parallel and Distributed Computing, v.32 n.1, p.103-117, Jan. 10, 1996 [doi>10.1006/jpdc.1996.0008]
	29	C.-C. Su and K. G. Shin. Adaptive Deadlock-Free Routing in Multicomputers Using Only One Extra Virtual Channel. In International Conference on Parallel Processing, volume I, pages 227-231, 1993.
	30	S. Toueg and K. Steiglitz. Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks. SIAM Journal on Computing, 10(4):702-712, November 1981.

CITED BY 6

	J. Duato , T. M. Pinkston, A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1219-1235, December 2001
	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
	D. N. Jayasimha , Loren Schwiebert , D. Manivannan , Jeff A. May, A foundation for designing deadlock-free routing algorithms in wormhole networks, Journal of the ACM (JACM), v.50 n.2, p.250-275, March 2003
	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
	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
	Loren Schwiebert, Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependencies, IEEE Transactions on Computers, v.50 n.9, p.865-876, September 2001