Clarification on Deadlocks in the Shift Example

[alyfarahat]

In lecture 15, we used Isend() to avoid a potential deadlock due to a circular wait of a blocking send in each process.

Would that still be the case if it were not a rotation? For example, if it were just a right-shift without rotation, with a chain-like communication topology instead of a ring, would we still worry about a possible deadlock?

[cswiercz]

If the right-shift operation simply "threw away" the right-most element of the array in the "last" process then that last process isn't obligated to send its right element to process 0. Here, you could have some sort of conditional

if (rank < size-1)  // only send data if you're not the "right-most" process
{
    MPI_Send(&right_ghost, ...);
}

MPI_Recv(&left_ghost, ...)

Because the rank=size-1 process never performs the send it will head straight to its MPI_Recv() call. This call corresponds to Process rank=size-2's MPI_Send() which ends up being resolved so that Process rank=size-2 and then proceed to its MPI_Recv(), etc... Thus, the non-circular communication chain is resolved.

So the short answer is: if the communication pattern in this problem were linear instead of circular (and the right-most array element is thrown away as a result) then blocking MPI_Send()s do not lead to deadlock!