How does the computational cost of an mpi_allgather operation compare with a gather/scatter operation?

Question

I'm working on a problem that can be parallelized by using a single mpi_allgather operation or one mpi_scatter and one mpi_gather operation. These operations are called within a while loop, so they may be called many times.

In the implementation with an MPI_allgather scheme, I'm gathering a distributed vector onto all processes for duplicate matrix solving. In the other implementation, I gather the distributed vector onto a single processor (the root node), solve the linear system on this processor, and then scatter the solution vector back onto all the processes.

I'm curious to know if the cost of an allgather operation is significantly more than the scatter and gather operations combined. Does the length of the message play a significant role in its complexity? Does it vary between implementations of mpi?

Edit:

Answer 1

First, the exact answer depends on: (1) usage, i.e. function input arguments, (2) MPI implementation quality and details, and (3) the hardware you're using. Often, (2) and (3) are related, such as when the hardware vendor optimizes MPI for their network.

In general, fusing MPI collectives is better for smaller messages, since start-up costs can be nontrivial and the synchronization entailed by blocking collectives should be minimized if there is variation in compute time between calls. For larger messages, the goal should be to minimize the amount of data being sent.

For example, in theory, MPI_Reduce_scatter_block should be better than MPI_Reduce followed by MPI_Scatter, although the former is often implemented in terms of the latter, such that there is no real advantage. There's a correlation between implementation quality and frequency of usage in most implementations of MPI, and vendors obviously optimize those functions for which this is required by the machine contract.

On the other hand, if one is on a Blue Gene, doing MPI_Reduce_scatter_block using MPI_Allreduce, which does more communication than MPI_Reduce and MPI_Scatter combined, is actually quite a bit faster. This is something I recently discovered and is an interesting violation of the principle of performance self-consistency in MPI (this principle is described in more detail in "Self-Consistent MPI Performance Guidelines").

In the specific case of scatter+gather versus allgather, consider that in the former, all the data must go to and from a single process, which makes it the bottleneck, whereas in the allgather, data can flow in and out of all ranks immediately, because all ranks have some data to send to all other ranks. However, sending data from all nodes at once is not necessarily a good idea on some networks.

Finally, the best way to answer this question is to do the following in your code and answer the question by experiment.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

An even better option is to have your code measure it experimentally during the first two iterations, then use whichever is faster for the remaining iterations:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}

Answer 2

Jeff's absolutely right about the only way to be sure is to measure - we're scientists, after all, and this is an empirical question - and gives excellent advice about how to implement such measurements. Let me now offer a contrary (or, maybe, complementary) view.

There's a distinction to be made between writing a code to be widely used, and tuning it to a specific end. In general we're doing the first - building our code so that a) we can use it on a wide variety of platforms, and b) the code is maintainable and extendable for years to come. But sometimes we're doing the other - we've got a year's worth of allocation on some big machine, and we are ramping up to some required set of large simulations and we need a certain baseline of performance to get what we need done during the time of the granted allocation.

When we're writing code, making it widely useable and maintainable is much more important than shaving a few percent off of runtime on a particular machine. In this case, the right thing to do is almost always to use the routine that best describes what you want to do - this is generally the most specific call you can make that does what you want. Eg, if a straight allgather or allgatherv does what you want, you should use that rather than rolling your own out of scatter/gatter operations. The reasons are that:

• The code now more clearly represents what you're trying to do, making it more understandable to the next person who comes to your code the following year having no idea what the code is supposed to do (that person could well be you);
• Optimizations are available at the MPI level for this more specific case that aren't in the more general case, so your MPI library can help you; and
• Trying to roll your own will likely backfire; even if it performs better on machine X with MPI implementation Y.ZZ, it may well perform much worse when you move to another machine, or upgrade your MPI implementation.

In this fairly common case, if you find out that some MPI collective works unreasonably slowly on your machine, the best thing to do is to file a bug report with the mpi vendor; you don't want to complicate your own software trying to work around in application code what should properly be fixed at the MPI library level.

However. If you're in "tuning" mode - you have a working code, you've got to ramp up to very large scales in a short period of time (eg, a year-long allocation), and you've profiled your code and found out that this particular part of your code is a bottleneck, then it makes sense to start performing these very specific tunings. Hopefully they won't be long-term parts of your code - ideally these changes will remain in some project-specific branch of your repository - but you may need to do them. In that case, the coding of two different approaches distinguished by preprocessor directives, or an "autotuning" approach for a specific communication pattern - can make a lot of sense.

So I'm not disagreeing with Jeff, I just want to add some context about when you should be concerned enough with such relative performance questions to modify your code to deal with it.