Unit IV — Programming Models & Tools

MPI: Message Passing

Session 11 • 2311CSC501J — Parallel Processing • Lab 2: Parallel Sort

What You'll Learn

Processes, ranks & the communicator (SPMD)
Point-to-point: Send / Recv
Collectives: Bcast, Scatter, Gather, Reduce
Lab 2: a distributed parallel sort

"Shared memory stops at the edge of one machine. Message passing is how thousands of machines cooperate."

— the whole point of MPI

Shared Memory Hits a Wall

OpenMP (Session 10) was easy — but it can't leave the box

OpenMP threads all share one memory on one machine.
A single server maxes out at ~64–128 cores and a few TB of RAM. Then you're stuck.
Weather models, AI training, and physics simulations need thousands of machines.

MPI = Message Passing Interface. The standard for distributed-memory parallelism: many machines, each with its own private memory, cooperating by explicitly sending messages to each other.

Shared memory (OpenMP)

Threads read/write the same RAM. No copying — but bounded by one machine.

Distributed memory (MPI)

No shared RAM. Data moves only by messages — but scales to a whole cluster.

The MPI Mental Model

MPI runs processes, not threads. mpirun -np 4 launches 4 full copies of your program — each with its own private memory. They cannot see each other's variables. Ever.

Term	Meaning
Process	One running copy of your program, with its own memory
Rank	A process's unique id: 0, 1, ... size−1 (its "jersey number")
Size	How many processes there are in total
Communicator	`MPI_COMM_WORLD` — the group of all processes

SPMD = Single Program, Multiple Data (callback to Flynn, Session 02). One source file, run by every process; each behaves differently based on its rank. if (rank == 0) { ... } is how one process plays "master."

The Four Lines Every MPI Program Has

#include <mpi.h>

int main(int argc, char **argv) {
    MPI_Init(&argc, &argv);                   // 1. start MPI (first call)

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);      // 2. which process am I?
    MPI_Comm_size(MPI_COMM_WORLD, &size);      // 3. how many of us?

    printf("Hello from rank %d of %d\n", rank, size);

    MPI_Finalize();                           // 4. shut MPI down (last call)
    return 0;
}

Compile & run

mpicc hello.c -o hello
mpirun -np 4 ./hello

Output (order varies!)

Hello from rank 2 of 4
Hello from rank 0 of 4
Hello from rank 3 of 4
Hello from rank 1 of 4

The print order changes between runs — the processes run truly at once. That non-determinism is your first sign of real parallelism.

Point-to-Point: Send & Recv

One process hands a value directly to another. The two most fundamental MPI calls:

MPI_Send(&value, count, MPI_INT, dest,   tag, MPI_COMM_WORLD);
MPI_Recv(&value, count, MPI_INT, source, tag, MPI_COMM_WORLD, &status);
//        buffer  how-many  type   who    label  group

⚠ The deadlock trap

Send/Recv are blocking. If both processes call Recv first, each waits for a message the other hasn't sent — forever. Rule: order them so somebody sends before everybody receives.

Non-blocking MPI_Isend / MPI_Irecv return immediately (you MPI_Wait later). They let you overlap communication with computation and sidestep the deadlock.

Collectives: The Workhorses

You could build everything from Send/Recv — but you shouldn't. Collectives move data among all processes at once, and the library does it far more efficiently (often log(P) steps).

Collective	What it does
`MPI_Bcast`	Root sends one value to every process
`MPI_Scatter`	Root splits an array — one chunk to each process
`MPI_Gather`	Inverse of Scatter: collect chunks back onto root
`MPI_Reduce`	Combine values (sum, max, ...) onto root
`MPI_Allreduce`	Like Reduce, but every process gets the result

Scatter = fan-out, Reduce = fan-in. Together they are the map-reduce pattern — the same shape as the data jobs behind every large-scale analytics system.

Seeing the Collectives

BROADCAST                      SCATTER
  root: [7]                      root: [10 20 30 40]
        |                              |    |   |   |
   +----+----+----+             +------+    |   |   +------+
   v    v    v    v             v           v   v          v
 [7]  [7]  [7]  [7]           [10]       [20] [30]       [40]
 r0   r1   r2   r3            r0         r1   r2         r3


GATHER                         REDUCE (MPI_SUM)
 [10] [20] [30] [40]           [10] [20] [30] [40]
   |    |    |    |               \    \   /    /
   +----+----+----+                +---(+)---+
        v                              v
 root: [10 20 30 40]           root: [100]

Open 05-collectives.html from the Examples page to watch these animate. Every distributed algorithm is built by composing these four moves.

Lab 2: Parallel Sort — The Four Moves

Sorting a huge array on one machine is slow. Split the work across processes:

1. Scatter

Rank 0 splits the array into equal chunks, one per process.

2. Local sort

Each process sorts its own chunk (qsort) — all at the same time.

3. Gather

Sorted chunks return to rank 0 — now size sorted runs side by side.

4. Merge

Rank 0 does a cheap k-way merge of the sorted runs into one sorted array.

Do the expensive sorting in parallel, then pay a small, linear merge at the end. This is the sort phase of MapReduce and of real distributed sorts.

Lab 2: The Code, In One Picture

rank 0 builds:  [42 7 91 15 | 3 88 60 25]   (unsorted, 8 elements, 2 procs)

  MPI_Scatter  ->  rank 0: [42 7 91 15]    rank 1: [3 88 60 25]
  qsort (local)->  rank 0: [7 15 42 91]    rank 1: [3 25 60 88]   // both at once
  MPI_Gather   ->  rank 0: [7 15 42 91 | 3 25 60 88]   (two sorted runs)
  k-way merge  ->  rank 0: [3 7 15 25 42 60 88 91]     // fully sorted!

MPI_Scatter(data, per, MPI_INT, chunk, per, MPI_INT, 0, MPI_COMM_WORLD);
qsort(chunk, per, sizeof(int), cmp_int);          // each process, in parallel
MPI_Gather(chunk, per, MPI_INT, gathered, per, MPI_INT, 0, MPI_COMM_WORLD);
if (rank == 0) k_way_merge(gathered, size, per, sorted);

Full commented source: examples/04-parallel-sort.c. Scatter/Gather need equal chunks, so the total size divides evenly by the process count.

OpenMP vs MPI

	OpenMP (S10)	MPI (this session)
Unit of work	Threads	Processes
Memory	Shared	Private (per process)
Scale	One machine	Thousands of machines
Data sharing	Automatic (same RAM)	Explicit messages
Effort	Add a pragma	Rewrite around messages

Hybrid MPI + OpenMP is the real supercomputer recipe: MPI between nodes, OpenMP within each node. Messages across the cluster, shared memory inside each box.

You Already Know This Pattern

MPI is distributed systems with a different vocabulary. Every idea maps to something you'll build in production:

In MPI	In the systems you build
`MPI_Send` / `MPI_Recv`	A message on a queue / an RPC between services
`MPI_Scatter` + `MPI_Reduce`	Fan-out to workers, fan-in the results (map-reduce)
`MPI_Bcast`	Push config/state to every worker at once
Send/Recv deadlock	Two services each waiting on the other — a distributed deadlock

The parallel-sort you'll write in Lab 2 is exactly how a data warehouse sorts a table too big for one machine: shard it, sort each shard, merge. Same idea, thread → core → node → cluster.

Recap & What's Next

Key Takeaways

MPI = processes with private memory, cooperating by messages — it scales past one machine.
Every program: Init → Comm_rank / Comm_size → work → Finalize.
Send/Recv are point-to-point and blocking — mind the deadlock order.
Prefer collectives (Bcast/Scatter/Gather/Reduce) — the map-reduce workhorses.
Lab 2: scatter → local sort → gather → merge = a distributed sort.

Homework

Run 01-hello-mpi.c with -np 2, 4, 8; note how the print order changes.
Modify 03-collectives.c to compute the maximum instead of the sum (MPI_MAX).
Trace Lab 2 by hand for 6 numbers on 2 processes: scatter, sort, gather, merge.

Next session: CUDA & the Modern GPU Stack

From a cluster of CPUs to the thousands of cores inside one GPU.