Indirect adaptive routing on large scale interconnection networks

ABSTRACT

Recently proposed high-radix interconnection networks [10] require global adaptive routing to achieve optimum performance. Existing direct adaptive routing methods are slow to sense congestion remote from the source router and hence misroute many packets before such congestion is detected. This paper introduces indirect global adaptive routing (IAR) in which the adaptive routing decision uses information that is not directly available at the source router. We describe four IAR routing methods: credit round trip (CRT) [10], progressive adaptive routing (PAR), piggyback routing (PB), and reservation routing (RES). We evaluate each of these methods on the dragonfly topology under both steady-state and transient loads. Our results show that PB, PAR, and CRT all achieve good performance. PB provides the best absolute performance, with 2-7% lower latency on steady-state uniform random traffic at 70% load, while PAR provides the fastest response on transient loads. We also evaluate the implementation costs of the indirect adaptive routing methods and show that PB has the lowest implementation cost requiring <1% increase in the total storage of a typical high-radix router.

REFERENCES

• 1: Rajendra V. Boppana , Suresh Chalasani, A comparison of adaptive wormhole routing algorithms, Proceedings of the 20th annual international symposium on Computer architecture, p.351-360, May 16-19, 1993, San Diego, California, United States
• 2: Wook Choi , Sajal K. Das, Design and performance analysis of a proxy-based indirect routing scheme in ad hoc wireless networks, Mobile Networks and Applications, v.8 n.5, p.499-515, October 2003 [doi>10.1023/A:1025185727264]
• 3: C. Clos. A study of non-blocking switching networks. Bell System Technical Journal, 32:406--424, 1953.
• 4: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 5: 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
• 6: 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]
• 7: P. Gratz, B. Grot, and S. W. Keckler. Regional congestion awareness for load balance in networks-on-chip. High Performance Computer Architecture, 2008. HPCA 2008. IEEE 14th International Symposium on, pages 203--214, Feb 2008.
• 8: 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 [doi>10.1109/71.334898]
• 9: John Kim , William J. Dally , Dennis Abts, Flattened butterfly: a cost-efficient topology for high-radix networks, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 10: John Kim , Wiliam J. Dally , Steve Scott , Dennis Abts, Technology-Driven, Highly-Scalable Dragonfly Topology, Proceedings of the 35th International Symposium on Computer Architecture, p.77-88, June 21-25, 2008
• 11: John Kim , William Dally , Steve Scott , Dennis Abts, Cost-Efficient Dragonfly Topology for Large-Scale Systems, IEEE Micro, v.29 n.1, p.33-40, January 2009 [doi>10.1109/MM.2009.5]
• 12: John Kim , William J. Dally , Brian Towles , Amit K. Gupta, Microarchitecture of a High-Radix Router, Proceedings of the 32nd annual international symposium on Computer Architecture, p.420-431, June 04-08, 2005
• 13: Amit Kumar , Li-Shiuan Peh , Niraj K. Jha, Token flow control, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.342-353, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771803]
• 14: 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]
• 15: Olav Lysne , Sven-Arne Reinemo , Tor Skeie , Ashild Gronstad Solheim , Thomas Sodring , Lars Paul Huse , Bjorn Dag Johnsen, Interconnection Networks: Architectural Challenges for Utility Computing Data Centers, Computer, v.41 n.9, p.62-69, September 2008 [doi>10.1109/MC.2008.391]
• 16: Steve Scott , Dennis Abts , John Kim , William J. Dally, The BlackWidow High-Radix Clos Network, Proceedings of the 33rd annual international symposium on Computer Architecture, p.16-28, June 17-21, 2006
• 17: S. L. Scott and G. M. Thorson. The cray T3E network: Adaptive routing in a high performance 3D torus. In Hot Interconnects, pages 147--156, August 1996.
• 18: A. Singh. Load-Balanced Routing in Interconnection Networks. PhD thesis, Stanford University, 2005.
• 19: Arjun Singh , William J. Dally , Amit K. Gupta , Brian Towles, Adaptive channel queue routing on k-ary n-cubes, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007915]
• 20: L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350--361, 1982.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Performance

Keywords:
dragonfly, interconnection networks, routing