Advancing supercomputer performance through interconnection topology synthesis

ABSTRACT

In today's many-core era, the interconnection networks have been the key factor that dominates the performance of a computer system. In this paper, we propose a design flow to discover the best topology in terms of the communication latency and physical constraints. First a set of representative candidate topologies are generated for the interconnection networks among computing chips; then an efficient multi-commodity flow algorithm is devised to evaluate the performance. The experiments show that the best topologies identified by our algorithm can achieve better average latency compared to the existing networks.

REFERENCES

• 1: NR Adiga , G Almasi , GS Almasi , Y Aridor , R Barik , D Beece , R Bellofatto , G Bhanot , R Bickford , M Blumrich , AA Bright , J Brunheroto , C Caşcaval , J Castaños , W Chan , L Ceze , P Coteus , S Chatterjee , D Chen , G Chiu , TM Cipolla , P Crumley , KM Desai , A Deutsch , T Domany , MB Dombrowa , W Donath , M Eleftheriou , C Erway , J Esch , B Fitch , J Gagliano , A Gara , R Garg , R Germain , ME Giampapa , B Gopalsamy , J Gunnels , M Gupta , F Gustavson , S Hall , RA Haring , D Heidel , P Heidelberger , LM Herger , D Hoenicke , RD Jackson , T Jamal-Eddine , GV Kopcsay , E Krevat , MP Kurhekar , AP Lanzetta , D Lieber , LK Liu , M Lu , M Mendell , A Misra , Y Moatti , L Mok , JE Moreira , BJ Nathanson , M Newton , M Ohmacht , A Oliner , V Pandit , RB Pudota , R Rand , R Regan , B Rubin , A Ruehli , S Rus , RK Sahoo , A Sanomiya , E Schenfeld , M Sharma , E Shmueli , S Singh , P Song , V Srinivasan , BD Steinmacher-Burow , K Strauss , C Surovic , R Swetz , T Takken , RB Tremaine , M Tsao , AR Umamaheshwaran , P Verma , P Vranas , TJC Ward , M Wazlowski , W Barrett , C Engel , B Drehmel , B Hilgart , D Hill , F Kasemkhani , D Krolak , CT Li , T Liebsch , J Marcella , A Muff , A Okomo , M Rouse , A Schram , M Tubbs , G Ulsh , C Wait , J Wittrup , M Bae , K Dockser , L Kissel , MK Seager , JS Vetter , K Yates, An overview of the BlueGene/L Supercomputer, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-22, November 16, 2002, Baltimore, Maryland
• 2: 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]
• 3: W. Dally. Interconnect-centric computing. Keynote Speech, ISCA, 2007.
• 4: A. Gara et al. Overview of the Blue Gene/L system architecture. IBM J Res & Dev, 49(2/3):195--212, 2005.
• 5: D. Bailey et al. The NAS parallel benchmarks. Technical Report NAS-95-020, NASA Ames Research Center, 1995.
• 6: G. Bhanot et al. Optimizing task layout on the Blue Gene/L supercomputer. IBM J Res & Dev, 49(2/3):489--500, 2005.
• 7: P. Coteus et al. Packaging the Blue Gene/L supercomputer. IBM J Res & Dev, 49(2/3):213--248, 2005.
• 8: Yuanfang Hu , Hongyu Chen , Yi Zhu , Andrew A. Chien , Chung-Kuan Cheng, Physical Synthesis of Energy-Efficient Networks-on-Chip Through Topology Exploration and Wire Style Optimizationz, Proceedings of the 2005 International Conference on Computer Design, p.111-118, October 02-05, 2005 [doi>10.1109/ICCD.2005.84]
• 9: Yuanfang Hu , Yi Zhu , Hongyu Chen , Ronald Graham , Chung-Kuan Cheng, Communication latency aware low power NoC synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147058]
• 10: George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California
• 11: Li-Shiuan Peh , William J. Dally, A Delay Model for Router Microarchitectures, IEEE Micro, v.21 n.1, p.26-34, January 2001 [doi>10.1109/40.903059]
• 12: 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