skip to main content
10.1145/2925426.2926275acmconferencesArticle/Chapter ViewAbstractPublication PagesicsConference Proceedingsconference-collections
research-article

Galaxyfly: A Novel Family of Flexible-Radix Low-Diameter Topologies for Large-Scales Interconnection Networks

Published: 01 June 2016 Publication History

Abstract

Interconnection network plays an essential role in the architecture of large-scale high performance computing (HPC) systems. In the paper, we construct a novel family of low-diameter topologies, Galaxyfly, using techniques of algebraic graphs over finite fields. Galaxyfly is guaranteed to retain a small constant diameter while achieving a flexible tradeoff between network scale and bisection bandwidth. Galaxyfly lowers the demands for high radix of network routers and is able to utilize routers with merely moderate radix to build exascale interconnection networks. We present effective congestion-aware routing algorithms for Galaxyfly by exploring its algebraic property. We conduct extensive simulations and analysis to evaluate the performance, cost and power consumption of Galaxyfly against state-of-the-art topologies. The results show that our design achieves better performance than most existing topologies under various routing algorithms and traffic patterns, and is cost-effective to deploy for exascale HPC systems.

References

[1]
D. Abts, M. R. Marty, P. M. Wells, P. Klausler, and H. Liu. Energy proportional datacenter networks. In Proceedings of International Symposium on Computer Architecture (ISCA), pages 338--347, 2010.
[2]
J. H. Ahn, N. Binkert, A. Davis, M. McLaren, and R. S. Schreiber. Hyperx: Topology, routing, and packaging of efficient large-scale networks. In Proceedings of International Conference for High Performance Computing, Networking, Storage, and Analysis (SC), pages 41:1--41:11, 2009.
[3]
S. Ankit, H. Chi-Yao, P. Lucian, and G. P. Brighten. Jellyfish: Networking data centers randomly. In Proceedings of Symposium on Network System Design and Implementation (NSDI), pages 225--238, 2012.
[4]
M. Besta and T. Hoefler. Slim fly: A cost effective low-diameter network topology. In Proceedings of International Conference for High Performance Computing, Networking, Storage, and Analysis (SC), pages 348--359, 2014.
[5]
N. Binkert, A. Davis, N. P. Jouppi, M. McLaren, N. Muralimanohar, R. Schreiber, and J. H. Ahn. The role of optics in future high radix switch design. ACM Sigarch Computer Architecture News, 39(3):437--448, June 2011.
[6]
N. Chrysos, C. Minkenberg, M. Rudquist, C. Basso, and B. Vanderpool. Scoc: High-radix switches made of bufferless clos networks. In Proceedings of High-Performance Computer Architecture (HPCA), pages 402--414, 2015.
[7]
G. Faanes, A. Bataineh, D. Roweth, T. Court, E. Froese, B. Alverson, T. Johnson, J. Kopnick, M. Higgins, and J. Reinhard. Cray cascade: A scalable hpc system based on a dragonfly network. In Proceedings of International Conference for High Performance Computing, Networking, Storage, and Analysis (SC), pages 103:1--103:9, 2012.
[8]
I. Fujiwara, M. Koibuchi, H. Matsutani, and H. Casanova. Skywalk: a topology for hpc networks with low-delay switc. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), pages 263--272, 2014.
[9]
C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, and et al. Bcube: A high performance, server-centric network architecture for modular data centers. In Proceedings of International Conference on the applications, technologies, architectures, and protocols for computer communication (SIGCOMM), pages 63--74, 2009.
[10]
C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu. Dcell: A scalable and fault-tolerant network structure for data centers. ACM SIGCOMM Computer Communication Review, 38(4):75--86, Aug. 2008.
[11]
P. R. Hafner. Geometric realisation of the graphs of mckay- miller- siran. Journal of Combinatorial Theory, 90(2):223--232, 2004.
[12]
N. Hamedazimi, Z. Qazi, H. Gupta, V. Sekar, S. R. Das, J. P. Longtin, H. Shah, and A. Tanwer. Firefly: A reconfigurable wireless data center fabric using free-space optics. In Proceedings of International Conference on the applications, technologies, architectures, and protocols for computer communication (SIGCOMM), pages 319--330, 2014.
[13]
https://en.wikipedia.org/wiki/Isomorphism.
[14]
http://www.avagotech.com/optical_fpga#.
[15]
http://www.colfaxdirect.com.
[16]
http://www.mellanoxstore.com.
[17]
F. Ikki, K. Michihiro, O. Tomoya, M. Hiroki, and C. Henri. Augmenting low-latency hpc network with free-space optical links. In Proceedings of High-Performance Computer Architecture (HPCA), pages 390--401, 2015.
[18]
S. Jeloka, R. Das, R. G. Dreslinski, T. Mudge, and D. Blaauw. Hi-rise: A high-radix switch for 3d integration with single-cycle arbitration. In Proceedings of IEEE Computer Society Technical Committee on Microprogramming and Microarchitecture (MICRO), pages 471--483, 2014.
[19]
J. Kim, W. J. Dally, and D. Abts. Flattened butterfly: A cost-efficient topology for high-radix networks. In Proceedings of International Symposium on Computer Architecture (ISCA), pages 126--137, 2007.
[20]
J. Kim, W. J. Dally, S. Scott, and D. Abts. Technology-driven, highly-scalable dragonfly topology. In Proceedings of International Symposium on Computer Architecture (ISCA), pages 77--88, 2008.
[21]
M. Koibuchi, I. Fujiwara, H. Matsutani, and H. Casanova. Layout-conscious random topologies for hpc off-chip interconnects. In Proceedings of High-Performance Computer Architecture (HPCA), pages 484--495, 2013.
[22]
M. Koibuchi, H. Matsutani, H. Amano, D. F. Hsu, and H. Casanova. A case for random shortcut topologies for hpc interconnects. ACM Sigarch Computer Architecture News, 40(3):177--188, 2012.
[23]
S. B. Mark, D. Mark, H. Ram, K. James, L. Tom, R. Todd, D. U. Keith, and R. C. Zak. Intel omni-path architecture: Enabling scalable, high performance fabrics. In Proceedings of Symposium on High-Performance Interconnects (HOTI), pages 402--414, 2015.
[24]
B. D. McKay, M. Miller, and J. Siran. A note on large graphs of diameter two and given maximum degree. Journal of Combinatorial Theory, 74(1):110--118, 1998.
[25]
T. P. Morgan. The road to 200g networks starts with the transceiver. http://www.nextplatform.com.
[26]
J. Nan, U. B. Daniel, M. George, B. James, T. Brian, K. John, and J. D. William. A detailed and flexible cycle-accurate network-on-chip simulator. In Proceedings of International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 86--96, 2013.
[27]
A. Putnam, A. Caulfield, E. Chung, D. Chiou, K. Constantinides, and et al. A reconfigurable fabric for accelerating large-scale datacenter services. In Proceedings of International Symposium on Computer Architecture (ISCA), pages 13--24, 2014.
[28]
S. Satpathy, K. Sewell, T. Manville, Y.-P. Chen, R. Dreslinski, D. Sylvester, T. Mudge, and D. Blaauw. A 4.5Tb/s 3.4Tb/s/W 64x64 switch fabric with self-updating least-recently-granted priority and quality-of-service arbitration in 45nm CMOS. In Proceedings of International Solid-State Circuits Conference (ISSCC), pages 478--480, 2012.
[29]
S. Scott, D. Abts, J. Kim, and W. J. Dally. The blackwidow high-radix clos network. In Proceedings of International Symposium on Computer Architecture (ISCA), pages 16--28, 2006.
[30]
L. Xiangke, P. Zhengbin, W. Kefei, L. Yutong, X. Min, X. Jun, D. Dezun, and S. Guang. High performance interconnect network for tianhe system. Journal of Computer Science & Technology, 30(2):259--272, 2015.

Cited By

View all
  • (2024)PolarStar: Expanding the Horizon of Diameter-3 NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659975(345-357)Online publication date: 17-Jun-2024
  • (2022)PolarFly: A Cost-Effective and Flexible Low-Diameter TopologySC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00017(1-15)Online publication date: Nov-2022
  • (2021)High-Performance Routing With Multipathing and Path Diversity in Ethernet and HPC NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.303576132:4(943-959)Online publication date: 1-Apr-2021
  • Show More Cited By
  1. Galaxyfly: A Novel Family of Flexible-Radix Low-Diameter Topologies for Large-Scales Interconnection Networks

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ICS '16: Proceedings of the 2016 International Conference on Supercomputing
    June 2016
    547 pages
    ISBN:9781450343619
    DOI:10.1145/2925426
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 June 2016

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. flexible-radix
    2. high performance computing
    3. interconnection
    4. low-diameter
    5. topology

    Qualifiers

    • Research-article
    • Research
    • Refereed limited

    Conference

    ICS '16
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 629 of 2,180 submissions, 29%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)18
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 09 Mar 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)PolarStar: Expanding the Horizon of Diameter-3 NetworksProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659975(345-357)Online publication date: 17-Jun-2024
    • (2022)PolarFly: A Cost-Effective and Flexible Low-Diameter TopologySC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00017(1-15)Online publication date: Nov-2022
    • (2021)High-Performance Routing With Multipathing and Path Diversity in Ethernet and HPC NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.303576132:4(943-959)Online publication date: 1-Apr-2021
    • (2020)Designing low‐diameter interconnection networks with multi‐ported host‐switch graphsConcurrency and Computation: Practice and Experience10.1002/cpe.611535:11Online publication date: 3-Dec-2020
    • (2019)DeepHiRProceedings of the ACM International Conference on Supercomputing10.1145/3330345.3330381(403-413)Online publication date: 26-Jun-2019
    • (2019)Designing High-Performance Interconnection Networks with Host-Switch GraphsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286428630:2(315-330)Online publication date: 1-Feb-2019
    • (2019)Fault-Tolerant Adaptive Routing in Dragonfly NetworksIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.269337216:2(259-271)Online publication date: 1-Mar-2019
    • (2019)The Degree Diameter Problem for Host-Switch Graphs2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW.2019.00050(249-255)Online publication date: Nov-2019

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media