Subject: order requirements for point to point communication

From: [email-masked] (Marc Snir)
Date: Tue, 23 Nov 93 10:26:29 -0500

Pls look at the following examples and let me know if we agree on
the interpretation of the semantics for pt2pt communication

A

switch(myid)
  {

  case 0: { MPI_Ssend(...,1,0,MPI_Comm_world);
            MPI_Rsend(...,1,1,MPI_Comm_World);
          }

  case 1: { MPI_Irecv(...,0,1,MPI_Comm_world);
            MPI_Irecv(...,0,0,MPI_Comm_world);
          }
  }
....

Program is correct:  1st send matches second receive, and
vice-versa.  The 1st send can complete only if the 2nd receive has
started, which makes sure that 1st receive is posted.  Therefore, it
is correct to use a ready-receive send.   (Implication: the
operation that posts a receive cannot return before it is ready to
start accepting the message)

B

switch(myid)
  {

  case 0: { MPI_Send(...,2,0,MPI_Comm_world);
            MPI_Send(...,1,0,MPI_Comm_World);
           }

  case 1:  { MPI_Recv(...,0,0,MPI_Comm_world);
             MPI_Send(...,2,0,MPI_Comm_world);
            }

  case 2:   { MPI_recv(...,MPI_Any_source,0,MPI_Comm_world);
              MPI_recv(...,MPI_Any_source,0,MPI_Comm_world);
             }
   }
....

This is an example of causality violation:  Process 0 sends first to
2, next to 1; process 1 receives from 0, next sends to 2; yet
process 2 may receive the message of process 1 before it receives
the message of process 0: the two receives of 2 may match
the two messages sent to it in either order.
I.e., order is preserved only on direct
links, but need not be preserved when we have indirect causality.

C

switch(myid)
   {

   case 0: { MPI_Ssend(...,2,0,MPI_Comm_world);
             MPI_Send(...,1,0,MPI_Comm_world);
            }

   case 1:  { MPI_Recv(...,0,0,MPI_Comm_world);
              MPI_send(...,2,0,MPI_Comm_world);
             }

   case 2:   { MPI_recv(...,MPI_Any_source,0,MPI_Comm_world);
               MPI_recv(...,MPI_Any_source,0,MPI_Comm_world);
              }
    }

Same code as in example B, with the first send replaced by a
synchronous send.  A strict interpretation of our draft will imply
that in this case, too, either message sent to process 2 may match
either receive.  However, an "out of order" receive is somewhat
strange:   The first send of process 0 can complete only if a
receive has started at process 2.  The message of process 1 arrives
at process 2 only after a receive of the message of process 0 has
already started.  Thus, an "out of order" matching corresponds to a
situation where both receives have already been posted at process 2,
the message from process 0 arrives before any other message,
and even though it matches both
posted receives, it is accepted by the second posted receive.   I
find such behavior somewhat counterintuitive.

---

From: L J Clarke <[email-masked]>
Date: Tue, 23 Nov 93 17:45:12 GMT

> start accepting the message)

Agree program is correct.  

Dont quite understand "Implication:" - if you mean that in the above
example the second MPI_Irecv in "case 1" cannot return until the
MPI_Ssend in "case 0" has started then this is not consistent with my
interpretation which is that MPI_Irecv does not block, however if you
mean that said MPI_Irecv cannot return until it has locally prepared
itself then that seems okay since it must take bounded time. 

The example is good.  If we agree on the semantics that the program is
correct then we are saying that the Isend (Irecv) functions are not
equivalent to starting a thread which performs the Send (Recv) function. 

> links, but need not be preserved when we have indirect causality.

Yeah, pairwise ordering preserved but nothing said about such indirect
causality, this is my interpretation.  Interesting that if you do
replace all of the MPI_Send with MPI_Ssend then the above fragment does
not violate "global" causality. 

> find such behavior somewhat counterintuitive.

Yes, counterintuitive. My interpretation/understanding ... 

In the above example the two receives in process 2 were not immediate
(nonblocking) therefore the second cannot be started before the first
has completed and the fragment is deterministic in that the first
MPI_Recv in process 2 has accepted the MPI_Ssend in process 0 even
before the second recv in process 2 has started (which must then accept
the MPI_Send in process 1). 

If we make the modification you appear to suggest - i.e.  make the two
MPI_Recv in process 1 into MPI_Irecv

switch(myid)
   {

   case 2:   { MPI_Irecv(...,MPI_Any_source,0,MPI_Comm_world);
               MPI_Irecv(...,MPI_Any_source,0,MPI_Comm_world);
              }
    }

then it is intuitive that the same matching of sends with receives
occurs. 

The message from process 0 must have *started* to arrive at process 2
*before* the message from process 1, however it could be that the
message from process 0 *finished* arriving at process 2 *after* the
message from process 1. 

It seems the challenge is to find the words which will express the
desired semantics without ambiguity. Something like 

"when a message begins to arrive at a process and there is more than one
nonblocking receive which can match that message then the nonblocking
receive chosen to match is that which was posted earliest"

Discussion: Does this have too strong implementation requirements? It is
like saying that the behaviour must be as though posted receive requests
are stored in a linked list with new requests added to the back of the
list and matches taken from the nearest matching request to the front of
the list. Now if we do think this is too strong then do we also make a
step back to say that the ordering is not defined? If so then do we not
have to revise our opinion of the first example Marc gave? 

Nice hoop, Marc, nice hoop!

Best Wishes
Lyndon

         /--------------------------------------------------------\
    e||) | Lyndon J Clarke    Edinburgh Parallel Computing Centre | e||) 
    c||c | Tel: 031 650 5021  Email: [email-masked]  | c||c 
         \--------------------------------------------------------/