Yes. Many collectives have optimizations for power-of-two processes. In MPICH's source code allreduce.c, you can find the following comments. /* This is the default implementation of allreduce. The algorithm is: Algorithm: MPI_Allreduce For the heterogeneous case, we call MPI_Reduce followed by MPI_Bcast in order to meet the requirement that all processes must have the same result. For the homogeneous case, we use the following algorithms. For long messages and for builtin ops and if count >= pof2 (where pof2 is the nearest power-of-two less than or equal to the number of processes), we use Rabenseifner's algorithm (see http://www.hlrs.de/mpi/myreduce.html). This algorithm implements the allreduce in two steps: first a reduce-scatter, followed by an allgather. A recursive-halving algorithm (beginning with processes that are distance 1 apart) is used for the reduce-scatter, and a recursive doubling algorithm is used for the allgather. The non-power-of-two case is handled by dropping to the nearest lower power-of-two: the first few even-numbered processes send their data to their right neighbors (rank+1), and the reduce-scatter and allgather happen among the remaining power-of-two processes. At the end, the first few even-numbered processes get the result from their right neighbors. For the power-of-two case, the cost for the reduce-scatter is lgp.alpha + n.((p-1)/p).beta + n.((p-1)/p).gamma. The cost for the allgather lgp.alpha + n.((p-1)/p).beta. Therefore, the total cost is: Cost = 2.lgp.alpha + 2.n.((p-1)/p).beta + n.((p-1)/p).gamma For the non-power-of-two case, Cost = (2.floor(lgp)+2).alpha + (2.((p-1)/p) + 2).n.beta + n.(1+(p-1)/p).gamma For short messages, for user-defined ops, and for count < pof2 we use a recursive doubling algorithm (similar to the one in MPI_Allgather). We use this algorithm in the case of user-defined ops because in this case derived datatypes are allowed, and the user could pass basic datatypes on one process and derived on another as long as the type maps are the same. Breaking up derived datatypes to do the reduce-scatter is tricky. Cost = lgp.alpha + n.lgp.beta + n.lgp.gamma Possible improvements: End Algorithm: MPI_Allreduce */ --Junchao Zhang On Wed, Feb 25, 2015 at 2:59 PM, Aiman Fang <[email protected]> wrote:

Hi,

I came across a problem in experiments that makes me wondering if there is any optimization of collective calls, such as MPI_Allreduce, for 2^n number of ranks?

We did some experiments on Argonne Vesta system to measure the time of MPI_Allreduce calls using 511, 512 and 513 processes. (one process per node). In each run, the synthetic benchmark first did some computation and then called MPI_Allreduce 30 times, for total 100 loops. We measured the total time spent on communication.

We found that 512-process run gives the best performance. The time for 511, 512 and 513 processes are 0.1492, 0.1449 and 0.1547 seconds respectively. 512-proc outperforms 511-proc by 3.7%, and 513-proc by 6.7%.

The mpich version we used is as follows.

$ mpichversion MPICH Version: 3.1.2 MPICH Release date: Mon Jul 21 16:00:21 CDT 2014 MPICH Device: pamid MPICH configure: --prefix=/home/fujita/soft/mpich-3.1.2 --host=powerpc64-bgq-linux --with-device=pamid --with-file-system=gpfs:BGQ --disable-wrapper-rpath MPICH CC: powerpc64-bgq-linux-gcc -O2 MPICH CXX: powerpc64-bgq-linux-g++ -O2 MPICH F77: powerpc64-bgq-linux-gfortran -O2 MPICH FC: powerpc64-bgq-linux-gfortran -O2

Thanks!

Best, Aiman _______________________________________________ discuss mailing list [email protected] To manage subscription options or unsubscribe: https://lists.mpich.org/mailman/listinfo/discuss

_______________________________________________ discuss mailing list [email protected] To manage subscription options or unsubscribe: https://lists.mpich.org/mailman/listinfo/discuss