greatitself.
Continue
advanced29 min studyLesson 569 in Engineering

Point-to-point pipeline deadlocks

Trace communication matching, wait cycles, collective order, and buffer ownership instead of assuming asynchronous calls guarantee progress.

Before you begin
On this page

The question for today

What you’ll understand

  • Build a wait-for trace for a small communication cycle.
  • Check message identity, group, order, shape, and participation.
  • Separate progress guarantees from bandwidth bounds and timeout detection.

A pipeline can hang while every GPU is healthy if its ranks wait for communication that the schedule never posts. A wrong peer, reversed collective order, missing rank, or reused buffer can produce different failures with similar symptoms. This lesson scopes concrete API rules to PyTorch 2.8 distributed communication, while using explicit blocking assumptions for the hand traces. Nonblocking initiation enables some legal schedules; it is not a universal deadlock cure.

Match both endpoints of every logical message

A tensor transfer needs a sender, receiver, process group, direction, compatible shape and dtype, and the intended microbatch or virtual-boundary identity. Some backends match by communication order rather than supporting every tagging scheme, so source-level identifiers alone do not guarantee matching. Log the schedule’s logical identity even when the backend protocol uses ordered operations. Two equal-shaped messages swapped between microbatches can complete transport successfully while corrupting the gradient computation; progress and numerical correctness require separate checks.

PyTorch 2.8 documents that batched isend/irecv ordering must match the remote endpoint’s operations. With NCCL, set the intended current CUDA device and respect the special participation rule if the batch is the first collective call for its group. A subgroup-only pattern that is legal later is not automatically legal during that initialization case. When several process groups or collectives interact, maintain the required consistent creation and execution order across ranks; a local code path can otherwise wait for a different collective than its peer entered.

R0→R1→R2→R0R_0\to R_1\to R_2\to R_0
An arrow here means a rank is blocked waiting for an action that the next rank cannot post until its own wait completes. Under those explicit no-other-progress assumptions, the directed cycle has no enabled operation. A cycle in an arbitrary communication graph alone does not prove deadlock.↔ Scroll wide equations horizontally.

A request object does not remove dependencies

If every rank performs a blocking receive before posting the send that would satisfy another rank, the schedule can have no first enabled action. Posting nonblocking operations with the required matching order can break that artificial dependency, but immediately waiting on a send before posting its needed receive can recreate a cycle. Draw which action each wait requires, including collectives and CUDA-stream dependencies. The relevant graph is the wait-for graph of the actual implementation, not merely the model’s forward dependency graph.

Keep send storage valid and unmodified until the documented completion conditions permit reuse, and do not consume a receive destination before it is ready on the consumer’s execution stream. Host return and device completion differ for CUDA operations. An implementation can therefore appear to make progress while racing over a buffer. Capture request completion, stream ordering, and buffer ownership in the trace alongside message matching. Correctness requires those lifetimes even if a communication benchmark reports excellent bandwidth.

Tpayload≥∑jBjβT_{\mathrm{payload}}\geq\frac{\sum_j B_j}{\beta}
For payloads B_j bytes that must all traverse one assumed serial bottleneck of effective bandwidth beta bytes per second, this is a seconds lower bound after a valid progressing schedule exists. It cannot bound a deadlock’s duration or guarantee that requests are correctly matched.↔ Scroll wide equations horizontally.

Diagnose missing progress with bounded evidence

Collect rank-local logs with operation sequence, peer and group identity, tensor metadata, and completion events. A timeout identifies failure to meet a progress bound; it does not repair a bad schedule or prove which rank caused it. Distinguish a rank that exited, a missing participant, a mismatched collective, and a legal but overloaded transfer path. Reproduce with two or three ranks and small deterministic tensors before adding full training state. A recovery strategy must use the runtime’s supported fault behavior rather than assuming an interrupted communicator is immediately reusable.

The modular lab visualizes only a three-node cycle. Reset, set modulus to 3 and additive step to 1, predict the return point, then Step three times. The residues return to zero after visiting three positions. This arithmetic is not a wait-for graph execution: it has no blocked ranks, posted requests, tensor matching, collectives, or failure model. Use the separate hand trace to explain why a particular cycle has no enabled action, rather than treating any cyclic topology as a deadlock.

Work it through

Three receives with no first send

Three ranks first execute blocking receives in a cycle: rank zero waits for one, one waits for two, and two waits for zero. Each posts its corresponding send only after its receive returns. Assume no other work can supply these messages. After redesign, suppose three four-MiB messages share one serial four-GiB/s bottleneck.

  1. The trace has three blocked ranks and three wait edges forming a directed cycle. No rank has reached its send, so no required receive can complete under the stated assumptions. There is no finite bandwidth-derived completion time for this schedule.

  2. Redesign the initiation and wait order so matching sends and receives can be posted according to the backend’s contract, then wait only after the needed peers can participate. This requires checking endpoint order and lifetime, not merely renaming calls asynchronous.

  3. For the separate valid-progress bandwidth model, payload totals 12 MiB. Its movement lower bound is 12/4096 seconds, approximately 2.930 milliseconds, before startup, contention, and synchronization costs.

The result

A dependency repair establishes the possibility of progress; a transfer-volume calculation applies only after that repair.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

A cycle is topology, not a progress proof

Reset, set modulus m = 3 and additive step a = 1, predict the period, then Step three times to return to zero. This modular orbit illustrates cyclic node labels only; it does not execute blocking communication or detect pipeline deadlocks.

A cycle is topology, not a progress proofAddition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA deadlock argument needs blocked-action dependencies and no enabled progress, not merely a cyclic connection diagram.

Pause & reason

Check your understanding

Why can replacing blocking sends with isend still leave a pipeline deadlocked?

Your turn

Try it yourself

Two ranks each post a nonblocking send, immediately wait for it, and only then post their receive. Explain why progress is not guaranteed by that structure. Separately, compute the movement lower bound for one eight-MiB payload over an assumed eight-GiB/s bottleneck after a valid matching schedule exists.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Do not assume unlimited eager buffering or a receive that has not been posted. Keep the correctness argument separate from byte accounting.

Compare with the solution

Without a backend guarantee that both sends complete without posted matching receives, each wait can prevent the peer from reaching its receive. Post and order operations according to the supported communication contract before dependent waits. For the separate progressing payload model, 8/8192 seconds is approximately 0.977 milliseconds. That lower bound does not promise completion of the original blocked schedule or waive buffer-lifetime requirements.

Keep the idea

Take it with you

  • Message matching includes logical identity, group, endpoint order, and tensor metadata.
  • Nonblocking calls still require a dependency-respecting initiation and wait order.
  • Timeouts and bandwidth estimates answer different questions from a progress proof.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.