Communicator Info Assertion: No Wildcards

[mpiforumbot]

Originally by jdinan on 2014-11-20 12:48:50 -0600

---

Motivation

These info keys allow the programmer to assert that MPI_ANY_TAG and/or MPI_ANY_SOURCE will not be used in operations posted on a given communicator.

These assertions allow MPI implementations to organize message matching structures to reduce matching overheads. For example, operations posted on communicators with wildcard restrictions can be stored in a structure that is much more efficient to search than a FIFO ordered list. In addition, when multiple communication channels are used (e.g. shared memory, multiple rails, etc) restricting wildcards can allow matching to be handled independently per channel.

Proposed Info Keys

The following text would be added to page 249, line 12 of MPI 3.0:

The following info keys are valid for all communicators.

mpi_assert_no_any_tag -- If set to true, the process will not use the MPI_ANY_TAG wildcard
on the given communicator.

mpi_assert_no_any_source -- If set to true, the process will not use the MPI_ANY_SOURCE
wildcard on the given communicator.

[mpiforumbot]

Originally by jdinan on 2014-11-20 12:50:29 -0600

---

These info keys were originally part of #381, but have been split into a separate ticket because there is consensus on moving them forward for MPI 3.1.

[mpiforumbot]

Originally by jdinan on 2014-11-20 15:57:51 -0600

---

Jeff Hammond provided several references to papers that document performance challenges associated with wildcards:

-PAMI: A Parallel Active Message Interface for the Blue Gene/Q Supercomputer* -- http://dx.doi.org/10.1109/IPDPS.2012.73 - see IV.A.

"We have explored parallel receive queues with a seperate queue for a subset of source nodes. However, a wildcard any-source receive can serialize receive processing as it must be matched before all receives posted after that wildcard. We observed that the algorithms to process wild cards can be very complex and significantly limit performance in the presence of wild cards." (The next statement about the wildcard receives being common in BGQ applications is wrong, by the way, should anyone ask.)

-Enabling Concurrent Multithreaded MPI Communication on Multicore Petascale Systems* -- http://www.mcs.anl.gov/papers/P1761.pdf

"A further complication is introduced by the feature in MPI that allows “wild-card” (MPI_ANY_SOURCE) receives that can match incoming messages from any sender. For any receive (or for matching any incoming message), this feature requires two logical queues to be searched atomically -- receives expecting a specific sender and receives permitting any sender -- in a manner that maintains MPI’s message-ordering semantics. This requirement makes it difficult to allow for concurrency even in programs written to match receives with specific senders, which in the absence of MPI_ANY_SOURCE could be implemented efficiently with separate queues for separate senders. MPI_ANY_SOURCE implies a shared queue that all threads must check and atomically update, thereby limiting concurrency."

-Scalability-Driven Approaches to Key Aspects of the Message Passing Interface for Next Generation Supercomputing* --http://post.queensu.ca/~pprl/thesis/Judicael_Zounmevo_PhD_thesis.pdf

"As a result, all protocol improvement proposals which resort to receiver initiation must fall back to a default, potentially inefficient protocol, when MPI wildcards are involved." (page 39)

[mpiforumbot]

Originally by jsquyres on 2014-12-10 11:22:50 -0600

---

Note to chapter committee: if #411 passes, the info key names need to be prefixed with "mpi_".

[mpiforumbot]

Originally by jdinan on 2015-01-23 16:24:37 -0600

---

TupleQ: Fully-asynchronous and zero-copy MPI over Infiniband -- http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5161056

When a wildcard receive is posted all connections to the receiver are shutdown. This prevents any messages from being retried by the HCA and all will end up connecting back to the receiver with a traditional mechanism described in Section 4. After the wildcard has been matched the receiver will notify the senders and the tuple queues can be used again.

This fallback can be quite expensive if it occurs too often, so TupleQ will fall back to a traditional implementation model if it occurs too frequently.