MPI 3.1/4 – how can progress be ensured with passive-target synchronization?

[csubich]

Greetings,

I initially interpreted the below issue as a problem within the Intel MPI implementation, but after posting on their community forums¹ Intel confirms that this is allowable behaviour per their interpretation. Either I'm misinterpreting the specification (and thus doing something undefined), Intel is wrong, or the specification is ambiguous.

Problem

Somewhat recently, I was flummoxed by a deadlock in MPI code that used passive-target synchronization. A local process would spin-wait on a variable in a shared-memory window (using local load and MPI_Win_sync), and a remote process would (eventually) update that variable with MPI_Fetch_and_op.

The expected result was… well, progress. In fact, the Intel MPI implementation would reliably deadlock when the RMA operation involved communication over an interconnect (i.e. something more than a local shared memory access). Sample code is as follows:

#include <mpi.h>
#include <stdio.h>

int main(int argc, char ** argv) {
    MPI_Init(&argc, &argv); // Initialize MPI
    int rank, nproc;
    // Get MPI rank and world size
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    MPI_Comm_size(MPI_COMM_WORLD,&nproc);

    int * rma_memory; // RMA memory (to be allocated)
    MPI_Win rma_window;
    MPI_Win_allocate(sizeof(int),1,MPI_INFO_NULL,MPI_COMM_WORLD,&rma_memory,&rma_window);

    // Get and display memory model for window
    int *memory_model, flag;
    MPI_Win_get_attr(rma_window, MPI_WIN_MODEL, &memory_model, &flag);
    if (*memory_model == MPI_WIN_UNIFIED) {
        printf("Rank %d created RMA window with the unified memory model\n",rank);
    } else if (*memory_model == MPI_WIN_SEPARATE) {
        printf("Rank %d created RMA window with the separate memory model\n",rank);
    } else {
        printf("Rank %d created RMA window with an unknown memory model(???)\n",rank);
    }

    *rma_memory = 0; // Initialize to zero

    // All processes will lock the window
    MPI_Win_lock_all(MPI_MODE_NOCHECK,rma_window);

    if (rank == 0) { 
        // Rank 0: wait for rank 1 to enter its spinlock, then use MPI_Fetch_and_op to increment
        // *rma_memory at rank 1

        // Receive zero-byte message indicating that rank 1 is ready to enter its spinlock
        MPI_Recv(0,0,MPI_BYTE,1,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);

        // Wait a further 0.1s so that rank 1 should have assuredly completed any progress-making
        // MPI calls
        double tic = MPI_Wtime(); 
        while (MPI_Wtime() - tic < 0.1); 

        tic = MPI_Wtime(); // Reset tic value to account for delay

        // Perform fetch-and-op
        int one = 1; 
        int result = -1;
        MPI_Fetch_and_op(&one, &result, MPI_INT, 1, 0, MPI_SUM, rma_window);

        // Flush the window to ensure completion
        MPI_Win_flush_all(rma_window); 

        printf("Rank 0: sent %d, received %d (should be 0) in %.2fms\n",one, result, (MPI_Wtime() - tic)*1e3);
    } else if (rank == 1) {
        // Rank 1: Send a message to rank 0 indicating readiness for Fetch_and_op
        MPI_Send(0,0,MPI_BYTE,0,0,MPI_COMM_WORLD);

        double tic = MPI_Wtime();

        // Spinlock waiting for '1' to be written to the RMA_Window
        while (*rma_memory != 1 && MPI_Wtime() - tic < 5) {
            // Separate memory model: synchronize remote and local copies of window
            // Unified memory model: memory barrier
            MPI_Win_sync(rma_window);
        }
        int old_value = *rma_memory;
        printf("Rank 1: Memory value %d (should be 1) in %.2fms\n",old_value,1e3*(MPI_Wtime()-tic-0.1));

        // Demonstrate forced progress
        MPI_Win_flush(1,rma_window); // Should be a no-op, since there are no pending RMA ops from this rank
        MPI_Win_sync(rma_window);
        if (old_value != *rma_memory) {
            printf("Rank 1: After flush, memory value is now %d (should be 1)\n",*rma_memory);
        }
    }

    MPI_Win_unlock_all(rma_window);
    MPI_Win_free(&rma_window);
    MPI_Finalize();
    return 0;
}

The problem is visible even on a single node of a cluster when the shared-memory interconnect is disabled:

$ mpirun -genv 'I_MPI_SHM=off' -np 2 ./a.out
Rank 0 created RMA window with the unified memory model
Rank 1 created RMA window with the unified memory model
Rank 1: Memory value 0 (should be 1) in 4900.00ms
Rank 1: After flush, memory value is now 1 (should be 1)
Rank 0: sent 1, received 0 (should be 0) in 4900.14ms

The root problem appears to be that rank 0 is waiting on the assistance of the rank 1 to complete the Fetch part of Fetch_and_op, but the MPI_Win_sync inside the spinlock on rank 1 does not engage the MPI progress engine.

Per the specification, I think that this behaviour is surprising if not spec-noncompliant. Per §12.7 of the 4.1 draft (atomicity isn't the problem here):

U2. Accessing a location in the window that is also the target of a remote update is valid (not erroneous) but the precise result will depend on the behavior of the implementation. Updates from an origin process will appear in the memory of the target, but there are no atomicity or ordering guarantees if more than one byte is updated. Updates are stable in the sense that once data appears in memory of the target, the data remains until replaced by another update. This permits polling on a location for a change from zero to nonzero or for a particular value, but not polling and comparing the relative magnitude of values.

Replacing the Fetch_and_op call on rank 0 with separate MPI_Get and MPI_Put calls does function properly, without deadlock, even if it has ambiguous correctness (I'm not sure about the combination of Get and Put with the same RMA target) and is absolutely erroneous in the general case of multiple writers.

Proposal

Prior to the MPI 4.1 draft, I would have asked that the call to Win_sync engage the progress engine even in the unified memory model, but that's now explicitly not required (p608). I'm not sure what the required change now is, if this deadlock is not in fact an implementation bug.

The trouble seems to be twofold:

• It's not obvious that the target of some RMA memory operations like Fetch_and_op must actively participate (via progress), even if the window has passive-target synchronization, and
• There's no obvious call to ensure such progress. Win_flush works in Intel MPI, but it's an unnatural fit because the target rank in general may have no idea what other rank is executing the atomic update. Additionally, the flush calls might implicitly cause communication even if there's nothing to do, and that's unnecessary in this case where the target rank certainly 'knows' if it needs to do something with respect to an atomic RMA operation.
  • In the Intel MPI implementation, other calls that might seemingly force progress don't. For example, a call to MPI_Test with MPI_REQUEST_NULL doesn't force progress. Rank 1 also can't force progress by sending a zero-length message to itself.
  • OpenMPI gave me odd results my testing system, but I can't guarantee that it was configured correctly.
  • In general, progress is guaranteed "while blocked on an MPI call," but with passive-target synchronization there's no obviously correct, minimal way to become blocked on an MPI call.

Changes to the Text

Again presuming this behaviour is intended or allowable:

• Document which calls might require the target's active participation, even in a passive-target epoch
• (More controversially?) Add MPI_Engage_progress() to the API as the minimal call that will tell the MPI implementation to make progress on any outstanding requests with no further semantic intent.

Impact on Implementations

Implementations will likely complain about any specification-guaranteed background progress. In the Intel forum thread linked above, the Intel representative closed the issue (then presented as a question about progress during Win_sync) because Win_sync was simply a memory barrier.

Impact on Users

At minimum, black-and-white documentation about participation requirements would have saved me, a user, a few headaches trying to distill the unexpected deadlock into a minimal example. (The original case involved Fetch_and_op to one location, then an MPI_Put of a status flag to a second; the latter was spinwaited upon, blocking completion of the original Fetch_and_op.)

References and pull requests:

Footnotes

1. (https://community.intel.com/t5/Intel-oneAPI-HPC-Toolkit/Intel-MPI-fails-to-ensure-progress-for-one-sided-operations/m-p/1519581) ↩

[jeffhammond]

Replace MPI_Win_sync(rma_window); with MPI_Win_flush(0,rma_window); and it should work.

We've debated this topic for most of the years I've been in the MPI Forum, without making any progress on it (pun intentional).

https://pmodels.github.io/casper-www/ was the pragmatic response from Argonne when I was there.

[jeffhammond]

This is what most people use:

int MPIX_Engage_progress(void)
{
  return MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}

[csubich]

Replace MPI_Win_sync(rma_window); with MPI_Win_flush(0,rma_window); and it should work.

It does, yes, but I get worried about a naive implementation of flush that has some communication overhead even when no RMA operations are pending.

We've debated this topic for most of the years I've been in the MPI Forum, without making any progress on it (pun intentional).

In that case, might I request a note in a future MPI spec to state that in a passive communication epoch, even processes that only expect to be the targets of communication may need to periodically ensure MPI progress?

The headline description of a passive target epoch (p588, v4.1RFC) states:

The MPI process that owns the target window may be distinct from the two communicating MPI processes, in which case it does not participate explicitly in the communication.

… which gives the vague impression that no matter the RMA calls executed by other processes, the process that owns the target window does not need to do anything to ensure their eventual completion.

It'd be better yet if the specification could split the RMA calls into ones that may require progress on the target and ones that definitely do not, but I suspect that would be controversial.

return MPI_Probe

Oh, that makes a lot of sense, and I can use an IProbe version in the RMA context. I tend to forget that the Probe calls exist.

[jeffhammond]

Replace MPI_Win_sync(rma_window); with MPI_Win_flush(0,rma_window); and it should work.

It does, yes, but I get worried about a naive implementation of flush that has some communication overhead even when no RMA operations are pending.

It shouldn't expensive. Checking a queue for emptiness is trivial. It's going to be less expensive than error checking, probably by a lot.

We've debated this topic for most of the years I've been in the MPI Forum, without making any progress on it (pun intentional).

In that case, might I request a note in a future MPI spec to state that in a passive communication epoch, even processes that only expect to be the targets of communication may need to periodically ensure MPI progress?

I think it would be useful to add an example of the use case you have, which is not uncommon, and show how to do it correctly.

The headline description of a passive target epoch (p588, v4.1RFC) states:

The MPI process that owns the target window may be distinct from the two communicating MPI processes, in which case it does not participate explicitly in the communication.

… which gives the vague impression that no matter the RMA calls executed by other processes, the process that owns the target window does not need to do anything to ensure their eventual completion.

Yes, but eventually is a long time 😉

It'd be better yet if the specification could split the RMA calls into ones that may require progress on the target and ones that definitely do not, but I suspect that would be controversial.

I doubt it would be controversial. @Wee-Free-Scot and others have been looking at issues like this for a while.

return MPI_Probe

Oh, that makes a lot of sense, and I can use an IProbe version in the RMA context. I tend to forget that the Probe calls exist.

[Wee-Free-Scot]

The new (in MPI-4.1) subsection 2.9 in the Terms chapter defines "progress" in the MPI Standard for the first time. It only gives example procedures from point-to-point, but the rules stated there can be used to put RMA procedures into categories "must guarantee progress" and "others".

@csubich Once you've had a chance to read that and to apply it to RMA, any remaining confusion or unresolved conflicts would be really useful feedback.

[csubich]

@Wee-Free-Scot I apologize for having missed your request for feedback earlier. I've come back to this project and I've had the opportunity to look at the new language.

The extra language is nice, and having a black and white definition of 'progress' certainly helps. The definition of 'decoupled MPI activities' also helps explain the sense in which RMA calls might need help from a progress engine.

One subtlety, however, is that the text permits an MPI engine to not make progress on calls that might block but do not. For example, a process that calls MPI_Sendrecv to send a message to itself does not force other MPI activities to make progress because the implementation can effect the sendrecv without blocking. (The above-thread-mentioned Intel MPI does just this.)

This leads to a perverse interpretation of 'progress' that (I think) is permitted by 4.1 but might still cause the above code to deadlock:

• Processes start by MPI_ISending a message to each other with a dummy tag, to be received only before exiting
• MPI_Probe (any source / any tag) will find and return this message without necessarily blocking, and MPI_Iprobe would return with flag=true; neither is guaranteed to make progress
• MPI_Win_flush_all(window) might return without blocking if the (target) process realizes it has not issued any RMA calls and thus returns early.

A minor extension to the specification to include a "must make RMA progress" call would be to permit MPI_Win_test to be called on non-PSCW windows, defined to always return flag=false¹ and thus engage progress.

Footnotes

1. Maybe the flag could be given semantic meaning, such as "false if this window is / might be part of an access epoch," allowing MPI_Fence synchronization with MPI_MODE_NOSUCCEED to cause flag=true, or any passive-target exposure where the implementation can know that no other process has locked the window (perhaps only provably true with the separate memory model?). Otherwise, "always flag=false" retains the existing meaning of "MPI_Win_wait would have immediately returned," since calling Win_wait on a non-PSCW window is erroneous. ↩

[Wee-Free-Scot]

The "perverse interpretations" that you mention are all intentional implementation flexibility.

The canonical "kick the progress engine" call is a call to MPI_Iprobe with parameters that select a message that is never sent. Each call must return false, the repetition of such calls must be guaranteed to make progress (even though no individual call is required to make progress). Being required to make progress is MPI-wide -- so it includes RMA operations, even though the canonical procedure is from the point-to-point chapter.

Given this, overloading the MPI_Win_test procedure in this way seems superfluous. Separately, it seems problematic because you can (although certainly shouldn't) mix the RMA synchronisation methods on the same window, so calling MPI_Win_test has an existing meaning.

[csubich]

The canonical "kick the progress engine" call is a call to MPI_Iprobe with parameters that select a message that is never sent.

First, to take a step back I'll reiterate that it is frustrating and deeply unintuitive that legal sequences of RMA calls might require non-RMA calls to avoid deadlock. I accept that's how the specification works, but the complete absence of "messages" from the 'RMA way' makes IProbe a weird tool to reach for.

It doesn't help that this issue seems to be limited to passive-target synchronization. Both fence and PSCW contain blocking calls that will force progress, so the originating problem can't occur. Here, the obvious way of writing the passive-target code did lead to the problem, and I didn't ignore any bright signposts in the specification. I would have preferred things if Win_sync was required to eventually make progress in the same way as a false-returning test, but again that ship's sailed.

Finally, if "a call to MPI_Iprobe with parameters that select a message that is never sent" is to be the only way to guarantee progress in this case, then in my opinion the specification ought to include a canonical example of this. In particular, library code can't guarantee that any tuple of (communicator, source, tag) is not being used elsewhere, so to robustly match nothing¹ the library must clone a communicator (MPI_Comm_self² being the only one that doesn't involve a collective call) to give a sterile environment for the check. Even that might have unintended consequences if the source communicator has a keyval attached with a nontrivial copy callback.

This feels absurd. The semantic intent of "make progress" is fundamental to MPI itself, but I'm really contorting myself to find a way to just engage the progress engine (if necessary) without making additional assumptions about the MPI environment.

so calling MPI_Win_test has an existing meaning.

I don't truly like proposing such an extension, but it's the only way I can see to "test" using only MPI objects guaranteed to have meaning for the RMA code, without side-effects elsewhere.

Footnotes

1. I can't even use MPI_Proc_null to "try to match nothing and fail at it!" §3.10 defines such an IProbe to return with flag=true. ↩

2. MPI_Comm_self is also not initialized with the "sessions" model, so even this approach might fail. ↩

[Wee-Free-Scot]

I agree with much of your complaint and share much of your frustration.

IMHO, it was a major step forward to include a definition of strong progress vs. weak progress and to state that MPI only requires weak progress.

IMHO, the best fix would be to require strong progress for RMA passive target operations, even if the MPI library only supports weak progress everywhere else.

Tangential to that would be a query procedure that permitted the user to ask whether strong progress is supported (to permit the user to code around the limitations of weak progress only when absolutely needed).

Your proposal of adding MPI_Progress_do (or similar) has been suggested many times before and never gets enough support. For me, it should not be needed; the fact that it is needed indicates a deeper problem.

---

Have you tried (and measured performance of) JeffH's suggestion of using MPI_Win_flush instead of MPI_win_sync? We will need an incontrovertible failure mode for an undeniable use-case.

[wgropp]

I agree with this (mostly): passive target RMA really doesn't make much sense without strong progress. The exception is the lockall case - a subset of the uses here would work with weak progress. But that's rather ugly and probably not worth it.

[csubich]

Your proposal of adding MPI_Progress_do (or similar) has been suggested many times before and never gets enough support. For me, it should not be needed; the fact that it is needed indicates a deeper problem.

The problem is that the specification desperately wants to assume strong progress for passive-target synchronization, IMO to the point that it gives a misleading impression about progress. Consider this bit from §12.7 (4.1):

An update by a put or accumulate operation to a public window copy becomes visible in the private copy in MPI process memory at the latest when an ensuing call to MPI_WIN_WAIT, MPI_WIN_FENCE, MPI_WIN_LOCK, MPI_WIN_LOCK_ALL, or MPI_WIN_SYNC is executed on that window by the window owner. In the RMA unified memory model, an update by a put or accumulate operation to a public window copy eventually becomes visible in the private copy in MPI process memory without additional RMA calls.

… which describes the deadlock at issue here. The thin wedge of correctness comes in the "update to a public window copy" part, which is only guaranteed (earlier) by:

If an RMA operation is completed at the origin by a call to MPI_WIN_UNLOCK or MPI_WIN_FLUSH (with rank=target), MPI_WIN_UNLOCK_ALL, or MPI_WIN_FLUSH_ALL, then the operation is completed at the target by that same call.

… which, when parsing very finely, does not give any guarantees that the origin's call to MPI_Win_flush must eventually return. (In contrast, U2 on p608 seems to contemplate a spinwait that polls a memory location via load, waiting for the value to change.)

The Rationale section on p616 starts to bring this problem to light, but on p617 it only warns about deadlock when using shared memory for loads:

The use of shared memory loads and/or stores for synchronizing purposes between MPI processes does not guarantee progress, and therefore a deadlock may occur if an MPI implementation does not provide strong progress, as shown in Example 12.13.

From the implementation's point of view, a local load/store from a window seems to be equivalent to a shared memory load/store, thus permitting the deadlock in this issue. For fence and PSCW window synchronizations, the synchronization primitives enforce completion-or-blocking, but passive-target synchronization doesn't have a natural way to do this.

The frustrating part is that I don't even really need proper, strong progress (although it'd be nice, certainly), just something to add to what would otherwise be busy-wait loops. The MPI_Iprobe call will serve me fine in practice because I'm not really dealing with a perversely adversarial outer program, but in turn I'm frustrated that while the call is necessary it's so ugly and fragile.

To summarize, my thesis statement is this: it is very surprising that a non-erroneous sequence of passive-target window operations, RMA calls, loads, and stores that always completes with strong progress can nonetheless deadlock with weak progress, absent explicit and seemingly extraneous calls to a progress-causing MPI routine from another chapter of the specification.

---

Have you tried (and measured performance of) JeffH's suggestion of using MPI_Win_flush instead of MPI_win_sync? We will need an incontrovertible failure mode for an undeniable use-case.

In my particular case with Intel-MPI, MPI_Win_flush is sufficient to ensure progress. Perusing the source of mpich (which I believe is the base for Intel-MPI), Win_flush specifically polls for progress if the polling interval has passed, so any use of Win_flush breaks the deadlock, and as far as I can tell it doesn't have any negative performance implications.

For OpenMPI (4.1.2a1), Win_flush(0,...) as suggested does break the deadlock, but using either the self-rank (1) or another rank (2+, for suitable nproc) does not. From OpenMPI's source there, it seems like the implementation doesn't (always) call the generic progress-doer, but rather it checks for messages in specific queues. It seems like I'd either need to call Win_flush_all or guess the rank that needs help with the fetch-and-op (trivial in the sample code, not necessarily possible in general).

At the moment, I can't give good performance measurements of the cost of the latter. On the cluster I'm using, Open-MPI seems to randomly and intermittently take 10-40ms to resolve the deadlock even with non-flush progress-inducers, so the impact of flush_all isn't easy to see. The system administrators there prefer (and have tuned) Intel-MPI, hence why I use it as default.

Besides that, however, Win_flush is not one of the functions that the 4.1 specification defines as "must make progress," since it is not a test function and may not block. From what I can tell, OpenMPI seems to treat the fetch-and-op as a request that the receiving process op-and-put, which coincidentally makes it something flush-able.

[jeffhammond]

I agree with this (mostly): passive target RMA really doesn't make much sense without strong progress. The exception is the lockall case - a subset of the uses here would work with weak progress. But that's rather ugly and probably not worth it.

NWChem has always worked without background progress. It just runs at half the speed because, on average, half the processes are waiting in Get while the other half are in DGEMM. Global Arrays in general does not deadlock in the absence of background progress although the performance can be terrible.

The Casper project provides a way to get background progress in RMA without changing an implementation. It has been challenging to add strong progress for some networks without intrusive changes that implementations aren't willing to do.

[devreal]

We talked about this at the January 18, 2024 WG meeting: the outcome was that it would be nice to have a procedure that ensures progress of incoming RMA operations in passive target without the overhead of iprobe (triggers all other parts of MPI) or flush (waits for outgoing operations to complete) and the ability to become a no-op if no progress is needed. This could be a simple addition to the standard within the context of RMA and should be fairly straightforward to implement. We just need a name for it :)

[Wee-Free-Scot]

This is a new semantic in MPI -- currently everything that ensures progress is required to ensure all types of progress, that is, progress for all of the pending MPI operations (equivalently, for all of the MPI decoupled activities) irrespective of the "type".

That is not an argument against the proposed addition, but it is a note of caution regarding how tricky it might be to write a good definition of what the new procedure is required to do and what it is permitted not to do.

[Wee-Free-Scot]

Example wording:
"Repeated calls to this procedure guarantee progress of MPI decoupled activities at the calling MPI process that are generated by enabled passive target operations targeting the calling MPI process from any origin process. In contrast to other MPI procedures that provide a guarantee of progress, this procedure provides no guarantee of progress for any other MPI operations."