A Pipelined Algorithm for Large,Irregular All-Gather Problems

Abstract

We describe and evaluate a new pipelined algorithm for large, irregular all-gather problems. In the irregular allgather problem each process in a set of processes contributes individual data of possibly different size, and all processes have to collect all data from all processes. The pipelined algorithm is useful for the implementation of the MPI_Allgatherv collective operation of the Message-Passing Interface (MPI) for large problems. By conception, the new algorithm is well suited to implementation on clustered multiprocessors, such as symmetric multiprocessing (SMP) clusters. The new algorithm has been implemented within different MPI libraries. Benchmark results on NEC SX-8, Linux clusters with InfiniBand and Gigabit Ethernet, IBM Blue Gene/P, and SiCortex systems show huge performance gains in accordance with the expected behavior.

Keywords

message-passing interface collective operations all-gather problem pipelining NEC SX-8 Linux clusters IBM Blue Gene/P SiCortex

Get full access to this article

View all access options for this article.

References

Balaji, P. et al. (2007). Nonuniformly communicating noncontiguous data: a case study with PETSc and MPI. In 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), pp. 1-10.

Benson, G.D. et al. (2003). A comparison of MPICH allgather algorithms on switched networks. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 10th European PVM/MPI Users’ Group Meeting (Lecture Notes in Computer Science, Vol. 2840). Berlin: Springer, pp. 335-343.

Bruck, J. et al. (1997). Efficient algorithms for all-to-all communications in multiport message-passing systems. IEEE Trans. Parallel Distrib. Syst. 8: 1143-1156.

Gropp, W. and Lusk, E. ( 1999). Reproducible measurements of MPI performance characteristics . In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 6th European PVM/MPI Users’ Group Meeting (Lecture Notes in Computer Science, Vol. 1697). Berlin: Springer, pp. 11-18.

Hedetniemi, S.M. , Hedetniemi, T. and Liestman, A.L. ( 1988). A survey of gossiping and broadcasting in communication networks. Networks 18: 319-349.

Krumme, D.W. , Cybenko, G. and Venkataraman, K.N. ( 1992). Gossiping in minimal time. SIAM Journal on Computing 21: 111-139. IRREGULAR ALL-GATHER PROBLEMS

Mamidala, A.R. , Vishnu, A. and Panda, D.K. ( 2006). Efficient shared memory and RDMA based design for mpi_allgather over InfiniBand. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 13th European PVM/MPI Users’ Group Meeting (Lecture Notes in Computer Science, Vol. 4192). Berlin: Springer , pp. 66-75.

MPI Forum (2008). MPI: A Message-Passing Interface Standard. Version 2.1. http://www.mpi-forum.org.

Thakur, R. , Gropp, W.D. and Rabenseifner, R. ( 2004). Improving the performance of collective operations in MPICH. Int. J. High Perform. Comput. Appl. 19: 49-66.

10.

Träff, J.L. ( 2006). Efficient allgather for regular SMP-clusters. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 13th European PVM/MPI Users’ Group Meeting (Lecture Notes in Computer Science, vol. 4192). Berlin: Springer, pp. 58-65.

11.

Träff, J.L. ( 2009). Relationships between regular and irregular collective communication operations on clustered multiprocessors. Parallel Process. Lett. 19: 85-96.

12.

Träff, J.L. , Gropp, W. , and Thakur, R. ( 2007). Self-consistent MPI performance requirements. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 14th European PVM/MPI Users’ Group Meeting (Lecture Notes in Computer Science, Vol. 4757). Berlin: Springer, pp. 36-45.