Case Study 1: The Halo Exchange That Hangs (Sometimes)

"It worked on the test grid. That is the most dangerous sentence in message passing."

Executive Summary

A colleague hands you a distributed heat solver they wrote from the Chapter 24 code and the Chapter 34 pattern. It runs beautifully on their laptop with a $100 \times 100$ test grid, and then hangs — no error, no output, just a stalled job that the scheduler eventually kills — the moment they run it "for real" at $2000 \times 2000$ on the cluster. They are convinced the cluster is broken. It is not. This study is the diagnosis, and it is a tour of the two most common ways a halo exchange goes wrong: a deadlock that hides behind small-message buffering, and a subtler ordering bug that survives the deadlock fix and silently corrupts the physics. You will read their code, reproduce the failure by reasoning about it, find both bugs, apply the mpi_sendrecv cure from §34.2, and verify the repaired solver against the serial reference. Nothing about the cluster is wrong; the bugs were latent in the code all along, and the larger problem merely exposed the first while the second was always producing quietly wrong answers.

Skills applied: the mpi_send/mpi_recv argument order and the standard-mode deadlock (§34.2); the eager-vs-rendezvous buffering distinction (§34.2, ⚠️ pitfall); mpi_sendrecv and MPI_PROC_NULL (§34.4); the exchange-then-update ordering of a halo step (§34.4); verifying a distributed result against a serial reference (Project Checkpoint, honesty note).

Background

The colleague's solver uses the exact 1D decomposition of the chapter: the plate is cut into horizontal strips, each process stores u(nx, 0:nloc+1) with ghost rows at 0 and nloc+1, and each step exchanges halos and then applies the five-point stencil. The physics kernel is a faithful copy of Chapter 24 — that part is correct. The trouble is entirely in the two routines around it: how they exchange, and when. Here is the exchange they wrote:

! ------- the colleague's halo exchange (BROKEN) -------
subroutine exchange_halos(u, nx, nloc, up, down)
  use mpi
  use, intrinsic :: iso_fortran_env, only: dp => real64
  real(dp), intent(inout) :: u(nx, 0:nloc+1)
  integer,  intent(in)    :: nx, nloc, up, down
  integer :: ierr, status(MPI_STATUS_SIZE)

  if (up /= MPI_PROC_NULL) then
    call mpi_send(u(:,1), nx, MPI_DOUBLE_PRECISION, up, 0, MPI_COMM_WORLD, ierr)   ! send first...
    call mpi_recv(u(:,0), nx, MPI_DOUBLE_PRECISION, up, 0, MPI_COMM_WORLD, status, ierr)
  end if
  if (down /= MPI_PROC_NULL) then
    call mpi_send(u(:,nloc),   nx, MPI_DOUBLE_PRECISION, down, 0, MPI_COMM_WORLD, ierr)
    call mpi_recv(u(:,nloc+1), nx, MPI_DOUBLE_PRECISION, down, 0, MPI_COMM_WORLD, status, ierr)
  end if
end subroutine exchange_halos

And here is their time loop:

do step = 1, nsteps
  call apply_stencil(u, u_new, nx, nloc, r)   ! update FIRST...
  u(:,1:nloc) = u_new(:,1:nloc)
  call exchange_halos(u, nx, nloc, up, down)  ! ...then exchange
end do

Two files, two bugs, one of which hangs and one of which lies.

Phase 1 — Reproduce by Reasoning

We do not need the cluster to see the failure; we need only trace the exchange. Every process runs the same code, so consider what all of them do at the same instant on the first exchange. Each process with an "up" neighbour calls mpi_send to that neighbour — and then waits inside that send for the neighbour to receive. But the neighbour, running the identical code, is also sitting in its own first mpi_send (to its up neighbour), not in a receive. So process 5 waits for process 4 to receive, but process 4 is busy waiting for process 3, which is waiting for process 2, and so on. Nobody is receiving; everybody is sending. That is a circular wait — a deadlock.

So why does it ever work? Because mpi_send is standard mode, which is permitted (but not required) to copy a small message into an internal buffer and return immediately, before any matching receive is posted. At $100 \times 100$, a row is 100 doubles — 800 bytes — comfortably under the implementation's "eager" threshold, so every mpi_send buffers and returns, all the receives then run, and the code works. At $2000 \times 2000$, a row is 2000 doubles — 16 KB — above the threshold, so mpi_send switches to the "rendezvous" protocol and blocks until the matching receive appears. It never does, and the job hangs. The bug was present at $100 \times 100$ too; it was simply masked. Correctness must never depend on MPI choosing to buffer for you.

The tell: a program that works below some problem size and hangs above it, with no error message, is almost always a standard-mode send/receive deadlock crossing the eager threshold.

Phase 2 — Fix the Deadlock with mpi_sendrecv

The deadlock cure from §34.2 is to stop doing a blind send-then-receive and instead use the single call MPI provides for exactly this exchange, which is guaranteed never to deadlock regardless of message size:

! ------- the corrected exchange (deadlock-free) -------
subroutine exchange_halos(u, nx, nloc, up, down)
  use mpi
  use, intrinsic :: iso_fortran_env, only: dp => real64
  real(dp), intent(inout) :: u(nx, 0:nloc+1)
  integer,  intent(in)    :: nx, nloc, up, down
  integer :: ierr, status(MPI_STATUS_SIZE)

  call mpi_sendrecv(u(:,1),      nx, MPI_DOUBLE_PRECISION, up,   0,   &   ! send top row up,
                    u(:,0),      nx, MPI_DOUBLE_PRECISION, up,   0,   &   ! recv upper ghost from up
                    MPI_COMM_WORLD, status, ierr)
  call mpi_sendrecv(u(:,nloc),   nx, MPI_DOUBLE_PRECISION, down, 0,   &   ! send bottom row down,
                    u(:,nloc+1), nx, MPI_DOUBLE_PRECISION, down, 0,   &   ! recv lower ghost from down
                    MPI_COMM_WORLD, status, ierr)
end subroutine exchange_halos

Two improvements at once. First, mpi_sendrecv posts the send and the receive together, so there is no window in which everyone is stuck sending — the classic shift pattern completes and never hangs. Second, we dropped the if (up /= MPI_PROC_NULL) guards entirely: a send or receive to MPI_PROC_NULL is already a no-op, so passing the null rank straight through is correct and leaves the physical-edge ghost rows untouched. The corrected routine is shorter than the broken one and cannot deadlock at any grid size. Run it at $2000 \times 2000$ and the hang is gone.

Phase 3 — The Second Bug: Exchanging After the Update

With the deadlock fixed, the colleague reports the solver now runs at full size — but the temperatures near the strip boundaries are subtly wrong, and worse each step. This is the dangerous bug, because it produces no error at all; it just computes the wrong physics. Look again at their time loop:

call apply_stencil(u, u_new, nx, nloc, r)   ! update uses the CURRENT ghost rows...
u(:,1:nloc) = u_new(:,1:nloc)
call exchange_halos(u, nx, nloc, up, down)  ! ...which are only refreshed AFTER

The update runs before the halo exchange. On the very first step the ghost rows still hold their initial values, so a process updates its edge rows from stale neighbour data; the exchange then refreshes the ghosts, but the damage is already in u. Each step, every process's top and bottom owned rows are computed from neighbour values that are one step out of date, and because the error feeds back into the next step's exchange, it accumulates. The interior rows (which read only owned data) are fine; the edge rows drift, and the drift spreads inward. The fix is to reverse the order — exchange first, then update — so that when the stencil reaches an edge row, the ghost beside it already holds the neighbour's current value:

do step = 1, nsteps
  call exchange_halos(u, nx, nloc, up, down)  ! refresh ghosts FIRST...
  call apply_stencil(u, u_new, nx, nloc, r)   ! ...so the update reads current neighbour rows
  u(:,1:nloc) = u_new(:,1:nloc)
end do

This is the ordering the Project Checkpoint uses, and it is not a stylistic preference — it is the difference between a correct solver and one that silently lags its own boundaries.

Phase 4 — Verify Against the Serial Reference

A distributed result you cannot check is a result you cannot trust, and the check is built into the design: because domain decomposition changes only how the work is divided, a correct MPI solver must print the identical field a single-process run prints. So we run the repaired solver on the Project Checkpoint's small problem — the $5 \times 6$ plate, top edge 100, $r = 0.2$, three steps — on 1 process and on 2, and compare. Both must produce:

after step 3 (either -np 1 or -np 2, identical):
   100.0  100.0  100.0  100.0  100.0
     0.0   32.8   38.4   32.8    0.0
     0.0    7.2    8.8    7.2    0.0
     0.0    0.8    0.8    0.8    0.0
     0.0    0.0    0.0    0.0    0.0
     0.0    0.0    0.0    0.0    0.0

The 0.8 values in the fourth row are the acid test: they exist only if the halo carried the third row's 4.0s across the process boundary before the update that needed them. With the broken (update-first) ordering, those cells would read a stale zero ghost and the fourth row would stay cold — a visible, checkable symptom. With both bugs fixed, -np 1 and -np 2 agree to the last digit, which is exactly the guarantee a correct decomposition must satisfy. (Had we compared floating-point results across different reductions or summation orders we would have to allow tiny rounding differences; here the arithmetic per cell is identical regardless of process count, so the agreement is exact.)

Phase 5 — A Checklist Born From the Bugs

Both failures were avoidable, and each teaches a rule worth keeping on a card by the keyboard:

None of these is exotic; all five are the everyday failure modes of message passing, and a distributed code that survives them is most of a working distributed code.

Discussion Questions

1. The deadlock "passed" every test the colleague ran because their tests were small. Design a test for a halo exchange that would have caught the deadlock on a laptop, without a cluster and without a large grid. (Hint: what makes mpi_send block is the message size relative to a threshold — can you force rendezvous mode?)
2. The update-first ordering bug corrupted only the edge rows at first. Explain why the interior rows were correct on step 1 but not on step 10, and connect this to why the bug is harder to catch than the deadlock.
3. The verification relied on -np 1 and -np 2 producing bit-identical output. For this explicit stencil that is legitimate. Name a kind of parallel computation for which you would not expect bit-identical results across process counts, and say what tolerance you would check instead.

Your Turn: Extensions

• Option A. Take the broken exchange_halos and, without switching to mpi_sendrecv, fix the deadlock by ordering the calls (even ranks send-then-receive, odd ranks receive-then-send). Verify it produces the same field. Which fix do you find clearer, and why does the book prefer mpi_sendrecv?
• Option B. Add a defensive check to the solver: after the exchange, have each process verify that its ghost rows are not all still their initial value on step 1 (a cheap "did the halo actually arrive?" assertion). What would this have printed under the update-first bug?
• Option C. Reproduce the eager/rendezvous transition empirically (conceptually — do not present a timing as measured): reason about, and write down, the row length at which a 8-byte-per-element message crosses a typical 16 KB eager threshold. How many grid columns is that, and does it match the colleague's 100-vs-2000 experience?

Key Takeaways

• A program that works small and hangs large is a standard-mode send/receive deadlock crossing the eager buffer threshold. The fix is mpi_sendrecv; the lesson is never to rely on buffering for correctness.
• Exchange halos before the update, not after. Update-first reads stale ghosts, corrupting edge rows in a way that compounds and produces no error — the most dangerous kind of MPI bug.
• MPI_PROC_NULL replaces boundary if-guards, making the exchange shorter and less error-prone.
• Verify a distributed solver against the serial reference. A correct domain decomposition must print the identical field on any process count; that bit-for-bit agreement is the check that the communication is right.