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.

The MPI Mental Model

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;
}

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

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

Worked Example: The Deadlock Everyone Writes Once

Two ranks swap data. Every rank runs the same three lines — SPMD, as always.

int partner = 1 - rank;                    // 0 <-> 1

MPI_Send(sendbuf, n, MPI_DOUBLE, partner, 0, MPI_COMM_WORLD);
MPI_Recv(recvbuf, n, MPI_DOUBLE, partner, 0, MPI_COMM_WORLD, &status);

Three fixes, worst to best

if (rank % 2 == 0) {
    Send(); Recv();
} else {
    Recv(); Send();
}

MPI_Sendrecv(
  sendbuf,n,...,partner,0,
  recvbuf,n,...,partner,0,
  comm, &status);

MPI_Isend(..., &req[0]);
MPI_Irecv(..., &req[1]);
/* do useful work! */
MPI_Waitall(2, req, ...);

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).

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]

Worked Example: Trace Four Collectives

Rank 0 starts with [10, 20, 30, 40, 50, 60, 70, 80]. Four ranks. Sum it. Watch exactly what each rank holds after each call.

Lab 2: Parallel Sort — The Four Moves

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

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

Worked Example: When Is MPI Actually Worth It?

Sum 1 billion doubles (8 GB). One second serially. Three ways to do it in parallel — and the winner is not the one with the most machines.

You Already Know This Pattern

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

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.