<meta http-equiv="Content-Type" content="text/html; charset=utf-8"><div dir="ltr">Yes. Many collectives have optimizations for power-of-two processes. In MPICH's source code allreduce.c, you can find the following comments. <div><div><br></div><div><div>/* This is the default implementation of allreduce. The algorithm is:</div><div> </div><div> Algorithm: MPI_Allreduce</div><div><br></div><div> For the heterogeneous case, we call MPI_Reduce followed by MPI_Bcast</div><div> in order to meet the requirement that all processes must have the</div><div> same result. For the homogeneous case, we use the following algorithms.</div><div><br></div><div><br></div><div> For long messages and for builtin ops and if count >= pof2 (where</div><div> pof2 is the nearest power-of-two less than or equal to the number</div><div> of processes), we use Rabenseifner's algorithm (see </div><div> <a href="http://www.hlrs.de/mpi/myreduce.html">http://www.hlrs.de/mpi/myreduce.html</a>).</div><div> This algorithm implements the allreduce in two steps: first a</div><div> reduce-scatter, followed by an allgather. A recursive-halving</div><div> algorithm (beginning with processes that are distance 1 apart) is</div><div> used for the reduce-scatter, and a recursive doubling </div><div> algorithm is used for the allgather. The non-power-of-two case is</div><div> handled by dropping to the nearest lower power-of-two: the first</div><div> few even-numbered processes send their data to their right neighbors</div><div> (rank+1), and the reduce-scatter and allgather happen among the remaining</div><div> power-of-two processes. At the end, the first few even-numbered</div><div> processes get the result from their right neighbors.</div><div><br></div><div> For the power-of-two case, the cost for the reduce-scatter is </div><div> lgp.alpha + n.((p-1)/p).beta + n.((p-1)/p).gamma. The cost for the</div><div> allgather lgp.alpha + n.((p-1)/p).beta. Therefore, the</div><div> total cost is:</div><div> Cost = 2.lgp.alpha + 2.n.((p-1)/p).beta + n.((p-1)/p).gamma</div><div><br></div><div> For the non-power-of-two case, </div><div> Cost = (2.floor(lgp)+2).alpha + (2.((p-1)/p) + 2).n.beta + n.(1+(p-1)/p).gamma</div><div><br></div><div> </div><div> For short messages, for user-defined ops, and for count < pof2 </div><div> we use a recursive doubling algorithm (similar to the one in</div><div> MPI_Allgather). We use this algorithm in the case of user-defined ops</div><div> because in this case derived datatypes are allowed, and the user</div><div> could pass basic datatypes on one process and derived on another as</div><div> long as the type maps are the same. Breaking up derived datatypes</div><div> to do the reduce-scatter is tricky. </div><div><br></div><div> Cost = lgp.alpha + n.lgp.beta + n.lgp.gamma</div><div><br></div><div> Possible improvements: </div><div><br></div><div> End Algorithm: MPI_Allreduce</div><div>*/</div></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr">--Junchao Zhang</div></div></div>
<br><div class="gmail_quote">On Wed, Feb 25, 2015 at 2:59 PM, Aiman Fang <span dir="ltr"><<a href="mailto:aimanf@cs.uchicago.edu" target="_blank">aimanf@cs.uchicago.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
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?<br>
<br>
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.<br>
<br>
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%.<br>
<br>
The mpich version we used is as follows.<br>
<br>
$ mpichversion<br>
MPICH Version: 3.1.2<br>
MPICH Release date: Mon Jul 21 16:00:21 CDT 2014<br>
MPICH Device: pamid<br>
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<br>
MPICH CC: powerpc64-bgq-linux-gcc -O2<br>
MPICH CXX: powerpc64-bgq-linux-g++ -O2<br>
MPICH F77: powerpc64-bgq-linux-gfortran -O2<br>
MPICH FC: powerpc64-bgq-linux-gfortran -O2<br>
<br>
Thanks!<br>
<br>
Best,<br>
Aiman<br>
_______________________________________________<br>
discuss mailing list <a href="mailto:discuss@mpich.org">discuss@mpich.org</a><br>
To manage subscription options or unsubscribe:<br>
<a href="https://lists.mpich.org/mailman/listinfo/discuss" target="_blank">https://lists.mpich.org/mailman/listinfo/discuss</a><br>
</blockquote></div><br></div>