Optimizing All-to-All Collective Communication by Exploiting Concurrency in Modern Networks

ABSTRACT

The paper proposes a novel approach for optimizing performance of all-to-all collective communication by taking advantage of concurrency available in modern networks such as Infiniband or Quadrics. Using the MPI AllGather operation as an example, we describe how network concurrency can be exploited in an optimized implementation of this operation. For example, compared to leading MPI implementations for a 32-KB message on 128 processors, our new algorithm yields a 65% improvement on the Infiniband at Virginia Tech and an 89% improvement on the Quadrics cluster at Pacific Northwest National Laboratory.

REFERENCES

• 1: [1] "Elan4 NIC Diagram." http://www.quadrics.com/Quadrics/QuadricsHome. nsf/DisplayPages/79CEA2573DC8909880256D88004A5C0 1/$File/QuadricsHotChipsOld1.ppt
• 2: [2] "Infinihost NIC Diagram." http://www.hd3d.com/diagram02.html
• 3: [3] J. Beecroft, D. Addison, F. Petrini, and M. McLaren, "QsNetII: An Interconnect for Supercomputing Applications," Quadrics. http://doc.quadrics.com/Quadrics/QuadricsHome.nsf/Di splayPages/7B383554432E5F4D80256EAD0010AA83/$File/Qs Net+Hot+chips+paper1.pdf
• 4: [4] N. Arnold, K. Thilo, E. B. Henri, and M. Jason, Object-based collective communication in Java. Palo Alto, California, United States: ACM Press, 2001.
• 5: [5] M. Barnett, L. Shuler, R. van de Geijn, S. Gupta, D. G. Payne, and J. Watts, "Interprocessor collective communication library (InterCom)," 1994.
• 6: Vasanth Bala , Jehoshua Bruck , Robert Cypher , Pablo Elustando , Alex Ho , Ching-Tien Ho , Shlomo Kipnis , Marc Snir, CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.154-164, February 1995 [doi>10.1109/71.342126 ]
• 7: William Gropp , Ewing Lusk , Nathan Doss , Anthony Skjellum, A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, v.22 n.6, p.789-828, Sept. 1996 [doi>10.1016/0167-8191(96)00024-5 ]
• 8: [8] L. Jiuxing, "Designing high performance and scalable mpi over infiniband," 2004, pp. 186.
• 9: [9] S. Xantheas and G. Fanourgakis, "Polarizable Water Potentials," 2005, pp. Personal Communication.
• 10: [10] Z. Yeliang, V. Tipparaju, J. Nieplocha, and S. Hariri, "Parallelization of the NAS Conjugate Gradient Benchmark Using the Global Arrays Shared Memory Programming Model," 2005.
• 11: [11] S. Baden, P. Collela, D. Shalit, and B. Van Straalen, "Abstract Kelp," presented at International Conference on Computational Science, San Francisco, CA, 2001.
• 12: [12] R. Bariuso and A. Knies, SHMEM's User's Guide: Cray Research, Inc., 1994.
• 13: [13] A. Basumallik, S.-J. Min, and R. Eigenmann, "Towards OpenMP execution on software distributed shared memory systems," presented at Int'l Workshop on OpenMP: Experiences and Implementations (WOMPEI'02), 2002.
• 14: Jarek Nieplocha , Bryan Carpenter, ARMCI: A Portable Remote Memory Copy Libray for Ditributed Array Libraries and Compiler Run-Time Systems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.533-546, April 12-16, 1999
• 15: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 16: [16] S. V. Sathish, E. F. Graham, and D. Jack, Automatically tuned collective communications. Dallas, Texas, United States: IEEE Computer Society, 2000.
• 17: [17] "InfiniBand Trade Association. InfiniBand Architecture Specification, Release 1.0, October 24 2000." www.infinibandta.org
• 18: Vinod Tipparaju , Jarek Nieplocha , Dhabaleswar Panda, Fast Collective Operations Using Shared and Remote Memory Access Protocols on Clusters, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.84.1, April 22-26, 2003
• 19: [19] S. Susumu, M. Hiroyuki, N. Shigeki, and H. Jun-ichi, Scatter and gather operations on an asynchronous communication model. Como, Italy: ACM Press, 2000.
• 20: Weikuan Yu , D. K. Panda , D. Buntinas, Scalable, high-performance NIC-based all-to-all broadcast over Myrinet/GM, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.125-134, September 20-23, 2004
• 21: A. R. Mamidala , Jiuxing Liu , D. K. Panda, Efficient Barrier and Allreduce on Infiniband clusters using multicast and adaptive algorithms, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.135-144, September 20-23, 2004
• 22: Darius Buntinas , Dhabaleswar K. Panda , José Duato , P. Sadayappan, Broadcast/Multicast over Myrinet Using NIC-Assisted Multidestination Messages, Proceedings of the 4th International Workshop on Network-Based Parallel Computing: Communication, Architecture, and Applications, p.115-129, January 08, 2000
• 23: [23] W. Yu, D. Buntinas, and D. K. Panda, "High performance and reliable NIC-based multicast over Myrinet/GM-2," presented at Parallel Processing, 2003. Proceedings. 2003 International Conference on, 2003.
• 24: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015 ]
• 25: Fabrizio Petrini , Salvador Coll , Eitan Frachtenberg , Adolfy Hoisie, Hardware- and Software-Based Collective Communication on the Quadrics Network, Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA'01), p.24, October 08-10, 2001
• 26: J. Nieplocha , V. Tipparaju , M. Krishnan , D. K. Panda, High Performance Remote Memory Access Communication: The Armci Approach, International Journal of High Performance Computing Applications, v.20 n.2, p.233-253, May 2006 [doi>10.1177/1094342006064504]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Experimentation, Measurement, Performance