Moving the Data,
Not Just the Answer
Week 4 moved one number per rank. This week the whole vector travels: out, and back. Which calls move an array, what you must tell them, and what it costs.
Concept map
Monday gives the calls and the cost model. Wednesday walks the code. Click a node to jump to it.
z = x + y. N elements, all on rank 0. What has to move?
Week 4 sent one double per rank, once. Every input was a constant anyone could know. Here x and y exist only on rank 0.
A double is 8 bytes, so each vector is 8 MB. Rank 0 keeps its own quarter.
Out: ¾ of x + ¾ of y = 6 MB + 6 MB = 12 MB
Back: ¾ of z = 6 MB
Total: 18 MB, all through rank 0's one link
Messages: 9 (2 to each of 3 workers, 1 back from each) — irrelevant at this size
The trap is counting messages instead of bytes. At this size the message count is nothing; the bytes are the whole bill.
The bill, for any N and p
Model, not measurement: wire at 20 GB/s (Cardinal's NDR200 planning number), one add at about 1 ns (Week 4's tf). Rank 0's own block never moves.
Out, work, back
The whole vector on rank 0, dealt out in blocks (scatter), each rank adds its block, the blocks come back in rank order (gather). Step through it.
Scatter
Rank 0's array, in p equal blocks. Block r goes to rank r. Rank 0's own block is copied, not sent.
Gather
Scatter run backwards, the way Bcast was Reduce run backwards. Block r lands at r × count in rank 0's array. Rank order, always.
Design MPI_Scatter before you see it
Week 4 you designed MPI_Reduce: seven arguments. This call moves an array, not one value. On the root, where is the whole thing? On every rank, where does my piece go?
List the arguments. There are 8.
| Side | What the caller must say | Name |
|---|---|---|
| Send (root) | Where the whole array is | sendbuf |
| How many go to EACH rank | sendcount | |
| What type | sendtype | |
| Receive (me) | Where my piece goes | recvbuf |
| How many | recvcount | |
| What type | recvtype | |
| Both | Who is the root | root |
| Which communicator | comm |
Why two types: the sender and receiver may describe the same bytes differently. That is Week 6. For now both are MPI_DOUBLE.
MPI_Scatter(x, ___, MPI_DOUBLE, myX, ___, MPI_DOUBLE, 0, MPI_COMM_WORLD). What goes in the first blank, sendcount? sendcount is per rank, not the total. Scatter(x, 250, ...) at p = 4 deals 250 to each rank, 1,000 in total. Most people write N on the board the first time. R03's TODO 3 depends on getting this right.
MPI_Scatter(sendbuf, sendcount, sendtype, // root: all recvbuf, recvcount, recvtype, // me: my block root, comm); MPI_Gather (sendbuf, sendcount, sendtype, // me: my block recvbuf, recvcount, recvtype, // root: all root, comm); // sendcount = elements PER RANK, not the total
Read it carefully: where does block r land?
The root's whole-array buffer is used only on the root: read by Scatter, written by Gather. Every other rank can pass nullptr there. Every rank calls both, root included.
When it won't divide
20 elements, 3 ranks. MPI_Scatter has one sendcount, and 20 ÷ 3 is not a whole number. You have seen this twice: Week 4's trapezoid and R02's TODO 1.
counts[r] is how many rank r gets; displs[r] is where rank r's block starts in the big array. displs is the running sum of counts; nothing else. The first N % p ranks take one extra — Week 4's fourthMethod, as two arrays.
Why not pad to 21? Legitimate, and it is the "require divisibility" design from Week 4. But then every rank, forever, has to know which element is fake.
int base = N / p;
int extra = N % p;
for (int r = 0; r < p; r++) {
counts[r] = base + (r < extra ? 1 : 0);
displs[r] = (r == 0) ? 0 : displs[r - 1] + counts[r - 1];
}
MPI_Scatterv(x, counts, displs, MPI_DOUBLE, // root: how many, and where
myX, counts[myRank], MPI_DOUBLE, // me: my count
0, MPI_COMM_WORLD);
counts and displs, for any N and p
Every rank can build both arrays itself: it knows N, p and its own rank. No message needed. Wednesday's hand-rolled version sends the count anyway; R03's Diff Journal asks whether it had to.
counts[myRank]. MPI_Gatherv takes the same two arrays on the receiving side. R03's TODO 1 is this loop; TODO 3 is one Gatherv.The family: seven collectives, one picture each
Reference, not lecture. Week 4 did Reduce and Bcast; today did Scatter and Gather. Pick a row to draw it at p = 4.
| 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
- Every rank calls it.
- Same order on every rank.
- No tags.
- Returns when my part is done. Not a barrier.
- Allgather and Allreduce have no root: everyone ends up with the answer.
Two to name and move on from
Allgather and Allreduce are "then broadcast the result", done better than you would do it by hand. Alltoall is different: every rank sends a personal block to every other rank. It is the transpose, and the most expensive call on the list — p(p − 1) blocks in flight.
MPI_Bcast and then MPI_Reduce. Rank 1 calls MPI_Reduce and then MPI_Bcast. Both are on MPI_COMM_WORLD. What happens?Two collectives in different orders on different ranks is a hang. No tags means there is nothing to match them up, so the rule has to be: same order on every rank. And a collective returning on rank 0 does not mean rank 1 is finished — it is not a barrier.
Three ways to deal the same 12 cards
Week 1's card sort. Your tables dealt cyclically: one card to each player in turn. That is a data distribution, and it has a name.
| Scheme | Rule | Sends per rank |
|---|---|---|
| Block | contiguous chunks | one message per rank |
| Cyclic | element i goes to rank i mod p | pack every p-th element into a buffer first |
| Block-cyclic | blocks of B, dealt round robin | pack from an index list first |
A message costs a start, plus a rate
Week 4 needed only α, because one double is nothing. A vector is not nothing, so the model gets a second term.
| α ≈ 2 µs | start-up, any size: Week 4's tm |
| β ≈ 0.05 ns/B | 20 GB/s: Cardinal's NDR200 link (25 GB/s peak), with headroom |
| α / β ≈ 40 KB | the crossover: below it, count messages; above it, count bytes |
Model: 1,024 × 0.05 ns = 51.2 ns of bytes against 2,000 ns of start-up. A 1 KB message is a start-up with a little data attached. The two terms are equal at m = α / β = 2 µs × 20 GB/s = 40 KB. Write it down.
Where the two terms cross
Log-log, drawn from the model with α = 2 µs and β = 1/(20 GB/s). Planning numbers, not measurements. If R03's data disagrees, that is its Diagnosis section.
p = 16, 1 MB per worker. Does a tree help?
Loop: rank 0 receives 15 messages. Tree: ⌈log₂ 16⌉ = 4 rounds. Week 4 says the tree wins. Now count bytes.
A tree saves messages, not bytes.
Bytes into rank 0: 15 workers × 1 MB = 15 MB, loop or tree At 20 GB/s: 15 MB ÷ 20 GB/s = 750 µs Start-ups, loop: 15 × 2 µs = 30 µs Start-ups, tree: 4 × 2 µs = 8 µs Ratio: (750 + 30) ÷ (750 + 8) ≈ 1.03
A tree changes the route — in a binomial tree most of the data, 11 of the 15 MB here, passes through an intermediate rank first — not how much arrives at the root. The α difference is real, and invisible next to 750. Three percent is below run-to-run noise.
Same question, other message sizes (p = 16)
Model: loop = 15 α + 15 m β; tree = 4 α + 15 m β. The byte term is the same in both because the root's link carries all 15 blocks either way. p stays at 16 here on purpose: R03's prediction is this question at p = 8 and two sizes, and it is yours to work by hand before the lab.
Your numbers, on Cardinal
Today is a concept day: nothing new to run yet. Two things to do before Wednesday, and a set of planning numbers to keep.
-
Check out Wednesday's branch so the build is done before the walk
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 module load mvapich/4.1 boost/1.83.0 cd Default && make OSC && cd ..
If you already have the clone, skip the clone line.
module loadevery session: modules do not persist. -
When you time anything, put one process per node
module load mvapich/4.1 boost/1.83.0 salloc --nodes=3 --ntasks-per-node=1 -c 2 --time=00:15:00 -A PCS0313 srun -c 2 -n 3 ./Default/MPI 20
--nodes=N --ntasks-per-node=1makes every message cross the InfiniBand link, which is what the model prices.--nodes=1 --ntasks-per-node=Nkeeps them in shared memory and measures something else. The login node is shared; time nothing there.exitreleases the allocation.
Read your own numbers against the model
A · The planning numbers
| α | 2 µs per message, any size (Week 4's tm) |
| β | 0.05 ns/B — 20 GB/s planning; NDR200 is 25 GB/s peak |
| α / β | 40 KB crossover |
| tf | 1 ns per add |
| nodes | 378, 96 usable cores each (two sockets of 48) |
What you should see
Nothing to run here. These are planning numbers, not measurements. Every time on this page that is not from a slide was computed from them, and is labelled model.
B · R02, re-read
R02's messages were one double each: the model charges them α and nothing else, because 8 bytes at 0.05 ns/B is 0.4 ns. Look at your own ELAPSED numbers and your Karp–Flatt e. If e rose with p, where in t(m) does that cost live? If your π got better as p grew, you multiplied the problem instead of dividing it.
What you should see
Your own R02 table. The question is whether its shape matches a cost that is all α — a fixed charge per message, p − 1 of them at the root.
C · Wednesday's file, with today's arithmetic
The run in step 2 is lecture05 at N = 20, p = 3: the Scatterv example from this page, in code. Before you look at the output, write down counts and displs for 20 and 3 (the calculator on screen 5 checks you).
What you should see
Five methods, each ending in a CHECK line; vectors print when N ≤ 30, so the blocks are visible. The uneven methods deal 7, 7, 6 at displacements 0, 7, 14. Wednesday walks why two of the versions are wrong — one of them only some of the time.
D · R03's prediction, Oct 2
Hand-rolled gather vs MPI_Gatherv, timed, at p = 8 and two sizes. The prediction is written in the first five minutes with no machine: the ratio, from t(m). This page stops at p = 16. Do p = 8 on paper, then the lab tells you whether the model's assumption about the α's holds.
What you should see
Not yet known. That is the point of the lab's Diagnosis section: if the small-N sweep disagrees with 15 start-ups in a row, the model is what gets revised.
lecture05 built, and α, β and 40 KB written down. Before Oct 2 (R03): the Scatterv loop by hand for 20 and 3, and a ratio for p = 8 that you are willing to be wrong about.Check yourself
Six questions, instant feedback, nothing recorded.
MPI_Scatter(x, sendcount, MPI_DOUBLE, myX, recvcount, MPI_DOUBLE, 0, comm) with 1,000 elements and p = 4. sendcount isMPI_Gather has returned on rank 0. Which is guaranteed?