MPI II — Splitting the Work,
Timing It, Talking to It
One problem you can check by hand, and the three questions every MPI program has to answer about it: who does which part, whose clock counts, and who is allowed to talk to the outside world.
Concept map
Week 3 gave you a program that says hello. Today the program does arithmetic, and three questions appear that hello never had to answer. Click a node to jump to it.
The problem, serial first
Area under a curve, by trapezoids. f(x) = x², a = 0, b = 5. Exact answer 125/3 = 41.666… An answer you can check by hand is a gift.
double Trap(double left, double right,
long int numTraps, double h) {
double retValue, x;
retValue = (f(left) + f(right)) / 2.0;
for (long int i = 1; i <= numTraps - 1; i++) {
x = left + i * h;
retValue += f(x);
}
retValue = retValue * h;
return retValue;
}
Cut [a, b] into n trapezoids, h = (b − a) / n. Area ≈ h · [ f(x₀)/2 + f(x₁) + … + f(xₙ₋₁) + f(xₙ)/2 ]. The whole computation is one loop.
What one trip costs
One f(x), one add, one loop step per trapezoid. Call it t_f: about a nanosecond. The order of magnitude is what matters.
Measure yours: time the serial run and divide by n. T₁ / n.
Everything else today is about who runs which part of this loop.
The picture
x² on [0, 5], drawn with n trapezoids. The sum is the one Trap() computes, run here for the n you choose.
Every rank finds its own piece
p ranks, n trapezoids. Who does what? What does each rank need to know before it can start, and does it need to hear from anyone?
This is domain decomposition. Every rank computes its own interval from its rank, p, a, b and n. No message to start. Only one double per rank ever crosses the wire: the answer.
local_n = n / p; local_a = a + myRank * local_n * h; local_b = local_a + local_n * h; local_sum = Trap(local_a, local_b, local_n, h);
Week 1 callback: this is the deal. How did your table deal, and how did it merge?
Explore the split
The four lines above, evaluated for every rank. a = 0, b = 5. Each rank's numbers come from its rank alone.
Two ways to merge
You already measured both in Week 1. Rank 0 takes p − 1 messages one after another, or pairs combine in rounds.
All at once: linear
Rank 0 takes p − 1 messages, one after another. Cost grows like p − 1.
Pairwise: tree
Pairs combine in rounds. Rank 0 waits ⌈log₂ p⌉ rounds, not p − 1 messages.
Linear
Tree
Each step is one message time, t_m. Several messages in the same round of the tree overlap; the linear merge serializes everything on rank 0.
The cost model
Compute time plus message time. Planning numbers, not measurements. The model has no fudge terms: if a measurement disagrees with it, something real is missing.
Tₚ ≈ (n / p) · t_f + C(p) · t_m
| Symbol | Meaning | Value |
|---|---|---|
| Tₚ | Total time on p processes | what you are predicting |
| n | Number of trapezoids, the problem size | 1,024,000,000 |
| p | Number of processes | 10 on Friday's layout |
| t_f | One trapezoid: one f(x), one add, one loop step | ≈ 1 ns |
| t_m | One small message between two nodes | ≈ 2 µs |
| C(p) | How many messages the merge costs | p − 1 linear, ⌈log₂ p⌉ tree |
t_m is the latency of one small message between nodes on this class of interconnect, 1 to 2 microseconds; 2 keeps the arithmetic round.
The model says nearly six thousand to one.
compute per rank 0.1 s 1.024 × 10⁸ × 1 ns linear merge 18 µs 9 messages × 2 µs tree merge 8 µs 4 rounds × 2 µs
Tree versus linear saves about 10 µs of a 0.1 s run: one part in ten thousand. Your min-of-5 rule exists because run-to-run noise is far bigger than that. Switching to a tree merge would change nothing you could measure.
A model can tell you an optimization is not worth measuring. That is the most important idea today.
The model, as a calculator
Change n, p and the merge. Everything below is the formula above with t_f = 1 ns and t_m = 2 µs: a model, not a measurement.
When splitting pays
The 2018 trapezoid code set n = 1024. It was a correctness demo.
Parallel loses, about eighteen to one.
serial ~1 µs 1,024 × 1 ns parallel, p = 10 ~18 µs 0.1 µs compute + 9 messages
That program could never have shown a speedup. One message costs about two thousand trapezoids: t_m / t_f ≈ 2,000. Parallelism pays only when each rank's work dwarfs one message. That is Week 2's iso-efficiency, with a price tag on it.
Break-even, live
Speedup > 1 needs n·t_f·(1 − 1/p) > (p − 1)·t_m, so n > p·t_m / t_f. Efficiency E = n·t_f / (n·t_f + p(p − 1)·t_m) is 50% at n ≈ p(p − 1)·t_m / t_f. Linear merge throughout.
Whose clock
Ten ranks, ten clocks. Whose time is the program's time?
The slowest rank is the program. A mean hides a straggler; the max is the straggler.
MPI_Barrier(MPI_COMM_WORLD);
double start = MPI_Wtime();
... the work ...
double local = MPI_Wtime() - start;
double elapsed;
MPI_Reduce(&local, &elapsed, 1, MPI_DOUBLE,
MPI_MAX, 0, MPI_COMM_WORLD);
Rank 0's clock was correct in Week 3, but only because of the closing barrier. Your harness does the equivalent: barrier, rank 0's clock, barrier. The closing barrier makes rank 0 wait for the slowest, so its number is the max, give or take one barrier.
MPI_Wtime returns wall-clock seconds as a double; MPI_Wtick gives its resolution. Clocks on different ranks are not promised to agree unless the MPI_WTIME_IS_GLOBAL attribute says so, so only differences taken on one rank are safe.
What each statistic hides
A model: each rank's finish time is (n/p)·t_f for n = 1.024·10⁹ plus a random skew of up to 20%, made up here so the three numbers differ. Run it several times.
Whose keyboard
Every rank prints one line. What order do they come out in? And if the program needs n from the keyboard, which ranks can read it?
Every rank's stdout is forwarded to mpiexec and interleaved as it arrives. No order is promised, and a line can even be split.
Print from rank 0, or tag each line with the rank and sort afterward. That is how the harness reads your HOST lines: it greps for the word ELAPSED rather than reading line N, and counts distinct HOST names, precisely because order is not promised. Your own Lab 1 output is the evidence.
Output: interleaved as it arrives
Simulated. p ranks each print one tagged line; the arrival order is drawn at random, which is the only guarantee you have.
Input: rank 0 reads, then shares
long n;
if (myRank == 0)
std::cin >> n;
MPI_Bcast(&n, 1, MPI_LONG, 0,
MPI_COMM_WORLD);
Why it depends on the launcher
The MPI standard does not specify stdin. Open MPI's mpirun and MPICH's Hydra mpiexec give it to rank 0 only. Slurm's srun sends it to every task by default (--input=all).
The portable rule survives either way: let rank 0 talk to the outside world, then Bcast. Check what Cardinal's own launcher does before stating "rank 0 only" as fact.
MPI_Bcast is the first collective after Reduce you will see. Week 5 does the rest.
Run it on Cardinal
Nothing new to build today. The evidence for both halves of this lecture is already in your Lab 1 sweep. Wednesday's code walk gets its own branch. About 15 minutes.
-
Get back to your Lab 1 checkout
Modules do not persist between sessions. Load them every time.
ssh <your-username>@cardinal.osc.edu module load mvapich/4.1 boost/1.83.0 cd mpi git checkout lab01
-
If you need a fresh copy
git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/mpi.git mpi cd mpi git checkout -b lab01 class/lab01 module load mvapich/4.1 boost/1.83.0 cd Default && make OSC && cd ..
Experiments
A · Read the harness output you already have
The sweep greps your program's stdout for the word ELAPSED and writes one CSV row per run. From the repository root, find the job output from your Lab 1 sweep and look at the two kinds of lines the lecture was about.
ls slurm-*.out grep -c ELAPSED slurm-<jobid>.out grep HOST slurm-<jobid>.out | head -30
What you should see
One ELAPSED line per run: the sweep ran p = 1, 2, 4, 7, 10 and repeated every point, so the count is the number of runs, not the number of process counts. The HOST lines: one per rank per run. Check whether they are in rank order, and whether two trials at the same p agree on the order. The harness counts distinct HOST names instead of trusting the order, for the reason you just read.
B · Watch the order change, live
Four nodes, one process each, so every line travels over the network to the launcher. Run it three times.
salloc --nodes=4 --ntasks-per-node=1 -c 2 --time=00:15:00 -A PCS0313 module load mvapich/4.1 boost/1.83.0 srun -c 2 -n 4 ./Default/MPI srun -c 2 -n 4 ./Default/MPI srun -c 2 -n 4 ./Default/MPI exit
What you should see
The greeting lines come out in rank order, because rank 0 receives them with a loop over q = 1 … p − 1 and prints each one as it arrives. The HOST lines are printed by every rank itself, so they can come out in any order, and the order can differ between the three runs. If all three agree, that is luck, not a promise.
C · Model against measurement
Open main.cpp on the lab01 branch and find what sits between the opening barrier and the closing one. If it is the greeting exchange, that is a linear merge of strings: rank 0 receives p − 1 messages, one after another, and the model says it costs about (p − 1) · t_m with t_m ≈ 2 µs. Take your minimum ELAPSED at p = 10 from the sweep CSV and put it next to the model's 18 µs.
What you should see
The two numbers will not agree. The model has no fudge terms, so a gap means something real is missing from it. Name the mechanism, not just "overhead": what else happens between the opening and closing barrier that the model does not count? That naming is the Diagnosis skill, and it is what R02 asks for.
local_n = n / p.Check yourself
Six questions, instant feedback, nothing recorded.