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.

Eight boxes, rank 0 to rank 7, each with its own memory, all running the same program. Below them a network line connects all eight. A message labelled MPI_Send from rank 0 to MPI_Recv on rank 1 travels over the network.
One program, eight processes, eight separate memories: a value moves from rank 0 to rank 1 only if rank 0 sends it and rank 1 receives it.

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 pageMeaning
dataa 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
donethe rank's call has returned
schedule panelone 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_Recv yet, the message waits in its unexpected-message queue. MPI_Send returns 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_Send waits 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.

Three time-down diagrams with rank 0 and rank 1. Eager, 1 KB: one data arrow, MPI_Send returns at once, the message waits in rank 1's queue until MPI_Recv. Rendezvous, 1 MB: RTS from rank 0, CTS back once MPI_Recv is posted, then the data; MPI_Send returns after the data. Deadlock: both ranks send RTS to each other, neither posts a receive, so no CTS ever comes and both stay blocked in MPI_Send.
The same MPI_Send returns at once for 1 KB, waits for the receiver for 1 MB, and never returns if both ranks send 1 MB first.

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_Isend and MPI_Irecv, which return at once with a request, then MPI_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).

CallBeforeAfter
MPI_Bcastroot has n = 42every rank has 42
MPI_Scatterroot has blocks A–Hrank r has block r
MPI_Gatherrank r has block rroot has A–H in rank order
MPI_Reduce with MPI_SUMranks have 3 1 4 1 5 9 2 6root has 31
MPI_Allreduce with MPI_SUMranks have 3 1 4 1 5 9 2 6every 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.

Two time-down schedules for broadcasting from rank 0 to 8 ranks. Left, linear: 7 rows, in each row rank 0 sends one arrow, to rank 1, then 2, and so on up to 7. Right, binomial tree: 3 rows; row 1 has one arrow 0 to 4, row 2 has 0 to 2 and 4 to 6, row 3 has four arrows 0 to 1, 2 to 3, 4 to 5 and 6 to 7.
Both send 7 messages, but the tree sends them 1, 2 and 4 at a time and finishes in 3 rounds instead of 7.

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 rankslinear roundstree roundsmessages (both)
8737
6463663
10241023101023

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.

On the mind map

Open the Computer Architecture mind mapComputerArchitectureAbstraction and numbers: layers and bit patternsAbstraction and numbersCombinational logic: output depends only on inputsCombinational logicSequential logic: state held by a clockSequential logicMIPS software: how C becomes machine wordsMIPS softwareThe processor: datapath plus controlThe processorPipelines and parallelism: more instructions at oncePipelines and parallelismMemory and I/O: small fast near, big slow farMemory and I/OMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches splitOpen the Computer Architecture mind mapComputer Architecturemore instructions at oncePipelines and parallelismMIPS pipelineMIPS pipelineforward data, stall on load-useBranch predictionBranch prediction2-bit counters guess, flush if wrongOut-of-order executionOut-of-order executionrenaming removes WAR and WAW hazardsSIMD, threads, multicoreSIMD, threads, multicoreAmdahl's law caps the speedupAmdahl vs GustafsonAmdahl vs Gustafsonfixed job caps at 1/s; scaled growsMPI Send/Recv & CollectivesTrees: log₂ p rounds; Send may blockParallel Prefix SumParallel Prefix SumBlelloch: 2(n−1) work, 2 log n spanOpenMP loop schedulesOpenMP loop schedulesUneven costs: dynamic beats static blocksGPU and SIMT warpsGPU and SIMT warps32 lanes, one instruction; branches split
This page on the Computer Architecture mind map · 42 pages in 7 branches · open it to see the whole map and test yourself in recall mode.