Supersteps and Message Bounds: Why Distributed Parallelism Costs More

A cluster is not a big shared-memory machine. Each node has its own memory, a message passing between two nodes costs a fixed latency plus a per-byte charge, and the network is a shared resource that all pairs contend for. In that setting an algorithm’s arithmetic is frequently not the term that decides its running time; the number of messages and the number of bytes do. The models that capture this rank algorithms differently from the PRAM, and the differences are large enough to reverse the ranking.

The superstep as the unit of cost

Valiant’s bulk-synchronous parallel model replaces the PRAM’s lockstep step with a superstep. Each superstep has three parts: a local computation using only the processor’s own memory, a communication phase in which each processor sends and receives a bounded number of messages, and a barrier that makes all messages visible before the next superstep begins. A BSP machine is described by three parameters: P processors, a per-processor rate g (the time to deliver one word through the network per processor), and a latency L (the fixed cost of the barrier and of a message in flight).

The cost of a superstep is w + h·g + L, where w is the maximum local work over processors and h is the maximum number of words sent or received by any one processor. Total time is the sum over supersteps. The L term is why supersteps should be few: a computation with a thousand supersteps pays a thousand latencies, and on a machine where L is microseconds that is milliseconds before any arithmetic.

The h-relation is the second constraint. If the total volume of data exchanged in a superstep is V words, then some processor must send or receive at least V/P words, so h ≥ V/P, and the superstep costs at least (V/P)·g. A communication pattern that sends every processor’s data to every other, an all-to-all, has V = P² and therefore h = P: the cost per superstep grows linearly with the processor count, which is why all-to-all exchanges are the operation that kills scaling.

Latency and bandwidth as separate currencies

The two network parameters do not scale together, and confusing them produces algorithms that are optimal in the wrong metric.

Bandwidth-limited patterns send few large messages. A streaming reduction where each processor sends its partial result to a neighbour, with the messages concatenated into a chain, moves the same total bytes as any other pattern but with P−1 messages of increasing size. The bytes dominate and the latency is amortised.

Latency-limited patterns send many small messages. A sparse graph traversal that requests individual neighbours from remote nodes sends one message per edge, and each message carries a few bytes and a node identifier. The payload is negligible and the per-message cost dominates; the algorithm is latency-bound and adding processors increases the number of messages.

The distinction predicts which optimisations help. For a bandwidth-bound kernel, the fix is to reduce the total volume through better blocking, compression, or an algorithm with a lower communication lower bound. For a latency-bound kernel, the fix is to aggregate: batch requests to the same node into one message, overlap communication with computation, or restructure so that a superstep carries many requests.

Overlap is the third lever, and it is the reason the BSP cost model is an upper bound rather than a description. In a real system a node can send while computing, so the communication of superstep i can hide under the computation of superstep i+1. A double-buffered implementation effectively removes the L term from all but the first and last supersteps. The model assumes no overlap; hardware permits it, and kernels that exploit it beat the model’s prediction by the overlap fraction.

Matrix multiplication as the worked case

Multiplying two n×n matrices on P processors is the canonical exercise, because the answer is not the obvious one. The arithmetic is Θ(n³), and a sequential implementation with blocked loops is bound by cache capacity rather than by the ALU. On a distributed machine the question is how much memory each processor needs, and how many words each must move.

The 2D algorithm divides the output into a √P × √P grid of blocks and assigns each processor one block, an n/√P × n/√P tile. Each processor holds one block of A and one block of B at a time, taken from its row and its column of the processor grid, and each block is broadcast to the other processors in that row or column. With blocks n/√P × n/√P the algorithm runs √P supersteps; each processor receives two blocks of (n/√P)² words per superstep, so the h-relation is Θ(n²/P) and the per-processor volume is Θ(n²/√P). Memory per processor is Θ(n²/P): the output tile plus the two blocks.

The lower bound says that any algorithm that computes the n³ products with each processor holding at most M words must move at least Ω(n³/(P√M)) words per processor. At M = Θ(n²/P) that evaluates to Ω(n²/√P), so the 2D algorithm is optimal when the matrices barely fit. The bound improves if each processor holds more memory: at M = Θ(n²/P^{2/3}) it falls to Ω(n²/P^{2/3}), and the 3D algorithm attains it by replicating the inputs across a third grid dimension of size P^{1/3} and reducing over it. The cost is memory, a factor of P^{1/3} more per processor, and the benefit is a factor of P^{1/6} less communication.

The comparison is the point. The 2D algorithm is optimal in the abstract work model and optimal among algorithms with minimal memory; it is not optimal for the machine, because the machine has memory to spare and the network is the scarce resource. Choosing between the two is choosing how to spend memory to buy bandwidth, and the lower bound is what makes the choice quantitative rather than a guess. This is the distributed counterpart of the cache-blocking argument in the PRAM discussion, and the exponents differ because the cost being minimised differs.

Sorting across a network

Sorting shows the same pattern with a different structure. On a shared-memory machine, a parallel sort partitions the input, sorts each partition locally, and merges with merge-path partitioning, and the only shared-memory traffic is the merge’s boundary search.

On a distributed machine the same algorithm becomes a sample sort: each processor sorts its local block, takes a sample of its elements, all samples are gathered and sorted to choose P−1 splitters, each processor sends its elements to the processor whose range they fall in, and each processor sorts what it receives. The communication is one all-to-all of n words in total plus one all-to-all of P·s sample words, so h = Θ(n/P + P·s) per superstep. The volume Θ(n) is optimal up to the sample term, and the algorithm needs two supersteps rather than one, because the splitters cannot be chosen until the samples have been gathered.

The regularity that makes sample sort work is that the data can be redistributed without knowing which element goes where in advance — only which range it falls in. For problems where the destination depends on the data in a finer way, such as a graph partition, the all-to-all is unavoidable and h grows with the irregularity. This is the general shape of the difficulty: the lower bound is on volume, and the achievable volume depends on how much structure the algorithm can impose on the data movement.

Diagnosing the bound that binds

Three questions separate a communication-bound kernel from an arithmetic-bound one, and the answers come from counting rather than from measurement.

How many words must move? Compare the algorithm’s per-processor volume against the lower bound for its problem class. For matrix multiplication the bound is Ω(n³/(P√M)) words per processor; for sorting, an element that starts on the wrong processor has to cross the network, so no algorithm moves fewer than Θ(n) words in total; for a dense linear solve the bound is Θ(n²/√P) words per processor, the same exponent structure as multiplication.

How many messages? Divide the volume by the largest message the pattern allows. If the result is comparable to the superstep count times P, the kernel is latency-bound and message aggregation is the lever.

How much can overlap? Compare the communication time of one superstep to the computation time of the next. If communication is smaller, the L and h·g terms hide and the model’s prediction is pessimistic; if it is larger, no amount of overlap saves the kernel and the algorithm must be changed.

The answers determine whether the next step is a better implementation or a different algorithm. A kernel whose volume is already at the lower bound cannot be improved by tuning the network path; it needs more memory per processor, a different decomposition, or a problem-specific structure that reduces the required exchange. That is the same conclusion the cache-oblivious analysis reaches one level down, and it is why communication, not arithmetic, is the quantity that parallel algorithm design at scale is actually about.

The final correction is that the bounds are asymptotic and the constants are large. A kernel that moves a factor of two more words than optimal may still be the fastest available implementation if its messages are larger and its supersteps fewer. The bounds rank algorithms; they do not measure them.