Misleading discussion of thread ordering

[mpiforumbot]

Originally by gropp on 2008-12-19 17:06:19 -0600

---

Description

On page 42, lines 10-17, there is a description of ordering of point to point operations in multi-threaded MPI applications that can be read to imply that send operations, in separate threads, may not preserve order even if there is a well-defined order (enforced, for example, with a pthread_barrier). This is a proposal to more precisely word this paragraph to make it clear under what cases a multithreaded code must preserve order. E.g., In the case:

   thread a                thread b
   MPI_Send()
   pthread_barrier_wait    pthread_barrier_wait
                           MPI_Send()

Are the sends ordered or not? Note that there is no valid interleaving that puts the MPI_Send in thread b before the MPI_Send in thread a.

History

There is/was another ticket (#144) that proposed a similar fix. This ticket combines the two.

Proposed Solution

Page 42, lines 10-17: Replace

If a process has a single thread of execution, then any two communications executed by this process are ordered. On the other hand, if the process is multi-threaded, then the semantics of thread execution may not define a relative order between two send operations executed by two distinct threads. The operations are logically concurrent, even if one physically precedes the other. In such a case, the two messages sent 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 two receives in either order.

with

If a process has a single thread of execution, then any two communications executed by this process are ordered. On the other hand, if the process is multi-threaded, then the semantics of thread execution might not define a relative order between two send operations executed by two distinct threads. However, it may be possible to define such an order by using operations defined between threads, such as the use of pthread_barrier_wait when using POSIX threads. If an order is not defined, the operations are logically concurrent, even if one physically precedes the other. In such a case, the two messages sent 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 two receives in either order.

Impact on Implementations

Implementations would have to enforce the ordering of sends and receives on different threads. Since the MPI implementation cannot tell whether there was explicit synchronization, it would have to assume that there was explicit synchronization between any two sends (or receives) that do not overlap, i.e., two sends do not overlap if the first MPI_Send() returns before the second MPI_Send() is called.

It is possible than an implementation interpreted the standard to say that sends/receives are never ordered between threads, and so, for performance reasons, allows each thread to have it's own send path (separate queues, DMA, network injection port, etc) and receive path (to perform sending and matching from different threads in parallel). Such an implementation would need to be changed.

Impact on Applications / Users

Users would have a way to enforce ordering between sends on different threads. I suspect that many users are already using barriers to do this.

Alternative Solutions

none

Entry for the Change Log

Section 3.5 on page 42.

Ordering guarantees of send or receive operations on different threads have been clarified.

[mpiforumbot]

Originally by rsthakur on 2009-04-07 10:09:05 -0500

---

Copying Dick Treumann's email reply here (also in ticket #144) so that it stays with the ticket.

---

The standard already says: 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. 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 one is still pending. This requirement facilitates matching of sends to receives. It guarantees that message-passing code is deterministic,

I think that already provides the appropriate guarantee. Two concurrent threads making MPI calls do not provide any enforcement of "succession" and the standard points this out to be helpful. It should not really have been necessary to say this.

Explicit temporal ordering of actions on otherwise concurrent threads by an application is common and it is not the job of the MPI standard to say how this is to be done. MPI should probably only say in any situation where "succession" is ambiguous, MPI makes no guarantee of disambiguation. Where "succession" is clear cut, MPI will reflect the succession order.

[mpiforumbot]

Originally by buntinas on 2009-04-07 10:37:20 -0500

---

I've modified the description to combine the ideas from #144.

[mpiforumbot]

Originally by balaji on 2009-04-07 11:04:36 -0500

---

This ticket is OK as long as we know there are no existing MPI implementations that use different per-thread connections. If there is such an MPI implementation, I think this would be out-of-scope for MPI-2.2.

[mpiforumbot]

Originally by rsthakur on 2009-04-07 11:09:04 -0500

---

OK with me.

[mpiforumbot]

Originally by buntinas on 2009-04-07 11:10:40 -0500

---

Reviewed by me.

[mpiforumbot]

Originally by timattox on 2009-04-07 11:45:02 -0500

---

Reviewed by me

[mpiforumbot]

Originally by schulzm on 2009-04-07 12:44:30 -0500

---

Added myself as a reviewer

Someone should check if pthread_barrier_wait is really a call defined by the POSIX
standard (at least ~10 years ago it was not). If it is not, the reference to POSIX
should be removed in the text or pthread_barrier should be replaced with "a thread
barrier operation". If it is, the text should say pthread_barrier_wait() instead of
pthread_barrier.

Besides that, this ticket looks good to me

[mpiforumbot]

Originally by gropp on 2009-04-07 13:03:59 -0500

---

Corrected pthread_barrier to pthread_barrier_wait; otherwise, reviewed ok

[mpiforumbot]

Originally by buntinas on 2009-04-07 14:13:42 -0500

---

Replying to schulzm:

Someone should check if pthread_barrier_wait is really a call defined by the POSIX
standard (at least ~10 years ago it was not). If it is not, the reference to POSIX
should be removed in the text or pthread_barrier should be replaced with "a thread
barrier operation". If it is, the text should say pthread_barrier_wait() instead of
pthread_barrier.

Well, it doesn't really say that pthread_barrier_wait is POSIX, it just says that you can use it with POSIX threads. So even if pthread_barrier_wait is not strictly part of POSIX, but is still widely used, I think it should be OK to use in this context.

[mpiforumbot]

Originally by rlgraham on 2009-04-08 09:27:09 -0500

---

fine with me

[mpiforumbot]

Originally by smithbr on 2009-04-17 09:28:41 -0500

---

Add smithbr to CC