Order of received messages using Bsend and Ssend

[ShaunJ]

Process A:
MPI_Bsend(buf, count, MPI_BYTE, dest, tag0, MPI_COMM_WORLD);
MPI_Ssend(buf, count, MPI_BYTE, dest, tag1, MPI_COMM_WORLD);

Process B
MPI_Recv(buf, count, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);
MPI_Recv(buf, count, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);

Is it guaranteed that process B will receive tag0 before receiving
tag1? Is it possible that the tag0 message will still be holding in an
outgoing buffer of process A while tag1 has been successfully sent and
received?

In the following example [1], it's guaranteed that process one
received the messages in the reverse order they were sent.
[1] http://www.mpi-forum.org/docs/mpi-11-html/node41.html

CALL MPI_COMM_RANK(comm, rank, ierr)
IF (rank.EQ.0) THEN
CALL MPI_BSEND(buf1, count, MPI_REAL, 1, tag1, comm, ierr)
CALL MPI_SSEND(buf2, count, MPI_REAL, 1, tag2, comm, ierr)
ELSE ! rank.EQ.1
CALL MPI_RECV(buf1, count, MPI_REAL, 0, tag2, comm, status, ierr)
CALL MPI_RECV(buf2, count, MPI_REAL, 0, tag1, comm, status, ierr)
END IF

I've read that MPI guarantees that two messages sent from one process,
A, to another process, B, are guaranteed to arrive at process B in
order they were sent [2], but the above example seems to contradict
that -- usefully so. Being that messages can evidently arrive in a
different order than they were sent, I'm trying to figure what under
what conditions messages are guaranteed to arrive in the order they
were sent, and when messages may -- or as in the above example, must
-- arrive out of order.
[2] http://www.csd.uoc.gr/~hy555/dbpp/text/node96.html

Thanks,
Shaun

[Greg Lindahl]

Post by ShaunJ
I've read that MPI guarantees that two messages sent from one process,
A, to another process, B, are guaranteed to arrive at process B in
order they were sent [2], but the above example seems to contradict
that

Not really. The receiver in [2] asked for the messages out of
order. So yes, the messages arrived in order, but they weren't asked
for (received) in order. arrived != received.

Note that the Bsend is used to guarantee that send buffering will be
available. Otherwise the program would be unsafe.

-- greg

[Michael Hofmann]

Post by ShaunJ
MPI_Bsend(buf, count, MPI_BYTE, dest, tag0, MPI_COMM_WORLD);
MPI_Ssend(buf, count, MPI_BYTE, dest, tag1, MPI_COMM_WORLD);
Process B
MPI_Recv(buf, count, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);
MPI_Recv(buf, count, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG,
MPI_COMM_WORLD, &status);
Is it guaranteed that process B will receive tag0 before receiving
tag1?

Yes, because: "If a sender sends two messages in succession to the same
destination, and both match the same receive, then this operation cannot
receive the second message if the first one is still pending." [1]

Post by ShaunJ
Is it possible that the tag0 message will still be holding in an
outgoing buffer of process A while tag1 has been successfully sent and
received?

No, because this violates the correct receive order of the messages (as
described above). The communication mode (buffered, synchronous etc.) has
no influence on this order.

Post by ShaunJ
In the following example [1], it's guaranteed that process one
received the messages in the reverse order they were sent.
[1] http://www.mpi-forum.org/docs/mpi-11-html/node41.html
CALL MPI_COMM_RANK(comm, rank, ierr)
IF (rank.EQ.0) THEN
CALL MPI_BSEND(buf1, count, MPI_REAL, 1, tag1, comm, ierr)
CALL MPI_SSEND(buf2, count, MPI_REAL, 1, tag2, comm, ierr)
ELSE ! rank.EQ.1
CALL MPI_RECV(buf1, count, MPI_REAL, 0, tag2, comm, status, ierr)
CALL MPI_RECV(buf2, count, MPI_REAL, 0, tag1, comm, status, ierr)
END IF
I've read that MPI guarantees that two messages sent from one process,
A, to another process, B, are guaranteed to arrive at process B in
order they were sent [2], but the above example seems to contradict
that -- usefully so.

No, there is no contradiction. The order is guaranteed only if multiple
messages match the same receive. The example uses different tags. The
first receive matches _only_ the second message. So, there is nothing to
order.

Post by ShaunJ
Being that messages can evidently arrive in a
different order than they were sent, I'm trying to figure what under
what conditions messages are guaranteed to arrive in the order they
were sent, and when messages may -- or as in the above example, must
-- arrive out of order.

I think it is very clear. A receive matches only a certain amount of
messages depending on the source, tag and comm values. If a receive
matches multiple messages, then the receive order (of the matching
messages) is determined by the send order (of the matching messages).
Together with some other rules, this "guarantees that message-passing code
is deterministic, if processes are single-threaded and the wildcard
MPI_ANY_SOURCE is not used in receives." [1]

[1] http://www.mpi-forum.org/docs/mpi-11-html/node41.html


Michael

[ShaunJ]

On Jul 8, 12:49 am, "Michael Hofmann" <***@s2000.tu-
chemnitz.de> wrote:
...

I think it is very clear. A receive matches only a certain amount of  
messages depending on the source, tag and comm values. If a receive  
matches multiple messages, then the receive order (of the matching  
messages) is determined by the send order (of the matching messages).  
Together with some other rules, this "guarantees that message-passing code  
is deterministic, if processes are single-threaded and the wildcard  
MPI_ANY_SOURCE is not used in receives." [1]

Thanks, Michael. Your answer clears it up nicely.

Cheers,
Shaun