Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Increasing integrated-circuit pin bandwidth has motivateda corresponding increase in the degree or radix of interconnection networksand their routers. This paper introduces the flattened butterfly, a cost-efficient topology for high-radix networks. On benign (load-balanced) traffic, the flattened butterfly approaches the cost/performance of a butterfly network and has roughly half the cost of a comparable performance Clos network.The advantage over the Clos is achieved by eliminating redundant hopswhen they are not needed for load balance. On adversarial traffic, the flattened butterfly matches the cost/performance of a folded-Clos network and provides an order of magnitude better performance than a conventional butterfly.In this case, global adaptive routing is used to switchthe flattened butterfly from minimal to non-minimal routing - usingredundant hops only when they are needed. Minimal and non-minimal, oblivious and adaptive routing algorithms are evaluated on the flattened butterfly.We show that load-balancing adversarial traffic requires non-minimalglobally-adaptive routing and show that sequential allocators are required to avoid transient load imbalance when using adaptive routing algorithms.We also compare the cost of the flattened butterfly to folded-Clos, hypercube,and butterfly networks with identical capacityand show that the flattened butterfly is more cost-efficient thanfolded-Clos and hypercube topologies.

REFERENCES

• 1: Amphenol. http://www.amphenol.com/.
• 2: L. N. Bhuyan and D. P. Agrawal. Generalized hypercube and hyperbus structures for a computer network. IEEE Trans. Computers, 33(4):323--333, 1984.
• 3: K.-Y. K. Chang et al. A 0.4-4-Gb/s CMOS Quad Transceiver Cell Using On-Chip Regulated Dual-Loop PLLs. IEEE Journal of Solid--State Circuits, 38(5):747--754, 2003.
• 4: C. Clos. A Study of Non-Blocking Switching Networks. The Bell System technical Journal, 32(2):406--424, March 1953.
• 5: Cray XT3. http://www.cray.com/products/systems/xt3/.
• 6: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 7: 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]
• 8: W. J. Dally, P. P. Carvey, and L. R. Dennison. The Avici Terabit Switch/Router. In Proc. of Hot Interconnects, pages 41--50, August 1998.
• 9: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 10: Henry G. Dietz , Timothy Mattox, Compiler Techniques for Flat Neighborhood Networks, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.244-258, August 10-12, 2000
• 11: Gore. http://www.gore.com/electronics.
• 12: E. J. Kim , K. H. Yum , G. M. Link , N. Vijaykrishnan , M. Kandemir , M. J. Irwin , M. Yousif , C. R. Das, Energy optimization techniques in cluster interconnects, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871620]
• 13: John Kim , William J. Dally , Dennis Abts, Adaptive routing in high-radix clos network, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188552]
• 14: 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 [doi>10.1109/ISCA.2005.35]
• 15: C. P. Kruskal and M. Snir. The performance of multistage interconnection networks for multiprocessors. IEEE Trans. Computers, 32(12):1091--1098, 1983.
• 16: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• 17: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States [doi>10.1145/264107.264206]
• 18: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 19: Microprocessor Report. http://www.mdronline.com/.
• 20: C. S. Patel, Power constrained design of multiprocessor interconnection networks, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.408, October 12-15, 1997
• 21: G. Pautsch. Thermal Challenges in the Next Generation of Supercomputers. CoolCon, 2005.
• 22: G. Pfister. An Introduction to the InfiniBand Arechitecture (http://www.infinibandta.org). IEEE Press, 2001.
• 23: 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 [doi>10.1109/ISCA.2006.40]
• 24: S. Scott and G. Thorson. The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus. In Hot Chips 4, Stanford, CA, Aug. 1996.
• 25: Li Shang , Li-Shiuan Peh , Niraj K. Jha, Dynamic Voltage Scaling with Links for Power Optimization of Interconnection Networks, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.91, February 08-12, 2003
• 26: H. J. Siegel. A model of simd machines and a comparison of various interconnection networks. IEEE Trans. Computers, 28(12):907--917, 1979.
• 27: A. Singh. Load-Balanced Routing in Interconnection Networks. PhD thesis, Stanford University, 2005.
• 28: Arjun Singh , William J. Dally , Amit K. Gupta , Brian Towles, GOAL: a load-balanced adaptive routing algorithm for torus networks, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California [doi>10.1145/859618.859641]
• 29: Vassos Soteriou , Li-Shiuan Peh, Design-Space Exploration of Power-Aware On/Off Interconnection Networks, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.510-517, October 11-13, 2004
• 30: L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350--361, 1982.
• 31: Hangsheng Wang , Li-Shiuan Peh , Sharad Malik, Power-driven Design of Router Microarchitectures in On-chip Networks, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.105, December 03-05, 2003
• 32: K.-L. J. Wong, H. Hatamkhani, M. Mansuri, and C.-K. K. Yang. A 27-mW 3.6-Gb/s I/O Transceiver. IEEE Journal of
• 33: S. Young and S. Yalamanchili. Adaptive routing in generalized hypercube architectures. In Proc. of the IEEE Symposium on Parallel and Distributed Processing, pages 564--571, Dallas, TX, Dec. 1991.

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:
Design, Performance

Keywords:
cost model, flattened butterfly, global adaptive routing, high-radix routers, interconnection networks, topology