Order



next up previous contents
Next: Progress Up: Semantics of Blocking Previous: Multithreading

Order

  ordermessage order

Messages are non-overtaking. Conceptually, one may think of successive messages sent by a process to another process as ordered in a sequence. Receive operations posted by a process are also ordered in a sequence. Each incoming message matches the first matching receive in the sequence. This is illustrated in Figure gif. Process zero sends two messages to process one and process two sends three messages to process one. Process one posts five receives. All communications occur in the same communication domain. The first message sent by process zero and the first message sent by process two can be received in either order, since the first two posted receives match either. The second message of process two will be received before the third message, even though the third and fourth receives match either.

  
Figure: Messages are matched in order.

Thus, if a sender sends two messages in succession to the same destination, and both match the same receive, then the receive cannot get the second message if the first message is still pending. If a receiver posts two receives in succession, and both match the same message, then the second receive operation cannot be satisfied by this message, if the first receive is still pending.

These requirements further define message matching. matchingmessage matching They guarantee that message-passing code is deterministic, if processes are single-threaded and the wildcard MPI_ANY_SOURCE is MPI_ANY_SOURCE not used in receives. Some other MPI functions, such as MPI_CANCEL or MPI_WAITANY, are additional sources of nondeterminism. deterministic programs

In a single-threaded process all communication operations are ordered according to program execution order. The situation is different when processes are multi-threaded. order, with threads The semantics of thread execution may not define a relative order between two communication operations executed by two distinct threads. The operations are logically concurrent, even if one physically precedes the other. In this case, no order constraints apply. Two messages sent by concurrent threads can be received in any order. Similarly, if two receive operations that are logically concurrent receive two successively sent messages, then the two messages can match the receives in either order.

It is important to understand what is guaranteed by the ordering property and what is not. Between any pair of communicating processes, messages flow in order. This does not imply a consistent, total order on communication events in the system. Consider the following example.

CALL MPI_COMM_RANK(comm, rank, ierr)
IF (rank.EQ.0) THEN
   CALL MPI_SEND(buf1, count, MPI_REAL, 2, tag, comm, ierr)
   CALL MPI_SEND(buf2, count, MPI_REAL, 1, tag, comm, ierr)
ELSE IF (rank.EQ.1) THEN
   CALL MPI_RECV(buf2, count, MPI_REAL, 0, tag, comm, status, ierr)
   CALL MPI_SEND(buf2, count, MPI_REAL, 2, tag, comm, ierr)
ELSE IF (rank.EQ.2) THEN
   CALL MPI_RECV(buf1, count, MPI_REAL, MPI_ANY_SOURCE, tag, comm, 
                  status, ierr)
   CALL MPI_RECV(buf2, count, MPI_REAL, MPI_ANY_SOURCE, tag, comm, 
                  status, ierr)

END IF
  

Example: Order preserving is not transitive.



next up previous contents
Next: Progress Up: Semantics of Blocking Previous: Multithreading



Jack Dongarra
Fri Sep 1 06:16:55 EDT 1995