Fully-adaptive routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully-adaptive routing: packet switching performance and wormhole algorithms

Full text

Pdf (978 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1991 ACM/IEEE conference on Supercomputing table of contents

Albuquerque, New Mexico, United States

Pages: 654 - 663

Year of Publication: 1991

ISBN:0-89791-459-7

Authors

S. A. Felperin	CRAAG IBM Argentina, ESLAI
L. Gravano	CRAAG IBM Argentina, ESLAI
G. D. Pifarré	CRAAG IBM Argentina, ESLAI
J. L. C. Sanz	IBM Almaden Research Center, CRAAG IBM Argentina

Sponsors

IEEE : Institute of Electrical and Electronics Engineers
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/125826.126141 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	K. Gunther, "Prevention of deadlocks in packetswitched data transport system," IEEE Transaclzons on Communications, vol. com-29, April 1981.
	2	P. Merlin and P. Schweitzer, "Deadlock avoidance in store-and-forward networks. 1' Store-andforward deadlock," IEEE Transactions on Communications, vol. 28, March 1980.
	3	W. Dally and C. Seitz, "Deadlock-free routing in multiprocessor interconnection network," 5206:TR:86, Computer Science Department, California Institute of Technology, 1986.
	4	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]
	5	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]
	6	L. G. Valiant, "Optimality of a two-phase strategy for routing in interconnection networks," March 1982.
	7	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]
	8	A. Ranade, "How to emulate shared memory," in Foundations of Computer Science, pp. 185- 194, 1985.
	9	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]
	10	M. Fulgham, R. Cypher, and J. Sanz, "A comparison of SIMD hypercube routing strategies," RJ 7722 (71587), IBM Almaden Research Center, 1990.
	11	T. Leighton, D. Lisinski, and B. Maggs, "Empirical evaluation of randomly-wired multistage networks," in ICCD'90, 1990.
	12	R. Cypher , C. G. Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.193-203, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100240]
	13	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]
	14	J. Patel, "Performance of processor-memory interconnections for multiprocessors," IEEE Transactions on Compulers, vol. c-30, pp. 771-780, October 1981.
	15	C. Kruskal and M. Snir, "The performance of multistage interconnection networks for multiprocessors," IEEE Transactions on Computers, vol. c-32, pp. 1091-1098, December 1983.
	16	D. Dins and J. Jump, "Analisys and simulations of buffered delta networks," IEEE Transactions on Computers, vol. c-30, pp. 273-282, April 1981.
	17	G. Pfister and V. Norton, "'hot spot' contention and combining in multistage interconnection networks," IEEE Transactions on Computers, vol. c- 34, pp. 943-948, October 1985.
	18	S. Felperin and J. Sanz, "Simulation Results on the Performance of Fully-Adaptive Minimal Deadlock-Free Routing for Meshes and Hypercubes," TR:91-06, IBM Argentina, CRAAG, March 1991.
	19	L. Gravano, G. Pifarr6, and J. Sanz, "Adaptive Worm-hole' Lting in Tori and Hypercubes," TR:91-1 .8M Argentina - CRAAG, March 1991.
	20	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
	21	J. Ngai and C. Seitz, "Adaptive routing in multicomputers," in Opportunities and constraints of parallel computing (J. Sanz, ed.), Springer Verlag, New York, 1989.
	22	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]

CITED BY 11

	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
	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
	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
	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
	Chung-Ta King , Wei-Kuo Liao, Valved Routing: Efficient Flow Control for Adaptive Nonminimal Routing in Interconnection Networks, IEEE Transactions on Computers, v.44 n.10, p.1181-1193, October 1995
	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
	L. D. Aronson, Homogeneous Routing for Homogeneous Traffic Patterns on Meshes, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.781-793, August 2000
	Ahmed Louri , Brent Weech , Costas Neocleous, A Spanning Multichannel Linked Hypercube: A Gradually Scalable Optical Interconnection Network for Massively Parallel Computing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.5, p.497-512, May 1998
	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
	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