Early evaluation of direct large-scale InfiniBand networks with adaptive routing

Alexander N. Daryin; Anton A. Korzh

doi:10.14529/jsfi140303

Authors

Alexander N. Daryin T-Platforms, Moscow
Anton A. Korzh Micron Technology, Inc., Boise

DOI:

https://doi.org/10.14529/jsfi140303

Abstract

We assess the problem of choosing optimal direct topology for InfiniBand networks in terms of performance. Newest topologies like Dragonfly, Flattened butterfly and Slim Fly are considered, as well as standard Tori and Hypercubes.We consider some reasonable extensions to InfiniBand hardware which could be implemented by vendors easily and may allow reasonable routing algorithms for such topologies. A number of routing algorithms are proposed and compared for
various traffic patterns. Mapping algorithms for Dragonfly and Flattened Butterfly are proposed. Based on this research it has been decided to use Flattened Butterfly topology for system #22 in November 2014 Top 500 list.

References

November 2014 TOP500 list (http://top500.org/lists/2014/11/).

SwitchX product brief (http://www.mellanox.com/related-docs/prod_silicon/SwitchX_VPI.pdf).

InfiniBandTM Architecture Specification, volume 1. IBTA, 2007.

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 SC’09. IEEE, Nov 2009.

M. Besta and T. Hoefler. Slim Fly: A cost effective low-diameter network topology. In Proceedings of SC’14, pages 348–359. IEEE, Nov 2014.

L. N. Bhuyan and D. P. Agrawal. Generalized hypercube and hyperbus structures for a computer network. IEEE Transactions on Computers, 33(4):323–333, Apr 1984.

W. J. Dally and B. P. Towles. Principles and Practices of Interconnection Networks. Elsevier Science, 2003.

J. Domke, T. Hoefler, and W. E. Nagel. Deadlock-free oblivious routing for arbitrary topolo- gies. In Proceedings of IPDPS-11, pages 616–627. IEEE, May 2011.

J. Duato, S. Yalamanchili, and L. Ni. Interconnection Networks. Elsevier Science, 2002.

G. Faanes, A. Bataineh, D. Roweth, T. Court, E. Froese, B. Alverson, T. Johnson, J. Kop- nick, M. Higgins, and J. Reinhard. Cray Cascade: a scalable HPC system based on a Dragonfly network. In Proceedings of SC’12, pages 1–9. IEEE, Nov 2012.

C. J. Glass and L. M. Ni. The turn model for adaptive routing. Journal of the ACM, 41(5):874–902, Sep 1994.

T. Hoefler, T. Schneider, and A. Lumsdaine. Multistage switches are not crossbars: Effects of static routing in high-performance networks. In Proceedings of CLUSTER 2008, pages 116–125. IEEE, Sep 2008.

T. Hoefler, T. Schneider, and A. Lumsdaine. Optimized routing for large-scale infiniband networks. In Proceedings of HOTI’09, pages 103–111, Aug 2009.

D. J. Kerbyson, K. J. Barker, A. Vishnu, and A. Hoisie. A performance comparison of current HPC systems: Blue Gene/Q, Cray XE6 and InfiniBand systems. Future Generation Computer Systems, 30:291–304, Jan 2014.

J. Kim, W. J. Dally, and D. Abts. Flattened butterfly: a cost-efficient topology for high-radix networks. In Proceedings of ISCA’07, number 13, pages 126–137. ACM, May 2007.

J. Kim, W. J. Dally, S. L. Scott, and D. Abts. Cost-efficient Dragonfly topology for large- scale systems. IEEE Micro, 29(1):33–40, 2008.

A. V. Kostochka and L. S. Melnikov. On bounds of the bisection width of cubic graphs. In J. Nesetril and M. Fiedler, editors, Proceedings of the Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, volume 51 of Annals of Discrete Mathematics, pages 151–154. Elsevier, 1992.

P. Lopez, J. Flich, and J. Duato. Deadlock-free routing in InfiniBandTM through destination renaming. In Proceedings of ICPP-01, pages 427–434. IEEE, Sep 2001.

D. F. Lugones, D. Franco, and E. Luque. Dynamic routing balancing on infiniband network. Journal of Computer Science & Technology, 8(2):104–110, Jul 2008.

J. C. Martinez, J. Flich, A. Robles, P. Lopez, and J. Duato. Supporting fully adaptive routing in InfiniBand networks. In Proceedings of IPDPS-03. IEEE, Apr 2003.

B. D. McKay, M. Miller, and J. Sˇir ́anˇ. A note on large graphs of diameter two and given maximum degree. Journal of Combinatorial Theory, Series B, 74(1):110–118, Sep 1998.

M. Morgenstern. Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62(1):44–62, Sep 1994.

T. Skeie, O. Lysne, and I. Theiss. Layered shortest path (LASH) routing in irregular system area networks. In Proceedings of IPDPS-02, pages 162–169, Apr 2002.

H. Subramoni, S. Potluri, K. C. Kandalla, B. Barth, J. Vienne, J. Keasler, K. Tomko, K. Schulz, A. Moody, and D. K. Panda. Design of a scalable InfiniBand topology service to enable network-topology-aware placement of processes. In Proceedings of SC’12. IEEE, Nov 2012.

R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215–225, Apr 1975.

A. Thamarakuzhi and J. A. Chandy. 2-dilated flattened butterfly: A nonblocking switching topology for high-radix networks. Computer Communications, 34(15):1822–1835, Sep 2011.

L. G. Valiant. A scheme for fast parallel communication. SIAM journal on computing, 11(2):350–361, May 1982.

E. Zahavi, I. Keslassy, and A. Kolodny. Distributed adaptive routing for big-data applica- tions running on data center networks. In Proceedings of ANCS’12, pages 99–110. ACM, 2012.

E. Zahavi, I. Keslassy, and A. Kolodny. Distributed Adaptive Routing Convergence to Non- Blocking DCN Routing Assignments, volume 32, pages 88–101. Jan 2014.