Messages, Costs, and
the Bugs That Pass
Six weeks of MPI in eleven screens. Every section is a mechanism you were taught, with the question the lecture asked before it showed you the answer. Commit before you reveal.
The module in one picture
Three lanes. Everything in the module lives in one of them. Click a node to go there.
SPMD and the six arguments
One source file, p copies. The only thing that differs between them is one integer.
MPI_Init(&argc, &argv); // nothing works before MPI_Comm_size(MPI_COMM_WORLD, &numProcs); // how many of us? MPI_Comm_rank(MPI_COMM_WORLD, &myRank); // which one am I? // ... the work. Every if (myRank == 0) is you breaking the symmetry on purpose. MPI_Finalize(); // nothing works after
MPI_Send(buffer, count, type, dest, tag, comm);
MPI_Recv(buffer, count, type, source, tag, comm, &status);
// count is ITEMS, not bytes. Five of the six must agree on both ends.
Three things the receiver does not know
- How long. "Greetings from 7 of 10" and "from 10 of 10" differ.
MPI_ProbethenMPI_Get_count: ask before you accept. - Where the string ends.
msg.size() + 1— the null terminator travels or rank 0 prints whatever was next in memory. Fine on a laptop, garbage on Cardinal. - When it starts. Ten clocks. Barrier, then start; barrier, then stop. Without the fence you time launch skew and call it your algorithm.
for (q = 1; q < p; q++) MPI_Recv(…, q, …). Rank 9 finishes first. What happens? The loop names its source, so rank 0 waits for rank 1 even if rank 9 is ready. Nothing is lost; the library holds it. This is the linear merge: p − 1 arrivals, one after another. Hold the thought — it is why collectives exist, and why MPI_ANY_SOURCE looks like a tempting fix (it is not).
Timing across ranks: the protocol in one sentence
The slowest rank is the program. Max across ranks within a run, min across runs. Rank 0's clock is only honest because the closing barrier makes it wait for the slowest; MPI_Reduce(…, MPI_MAX, …) says the same thing explicitly. Output: no order is promised; print from rank 0 or tag each line with its rank. Input: one rank reads, then MPI_Bcast.
The remainder, three times
The same bug came back every week with a different face. n / p in integer arithmetic throws away n % p.
| Week | Where | What it looked like | Which p found it |
|---|---|---|---|
| 4 | Trapezoid: local_n = n / p, Trap() takes a long | 41.6667 at every p; wrong in the 7th decimal | 3, 6, 7, 9 — not 1, 2, 4, 5, 8, 10 |
| 5 | Vector sum: mySize = N / p | The last two elements of z are 0 | 3 (20 = 3·6 + 2) |
| 7 | Row-then-column sum on a 4-wide grid | Ranks in short columns get row 0's sum only | 5, 6, 7, 9 — not 4, 8, 12 |
Explore: naive split vs the fix
Naive: every rank takes n / p. Hatched = never owned.
Fixed: base = n / p, extra = n % p, the first extra ranks take one more; first = r·base + min(r, extra).
Powers of two hide remainders. A test set that finds this bug has to include a p that does not divide the work — 3 and 7 are in every lab checklist for exactly this reason. Honest alternative to the fix: refuse and MPI_Abort when n % p != 0. Silently truncating is the only wrong choice.
Collectives and their rules
You designed MPI_Reduce before you saw it. Seven arguments. Then Bcast was Reduce backwards, Gather was Scatter backwards.
| Call | Before | After |
|---|---|---|
| Bcast | root: A | everyone: A |
| Scatter(v) | root: A B C D | rank r: block r |
| Gather(v) | rank r: block r | root: A B C D |
| Allgather | rank r: block r | everyone: A B C D |
| Reduce | rank r: a value | root: the sum |
| Allreduce | rank r: a value | everyone: the sum |
| Alltoall | rank r: p blocks | rank r: block r from everyone |
The rules that bite
- Every rank calls it — root included, no
ifaround it. A rank that skips a collective leaves everyone else waiting forever. - Same order on every rank. Two collectives in different orders on different ranks is a hang.
- No tags. Nothing to match.
- Returns when my part is done. A collective is not a barrier.
sendcountis per rank, not the total. Blocks land in rank order atr × count.
Scatterv: counts and displs
20 ÷ 3 is not whole. One sendcount cannot say 7, 7, 6. Two arrays can, and every rank can compute both itself — no message needed.
ANY_SOURCE: the slot and the sender disagree
Rank 0's loop decides the slot (z[i·mySize] on iteration i). MPI_ANY_SOURCE decides the sender (whoever arrives first). They agree only when workers happen to answer in rank order. Press the button to see a run.
p = 4, three workers reply …
Four runs right, two wrong, same binary. The intermittent bug is the worse one: it passes the demo and ships. Two correct fixes: receive from rank r by name into displs[r], or keep ANY_SOURCE but read status.MPI_SOURCE and compute the slot from it.
What a message costs
Week 4 needed one number. Week 5 needed two. Week 6 added a third.
| t(m) ≈ α + m·β | α ≈ 2 µs start-up, any size · β ≈ 0.05 ns/B (20 GB/s) · crossover α/β ≈ 40 KB: below it count messages, above it count bytes |
| Tₚ ≈ (n/p)·t_f + C(p)·t_m | t_f ≈ 1 ns per trapezoid · C(p) = p − 1 linear, ⌈log₂ p⌉ tree · one message costs about 2,000 trapezoids |
| t_pack(m) ≈ α + m·β + 2m·γ | γ ≈ 0.1 ns/B, one memory copy out of cache (10 GB/s) · pack pays it twice; a derived type pays it zero, one or two times — R04 measured which |
Planning numbers, not measurements. When your data disagrees with them, naming what is missing is the Diagnosis.
A tree saves messages, not bytes
p − 1 workers each send m bytes to rank 0. Loop: p − 1 sequential receives. Tree: ⌈log₂ p⌉ rounds. Either way, (p − 1)·m bytes arrive at the root's one link.
| α terms | bytes at root | time | |
|---|---|---|---|
| loop | |||
| tree |
Small messages: count the α's, and the tree wins by about (p−1)/log₂p. Large messages: count the bytes at the busiest link, and the two nearly tie. The model assumes the loop's α's wait in line one after another — R03 was the lab that asked whether they really do.
When does splitting pay?
Break-even needs n > p·t_m/t_f ≈ 2,000·p. The 2018 code used n = 1,024: a correctness demo that could never have shown a speedup.
Describe the data, don't copy it
A type is a list of (type, byte offset). Size is what travels. Extent is where the next one starts.
Padding: never add up sizes
Ask the compiler: offsetof(T, field), or subtract MPI_Get_address results. The guessed-offset version {0, 4, 12} describes bytes 0–19 of a 24-byte record; the top half of b never travels, and b arrives as 0.0 — CHECK ok at p = 1, wrong at every p ≥ 2.
MPI_Type_vector: count, blocklength, stride
An 8 × 8 matrix stored by rows. Describe where the elements are relative to the buffer you pass. Pass &A[0][3] for column 3, not A.
The receiver may take 8 plain MPI_DOUBLE: MPI matches the type signature (8 doubles), not the layout. Resize when you Scatter with it: a vector's extent spans first-to-last element, so rank 1 would start past the end of x. MPI_Type_create_resized(vec, 0, sizeof(double), …) makes rank r start at x[r] — the cyclic deal. It does not fix the remainder.
reduce(world, x, s, std::plus<double>(), 0) and broadcast(world, in, 0) where in is a struct with serialize() but no BOOST_IS_MPI_DATATYPE. Which of the two is more than one MPI call underneath? Easy for you is not always fast for the machine. A builtin with a builtin op maps straight to the MPI call. A serialize()-only class is packed: size, then bytes, plus a copy on each side — the same two-step you wrote by hand in Week 5. Add BOOST_IS_MPI_DATATYPE to a fixed-layout struct and Boost builds the derived type for you: one Bcast. You did it the hard way so you can read what the easy way costs.
Communicators and grids
A communicator is a group and a context. A collective is defined over a communicator, not over the program.
MPI_Comm_split: color picks the group, key orders it
int color = rank / COLS; // my row int key = rank; // order inside the row; ties break by old rank MPI_Comm_split(MPI_COMM_WORLD, color, key, &row); // collective on WORLD: every rank calls it
Opting out, and the thing you must never free
A rank that wants no new communicator still calls Split — with color = MPI_UNDEFINED. It gets MPI_COMM_NULL. Test for it before using or freeing. (The prime-group example at p = 8: ranks 0, 1, 4, 6 freed COMM_NULL and aborted with MPI_ERR_COMM.)
Context: why a library dups WORLD
Same ranks, same tag, sent first on a dup of WORLD — and a wildcard receive on WORLD cannot see it. A wildcard matches source and tag, never communicator. Rank arithmetic on WORLD can't give you that, and every collective would still involve everyone.
Grids: ask for neighbours, not rank ± 1
MPI_Cart_shift(line, 0, +1, &left, &right); // source, dest MPI_Sendrecv(&me, 1, MPI_INT, right, 0, &got, 1, MPI_INT, left, 0, line, &st); // open line, rank 0: left = MPI_PROC_NULL. A send to it does nothing; a receive from it completes at once.
No if at the edge. MPI_Dims_create picks a balanced shape (8 → 2×2×2, 6 → 3×2×1); after Cart_create with reorder = 1, ask the Cartesian communicator for your rank, not WORLD. coords[2] for a 3-D grid: Open MPI quietly fills two, MPICH refuses — "it works on my laptop" is a statement about one implementation.
Strips or blocks? Count the α's
Blocks send 2/√p of the bytes and twice the messages. A topology is a bet that you are above the knee at n = α/(4β) ≈ 10⁴.
Hang, wrong, crash, silent
There are only four things a broken MPI program can look like, and each has a cheap test. A hang says it failed. A crash says where. The other two say nothing unless you test for them.
Sort the bugs you met
Click a symptom for each. Instant feedback.
Eager or rendezvous: the hang that appears at scale
Two ranks. Each does MPI_Send to the other, then MPI_Recv. MPI_Send may return once the bytes are copied into a library buffer (eager) or only once the matching receive is posted (rendezvous). The library chooses by size. The test machine's eager limit was 4,096 B.
Three standard fixes were named in lecture: MPI_Sendrecv; even/odd ordering (evens send first, odds receive first); Isend/Irecv then Wait. What each one costs was left for you to reason about. Do that — mechanism first, then price.
A test set, and a method for a hang
Choose p from the problem's shape.
- p = 1 first: every path must still run (necessary, not sufficient — the guessed offsets pass there).
- A p that does not divide the work: 3 and 7.
- A p that breaks the shape: 6 on a 4-wide grid; 8 for a 2×2×2.
- A p larger than the work: some rank gets nothing — and must still call the collective.
- A size past the eager limit, not only m = 100.
Every hang is a rank waiting for a call another rank will never make.
- Bound it:
timeout, a short--time. - Trace
[rK] before/afterevery call, thenfflush— a hung rank never flushes. - Or
gdb -p <pid> -batch -ex bt, once per rank. - Draw it: an arrow from each waiter to who it waits for. A cycle is a deadlock. An arrow to a rank that left is a missing call.
MPI_Bcast(&P.nSamples, 1, MPI_DOUBLE, 0, comm) where nSamples is an int sitting just before seed in a struct. p = 4 prints π = 3.142584. Is the program right? Silent. The compiler sees int; MPI sees a pointer and the type you passed, and trusts your description of memory completely. Four identical streams of 500,000 darts still look like 2,000,000 darts. Only a CHECK against a serial recomputation with the same seeds catches it — "π equals the p = 1 run" is the wrong test, because a correct run differs from it.
Metrics drill
S = T₁ / Tₚ · E = S / p · Karp–Flatt e = (1/S − 1/p) / (1 − 1/p). Three decimals. Show your arithmetic on paper; the reasoning is what counts.
| p | Tₚ (s) | S | E | e |
|---|
Reading e: flat across p means a fixed serial fraction; rising means an overhead that grows with p (communication, imbalance, a boundary crossed). One e is a number; the trend across p is the diagnosis. Mechanisms that drop efficiency between two p's — you have met five: a serial section, communication growing with p, crossing a node boundary, load imbalance from the remainder, too little work per rank. For each, ask what its curve would look like and what second measurement would tell them apart.
Your own numbers (R02–R04)
Ask yourself what you learned about the cost of moving data, and name one specific place your intuition was wrong. "Communication is expensive" earns little. A belief, the number that replaced it, and the mechanism earn the points. Open each repository and fill this in. It stays in your browser.
| You varied | I predicted | I measured | The mechanism behind the gap | |
|---|---|---|---|---|
| R02 | p; 2·10⁸ samples fixed | |||
| R03 | p and N (10³, 10⁷) | |||
| R04 | n records, p = 2 |
One sentence: the belief I walked in with, and what replaced it
Saved as you type. Nothing leaves this page.
Check yourself
Eight questions, instant feedback, nothing recorded.
MPI_Scatter(x, N, MPI_DOUBLE, myX, N, MPI_DOUBLE, 0, comm) at p = 4, x has N doubles. What happens?MPI_Reduce except the ones that had no work, which returned early. p = 7, 6 batches. Result?MPI_Type_vector?struct { int n; double a; double b; }. sizeof, and the offset of b?MPI_Comm_split(WORLD, rank / COLS, rank, &row). Its rank in row?