Week 5 · MPI III · Companion to lecture 05b

One File, Five Ways
to Add Two Vectors

Five versions of z = x + y, all in src/main.cpp on branch lecture05. Two of them are wrong, and one of those passes some of the time.

Concept map

Monday gave you Scatterv and Gatherv. Today is one file that adds two vectors five ways, and two of the ways are wrong. Click a node to jump to it.

todaylater

It printed the right answer twice in a row. That is not the same as being right.

Mark this section done

Out by hand, back by hand

vectorSumExample(). Rank 0 holds x and y. Send and Recv only. Rank 0 is a worker too: it adds its own block.

Count the messages before you write the loop. At p = 4, how many messages go out from rank 0, and how many come back?

4 out, 4 back — one per rank each way. 3 out, 3 back — rank 0 does not send to itself. 6 out, 3 back — each worker needs its piece of x and its piece of y, and sends one block of z home. 8 out, 4 back — rank 0 also sends itself x and y.

Out: rank 0 sends each worker its piece of x and its piece of y. That is 2(p − 1) sends, 6 at p = 4. Back: each worker sends its block of z, p − 1 receives on rank 0, 3 at p = 4. Rank 0 keeps block 0 and adds it itself.

The question you should be asking, and the one the deck holds until the output: how big is each piece? If your answer is N/p, keep it on the board. Do not look for the bug yet.

mySize = problemSize / numProcs;

for (int i = 1; i < numProcs; i++) {          // out: 2(p-1) sends
    int index = i * mySize;
    MPI_Send(&x[index], mySize, MPI_DOUBLE, i, 0, ...);
    MPI_Send(&y[index], mySize, MPI_DOUBLE, i, 0, ...);
}

// ... rank 0 adds block 0 itself ...

for (int i = 1; i < numProcs; i++) {          // back: p-1 receives
    int index = i * mySize;
    MPI_Recv(&z[index], mySize, MPI_DOUBLE,
             MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &myStatus);
}

Count the messages

p 4

Every arrow starts or ends on rank 0. Rank 0 is the bottleneck both ways.

Two lines on this slide are wrong. Do not look for them yet: look at the output.

Mark this section done

N = 20: which runs are wrong?

Same program, N = 20, run a few times. Real output from lecture05, on the course's test machine.

p = 2          CHECK ok
p = 3   ... 15  9  9 14  0  0
               CHECK 2 of 20 WRONG
p = 4, run 1   CHECK 10 of 20 WRONG
p = 4, run 2   CHECK ok
p = 4, run 3   CHECK ok
p = 4, run 4   CHECK ok
p = 4, run 5   CHECK ok
p = 4, run 6   CHECK 8 of 20 WRONG

Same binary, same N, same p = 4. Four runs right, two wrong. p = 3 is wrong at the end, and the end is zeros. Give it two minutes before you answer.

Two bugs. What does each run tell you?

One bug: uninitialised memory. The zeros at p = 3 and the random failures at p = 4 are the same thing. p = 3 fails because 3 does not divide 20: a size bug, wrong every time. p = 4 divides 20, so the size is fine; something that depends on timing is wrong sometimes. p = 4 fails because 4 processes oversubscribe the machine; p = 3 fails because the vector is too short. Both are the Week 4 remainder bug. The p = 4 runs that passed got lucky with rounding.

First find p = 3: the last two elements are 0. Then the harder one: p = 4 divides 20 evenly, so the size is fine, and the same binary is right four times and wrong twice. Something depends on timing.

Bug 1 is mySize = problemSize / numProcs: 20 / 3 = 6, three ranks × 6 = 18, elements 18 and 19 are never sent. Bug 2 is MPI_ANY_SOURCE: the loop decides the slot, arrival decides the sender. The next two screens take them one at a time.

One is wrong every time. One is wrong sometimes. Which is worse?

The one that fails every time: it corrupts every result. The intermittent one: it passes the demo, passes the next four tests, and ships. Neither. Both print a CHECK line, so both get caught. The one that fails every time, because it loses data instead of misplacing it.

The p = 3 bug fails every run and gets fixed on day one. The p = 4 bug passes the demo, passes the next four tests, and ships.

Honesty note from the deck: these lines are real lecture05 output, but from Open MPI on one machine, oversubscribed, where arrival order is noisy. On Cardinal at one rank per node, p = 4 may well pass every time. That makes the point stronger, not weaker; --shuffle forces it.

Mark this section done

Bug 1: 20 ÷ 3 = 6, and two elements fall off

Integer division. Three ranks × 6 = 18. Nobody is ever sent elements 18 and 19, nobody computes them, and z[18], z[19] still hold the 0 that z.resize() put there.

mySize = problemSize / numProcs;   // 20/3 = 6

Each rank's block

N p 3

Same code, N = 20, p = 7. How many elements get computed, and how many are lost?

20 computed, 0 lost — 7 ranks is plenty. 21 computed — one rank reads past the end. 14 computed, 6 lost — 20 / 7 = 2, and 7 × 2 = 14. 18 computed, 2 lost — same as p = 3.

At p = 7: 20 / 7 = 2, so 14 elements computed and six lost. Move the slider above to 7 and count the grey cells.

Week 4's bug, loud this time. Same line of reasoning, n/p with the remainder thrown away. Last week it cost the seventh decimal and was invisible at 6 digits. This week it costs two whole elements and prints as zeros. A zero is easier to see than a wrong seventh decimal. Loud bugs are the kind ones.

Mark this section done

Bug 2: first to arrive is not rank 1

The loop decides the slot: the first receive goes to z[1 · mySize], the second to z[2 · mySize]. MPI_ANY_SOURCE decides the sender: whoever's message is there first. The two agree only when the workers happen to answer in rank order.

for (int i = 1; i < numProcs; i++) {
    int index = i * mySize;                        // the loop picks the SLOT
    MPI_Recv(&z[index], mySize, MPI_DOUBLE, MPI_ANY_SOURCE, ...);   // arrival picks the SENDER
}

Arrival simulator

p 4

N = 20. x and y hold integers from 1 to 10, so every misplaced element is still a plausible sum. The order the workers' replies reach rank 0 is drawn at random each run; --shuffle is the branch flag that makes the workers answer in reverse rank order.

p = 4 with --shuffle: the workers answer 3, 2, 1. How many of the 20 elements end up wrong?

15 of 20 — every worker's block lands in the wrong slot. 10 of 20 — rank 3's block lands in slot 1 and rank 1's in slot 3; rank 2 arrives second and lands in slot 2, which happens to be right. 0 of 20 — MPI_Recv sorts by the status's MPI_SOURCE. 5 of 20 — only the last reply is misplaced.

From the deck: --shuffle, p = 4: wrong every run (10 of 20 in most). "In most" because two misplaced elements can still be equal by coincidence, which is where the "8 of 20" run above came from. No error, no crash, and every element is still a plausible sum of two numbers from 1 to 10. Only the check catches it.

Rank 0's loop fills      arrives first, second, third
slot 1   z[5..9]     <-  rank 3's block
slot 2   z[10..14]   <-  rank 1's block
slot 3   z[15..19]   <-  rank 2's block

Week 4 callback: "Rank 0 waits for rank 1 even if rank 9 is ready first. Hold that thought until Week 5." This is the thought. MPI_ANY_SOURCE is the tempting fix for that wait, and here it is the bug.

Two correct fixes: receive from rank r by name (the next method does), or keep ANY_SOURCE but read status.MPI_SOURCE and compute the slot from it, which means receiving into a scratch buffer first. R03's lab checklist (Oct 2) bans ANY_SOURCE in the hand-rolled gather.

Mark this section done

Counts, displacements, and names

vectorSumExample_Uneven_Send_Recv(). Fix both bugs. Send and Recv only. Two arrays on rank 0 answer three questions.

20 elements, 3 ranks: who gets the extra two? Use Week 4's two integers.

Rank 2 gets 8, the others 6 — the last rank takes the remainder. Ranks 0 and 1 get 7, rank 2 gets 6 — base = 20 / 3 = 6, rem = 20 % 3 = 2, the first rem ranks take one more. Rank 0 gets 8 and keeps the extras itself. Nobody. N is rounded up to 21 and the extra element is ignored.

base = N / p, the first N % p ranks take one more. counts and displs, as on Monday. Rank 2 must size its buffer before it receives; rank 0 must put each reply in the right place: receive from rank r by name, into displs[r]. That is the whole fix for bug 2.

counts[r] = base + (r < rem ? 1 : 0);
displs[r] = (r == 0 ? 0 : displs[r-1] + counts[r-1]);

MPI_Send(&counts[r], 1, MPI_INT, r, TAG_COUNT, ...);     // size first
MPI_Send(x.data() + displs[r], cnt, MPI_DOUBLE, r, TAG_X, ...);
MPI_Send(y.data() + displs[r], cnt, MPI_DOUBLE, r, TAG_Y, ...);

// back on rank 0: from r, BY NAME, into r's slot
MPI_Recv(z.data() + displs[r], cnt, MPI_DOUBLE, r, TAG_Z, ...);

counts and displs

N p 3

Checked

CHECK ok at every p, with or without --shuffle. That is the evidence that both bugs are gone.

3(p − 1) messages out now: the count costs one more each. The count message is p − 1 extra messages in a pattern where messages are the cost.

Did the worker need to be told its count? It knows N, p and its own rank. Leave that question open; it is a Diff Journal bullet in R03, and R03's lab (Oct 2) does not send it.

Mark this section done

Same answer, three calls

vectorSumExample_Uneven_Scatter_Gather(). That was about 100 lines. Monday: Scatterv and Gatherv take counts and displs.

What must EVERY rank now compute that only rank 0 computed before?

Nothing new. Rank 0 still sends each rank its count first. Its own count only. Rank 0 alone builds displs. counts and displs, the whole arrays — because every rank passes them to every collective. The tree. Each rank works out which rank it forwards to.

In the hand-rolled version only rank 0 built them and told everyone. In the collective version every rank builds them, because every rank passes them. That is fine: it costs a loop of p iterations and zero messages. Two Scatterv calls (x, then y) and one Gatherv. The library still moves the same blocks; it just knows how, and may pick a tree.

for (int r = 0; r < numProcs; ++r) {        // EVERY rank
    counts[r] = base + (r < rem ? 1 : 0);
    displs[r] = (r == 0 ? 0 : displs[r-1] + counts[r-1]);
}

MPI_Scatterv(myRank == 0 ? x.data() : nullptr,
             counts.data(), displs.data(), MPI_DOUBLE,
             myX.data(), counts[myRank], MPI_DOUBLE, 0, comm);
MPI_Scatterv( ... the same for y ... );

vectorSum(myX, myY, myZ);

MPI_Gatherv(myZ.data(), counts[myRank], MPI_DOUBLE,
            myRank == 0 ? z.data() : nullptr,
            counts.data(), displs.data(), MPI_DOUBLE, 0, comm);

What each rank holds and passes

p 3 N = 20

Every row is computed by that rank, from N, p and nothing else. Every rank calls every collective. No if around it.

Gone

The count messages: every rank computes its own.
Tags and ANY_SOURCE: blocks land by rank.

Not gone

The bytes. Those still move.
The local vectorSum is unchanged.

The collective did not make the data any smaller. Does it make it any faster? That is R03's question (Oct 2). This page does not answer it; the lab measures it.

Mark this section done

Scattered data has to be packed

vectorSumExample_Cyclic(). Deal it like cards: element i goes to rank i mod p. Count the passes over memory, not the messages.

At p = 3, rank 1 owns elements 1, 4, 7, 10 … One MPI_Send takes one pointer and one count. How do you send rank 1 its elements?

One Send starting at &x[1] with count N/3 — MPI skips every third element. One Send per element — N/3 messages to rank 1. Copy every p-th element into a contiguous buffer first (pack), send the buffer once, and copy each result back out (unpack). Sort x so rank 1's elements are adjacent, then send a block.

They are not next to each other: they are p elements apart. One Send covers one contiguous run, so rank 0 copies every p-th element into a buffer (pack), sends the buffer, and on the way back copies each result out to every p-th slot (unpack). Same message count as block; two extra passes over the data on rank 0.

// pack: every p-th element into a buffer
for (int i = r; i < N; i += numProcs) {
    bufX[k] = x[i];
    bufY[k] = y[i];
    ++k;
}
MPI_Send(bufX.data(), cnt, MPI_DOUBLE, r, TAG_X, ...);
MPI_Send(bufY.data(), cnt, MPI_DOUBLE, r, TAG_Y, ...);

// unpack on the way back
for (int i = r; i < N; i += numProcs) {
    z[i] = bufZ[k++];
}

The pack loop, one step at a time

N 20 p 3 r

x[0..N−1], rank r's elements highlighted

bufX[0..cnt−1]

That is the price of a non-contiguous distribution when your only tool is a pointer and a count. Week 6: a derived datatype (MPI_Type_vector) describes "every p-th double" to MPI directly, so the library reads x in place and there is no pack loop at all. R04 (Oct 16) times exactly that difference.

Mark this section done

B = 64: correct is not balanced

vectorSumExample_BlockCyclic() deals blocks of B elements round-robin. The call in main() uses the default B = 64 with N = 20.

B = 64, N = 20, p = 4. What does CHECK print, and who holds the data?

CHECK WRONG — a block of 64 reads past the end of a 20-element vector. CHECK ok — each rank gets 5 elements, like the block version. CHECK ok — one block of 64 covers the whole vector, so rank 0 is dealt all of it and every other rank gets nothing. The program aborts: B must divide N.

One block of 64 covers the whole vector. Rank 0 does all of it. CHECK still says ok. Correct and balanced are two different checks, and nothing in the program checks the second one.

The deal

B 64 p 4 N = 20 · element i goes to rank (i / B) mod p

The correctness line is what the program's CHECK tests: every element owned by exactly one rank. The balance line is the check the program does not make.

Nothing in the output told you rank 0 did all the work. A CHECK that passes is a necessary condition. It is not evidence of a good decomposition.

Mark this section done

Run it on Cardinal

Branch lecture05. Predict before each run. About 20 minutes.

Clone once, check out the lecture branch

ssh <your-username>@cardinal.osc.edu
git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/mpi.git mpi
cd mpi
git fetch class
git checkout -b lecture05 class/lecture05

Load the modules, build

Modules do not persist between logins. The makefile's OSC target links Boost, so load the boost module or the link fails.
```
module load mvapich/4.1 boost/1.83.0
cd Default && make OSC && cd ..
```
Get four nodes of your own

One process per node, so every message crosses the network. The login node is shared; run nothing there.
```
salloc --nodes=4 --ntasks-per-node=1 -c 2 --time=00:15:00 -A PCS0313
module load mvapich/4.1 boost/1.83.0
```
Every run: srun -c 2 -n p ./Default/MPI [N] [--shuffle] [--trace] [--only=k]. Default is all five methods; --only=k runs method k of 1..5 in file order. Vectors print for N ≤ 30.

Experiments

A · p = 3: which methods fail, and how many elements?

srun -c 2 -n 3 ./Default/MPI

What you should see

vectorSumExample shows at least the two zeros at the end of z and CHECK 2 of 20 WRONG. Uneven_Send_Recv, Scatter_Gather, Cyclic and BlockCyclic all print ok.

B · p = 4 with --shuffle: which one breaks, and which don't?

srun -c 2 -n 4 ./Default/MPI 20 --shuffle

What you should see

Only vectorSumExample breaks (usually 10 of 20). Every other method stays ok, which is the demonstration that the fix is real and not lucky. The bug that needs --shuffle to show up is the one that ships.

C · The first method alone, six times, no --shuffle

for i in 1 2 3 4 5 6; do
    srun -c 2 -n 4 ./Default/MPI 20 --only=1 | grep CHECK
done

What you should see

On the course's test machine (Open MPI, oversubscribed) this gave four ok and two WRONG. On Cardinal at one rank per node, p = 4 may well pass every time. If it does, that is the point: a run that passes is not evidence the code is right. Experiment B is the evidence.

D · Bug 1 at p = 4 with an N that 4 does not divide

srun -c 2 -n 4 ./Default/MPI 22 --only=1
srun -c 2 -n 4 ./Default/MPI 22 --only=2
exit

What you should see

Predict first with the Bug 1 explorer; this one is the deck's arithmetic, not a transcript: 22 / 4 = 5, so 4 × 5 = 20 elements computed and the last two print as 0 in the first method (plus whatever ANY_SOURCE does that run). The second method prints ok. Then exit to release the allocation.

Before 8:30 on October 2 (R03): make CS4170_FA2026_R03_LASTNAME and uncheck the README box. Pull fa2026-mpi/lab03. Read the three TODOs; write none. Bring Monday's model: t(m) ≈ α + m·β, 2 µs, 20 GB/s. R03 is the full period: prediction in the first five minutes, with no machine. Come knowing α and β.

Mark this section done

Concept map

Out by hand, back by hand

Count the messages

N = 20: which runs are wrong?

Bug 1: 20 ÷ 3 = 6, and two elements fall off

Each rank's block

Bug 2: first to arrive is not rank 1

Arrival simulator

Counts, displacements, and names

counts and displs

Checked

Same answer, three calls

What each rank holds and passes

Gone

Not gone

Scattered data has to be packed

The pack loop, one step at a time

B = 64: correct is not balanced

The deal

Run it on Cardinal

Clone once, check out the lecture branch

Load the modules, build

Get four nodes of your own

Experiments

A · p = 3: which methods fail, and how many elements?

B · p = 4 with --shuffle: which one breaks, and which don't?

C · The first method alone, six times, no --shuffle

D · Bug 1 at p = 4 with an N that 4 does not divide

Check yourself