Message Matching: Tags, Ordering, and the Deadlock in Naive Exchange

The first parallel program most people write is a ring: every rank sends its data to the next rank and receives from the previous one. It is also the first program that hangs, and the hang is instructive because it depends on how much data is being sent. The same source code that works for a few hundred bytes stalls forever for a few megabytes, on the same machine, with the same rank count.

That size dependence is not a bug in any implementation. It follows from the matching rules and from the fact that a send is allowed to wait for its receive.

The envelope that matching actually uses

A message carries two kinds of information. The payload is the typed sequence of bytes described by a buffer address, a count, and a datatype. The envelope is everything else: the communicator, the source rank, and the tag. Matching inspects the envelope only. A receive with a count of ten integers will happily match a send of a thousand integers; the mismatch is discovered afterwards, when the data is copied and the receive buffer turns out to be too small.

The tag is an integer chosen by the sender, with a guaranteed range. The standard requires that MPI_TAG_UB be at least 32767, and implementations commonly allow considerably more, but a program that hard-codes a tag above that floor is not portable. Tags are not namespaced by anything except the communicator, which is why private communicators matter: two libraries sharing one communicator and a small tag space will eventually collide.

The source argument can be a specific rank or a wildcard, and the tag argument likewise. When either is a wildcard, the receive takes the first message in its queue that matches the remaining fields, and the status object reports what was actually received. MPI_Get_count then recovers the payload length from the status, which is the only reliable way to learn it when the sender chose the size.

Ordering is per source and tag, not global

The standard’s non-overtaking rule is narrower than “messages arrive in order”. It says that if a sender sends two messages that both match the same receive, the receive cannot match the second while the first is still pending. The same applies on the receive side: if two receives both match the same message, the first one posted gets it. This gives a per-pair, per-tag ordering guarantee and nothing more. Messages with different tags, or from different sources, may be delivered in any order, and a program that depends on cross-tag arrival order is relying on an accident.

The rule exists so that a stream of messages between two ranks can be interpreted as a sequence. A common pattern is to send a header with tag 1 and a body with tag 2; the non-overtaking rule does not order those two against each other, so the body can arrive first. If the receiver needs the header before it can size the body buffer, the correct construction is a single message with a derived datatype, or a probe followed by a sized receive, not two messages with different tags.

Wildcard receives interact badly with the ordering rule in a subtler way. A receive with MPI_ANY_SOURCE can match a message that was intended for a different part of the program, and once matched, the message is consumed. There is no way to put it back. Code that mixes a wildcard receive with specific receives on the same communicator is correct only if the wildcard is posted when no other message could be in flight, which is a global property that is hard to maintain as a program grows.

Why the same code deadlocks above a size threshold

A standard send, MPI_Send, is specified to return when the send buffer may be reused. How it achieves that is left to the implementation, and there are two strategies.

The eager strategy copies the payload into a buffer owned by the receiving side and returns immediately. It requires the receiver to have posted receive buffers, or the implementation to keep a pool of unexpected-message buffers. The rendezvous strategy sends a small request containing the envelope and the length, waits for the receiver to answer that it has a matching receive and a large enough buffer, and only then streams the data. The first has lower latency for small messages; the second avoids buffering arbitrary amounts of data.

Implementations choose between them by size, using a threshold that is a runtime parameter. Below it, MPI_Send behaves eagerly and returns without a receiver. Above it, MPI_Send blocks until the matching receive is posted. The threshold is not part of the standard and is not visible in portable code, which is exactly why the ring program appears to work and then stops working when the payload grows.

#include <mpi.h>

/* Safe ring exchange: each rank sends right and receives from left
   in one call, so the receive is posted before the send can block. */
void ring_exchange(const double *sendbuf, double *recvbuf, int count,
                   MPI_Comm comm)
{
    int rank, size;
    MPI_Comm_rank(comm, &rank);
    MPI_Comm_size(comm, &size);

    int right = (rank + 1) % size;
    int left  = (rank - 1 + size) % size;

    MPI_Sendrecv(sendbuf, count, MPI_DOUBLE, right, 0,
                 recvbuf, count, MPI_DOUBLE, left,  0,
                 comm, MPI_STATUS_IGNORE);
}

MPI_Sendrecv is the standard’s answer to this pattern. It is a single call that performs a send and a receive, and the implementation is free to post the receive first, so it cannot deadlock against itself. The naive version, a blocking send followed by a blocking receive, deadlocks once the payload exceeds the eager threshold: every rank is waiting for a receive that no rank can reach.

Two other repairs exist and both are worse. Ordering the operations by rank parity, so that even ranks send first and odd ranks receive first, works for a ring but requires reasoning about the communication graph, and the reasoning breaks when the graph changes. Buffered sends, MPI_Bsend, move the problem into a user-supplied buffer whose size must be chosen in advance; too small and the call fails, too large and memory is wasted on every rank. The non-blocking interface described in the article on progress and overlap is the general solution, because it separates initiation from completion.

What a send completion actually promises

The four send modes differ in when the buffer becomes reusable, and confusing them is a common source of corruption.

A standard send promises only that the buffer can be reused. A buffered send promises the same, having copied the data into the caller’s buffer, which is why the buffer must remain valid and why the call can fail with an out-of-buffer error. A synchronous send, MPI_Ssend, completes only when the matching receive has begun, which makes it a synchronization point and a useful debugging tool: replacing every standard send with a synchronous one exposes reliance on buffering. A ready send, MPI_Rsend, asserts that the matching receive is already posted; if it is not, the program is erroneous and the implementation is not required to detect it.

None of these modes changes the matching rules. A ready send that matches nothing does not become an ordinary send; it becomes undefined behaviour. The mode is a promise from the programmer to the library, not a hint.

Truncation, probing, and messages that never arrive

A receive whose buffer is smaller than the incoming payload is an error. The implementation may report it through the status and the return code, and in some cases it delivers a truncated message; either way, the data is not what the sender intended. The portable approach when the size is unknown is MPI_Probe, which matches a message without consuming it and fills a status from which MPI_Get_count yields the length, followed by a receive of exactly that size. The probe and the receive must use the same envelope, or a different message can be matched in between.

An unmatched send does not fail. It sits in the receiver’s unexpected-message queue, consuming memory, until a matching receive is posted or the job ends. A program that leaks messages this way grows slowly and then dies with an allocation failure far from the bug. Some implementations expose the queue depth as a debugging aid, but portable code cannot inspect it, so the practical defence is to keep the set of tags small and to make every send have exactly one statically obvious receive.

The reverse case, a receive with no send, blocks forever. Nothing in the interface distinguishes “the sender is slow” from “the sender will never come”, which is why job launchers treat a stalled rank as a failure after a timeout rather than waiting indefinitely. Timeouts are a launcher policy, not a message-passing semantic.