How costly is MPI_Comm_split?

Question

How costly is a call to MPI_Comm_split? Does it run in O(n), O(log(n)), or something else (with n being the number of ranks in the comm being split)?

I'm writing code targeting supercomputing systems that are based on infiniband.

Answer 1

If you use Open MPI, MPI_Comm_split() (and communicator creation generally speaking) might not be cheap.

The design choice was to have super fast conversion from a communicator id (e.g. CID, which is a number) to a communicator. This is as fast and simple as accessing an array.

In order to keep the memory footprint as low as possible, newly created communicators are always assigned the lowest available CID.

CID assignment is implemented via an iterative algo, that uses two MPI_Iallreduce() per iteration, and the number of iteration depends on how fragmented the CID space is on all the tasks. Depending on how many MPI tasks you are using, and how fragmented the CID space is, that can take quite some time.

You can see MPI_Comm_split() as a two steps tango - create the groups of the new communicator(s) - assign a CID to the new communicator(s)

The second step is the most expensive, and it does not only depend on the number of ranks in the initial communicator.

If I understand correctly, MPICH made an other design choice. Translating a communicator ID to a communicator is slightly more expensive (but that virtually happens each time a MPI subroutine is called), but always using the lowest available CID is not needed, so the second step is much cheaper (and that only happens when a new communicator is created).

So even if Open MPI and MPICH have comparable performances for point-to-point, collective and one sided communications, that could be a very different picture at scale if you create a lot of communicators (or if you use a third party library that does that under the hood).