Improving communication-phase completion times in HPC clusters through congestion mitigation

ABSTRACT

Congestion arises in cluster-based supercomputers due to contention for links, spreads due to oversubscription of communication resources, and reduces performance. We mitigate it using efficient, scalable adaptive routing and explicit rate calculation. We use virtual circuits for in-order packet delivery; path setup is performed by switches locally with no blocking or backtracking. For random permutations in a slightly enriched fat-tree topology, maximum contention is reduced by up to 50% relative to static routing, but only rate control can translate this into actual gain. Unfortunately, TCP's window-based rate control fails because of the low bandwidth-delay product, and small buffers moreover cause congestion spreading even with a single-packet window. InfiniBand's CCA employs multiple parameters, which must apparently be tuned per topology and traffic pattern. Focusing on phase-based applications, we present a distributed explicit rate-assignment algorithm for completion-time minimization of the communication phase (min-max flow completion). Also, a generally applicable packet-injection scheme for a source with different-rate flows that realizes desired rates even with very small switch buffers. Simulations show that adaptive routing alone is ineffective, rate control's effectiveness is limited, yet together they shorten the communication phase by tens of percents. Finally, our explicit rate-calculation algorithm is faster than current reactive schemes.

REFERENCES

• 1: "http://www.top500.org."
• 2: InfiniBand#8482; Trade Association, "Infiniband#8482; architecture specification, release 1.2," InfiniBand Trade Association, Oct 2004.
• 3: IEEE Computer Society, "IEEE Std 802.3#8482;-2005," Dec 2005.
• 4: G. Pfister and V. Norton, "Hot spot contention and combining in multistage interconnection networks," IEEE Trans. on Computers, vol. 34, no. 10, pp. 943--948, 1985.
• 5: V. Zdornov and Y. Birk, "Mitigating congestion in high-speed interconnects for computer clusters," Technion -- Israel Institute of Technology, CCIT 723, Mar 2009.
• 6: Dimitrios Stiliadis , Anujan Varma, General Methodology for Designing Efficient Traffic Scheduling and Shaping Algorithms, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.326, April 09-11, 1997
• 7: "http://www.omnetpp.org."
• 8: Fabrizio Petrini , Marco Vanneschi, k -ary n -trees: High Performance Networks for Massively Parallel Architectures, Proceedings of the 11th International Symposium on Parallel Processing, p.87, April 01-05, 1997
• 9: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 10: S. Even , A. Itai , A. Shamir, On the complexity of time table and multi-commodity flow problems, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, p.184-193, October 13-15, 1975
• 11: W. J. Dally , C. L. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 12: Tor Skeie , Olav Lysne , Ingebjørg Theiss, Layered Shortest Path (LASH) Routing in Irregular System Area Networks, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.194, April 15-19, 2002
• 13: A. Mejia, J. Flich, J. Duato, S. A. Reinemo, and T. Skeie, "Segment-based routing: an efficient fault-tolerant routing algorithm for meshes and tori," in Proc. 20th Int'l Parallel and Distributed Processing Symp. (IPDPS), Apr 2006, p. 10pp.
• 14: Shihang Yan , Geyong Min , Irfan Awan, An Enhanced Congestion Control Mechanism in InfiniBand Networks for High Performance Computing Systems, Proceedings of the 20th International Conference on Advanced Information Networking and Applications, p.845-850, April 18-20, 2006 [doi>10.1109/AINA.2006.87]
• 15: C. Gomez, F. Gilabert, M. E. Gomez, P. Lopez, and J. Duato, "Deterministic versus adaptive routing in fat-trees," in Proc. IEEE Int'l Parallel and Distributed Processing Symp. (IPDPS), Mar 2007, pp. 1--8.
• 16: 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]
• 17: J. C. Martínez , J. Flich , A. Robles , P. López , J. Duato, Supporting Fully Adaptive Routing in InfiniBand Networks, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.44.1, April 22-26, 2003
• 18: Jiuxing Liu , Abhinav Vishnu , Dhabaleswar K. Panda, Building Multirail InfiniBand Clusters: MPI-Level Design and Performance Evaluation, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.33, November 06-12, 2004 [doi>10.1109/SC.2004.15]
• 19: X.-Y. Lin, Y.-C. Chung, and T.-Y. Huang, "A multiple lid routing scheme for fat-tree-based infiniband networks," in Proc. 18th Int'l Parallel and Distributed Processing Symp. (IPDPS), 2004.
• 20: A. Vishnu , M. Koop , A. Moody , A. R. Mamidala , S. Narravula , D. K. Panda, Hot-Spot Avoidance With Multi-Pathing Over InfiniBand: An MPI Perspective, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, p.479-486, May 14-17, 2007 [doi>10.1109/CCGRID.2007.60]
• 21: Binh Vien Dao , Sudhakar Yalamanchili , Jose Duato, Architectural Support for Reducing Communication Overhead in Multiprocessor Interconnection Networks, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.343, February 01-05, 1997
• 22: Y. Turner and Y. Tamir, "Connection-based adaptive routing using dynamic virtual circuits," in Proc. International Conference on Parallel and Distributed Computing and Systems, 1998, pp. 379--384.
• 23: Dah-Ming Chiu , Raj Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 24: L. S. Brakmo and L. L. Peterson, "TCP vegas: End to end congestion avoidance on a global internet," IEEE Journal on Selected Areas in Communications, vol. 13, no. 8, pp. 1465--1480, 1995.
• 25: S. Floyd , T. Henderson, The NewReno Modification to TCP's Fast Recovery Algorithm, RFC Editor, 1999
• 26: Dina Katabi , Mark Handley , Charlie Rohrs, Congestion control for high bandwidth-delay product networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 27: L. Xu, K. Harfoush, and I. Rhee, "Binary increase congestion control for fast long-distance networks," in Proc. IEEE INFOCOM, vol. 4, 2004, pp. 2514--2524.
• 28: Yong Xia , Lakshminarayanan Subramanian , Ion Stoica , Shivkumar Kalyanaraman, One more bit is enough, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 29: J. R. Santos, Y. Turner, and G. J. Janakiraman, "End-to-end congestion control for infiniband," in Proc. IEEE INFOCOM, vol. 2, 2003, pp. 1123--1133.
• 30: M. Gusat , D. Craddock , W. Denzel , T. Engbersen , N. Ni , G. Pfister , W. Rooney , J. Duato, Congestion Control in InfiniBand Networks, Proceedings of the 13th Symposium on High Performance Interconnects, p.158-159, August 17-19, 2005 [doi>10.1109/CONECT.2005.14]
• 31: A. Charny, D. Clark, and R. Jain, "Congestion control with explicit rate indication," in Proc. IEEE Int'l Conf. on Communications (ICC), 1995, pp. 1954--1963.
• 32: Lampros Kalampoukas , Anujan Varma , K. K. Ramakrishnan, An efficient rate allocation algorithm for ATM networks providing max-min fairness, Proceedings of the IFIP Sixth International Conference on High Performance Networking VI, p.143-154, January 1995
• 33: Anna Charny , K. K. Ramakrishnan , Anthony Lauck, Time scale analysis scalability issues for explicit rate allocation in ATM networks, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.569-581, Aug. 1996 [doi>10.1109/90.532866]
• 34: R. Jain, S. Kalyanaraman, and R. Viswanathan, "The OSU scheme for congestion avoidance in ATM networks using explicit rate indication," in Proc. WATM First Workshop on ATM Traffic Management, 1995.
• 35: H. Tzeng and K. Siu, "Adaptive proportional rate control for abr service in atm networks," in Proc. IEEE Computers and Communications, 1995, pp. 529--535.
• 36: Yehuda Afek , Yishay Mansour , Zvi Ostfeld, Phantom: a simple and effective flow control scheme, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.169-182, August 28-30, 1996, Palo Alto, California, United States
• 37: Shivkumar Kalyanaraman , Raj Jain , Sonia Fahmy , Rohit Goyal , Bobby Vandalore, The ERICA switch algorithm for ABR traffic management in ATM networks, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.87-98, Feb. 2000 [doi>10.1109/90.836480]
• 38: Nandita Dukkipati , Nick McKeown, Why flow-completion time is the right metric for congestion control, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111336]
• 39: Raj Jain, Congestion control and traffic management in ATM networks: recent advances and a survey, Computer Networks and ISDN Systems, v.28 n.13, p.1723-1738, Oct. 1996 [doi>10.1016/0169-7552(96)00012-8]
• 40: L. Mamatas, T. Harks, and V. Tsaoussidis, "Approaches to congestion control in packet networks," Journal of Internet Engineering, vol. 1, no. 1, pp. 22--33, 2007.
• 41: J. Turner, "New directions in communications (or which way to the information age?)," vol. 24, no. 10, pp. 8--15, Oct 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
      C.2.2 Network Protocols

Keywords:
InfiniBand, adaptive routing, computer clusters, congestion, congestion control, interconnects