A framework for adaptive routing in multicomputer networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A framework for adaptive routing in multicomputer networks

Full text

Pdf (1.19 MB)

Source

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

Santa Fe, New Mexico, United States

Pages: 1 - 9

Year of Publication: 1989

ISBN:0-89791-323-X

Authors

J. Y. Ngai	Department of Computer Science, California Institute of Technology
C. L. Setiz	Department of Computer Science, California Institute of Technology

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): 5, Downloads (12 Months): 26, Citation Count: 32

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/72935.72936 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	Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
	2	William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
	3	[3] William J. Dally and Charles L. Seitz, "The Torus Routing Chip," Distributed Computing (1): 187-196, 1986.
	4	Charles M. Flaig, VLSI Mesh Routing Systems, California Institute of Technology, Pasadena, CA, 1987
	5	J. Y. Ngai, A framework for adaptive routing in multicomputer networks, California Institute of Technology, Pasadena, CA, 1990
	6	[6] P. Kermani and L. Kleinrock, "Virtual Cut-Through: A New Computer Communication Switching Technique," Computer Networks 3(4): 267-286, Sept. 1979.
	7	[7] P. Merlin, and P. Schweitzer, "Deadlock Avoidance in Store-and-Forward Networks -- I: Store-and Forward Deadlock," IEEE Transactions on Communications, Vol. COM-28(3): 345-354, March 1980.
	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	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	10	[10] Alain J. Martin, "A Synthesis Method for Self-timed VLSI Circuits," Proc. 1987 IEEE International Conference on Computer Design: VLSI in Computers & Processors, IEEE Comp. Soc. Press: 224-229, 1987.
	11	[11] Charles L. Seitz, "System Timing," Introduction to VLSI Systems, Chapter 7, C. Mead & L. Conway, Addison- Wesley, 1980.
	12	[12] M. T. Liu, "Distributed Loop Computer Networks," Advances in Computers, M. Yovits, Academic Press: 163-221, 1978.

CITED BY 32

	Amir Ben-Dor , Shai Halevi , Assaf Schuster, Potential function analysis of greedy hot-potato routing, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.225-234, August 14-17, 1994, Los Angeles, California, United States
	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
	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
	Rajendra V. Boppana , Suresh Chalasani, Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks, Proceedings of the 1994 conference on Supercomputing, p.693-702, December 1994, Washington, D.C., United States
	Suresh Chalasani , Rajendra V. Boppana, Fault-Tolerant Wormhole Routing Algorithms for Mesh Networks, IEEE Transactions on Computers, v.44 n.7, p.848-864, July 1995
	Rajendra V. Boppana , Suresh Chalasani, Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Kang G. Shin , Stuart W. Daniel, Analysis and implementation of hybrid switching, ACM SIGARCH Computer Architecture News, v.23 n.2, p.211-219, May 1995
	P. W. Dowd , M. Carrato, High speed routing in a parallel processing environment: a simulation study, Proceedings of the 24th annual symposium on Simulation, p.60-72, April 1991, New Orleans, Louisiana, United States
	Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States
	Suresh Chalasani , Rajendra V. Boppana, Fault-tolerant wormhole routing in tori, Proceedings of the 8th international conference on Supercomputing, p.146-155, July 11-15, 1994, Manchester, England
	Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, ACM SIGARCH Computer Architecture News, v.20 n.2, p.268-277, May 1992
	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
	Bhargav R. Bellur , Galen H. Sasaki, A SAT-based network access scheme for fairness in high speed networks, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.371-381, June 1997
	Ausif Mahmood , Donald J. Lynch , Roger B. Shaffer, Optimally adaptive, minimum-distance, circuit-switched routing in hypercubes, ACM Transactions on Computer Systems (TOCS), v.15 n.2, p.166-193, May 1997
	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
	Smaragda Konstantinidou , Lawrence Snyder, The Chaos Router, IEEE Transactions on Computers, v.43 n.12, p.1386-1397, December 1994
	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
	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
	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
	Kang G. Shin , Stuart W. Daniel, Analysis and Implementation of Hybrid Switching, IEEE Transactions on Computers, v.45 n.6, p.684-692, June 1996
	Rajendra V. Boppana , Suresh Chalasani, Fault-Tolerant Communication with Partitioned Dimension-Order Routers, IEEE Transactions on Parallel and Distributed Systems, v.10 n.10, p.1026-1039, October 1999
	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
	Rajendra V. Boppana , Suresh Chalasani , C. S. Raghavendra, Resource Deadlocks and Performance of Wormhole Multicast Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.535-549, June 1998
	Jack T. Brassil , Rene L. Cruz, Bounds on Maximum Delay in Networks with Deflection Routing, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.724-732, July 1995
	B. Hajek, Bounds on evacuation time for deflection routing, Distributed Computing, v.5 n.1, p.1-6, June 1991
	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
	Ming-Jer Tasi , Sheng-De Wang, A Fully Adaptive Routing Algorithm for Dynamically Injured Hypercubes, Meshes, and Tori, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.163-174, February 1998
	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
	Ramón Beivide , Enrique Herrada , José L. Balcázar , Agustin Arruabarrena, Optimal Distance Networks of Low Degree for Parallel Computers, IEEE Transactions on Computers, v.40 n.10, p.1109-1124, October 1991
	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
	S. Konstantinidou , L. Snyder, The chaos router: a practical application of randomization in network routing, ACM SIGARCH Computer Architecture News, v.19 n.1, p.79-88, March 1991
	Suresh Chalasani , Rajendra V. Boppana, Adaptive Multimodule Routers for Multiprocessor Architectures, Information Systems Frontiers, v.7 n.3, p.317-327, July 2005