A correct, portable program must invoke collective communications so that deadlock will not occur, whether collective communications are synchronizing or not. The following examples illustrate dangerous use of collective routines on intra-communicators.
Example
The following is erroneous.
We assume that the group of comm is {0,1}. Two MPI processes execute two broadcast operations in reverse order. If the operation is synchronizing then a deadlock will occur.
Collective operations must be executed in the same order at all members of the communication group.
Example
The following is erroneous.
Assume that the group of comm0 is {0,1}, of comm1 is {1, 2} and of comm2 is {2,0}. If the broadcast is a synchronizing operation, then there is a cyclic dependency: the broadcast in comm2 completes only after the broadcast in comm0; the broadcast in comm0 completes only after the broadcast in comm1; and the broadcast in comm1 completes only after the broadcast in comm2. Thus, the code will deadlock.
Collective operations must be executed in an order so that no cyclic dependencies occur. Nonblocking collective operations can alleviate this issue.
Example
The following is erroneous.
MPI process with rank 0 executes a broadcast, followed by a blocking send operation. MPI process with rank 1 first executes a blocking receive that matches the send, followed by a broadcast call that matches the broadcast of MPI process with rank 0. This program may deadlock. The broadcast call on MPI process with rank 0 may block until MPI process with rank 1 executes the matching broadcast call, so that the send is not executed. MPI process with rank 1 will definitely block on the receive and so, in this case, never executes the broadcast.
The relative order of execution of collective operations and point-to-point operations should be such, so that even if the collective operations and the point-to-point operations are synchronizing, no deadlock will occur.
Example
An unsafe, nondeterministic program.
All three MPI processes participate in a broadcast. MPI process with rank 0 sends a message to MPI process with rank 1 after the broadcast, and MPI process with rank 2 sends a message to MPI process with rank 1 before the broadcast. MPI process with rank 1 receives before and after the broadcast, with a wildcard source argument.
Two possible executions of this program, with different matchings of sends and receives, are illustrated in Figure 15. Note that the second execution has the peculiar effect that a send executed after the broadcast is received at another node before the broadcast. This example illustrates the fact that one should not rely on collective communication functions to have particular synchronization effects. A program that works correctly only when the first execution occurs (only when broadcast is synchronizing) is erroneous.
Finally, in multithreaded implementations, one can have more than one, concurrently executing, collective communication initialization call at an MPI process. In these situations, it is the user's responsibility to ensure that the same communicator is not used concurrently by two different collective communication initialization calls at the same MPI process. Collective communication initialization calls include all calls for blocking collective operations, all initiation calls for nonblocking collective operations, and all initialization calls for persistent collective operations.
Advice
to implementors.
Assume that broadcast is implemented using point-to-point MPI communication. Suppose the following two rules are followed.
It is the implementor's responsibility to
ensure that point-to-point messages are not confused with collective
messages. One way to accomplish this is, whenever a communicator is
created, to also create a ``hidden communicator'' for collective communication.
One could achieve a similar
effect more cheaply, for example, by using a hidden
tag or context bit to indicate
whether the communicator is used for point-to-point or collective
communication.
( End of advice to implementors.)
Example
Blocking and nonblocking collective operations can be interleaved, i.e.,
a blocking collective operation can be posted even if there is a
nonblocking collective operation outstanding.
Each MPI process starts a nonblocking barrier operation, participates in a blocking broadcast and then waits until every other MPI process started the barrier operation. This effectively turns the broadcast into a synchronizing broadcast with possible communication/communication overlap ( MPI_Bcast is allowed, but not required to synchronize).
Example
The starting order of collective operations on a particular communicator
defines their matching. The following example shows an erroneous
matching of different collective operations on the same communicator.
This ordering would match MPI_Ibarrier on rank 0 with MPI_Bcast on rank 1, which is erroneous and the program behavior is undefined. However, if such an order is required, the user must create different duplicate communicators and perform the operations on them. If started with two MPI processes, the following program would be correct:
Advice to users.
The use of different communicators offers some flexibility regarding the
matching of nonblocking collective operations. In this sense,
communicators could be used as an equivalent to tags. However,
communicator construction might induce overheads so that this should be
used carefully.
( End of advice to users.)
Example
Nonblocking collective operations can rely on the similar progress rules
as nonblocking point-to-point operations. Thus, if started with two
MPI processes, the following program is a valid MPI program and is
guaranteed to terminate:
The MPI library must progress the barrier in the MPI_Recv call. Thus, the MPI_Wait call in rank 0 will eventually complete, which enables the matching MPI_Send so all calls eventually return.
Example
Blocking and nonblocking collective operations do not match. The
following example is erroneous.
Example
Collective and point-to-point requests can be mixed in functions that
enable multiple completions. If started with two MPI processes, the
following program is valid.
The MPI_Waitall call returns only after the barrier and the receive completed.
Example
Multiple nonblocking collective operations can be outstanding on a
single communicator and match in order.
Advice to users.
Pipelining and double-buffering techniques can efficiently be used to
overlap computation and communication. However, having too many
outstanding requests might have a negative impact on performance.
( End of advice to users.)
Advice
to implementors.
The use of pipelining may generate many outstanding requests. A
high-quality hardware-supported implementation with limited resources
should be able to fall back to a software implementation if its
resources are exhausted. In this way, the implementation could limit the
number of outstanding requests only by the available memory.
( End of advice to implementors.)
Example
Nonblocking collective operations can also be used to enable
simultaneous collective operations on multiple overlapping
communicators (see Figure 16). The following example is started with three MPI processes and
three communicators. The first communicator comm1 includes ranks 0 and
1, comm2 includes ranks 1 and 2, and comm3 spans ranks 0 and 2. It is not
possible to perform a blocking collective operation on all communicators
because there exists no deadlock-free order to invoke them. However,
nonblocking collective operations can easily be used to achieve this
task.
Advice to users.
This method can be useful if overlapping neighboring regions (halo
or ghost zones) are used in collective operations. The sequence of the
two calls in each MPI process is irrelevant because the two nonblocking
operations are performed on different communicators.
( End of advice to users.)
Example
The progress
of multiple outstanding nonblocking collective operations
is completely independent.
Finishing the second MPI_IBCAST is completely independent of the first one. This means that it is not guaranteed that the first broadcast operation is finished or even started after the second one is completed via reqs[1].