Week 3 · MPI I · Companion to lecture 03

Processes, Messages,
and the Machine

In Week 1 you were all at one table. Now you are in six separate rooms. One source file runs p times, one integer differs between the copies, and every card that moves, somebody mailed. Then: Cardinal, modules, Slurm — how a job you submit becomes a job that runs.

Concept map

One period, two jobs: the model, and the machine you run it on. Click a node to jump to it.

todaylater

Separate processes. No shared memory. Every exchange is a message you wrote on purpose — a line you can point at, and time. That is why this course does MPI first.

Mark this section done

Six separate rooms

Week 1: six people, one deck, anyone could reach any card. Now nobody can reach anybody else's cards. Every card that moves, somebody mailed.

Most tables only see losses when they move to separate rooms. Something gets easier, not harder. What?

Dealing the cards — the deal is now a single bulk mailing. Races become impossible — you cannot corrupt a variable nobody else can touch. Finding the maximum — each room can read every other room's pile. Nothing. Separate rooms only add cost.

A variable in rank 2 is invisible to rank 3, so rank 3 cannot overwrite it. Communication is explicit — you wrote every byte of it — and so are the bugs. This pays off in Week 10, when you meet real races in shared memory.

Shared vs. distributed memory

	Shared memory	Distributed memory
Tool	OpenMP, threads, weeks 9–13	MPI, processes, weeks 3–8
Address space	one	p separate address spaces
A variable	threads read the same variable	a variable in rank 2 is invisible to rank 3
Communication	implicit — and so are the bugs	explicit — you wrote every byte of it
Reach	limited to one node	scales across the whole machine

Same problems, opposite failure modes. You will meet every idea twice this semester. In OpenMP the communication is hidden in the hardware; here it is a line you can point at — and time.

Mark this section done

SPMD, and the four calls every program has

Single Program, Multiple Data. You write ONE source file. It runs p times. The only thing that differs between the copies is a single integer: the rank.

p 5 Same main.cpp, p copies. Every process evaluates the if — they just answer it differently.

int numProcs, myRank;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
MPI_Comm_rank(MPI_COMM_WORLD, &myRank);

if (myRank != 0) {  /* send */  } else {  /* receive them all */  }

MPI_Finalize();

The skeleton

`MPI_Init`	nothing MPI works before this
`MPI_Comm_size`	how many of us are there?
`MPI_Comm_rank`	which one am I?
`MPI_Finalize`	nothing MPI works after this

MPI_COMM_WORLD is "everybody in this job". You will make smaller worlds in Week 7. Both branches of the if are in the same file and compiled into the same binary. Every if (myRank == 0) in your code is you breaking the symmetry on purpose.

This is the file you fork on Friday — Template branch, src/main.cpp. Nothing here is a toy.

Mark this section done

Send and Receive

Six arguments each. Five of them have to agree on both ends.

MPI_Send(buffer, count, type, dest,   tag, comm);
MPI_Recv(buffer, count, type, source, tag, comm, &status);

`buffer`	where the bytes are
`count`	how many items — not bytes
`type`	`MPI_CHAR`, `MPI_INT`, `MPI_DOUBLE` …
`dest` / `source`	which rank
`tag`	a label you choose, to tell messages apart
`comm`	which world

Which five must agree?

Click the arguments that have to match between the sender's MPI_Send and the receiver's MPI_Recv. Then check.

Mismatched count, type or tag is the most common first-week bug. The buffer is the one argument that is yours on each end: two different addresses in two different address spaces.

Mark this section done

This compiles. It runs. Sometimes it prints garbage.

Every rank except 0 builds a greeting and sends it. It will almost certainly work on your laptop. It will eventually fail on Cardinal, and not reproducibly.

std::ostringstream out;
out << "Greetings from " << myRank << " of " << numProcs;
std::string msg = out.str();

MPI_Send(msg.c_str(), msg.size(), MPI_CHAR, 0, 0, MPI_COMM_WORLD);

Where is the bug? (How does std::cout know where the string ends?)

tag is 0 and dest is 0 — the two zeros collide. MPI_CHAR should be MPI_BYTE; chars are not bytes on Cardinal. count is msg.size() — the null terminator is never sent, so rank 0 prints past the end of the string. msg.c_str() returns a temporary that is freed before Send copies it.

The +1 is the null terminator. Leave it off and rank 0 prints your string plus whatever happened to be in memory next to it.

MPI_Send(msg.c_str(), msg.size() + 1, MPI_CHAR, 0, 0, MPI_COMM_WORLD);
//                    ^^^^^^^^^^^^^^  the +1 is the null terminator

myRank 1

What sits past the terminator in rank 0's buffer is whatever was there before — the deck does not show it, and neither will this page. It looks fine on your laptop and fails on Cardinal.

Mark this section done

Ask before you accept

Rank 0 is about to call MPI_Recv. It knows who is sending, and the tag, and the type. It has to hand Recv a buffer before the message arrives.

Greetings from 7 of 10 and Greetings from 10 of 10. What is different about them, and why does that ruin the plan?

They come from different ranks, so rank 0 needs a different tag for each. They are different lengths, and rank 0 does not know which length is coming — so it cannot size the buffer up front. One of them arrives before rank 0 has called Recv, and is lost. Nothing: MPI_CHAR messages are always padded to the same length.

Recv needs a size up front. So ask first. MPI_Probe blocks until a message is ready and fills in a status — without taking the message off the wire. MPI_Get_count reads the length out of that status. (Sending the length first in a separate message is also a real design.)

MPI_Probe(q, 0, MPI_COMM_WORLD, &myStatus);      // wait, but don't consume
MPI_Get_count(&myStatus, MPI_CHAR, &count);      // now you know how big

Message length unknown

The length is a property of the string each rank built — computed here from the same ostringstream line, with the +1.

numProcs 10 sender q 7

Probe / Get_count / Recv is a pattern you will reuse all module: ask about the message before you accept it.

Mark this section done

The receive loop — rank 0 only

q = 1 … numProcs−1, in order. Rank 0 waits for rank 1 even if rank 9 is ready first.

for (int q = 1; q < numProcs; q++) {
    MPI_Probe(q, 0, MPI_COMM_WORLD, &myStatus);
    MPI_Get_count(&myStatus, MPI_CHAR, &count);
    char* buf = new char[count];
    MPI_Recv(buf, count, MPI_CHAR, q, 0, MPI_COMM_WORLD, &myStatus);
    std::cout << buf << "\n";
}

Step the loop

A model: each sender's greeting becomes ready at a different moment (the order is shuffled). Rank 0 can only take them in rank order. Step q and watch who waits for whom.

numProcs 10

This loop is a bottleneck. In three weeks (R03) you will put a number on it — and the collectives lecture replaces it.

Mark this section done

The barrier and the clock

Timing the wrong region is the most common way a scaling study quietly becomes fiction.

// No barrier. What is this actually measuring?
if (myRank == 0) timer.startTimer();

        ... the thing you think you are measuring ...

if (myRank == 0) timer.stopTimer();

It will give you a number. The number will look reasonable. It will be wrong in a specific, nameable way — name it.

Rank 0's clock is slower than the others', so the number is scaled wrong. Processes do not start at the same instant: rank 0 starts its clock before the others have even launched, and stops it while ranks may still be working. The timer is a local variable, so every rank has one and they are summed. Nothing — rank 0 is the only rank that matters, so its clock is the right one.

Without the first barrier you are timing startup skew — how staggered your launch was — and calling it your algorithm. Without the second, the clock stops when rank 0 is done, not when the last rank is.

MPI_Barrier(MPI_COMM_WORLD);
if (myRank == 0) timer.startTimer();

        ... the thing you are measuring ...

MPI_Barrier(MPI_COMM_WORLD);
if (myRank == 0) timer.stopTimer();

Same rule as Week 1: nobody touches a card until I say go, and the clock stops when the last person finishes — not the first.

What rank 0's clock measures

A model, in arbitrary time units: each rank launches at a different moment, then does its share of work. Compare the bracket (what rank 0's clock reports) against the honest number (the longest share of work).

p 4

The contract: one line your program owes the harness

std::cout << "ELAPSED " << timer.getElapsedTime() << std::endl;

The sweep script runs your binary once per process count, greps stdout for that word, and writes one CSV row per run. Delete the line and every row becomes NA — it will warn you on each run, and if you look away you come back to a file full of nothing.

Read harness/README.md before Friday. It explains what a sweep is, why every point is repeated, why you keep the minimum and not the mean, and the seven ways this normally goes wrong. Fifteen minutes, once, and it covers all eight labs. It is the only reading this week.

Mark this section done

Slurm: you do not run it. You ask for it to be run.

Cardinal: 378 Dell nodes, 39,312 cores, 96 usable cores per node, NDR200 InfiniBand. On Friday you use ten of those nodes, one process on each.

#!/bin/bash
#SBATCH --nodes=10
#SBATCH --ntasks-per-node=1
#SBATCH --time=1:00:00
#SBATCH --account=PCS0313

module load mvapich/4.1 boost/1.83.0

cd $SLURM_SUBMIT_DIR/Default && make OSC
cd $SLURM_SUBMIT_DIR

./harness/sweep.sh

`--time`	a promise. Overrun it and the job is killed
`--account`	PCS0313 — our class project. Every core-hour is billed to it
`sbatch`	submits and returns immediately. It does not wait, and neither should you
modules	per session. New shell, load them again. Half of "command not found" is this

Submit from the repository root, not from Default/. The harness resolves paths from the root.

Ten processes, two ways to place them

Same program. Same answer. Same number of processes. Commit to a number before you read anything else: how many times faster is the quicker one?

my number ×

Friday's job script uses --nodes=10 --ntasks-per-node=1 on purpose, so that every message in your sweep has to cross the wire. R01's What If asks you to predict what the other placement would have done instead. This page does not answer it. Being wrong costs you nothing — hedging costs you the exercise.

Mark this section done

Run it on Cardinal

The last five minutes of lecture, done at your own pace: account check, modules, the Template hello at p = 2, then a small sweep by hand. About 20 minutes.

Get a shell, then check your account

Open ondemand.osc.edu → Clusters → Cardinal Shell, or ssh. First connection shows a host-key fingerprint: verify it against OSC's published list once; do not just type yes.
```
ssh <your-username>@cardinal.osc.edu
id -nG | grep -i pcs0313
```
The grep should print a line containing PCS0313. If it prints nothing, tell the instructor now. A broken account found today is fixable; the same account found Friday costs you the lab.
Load the tools
```
module load mvapich/4.1 boost/1.83.0
```
Silence means success. Cardinal loads the Intel toolchain by default; we override it — mvapich is the MPI that knows about the InfiniBand, and boost we need from Week 6 on. Modules are per session: new shell, load them again.

Clone once, check out the lecture branch

git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/mpi.git mpi
cd mpi
git checkout -b Template class/Template

This is the src/main.cpp from the code walk. Friday's Lab 1 forks it as lab01.

Build, then get nodes of your own
```
cd Default && make OSC && cd ..
salloc --nodes=4 --ntasks-per-node=1 -c 2 --time=00:15:00 -A PCS0313
```
The login node is shared; time nothing there. Every run below is srun -c 2 -n p ./Default/MPI inside the allocation. If make says it cannot find mpicxx, step 2 did not happen in this shell.

Experiments

A · Hello at p = 2

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

What you should see

One greeting, Greetings from 1 of 2, printed by rank 0. A HOST line for each rank — two different hostnames, because the allocation puts one process per node. One ELAPSED line. Rank 0 sends nothing; it only receives.

B · A sweep by hand: p = 1, 2, 4

for p in 1 2 4; do
    echo "== p = $p"
    srun -c 2 -n $p ./Default/MPI | grep -E 'Greetings|ELAPSED'
done

What you should see

At p = 1, no greeting at all (the loop runs q = 1 … 0) and one ELAPSED. At p = 2 and p = 4, p − 1 greetings, always in rank order 1, 2, 3 — the loop asks for q in order, whatever order the messages became ready. Run p = 4 three times and compare the ELAPSED values: this is why the harness repeats every point and keeps the minimum.

C · The other placement

Release the four nodes, then ask for one node with four tasks on it.

exit
salloc --nodes=1 --ntasks-per-node=4 -c 2 --time=00:15:00 -A PCS0313
srun -c 2 -n 4 ./Default/MPI | grep -E 'HOST|ELAPSED'
exit

What you should see

Four HOST lines with the same hostname — the messages never leave the box. Write this ELAPSED next to experiment B's p = 4 value and compute the ratio yourself. The page does not tell you what it should be; that is R01's What If, and your written-down number from the Slurm screen is the one to compare against.

D · Leave off the +1 (optional)

In src/main.cpp, change msg.size() + 1 to msg.size() in the Send. Rebuild and run a few times inside an allocation.

cd Default && make OSC && cd ..
salloc --nodes=4 --ntasks-per-node=1 -c 2 --time=00:15:00 -A PCS0313
srun -c 2 -n 4 ./Default/MPI
srun -c 2 -n 4 ./Default/MPI
exit
git checkout src/main.cpp && cd Default && make OSC && cd ..

What you should see

Probably the correct three greetings. That is the point: the bug is invisible until it is not. It will eventually fail, and not reproducibly, because what follows the string in rank 0's buffer is whatever was there before. Put the +1 back before you leave.

Before Friday Sep 11 (Lab 1): account check passed, harness/README.md read (the only reading this week), and a prediction committed before you build anything. On Friday you fork the template, build it, run it at p = 2, submit a sweep at p = 1, 2, 4, 7, 10 with sbatch from the repository root, and leave with a commit hash and a job ID — not with results. Those come back from the queue.

Mark this section done

Concept map

Six separate rooms

Shared vs. distributed memory

SPMD, and the four calls every program has

The skeleton

Send and Receive

Which five must agree?

This compiles. It runs. Sometimes it prints garbage.

Ask before you accept

Message length unknown

The receive loop — rank 0 only

Step the loop

The barrier and the clock

What rank 0's clock measures

The contract: one line your program owes the harness

Slurm: you do not run it. You ask for it to be run.

Ten processes, two ways to place them

Run it on Cardinal

Get a shell, then check your account

Load the tools

Clone once, check out the lecture branch

Build, then get nodes of your own

Experiments

A · Hello at p = 2

B · A sweep by hand: p = 1, 2, 4

C · The other placement

D · Leave off the +1 (optional)

Check yourself