Non-Blocking Sends, Eager Limits, and the Progress Problem

The reason to use a non-blocking send is to do arithmetic while the network works. The interface supports that intention: MPI_Isend and MPI_Irecv return a request handle immediately, and a later wait or test reports completion. What the interface cannot promise is that any work happens in the interval. A non-blocking call starts a transfer; whether the transfer advances while the caller is multiplying matrices depends on the implementation, the fabric, and whether the receiving rank ever enters the library.

That gap between initiation and actual progress is the subject here. It explains why an application can issue a perfect set of non-blocking operations and still see the sum of communication and computation rather than their maximum, and why “post the receive early” is advice about protocol design rather than about style.

Initiation and completion are separate events

MPI_Isend takes the same arguments as MPI_Send plus an address where the request handle is written. It returns after the library has recorded the operation, not after the data has left the process. MPI_Irecv does the same for a receive, and MPI_Wait blocks until the operation is complete, while MPI_Test reports whether it is complete without blocking. MPI_Waitall and MPI_Testall do the same for an array of requests.

The contract on the buffer is strict in both directions. Between initiation and completion, the application must not read or write a send buffer, because the library may still be copying from it. It must not read a receive buffer, because the data may be partially written. After completion the buffer is the application’s again, and the request handle is set to a null value. Waiting twice on the same request is an error, and so is using a handle after it has been recycled by a wait.

Completion of a send means the buffer is reusable. It does not mean the receiver has the data, and it does not mean the receiver has even posted a matching receive. This is the same distinction as in the blocking case, described in the matching rules, and it is the source of most buffer-reuse bugs.

#include <mpi.h>

/* Exchange boundary rows with the two neighbours, without blocking.
   sbuf/rcv must remain untouched until MPI_Waitall returns. */
void exchange_rows(const double *top, const double *bottom,
                   double *from_top, double *from_bottom,
                   int n, int up, int down, MPI_Comm comm)
{
    MPI_Request req[4];

    MPI_Irecv(from_top,    n, MPI_DOUBLE, up,   0, comm, &req[0]);
    MPI_Irecv(from_bottom, n, MPI_DOUBLE, down, 1, comm, &req[1]);
    MPI_Isend(top,         n, MPI_DOUBLE, up,   1, comm, &req[2]);
    MPI_Isend(bottom,      n, MPI_DOUBLE, down, 0, comm, &req[3]);

    /* Interior update could run here, provided it touches neither
       the send buffers nor the receive buffers. */

    MPI_Waitall(4, req, MPI_STATUSES_IGNORE);
}

The order of the four calls matters less than the fact that both receives are posted before the waits. An implementation may start the sends immediately, but the matching receives must exist somewhere before a rendezvous transfer can complete.

Who advances the protocol while the CPU works

A message-passing library is not a device driver with an interrupt handler in user space. It is a set of functions that the application calls. When the application is inside a compute loop, no library function is running, so the only progress that can happen is progress the hardware performs on its own.

Two mechanisms exist. The first is eager delivery: the sender’s adapter writes small messages directly into buffers that the receiver’s library posted in advance, and the receiver’s library matches them the next time it is called. This works without the application’s cooperation, but only for payloads that fit the pre-posted buffers. The second is a rendezvous: the sender transmits a request, and the transfer proceeds only when the receiver answers. The answer requires the receiver’s library to be running, which means the receiver must call into MPI.

Some implementations add a background thread that polls the adapter and answers rendezvous requests. Others use hardware that can complete a rendezvous without host involvement. Both are optimizations, not requirements, and the standard is explicit that progress is not guaranteed while the process is outside the library. A program that depends on asynchronous progress for correctness, rather than for speed, is not portable.

The practical consequence is that a rank which computes for a long time without calling MPI_Test can stall its neighbours. Those neighbours see a send that never completes, and if they are blocked in MPI_Wait, the job appears hung even though every rank is making progress in its own arithmetic. Inserting a test into the compute loop, or calling a non-blocking collective that forces a poll, restores progress at the cost of some overhead per call.

Eager buffers hide the cost until they do not

The eager threshold from the point-to-point article reappears here with a different consequence. Below the threshold, MPI_Isend typically copies into a pre-posted or pooled buffer and completes quickly; the wait returns almost immediately, and the overlap is real only in the sense that the copy was deferred. Above the threshold, the send stays pending until the receiver posts a matching receive and the rendezvous completes.

This produces a characteristic performance curve. For small messages, the time per exchange is flat and dominated by the fixed cost of the call. For large messages, the time grows with the payload and the wait dominates. The knee is the threshold, and it moves with the implementation, the fabric, and the number of ranks per node. Code tuned to sit just below the knee on one machine will sit above it on another.

There is a second effect at the receiver. Eager messages that arrive before a matching receive are held in the unexpected-message queue, which consumes memory per message and per byte. A program that issues many small sends to a rank that is slow to post receives can exhaust that queue. The failure is an allocation error inside the library, reported at a point unrelated to the code that caused it.

Double buffering and the lifetime of a send buffer

The most common non-blocking bug is reusing a buffer one iteration too early. A halo exchange issues sends from the boundary arrays, then the interior update runs, then the next iteration overwrites the boundary before the wait. If the send is still pending, the receiver gets a mixture of two iterations.

The fix is either to wait before the overwrite or to alternate between two sets of buffers. Double buffering costs one extra copy of the boundary data, which for a three-dimensional decomposition is small compared with the interior, but it also doubles the number of outstanding requests and can push the message rate past what the adapter handles well. The choice depends on whether the wait is already on the critical path.

A subtler lifetime issue affects receives. A non-blocking receive writes into the application’s buffer when the message arrives, which may be long after the call. If the buffer is a local variable in a function that returns before the wait, the library writes into a dead stack frame. The request handle keeps the operation alive, but it does not keep the buffer alive. This is why receive buffers in non-blocking code are usually allocated by the caller and passed down, not created on the callee’s stack.

Persistent requests and the setup cost

A halo exchange repeats the same pattern every iteration: same partners, same tags, same counts, different data. Rebuilding the request each time costs a few hundred nanoseconds to a few microseconds per call, which is significant when the payload is small. Persistent requests separate the pattern from the data. MPI_Send_init and MPI_Recv_init build a request once, and MPI_Start or MPI_Startall activates it; the buffer addresses are fixed at init time, so the data must live at the same address each iteration.

The saving is real but bounded. It removes the argument-checking and request-allocation cost, not the network latency, so it matters most for codes with many small messages. It also removes flexibility: changing the partner list or the count requires freeing and rebuilding the requests.

MPI 4 added partitioned communication, which divides a single message into chunks that can be marked ready independently, allowing a producer to start a transfer before the whole buffer is filled. The mechanism targets exactly the case where a rank computes a large message in pieces and would otherwise wait for all of it. Its availability depends on the implementation, and it does not remove the progress requirement: the receiver still has to enter the library for the chunks to be consumed.

What overlap can and cannot buy

If computation takes C and communication takes T, perfect overlap gives max(C, T) and no overlap gives C + T. The speedup from overlap is therefore bounded by (C + T) / max(C, T), which is at most two when the two are equal and close to one when either dominates. Overlap is not a way to make communication free; it is a way to stop paying for it twice.

Three conditions must hold for the bound to be approached. The library must make progress while the application computes, which usually means the messages are small enough to be eager or the implementation has a progress thread. The compute phase must not touch the communication buffers. And the arithmetic must be long enough to cover the transfer, which for a large message on a fast fabric can be a substantial amount of work. When the third condition fails, the wait is short and the overlap was never needed; when the first fails, the wait is long and the overlap never happened. The strong scaling curve is where the difference becomes visible, because at large process counts the per-rank arithmetic shrinks while the per-message latency does not.