Avoiding Deadlocks

• The semantics of MPI_Send and MPI_Recv place some restrictions on how we can mix and match send and receive operations.
• Consider the following not complete code in which process 0 sends two messages with different tags to process 1, and process 1 receives them in the reverse order.

      1 int a[10], b[10], myrank; 
      2 MPI_Status status; 
      3 ... 
      4 MPI_Comm_rank(MPI_COMM_WORLD, &myrank); 
      5 if (myrank == 0) { 
      6   MPI_Send(a, 10, MPI_INT, 1, 1, MPI_COMM_WORLD); 
      7   MPI_Send(b, 10, MPI_INT, 1, 2, MPI_COMM_WORLD); 
      8 } 
      9 else if (myrank == 1) { 
     10   MPI_Recv(b, 10, MPI_INT, 0, 2, MPI_COMM_WORLD); 
     11   MPI_Recv(a, 10, MPI_INT, 0, 1, MPI_COMM_WORLD); 
     12 } 
     13 ...
  

• If MPI_Send is implemented using buffering, then this code will run correctly (if sufficient buffer space is available).

• However, if MPI_Send is implemented by blocking until the matching receive has been issued, then neither of the two processes will be able to proceed.
• This code fragment is not safe, as its behavior is implementation dependent.
• The problem in this program can be corrected by matching the order in which the send and receive operations are issued.
• Similar deadlock situations can also occur when a process sends a message to itself.
• Improper use of MPI_Send and MPI_Recv can also lead to deadlocks in situations when each processor needs to send and receive a message in a circular fashion.

• Consider the following not complete code, in which
  • process $i$ sends a message to process $i+1$ (modulo the number of processes),
  • process $i$ receives a message from process $i-1$ (module the number of processes).

      1 int a[10], b[10], npes, myrank; 
      2 MPI_Status status; 
      3 ... 
      4 MPI_Comm_size(MPI_COMM_WORLD, &npes); 
      5 MPI_Comm_rank(MPI_COMM_WORLD, &myrank); 
      6 MPI_Send(a, 10, MPI_INT,(myrank+1)%npes,1, MPI_COMM_WORLD); 
      7 MPI_Recv(b, 10, MPI_INT,(myrank-1+npes)%npes,1, MPI_COMM_WORLD); 
      8 ...
  

• When MPI_Send is implemented using buffering, the program will work correctly,
  • since every call to MPI_Send will get buffered, allowing the call of the MPI_Recv to be performed, which will transfer the required data.
• However, if MPI_Send blocks until the matching receive has been issued,
  • all processes will enter an infinite wait state, waiting for the neighbouring process to issue a MPI_Recv operation.

• Note that the deadlock still remains even when we have only two processes.
• Thus, when pairs of processes need to exchange data, the above method leads to an unsafe program.
• The above example can be made safe, by rewriting:

      1 int a[10], b[10], np, myrank; 
      2 MPI_Status status; 
      3 ... 
      4 MPI_Comm_size(MPI_COMM_WORLD, &np); 
      5 MPI_Comm_rank(MPI_COMM_WORLD, &myrank); 
      6 if (myrank%2 == 1) { 
      7   MPI_Send(a,10,MPI_INT,(myrank+1)%np,1,MPI_COMM_WORLD); 
      8   MPI_Recv(b,10,MPI_INT,(myrank-1+np)%np,1,MPI_COMM_WORLD); 
      9 } 
     10 else { 
     11   MPI_Recv(b,10,MPI_INT,(myrank-1+np)%np,1,MPI_COMM_WORLD); 
     12   MPI_Send(a,10,MPI_INT,(myrank+1)%np,1,MPI_COMM_WORLD); 
     13 } 
     14 ...
  

• This version partitions the processes into two groups.
• One consists of the odd-numbered processes and the other of the even-numbered processes.