Analysis and implementation of hybrid switching

ABSTRACT

The switching scheme of a point-to-point network determines how packets flow through each node, and is a primary element in determining the network's performance. In this paper, we present and evaluate a new switching scheme called hybrid switching. Hybrid switching dynamically combines both virtual cut-through and wormhole switching to provide higher achievable throughput than wormhole alone, while significantly reducing the buffer space required at intermediate nodes when compared to virtual cut-through. This scheme is motivated by a comparison of virtual cut-through and wormhole switching through cycle-level simulations, and then evaluated using the same methods. To show the feasibility of hybrid switching, as well as to provide a common base for simulating and implementing a variety of switching schemes, we have designed SPIDER, a communication adapter built around a custom ASIC, the Programmable Routing Controller (PRC).

REFERENCES

• 1: W. J. Dally and C. L. Seitz, "The torus routing chip," Journal of Distmbuted Computing, vol. 1, no. 3, pp. 187-196, 1986.
• 2: P. Kermani and L. Kleinrock, "Virtual cutthrough: A new computer communication switching technique," Computer Networks, vol. 3, pp. 267-286, September 1979.
• 3: 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]
• 4: 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]
• 5: J. Dolter, S. Daniel, A. Mehra, J. Rexford, W. Feng, and K. Shin, "SPIDER: Flexible and efficient communication support for point-to-point distributed systems," in Proc. Int'l Conf. on Distributed Computing Syslems, pp. 574-580, June 1994.
• 6: Stuart W. Daniel , Jennifer Rexford , James W. Dolter , Kang G. Shin, A programmable routing controller for flexible communications in point-to-point networks, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.320-331, October 02-04, 1995
• 7: Shekhar Borkar , Robert Cohn , George Cox , Thomas Gross , H. T. Kung , Monica Lam , Margie Levine , Brian Moore , Wire Moore , Craig Peterson , Jim Susman , Jim Sutton , John Urbanski , Jon Webb, Supporting systolic and memory communication in iWarp, Proceedings of the 17th annual international symposium on Computer Architecture, p.70-81, May 28-31, 1990, Seattle, Washington, United States
• 8: William J. Dally , J. A. Stuart Fiske , John S. Keen , Richard A. Lethin , Michael D. Noakes , Peter R. Nuth , Roy E. Davison , Gregory A. Fyler, The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms, IEEE Micro, v.12 n.2, p.23-39, March 1992 [doi>10.1109/40.127581]
• 9: D. Smitley, F. Hady, and D. Burns, "Hnet: A highperformance network evaluation testbed," Tech. Rep. SRC-TR-91-049, Supercomputing Research Center, Institute for Defense Analyses, December 1991.
• 10: Craig B. Stunkel , Dennis G. Shea , Bülent Abali , Monty Denneau , Peter H. Hochschild , Douglas Joseph , Ben J. Nathanson , Mickey Tsao , Philip R. Varker, Architecture and Implementation of Vulcan, Proceedings of the 8th International Symposium on Parallel Processing, p.268-274, April 01, 1994
• 11: Al Davis, Mayfly: a general-purpose, scalable, parallel processing architecture, Lisp and Symbolic Computation, v.5 n.1-2, p.7-48, May 1992 [doi>10.1007/BF01811115]
• 12: Kevin Bolding , Sen-Ching Cheung , Sung-Eun Choi , Carl Ebeling , Soha Hassoun , Ton Anh Ngo , Robert Wille, The chaos router chip: design and implementation of an adaptive router, Proceedings of the IFIP TC10/WG 10.5 International Conference on Very Large Scale Integration, p.311-320, September 07-10, 1993
• 13: James William Dolter, A programmable routing controller supporting multi-mode routing and switching in distributed real-time systems, University of Michigan, Ann Arbor, MI, 1993
• 14: A. Kovaleski, S. Ratheal, and F. Lombardi, "An architecture and interconnection scheme for timesliced buses in real-time processing," Proc. Real- Time Systems Symposium, pp. 20-27, 1986.
• 15: Advanced Micro Devices, 901 Thompson Place, P.O. Box 3453, Sunnyvale CA 94088-3453, Am79168/Am79169 TAXItm-275 Technical Manual, ban-0.1m-1/93/0 17490a ed.
• 16: J. Rexford , J. Dolter , Wu-Chang Feng , K. G. Shin, PP-MEss-SIM: a simulator for evaluating multicomputer interconnection networks, Proceedings of the 28th Annual Simulation Symposium, p.84, April 25-28, 1995
• 17: 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]
• 18: A. A. Chien, "A cost and speed model for k-ary n-cube wormhole routers," in Proc. Hot Interconnects, August 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Topology (e.g., bus, point-to-point)

General Terms:
Algorithms, Design, Theory, Verification