Deadlock with MPI

Question

I'm experimenting with MPI and was wondering if this code could cause a deadlock.

MPI_Comm_rank (comm, &my_rank);
if (my_rank == 0) {
   MPI_Send (sendbuf, count, MPI_INT, 1, tag, comm);
   MPI_Recv (recvbuf, count, MPI_INT, 1, tag, comm, &status);
} else if (my_rank == 1) {
   MPI_Send (sendbuf, count, MPI_INT, 0, tag, comm);
   MPI_Recv (recvbuf, count, MPI_INT, 0, tag, comm, &status);
}

Answer 1

MPI_Send may or may not block. It will block until the sender can reuse the sender buffer. Some implementations will return to the caller when the buffer has been sent to a lower communication layer. Some others will return to the caller when there's a matching MPI_Recv() at the other end. So it's up to your MPI implementation whether if this program will deadlock or not.

Because of this program behaves differently among different MPI implementations, you may consider rewritting it so there won't be possible deadlocks:

MPI_Comm_rank (comm, &my_rank);
if (my_rank == 0) {
   MPI_Send (sendbuf, count, MPI_INT, 1, tag, comm);
   MPI_Recv (recvbuf, count, MPI_INT, 1, tag, comm, &status);
} else if (my_rank == 1) {
   MPI_Recv (recvbuf, count, MPI_INT, 0, tag, comm, &status);
   MPI_Send (sendbuf, count, MPI_INT, 0, tag, comm);
}

Always be aware that for every MPI_Send() there must be a pairing MPI_Recv(), both "parallel" in time. For example, this may end in deadlock because pairing send/recv calls are not aligned in time. They cross each other:

RANK 0                          RANK 1
----------                      -------
MPI_Send() ---            ----  MPI_Send()    |
              ---      ---                    |
                 ------                       |
                   --                         | TIME
                 ------                       |
              ---      ---                    |
MPI_Recv() <--            --->  MPI_Recv()    v

These processes, on the other way, won't end in deadlock, provided of course, that there are indeed two processes with ranks 0 and 1 in the same communicator domain.

RANK 0                          RANK 1
----------                      -------
MPI_Send() ------------------>  MPI_Recv()   |
                                             | TIME
                                             |
MPI_Recv() <------------------  MPI_Send()   v

The above fixed program may fail if the size of the communicator com does not allow rank 1 (only 0). That way, the if-else won't take the else route and thus, no process will be listening for the MPI_Send() and rank 0 will deadlock.

If you need to use your current communication layout, then you may prefer to use MPI_Isend() or MPI_Issend() instead for nonblocking sends, thus avoiding deadlock.

Answer 2

The post by @mcleod_ideafix is very good. I want to add a couple more things about non-blocking MPI calls.

The way most MPI implementations is that they copy the data out of the user buffer into some other place. It might be a buffer internal to the implementation, it might be something better on the right kind of networks. When that data is copied out of the user buffer and the buffer can be reused by the application, the MPI_SEND call returns. This may be before the matching MPI_RECV is called or it may not. The larger the data you are sending, the more likely that your message will block until the MPI_RECV call is made.

The best way to avoid this is to use non-blocking calls MPI_IRECV and MPI_ISEND. This way you can post your MPI_IRECV first, then make your call to MPI_ISEND. This avoids extra copies when the messages arrive (because the buffer to hold them is already available via the MPI_IRECV) which makes things faster, and it avoids the deadlock situation. So now your code would look like this:

MPI_Comm_rank (comm, &my_rank);
if (my_rank == 0) {
   MPI_Irecv (recvbuf, count, MPI_INT, 1, tag, comm, &status, &requests[0]);
   MPI_Isend (sendbuf, count, MPI_INT, 1, tag, comm, &requests[1]);
} else if (my_rank == 1) {
   MPI_Irecv (recvbuf, count, MPI_INT, 0, tag, comm, &status, &requests[0]);
   MPI_Isend (sendbuf, count, MPI_INT, 0, tag, comm, &requests[1]);
}
MPI_Waitall(2, request, &statuses);

Answer 3

As mcleod_ideafix explained your code can result in a deadlock. Here you go: Explanation and two possible issue Solutions, one by rearranging execution order, one by async send recv calls

Heres the solution with async calls:

if (rank == 0) {
        MPI_Isend(..., 1, tag, MPI_COMM_WORLD, &req);
        MPI_Recv(..., 1, tag, MPI_COMM_WORLD, &status);
        MPI_Wait(&req, &status);
} else if (rank == 1) {
        MPI_Recv(..., 0, tag, MPI_COMM_WORLD, &status);
        MPI_Send(..., 0, tag, MPI_COMM_WORLD);
}