MPI_Sendrecv deadlocks on 3+ processes

Question

Trying to do a "halo/ghost" row exchange and I'm stumped by a deadlock (in code snippet below the picture). The "halo" rows to be exchanged are represented as dark-grey lines (in the picture) and as hp[0] and hp[M-1] (in the code).

[Can't post pictures; not enough reputation. Again in words: hp[0] and hp[M-1] are "halo" rows (i.e. rows to be exchanged) while hp[1] and hp[M-2] (and all rows in-between) are to be calculated with.]

Why would this snippet (which works OK for 2 processes) deadlock with 3+ processes?

// in-between processes ("P1" and "P2" in the picture; 
// one of "P1" and "P2" is of course missing in the case of 3 processes)
if (p > 0 && p < P-1) 
{ 
    MPI_Sendrecv(hp[M-2], N, MPI_DOUBLE, p+1, 0, 
                 hp[0],   N, MPI_DOUBLE, p-1, 0, MPI_COMM_WORLD, &s);  
    MPI_Sendrecv(hp[1],   N, MPI_DOUBLE, p-1, 1, 
                 hp[M-1], N, MPI_DOUBLE, p+1, 1, MPI_COMM_WORLD, &s);  
}
// root process ("P0" in the picture)
else if (p == 0) 
{
    MPI_Sendrecv(hp[M-2], N, MPI_DOUBLE, p+1, 0, 
                 hp[M-1], N, MPI_DOUBLE, p+1, 1, MPI_COMM_WORLD, &s);  
}
// last process ("P3" in the picture)
else 
{
    MPI_Sendrecv(hp[1],   N, MPI_DOUBLE, p-1, 1, 
                 hp[0],   N, MPI_DOUBLE, p-1, 0, MPI_COMM_WORLD, &s); 
}

Platform: Windows XP with DeinoMPI GUI which has a button "Show Messages" which "Interrupts the running job and prints the current state of the message queues"

Well, this is an example of a "current state" (when in deadlock):

Rank 0 queues:
 Posted receive queue:
  rank=2, tag=1, context_id=1(Collective), count=0, dtype=MPI_BYTE
Rank 1 queues:
 Posted receive queue:
  rank=0, tag=0, context_id=MPI_COMM_WORLD, count=10, dtype=MPI_DOUBLE
 Received but unmatched queue:
  rank=2, tag=2, context_id=MPI_COMM_WORLD, length=80
  rank=2, tag=2, context_id=MPI_COMM_WORLD, length=80
  rank=0, tag=1, context_id=1(Collective), length=0
Rank 2 queues:
 Posted receive queue:
  rank=1, tag=1, context_id=MPI_COMM_WORLD, count=10, dtype=MPI_DOUBLE

Why is there an MPI_BYTE as datatype and 1(Collective) as context? And why has Rank 0 in his receive queue a rank = 2?!

PS: Forgive me if I'm asking (and missing) something obvious, but I've read too many SO questions already, alas with no solution to be found. So many, that I know the HPC trio of Jonathan Dursi, High Performance Mark, and suszterpatt.

Update (full loop)

There isn't much more to the loop, so I can post it in its entirety: it has some commented MPI_Barriers because I was randomly trying which combination would work (talk about a "black box"). So, besides those MPI_Barriers (and a MPI_Sccaterv before the loop) there isn't any other communication going on. For the purpose of testing, I do a return 0; before MPI_Gatherv after the loop (so this should have no deadlock implications as well).

while (1)
{
    difference = 0.0;

    //MPI_Barrier(MPI_COMM_WORLD);

    // in-between processes ("P1" and "P2" in the picture; 
    // one of "P1" and "P2" is of course missing in the case of 3 processes)
    if (p > 0 && p < P-1) 
    { 
        MPI_Sendrecv(hp[M-2], N, MPI_DOUBLE, p+1, 0, 
                     hp[0],   N, MPI_DOUBLE, p-1, 0, MPI_COMM_WORLD, &s);  
        MPI_Sendrecv(hp[1],   N, MPI_DOUBLE, p-1, 1, 
                     hp[M-1], N, MPI_DOUBLE, p+1, 1, MPI_COMM_WORLD, &s);  
    }
    // root process ("P0" in the picture)
    else if (p == 0) 
    {
        MPI_Sendrecv(hp[M-2], N, MPI_DOUBLE, p+1, 0, 
                     hp[M-1], N, MPI_DOUBLE, p+1, 1, MPI_COMM_WORLD, &s);  
    }
    // last process ("P3" in the picture)
    else 
    {
        MPI_Sendrecv(hp[1],   N, MPI_DOUBLE, p-1, 1, 
                     hp[0],   N, MPI_DOUBLE, p-1, 0, MPI_COMM_WORLD, &s); 
    }
    //MPI_Barrier(MPI_COMM_WORLD);

    // calculate "hpNEW" for each inner point
    for (y = 1; y < M-1; ++y)
        for (x = 1; x < N-1; ++x)
        {
            hpNEW[y][x] = (hp[y][x-1] + hp[y][x+1] + hp[y-1][x] + hp[y+1][x]) / 4.0;
            if (fabs( hpNEW[y][x] - hp[y][x] ) > diff)
                difference = fabs(hpNEW[y][x] - hp[y][x]);
        }

    if (difference < EPSILON)
        break;

    // transfer "hpNEW"'s calculated inner points to "hp" for next iteration 
    for (y = 1; y < M-1; ++y)
        for (x = 1; x < N-1; ++x)
            hp[y][x] = hpNEW[y][x];
} // while END

One process will indeed break out of the loop first ... would/could this cause a deadlock (among other possible things unbeknownst to me)? If so, how to prevent it?

One other thing regarding "weird" tags. I just ran the above loop with all MPI_Barriers commented out ... and got this "strange" (there is a tag=4!) message queue state:

Rank 0 queues:
 Posted receive queue:
  rank=1, tag=4, context_id=1(Collective), count=30, dtype=MPI_DOUBLE
 Received but unmatched queue:
  rank=2, tag=1, context_id=1(Collective), length=0
Rank 1 queues:
 Posted receive queue:
  rank=0, tag=0, context_id=MPI_COMM_WORLD, count=10, dtype=MPI_DOUBLE
 Received but unmatched queue:
  rank=2, tag=1, context_id=MPI_COMM_WORLD, length=80
Rank 2 queues:
 Posted receive queue:
  rank=1, tag=1, context_id=1(Collective), count=0, dtype=MPI_BYTE

Answer 1

There are others, we're just the ones that have been active recently...

That's interesting about DeinoMPI on windows, I didn't realize it had nice tools to see what's going on in real time like that.

So you definitely aren't asking something obvious; on the face of it, I don't see anything wrong with the code you've posted. I personally find it clearer to use something like MPI_PROC_NULL to simplify the code logic:

left = p-1;
if (left < 0) left = MPI_PROC_NULL;
right = p+1;
if (right >= P) right = MPI_PROC_NULL;

MPI_Sendrecv(hp[M-2], N, MPI_DOUBLE, right, 0, 
             hp[0],   N, MPI_DOUBLE, left , 0, MPI_COMM_WORLD, &s);  
MPI_Sendrecv(hp[1],   N, MPI_DOUBLE, left , 1, 
             hp[M-1], N, MPI_DOUBLE, right, 1, MPI_COMM_WORLD, &s);  

and let the MPI library deal with the edge cases, rather than having the explicit tests if (p == 0), etc; but that's a question of taste and what you're going to do with the code afterwards.

The situation in the message queues is confusing enough that I don't think the code you've posted is responsible for the deadlock, although it might be where (say) rank 1 ends up manifesting the deadlock -- it might be where rank 1 is seen to hang.

If you look at what's going on, rank 1 is waiting for 10 doubles from rank 0, and rank 2 is waiting for 10 doubles from rank 1, so it's like the rightward-sending phase of your halo filling -- 1 and 2 have posted their respective receives for that phase -- except 2's tag is wrong, it's receiving 10 doubles with tag 1, which shouldn't happen (by the code above).

On top of that, rank 0 is waiting for that collective to finish (with zero data associated with it -- a barrier, maybe? Or an MPI_Finalize or something else with implied synchronization?) and so isn't sending to 1; rank 1 already has a message as part of that collective, so if it gets finished it would clear that immediately and do it's part of that collective. It also has two messages already sitting there from rank 2, with tag 2? So that must come from another phase of communication outside the current code snippet.

Just guessing from what I see in the queue, I'm guessing the code goes something like:

loop { 
    communication as posted above;

    another phase of communication;

    synchronization (barrier?)
}

and it's that second phase of communication which has a subtle error.

Update:

Ok, so processes exiting the loop at different times will definately cause lockups as processes start waiting for messages which will never come from their neighbours. But this is easy to fix; after you locally calculate the biggest difference, you then find the maximum of that difference across processors with an MPI_Allreduce; only if the global difference between hp and hpNEW is everywhere less than EPSILON do you continue.

// calculate "hpNEW" for each inner point locally
for (y = 1; y < M-1; ++y)
    for (x = 1; x < N-1; ++x)
    {
        hpNEW[y][x] = (hp[y][x-1] + hp[y][x+1] + hp[y-1][x] + hp[y+1][x]) / 4.0;
        if (fabs( hpNEW[y][x] - hp[y][x] ) > diff)
            diff = fabs(hpNEW[y][x] - hp[y][x]);
    }

// find the maximum of all the local differences

MPI_Allreduce (&diff, &globaldiff, 1, MPI_DOUBLE, MPI_MAX, MPI_COMM_WORLD);

if (globaldiff < EPSILON)
    break;