The idea: processes that share nothing and talk by messages
MPI (the Message Passing Interface) is how most programs on clusters and supercomputers run in parallel. You start one program many times, for example mpirun -np 8 ./prog. Each copy is a separate process called a rank, numbered 0 to 7, in the group MPI_COMM_WORLD. A rank finds its number with MPI_Comm_rank and the group size with MPI_Comm_size, and then does its own part of the work. The ranks share no memory. The only way to get data from one rank to another is to send it in a message.
The canvas shows the 8 ranks as boxes. Each box has the rank's data and what it is doing: waiting inside a call, blocked, or done. Time is counted in rounds: in one round every rank can send one message and receive one, all at the same time. The counters at the top add up the rounds and messages.
| On the page | Meaning |
|---|---|
| data | a message that carries data: a value, blocks, a partial sum |
| RTS / CTS (orange) | small control messages of the rendezvous protocol: request to send, clear to send |
| blocked (red) | a rank stuck in a call that can never finish |
| done | the rank's call has returned |
| schedule panel | one row per round, time going down; a dot means the rank holds data for the call, an arrow is a message |
MPI_Send and MPI_Recv
The two basic calls are MPI_Send(buf, count, datatype, dest, tag, comm) and MPI_Recv(buf, count, datatype, source, tag, comm, &status). Every message has an envelope: the source rank, a tag (a number you choose) and the communicator. A receive takes a message only if its envelope matches; it can also accept any sender or any tag with MPI_ANY_SOURCE and MPI_ANY_TAG. Two messages from the same sender with the same tag arrive in the order they were sent.
What "blocking" really means: eager and rendezvous
MPI_Recv is simple: it returns when the message is in your buffer. MPI_Send is the subtle one. It is called blocking, but the standard only promises that it returns when you may reuse the send buffer. It does not promise that the message has arrived, or even that a receive exists. How it gets there is up to the library:
- Eager (small messages): the library sends the data at once. If the receiver has not called
MPI_Recvyet, the message waits in its unexpected-message queue.MPI_Sendreturns right away. - Rendezvous (large messages): the library cannot buffer megabytes for every sender. It sends only the envelope, a request to send (RTS). The receiver answers clear to send (CTS) once a matching receive is posted, and only then does the data go.
MPI_Sendwaits all that time.
The size where one turns into the other is the eager limit. It depends on the library and the network; for example, Open MPI's TCP transport uses 64 KiB by default. The page uses 64 KB, so 1 KB is eager and 1 MB is rendezvous. In Demo 1 rank 0 sends 1 MB while rank 1 is already receiving: RTS, CTS, data, then the same the other way, 6 messages, and it works at any size.
Both ranks send first: a deadlock that depends on the size
A common way to swap data is for both ranks to call MPI_Send and then MPI_Recv. With 1 KB it works (Demo 2): both messages go eagerly, wait in the queues, and both receives find them. With 1 MB it hangs (Demo 3): both ranks send an RTS and wait for a CTS, but a CTS needs a posted receive, and each rank posts its receive only after its send returns. Each rank waits for the other, for ever.
The MPI standard calls a program that only works because of buffering unsafe. It may pass every test with small inputs and hang in production. To find such code, replace MPI_Send with MPI_Ssend (synchronous send), which always waits for the matching receive: an unsafe program then deadlocks even at 1 KB. The fixes:
- Order the calls: one rank sends first, the other receives first (Demo 1). In a ring, even ranks send first and odd ranks receive first.
MPI_Sendrecv: one call that posts the receive and the send together (Demo 4). Both RTS find a posted receive, and the swap takes 3 rounds instead of 6.MPI_IsendandMPI_Irecv, which return at once with a request, thenMPI_Waitall.
Collectives: every rank makes the same call
Many patterns involve all ranks, so MPI has collective operations. Every rank in the communicator calls the same function, and one rank is often the root (rank 0 here).
| Call | Before | After |
|---|---|---|
MPI_Bcast | root has n = 42 | every rank has 42 |
MPI_Scatter | root has blocks A–H | rank r has block r |
MPI_Gather | rank r has block r | root has A–H in rank order |
MPI_Reduce with MPI_SUM | ranks have 3 1 4 1 5 9 2 6 | root has 31 |
MPI_Allreduce with MPI_SUM | ranks have 3 1 4 1 5 9 2 6 | every rank has 31 |
A collective is not a barrier. A rank returns as soon as its own part is finished, so on the canvas some ranks turn done while others are still waiting.
Trees: log₂ p rounds instead of p − 1
The simple way to broadcast is linear: the root sends to rank 1, then rank 2, and so on. The root can send only one message per round, so that takes p − 1 = 7 rounds. A binomial tree lets every rank that already has the value pass it on. In round 1 rank 0 sends to rank 4; in round 2 ranks 0 and 4 send to 2 and 6; in round 3 four ranks send to the other four. The number of ranks with the value doubles each round, so it takes log₂ 8 = 3 rounds (Demo 5). The tree still sends 7 messages; it just sends many of them at the same time.
Gather and Reduce use the same tree upside down. In round 1 ranks 1, 3, 5 and 7 send to 0, 2, 4 and 6; in round 3 rank 4 sends to rank 0. For Reduce, each receiver adds what it gets: 3 + 1 = 4, 4 + 1 = 5, 5 + 9 = 14, 2 + 6 = 8, then 9 and 22, then 31. With the linear version rank 0 has to receive all 7 values itself, one per round (Demo 6). Scatter on the tree sends whole halves: rank 0 sends E–H to rank 4, which passes G–H to rank 6. That is 12 blocks moved instead of 7, in 3 rounds instead of 7.
| p ranks | linear rounds | tree rounds | messages (both) |
|---|---|---|---|
| 8 | 7 | 3 | 7 |
| 64 | 63 | 6 | 63 |
| 1024 | 1023 | 10 | 1023 |
Each round costs at least the network latency, a few microseconds. So the round count is what matters for small messages, and at 1024 ranks the tree is about 100 times faster.
Allreduce by recursive doubling
MPI_Allreduce could be a Reduce followed by a Bcast: 6 rounds on trees, 14 linear. Recursive doubling does it in 3 rounds. In round 1 every rank swaps its value with rank r XOR 1 (0 with 1, 2 with 3, …) and adds: the values become 4 4 5 5 14 14 8 8. In round 2 it swaps with r XOR 2: 9 9 9 9 22 22 22 22. In round 3 with r XOR 4: 31 on every rank (Demo 7). The price is more messages: all 8 ranks send in every round, 8 × 3 = 24, against 14 for Reduce + Bcast.
A parallel sum
Demo 8 adds 1 + 2 + … + 16 on 8 ranks. MPI_Scatter gives each rank two numbers (rank 0 gets 1 and 2, rank 7 gets 15 and 16). Each rank adds its own two: 3, 7, 11, …, 31. That is the only real work, and all 8 ranks do it at once. MPI_Reduce adds the 8 local sums on rank 0: 136. The work took one round; moving the data took 3 + 3 = 6 rounds and 14 messages. With only two numbers per rank, communication costs far more than the work. Real programs give each rank millions of numbers, so the local work is large and the messages are few. How much a fixed amount of communication limits the speedup is the subject of Amdahl's and Gustafson's laws.
MPI is explicit: you choose which rank sends what to whom. MapReduce is the opposite approach, where you write map and reduce and the framework moves the data and survives crashes. MPI ranks usually run on separate machines with distributed memory; Parallel Hardware compares that with shared-memory multicores.
See also OpenMP loop scheduling, the shared-memory side of parallel programming, where reduction(+:sum) does what MPI_Reduce does across ranks.
See also Parallel Prefix Sum, where the same tree reduction becomes the up-sweep of Blelloch's scan on a shared-memory PRAM.
What the page leaves out
Real MPI libraries pick an algorithm per call from the message size and the number of ranks. For large messages, Bcast is often a Scatter followed by an Allgather, and Allreduce a reduce-scatter followed by an allgather (Rabenseifner's algorithm), which move less data than the trees here. When p is not a power of two the trees get uneven. Left out: MPI_Allgather, MPI_Alltoall, MPI_Barrier, derived datatypes, communicators other than MPI_COMM_WORLD, non-blocking collectives, one-sided communication, and the exact cost of a message (latency plus size divided by bandwidth). Simplifications: one message per rank per round, every message takes one round whatever its size, the eager limit is fixed at 64 KB, and the root is always rank 0. Floating-point sums can differ slightly with the order of the additions, which depends on the algorithm.