Optimization of Collective Communication Operations in MPICH

Abstract

We describe our work on improving the performance of collective communication operations in MPICH for clusters connected by switched networks. For each collective operation, we use multiple algorithms depending on the message size, with the goal of minimizing latency for short messages and minimizing bandwidth use for long messages. Although we have implemented new algorithms for all MPI (Message Passing Interface) collective operations, because of limited space we describe only the algorithms for allgather, broadcast, all-to-all, reduce-scatter, reduce, and allreduce. Performance results on a Myrinet-connected Linux cluster and an IBM SP indicate that, in all cases, the new algorithms significantly outperform the old algorithms used in MPICH on the Myrinet cluster, and, in many cases, they outperform the algorithms used in IBM's MPI on the SP. We also explore in further detail the optimization of two of the most commonly used collective operations, allreduce and reduce, particularly for long messages and nonpower-of-two numbers of processes. The optimized algorithms for these operations perform several times better than the native algorithms on a Myrinet cluster, IBM SP, and Cray T3E. Our results indicate that to achieve the best performance for a collective communication operation, one needs to use a number of different algorithms and select the right algorithm for a particular message size and number of processes.

Keywords

Collective communication message passing MPI reduction

Get full access to this article

View all access options for this article.

References

Alexandrov, A. , Ionescu, M.F. , Schauser, K.E. , and Scheiman, C. 1997. LogGP: incorporating long messages into the LogP model for parallel computation . Journal of Parallel and Distributed Computing 44(1): 71–79 .

Barnett, M. , Gupta, S. , Payne, D. , Shuler, L. , van de Geijn, R. , and Watts, J. 1994. Interprocessor collective communication library (InterCom) . Proceedings of Supercomputing ‘94, Washington, DC, November.

Barnett, M. , Littlefield, R. , Payne, D. , and van de Geijn, R. 1993. Global combine on mesh architectures with wormhole routing . Proceedings of the 7th International Parallel Processing Symposium, Newport Beach, CA, April.

Benson, G.D. , Chu, C-W. , Huang, Q. , and Caglar, S.G. 2003. A comparison of MPICH allgather algorithms on switched networks. Recent Advances in Parallel Virtual Machine and Message Passing Interface, 10th European PVM/MPI Users' Group Meeting, Lecture Notes in Computer Science Vol. 2840, J. Dongarra , D. Laforenza , and S. Orlando , editors, Springer-Verlag, Berlin , pp. 335–343.

Bokhari, S. 1991. Complete exchange on the iPSC/860. Technical Report 91–4, ICASE, NASA Langley Research Center .

Bokhari, S. and Berryman, H. 1992. Complete exchange on a circuit switched mesh . Proceedings of the Scalable High Performance Computing Conference, Williamsburg, VA, April, pp. 300–306 .

Bruck, J. , Ho, C-T. , Kipnis, S. , Upfal, E. , and Weathersby, D. 1997. Efficient algorithms for all-to-all communications in multiport message-passing systems . IEEE Transactions on Parallel and Distributed Systems 8(11): 1143–1156 .

Chan, E.W. , Heimlich, M.F. , Purakayastha, A. , and van de Geijn, R.A. 2004. On optimizing collective communication . Proceedings of the 2004 IEEE International Conference on Cluster Computing, San Diego, CA, September.

Culler, D.E. , Karp, R.M. , Patterson, D.A. , Sahay, A. , Schauser, K.E. , Santos, E. , Subramonian, R. , and von Eicken, T. 1993. LogP: towards a realistic model of parallel computation . Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, May, pp. 1–12 .

10.

Hensgen, D. , Finkel, R. , and Manbet, U. 1988. Two algorithms for barrier synchronization . International Journal of Parallel Programming 17(1): 1–17 .

11.

Hockney, R.W. 1994. The communication challenge for mpp: Intel paragon and meiko cs-2 . Parallel Computing 20(3): 389–398 .

12.

Iannello, G. 1997. Efficient algorithms for the reduce-scatter operation in LogGP . IEEE Transactions on Parallel and Distributed Systems 8(9): 970–982 .

13.

Kale, L.V. , Kumar, S. , and Vardarajan, K. 2003. A framework for collective personalized communication . Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS ’03), Nice, France, April.

14.

Karonis, N. , de Supinski, B. , Foster, I. , Gropp, W. , Lusk, E. , and Bresnahan, J. 2000. Exploiting hierarchy in parallel computer networks to optimize collective operation performance . Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS ’00), Cancun, Mexico, May, pp. 377–384 .

15.

Kielmann, T. , Hofman, R.F.H. , Bal, H.E. , Plaat, A. , and Bhoedjang, R.A.F. 1999. MagPIe: MPI's collective communication operations for clustered wide area systems . ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'99), Atlanta, GA, May, pp. 131–140 .

16.

Mitra, P. , Payne, D. , Shuler, L. , van de Geijn, R. , and Watts, J. 1995. Fast collective communication libraries, please . Proceedings of the Intel Supercomputing Users' Group Meeting, June.

17.

Rabenseifner, R. 1999. Automatic MPI counter profiling of all users: First results on a CRAY T3E 900-512 . Proceedings of the Message Passing Interface Developer's and User's Conference 1999 (MPIDC ’99), Atlanta, GA, March, pp. 77–85 .

18.

Rabenseifner, R. and Wellein, G. 2003. Communication and optimization aspects of parallel programming models on hybrid architectures . International Journal of High Performance Computing Applications 17(1): 49–62 .

19.

Sanders, P. and Träff, J.L. 2002. The hierarchical factor algorithm for all-to-all communication. Euro-Par 2002 Parallel Processing, Lecture Notes in Computer Science Vol. 2400, B. Monien and R. Feldman , editors, Springer-Verlag, Berlin , pp. 799–803.

20.

Scott, D. 1991. Efficient all-to-all communication patterns in hypercube and mesh topologies . Proceedings of the 6th Distributed Memory Computing Conference, Portland, OR, April, pp. 398–403 .

21.

Shroff, M. and van de Geijn, R.A. 1999. CollMark: MPI collective communication benchmark. Technical Report, Department of Computer Sciences, University of Texas at Austin , December.

22.

Sistare, S. , vandeVaart, R. , and Loh, E. 1999. Optimization of MPI collectives on clusters of large-scale SMPs . Proceedings of Supercomputing: High Performance Networking and Computing, Portland, OR, November.

23.

Tipparaju, V. , Nieplocha, J. , and Panda, D.K. 2003. Fast collective operations using shared and remote memory access protocols on clusters . Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS ’03), Nice, France, April.

24.

Träff, J.L. 2002. Improved MPI all-to-all communication on a Giganet SMP cluster. Recent Advances in Parallel Virtual Machine and Message Passing Interface, 9th European PVM/MPI Users' Group Meeting, Lecture Notes in Computer Science Vol. 2474, D. Kranzlmuller , P. Kacsuk , J. Dongarra , and J. Volkert , editors, Springer-Verlag, Berlin , pp. 392–400.

25.

Vadhiyar, S.S. , Fagg, G.E. , and Dongarra, J. 1999. Automatically tuned collective communications . Proceedings of Supercomputing 99: High Performance Networking and Computing, Portland, OR, November.

26.

Worsch, T. , Reussner, R. , and Augustin, W. 2002. On benchmarking collective MPI operations. Recent Advances in Parallel Virtual Machine and Message Passing Interface, 9th European PVM/MPI Users' Group Meeting, Lecture Notes in Computer Science Vol. 2474, D. Kranzlmüller , P. Kacsuk , J. Dongarra , and J. Volkert , editors, SpringerVerlag, Berlin , pp. 271–279.