Communication Cost Models

"They told me to compute faster. I compute instantly now. I am still slow, because I spend my life waiting for the first byte to arrive."

A GPU Idling on a Communication Barrier

Distribution moves data, and moving data takes time that computation cannot hide for free. When eight workers each finish their share of a gradient, they must combine those partial results before the next step can begin, and that combine travels over wires with finite speed. To decide whether adding machines actually helps, you need a model of communication time that is simple enough to compute in your head yet faithful enough to predict the shape of real measurements. The standard such model, borrowed from decades of high-performance computing and used unchanged for distributed deep learning, describes the cost of a single message with just two constants. Everything in this section is an application of that two-constant model to the collective operations that synchronize distributed training.

1. The Alpha-Beta Model of a Single Message Beginner

Consider sending $n$ bytes from one machine to another. Empirically, the time this takes is well described by a straight line in $n$,

where $\alpha$ is the per-message latency (the fixed startup cost paid once per message regardless of size, measured in seconds) and $\beta$ is the inverse bandwidth (the marginal cost per byte, measured in seconds per byte, so that $1/\beta$ is the link bandwidth in bytes per second). The latency $\alpha$ bundles together the software overhead of issuing the transfer, the time for the first bits to traverse the link, and any per-message protocol cost; the bandwidth term $n\beta$ is the time to push the actual payload through a pipe of finite width. On a fast GPU interconnect, $\alpha$ is on the order of a few microseconds and $1/\beta$ is on the order of tens to hundreds of gigabytes per second. These two numbers are the entire model.

The model is useful precisely because the two terms dominate in different regimes. For a tiny message, $n\beta$ is negligible and $T(n) \approx \alpha$: the cost is the fixed overhead of having a message at all, so sending one byte costs almost the same as sending a thousand. For a huge message, $\alpha$ is negligible and $T(n) \approx n\beta$: the cost is just the payload divided by the bandwidth. The message size at which the two terms are equal, $n = \alpha/\beta$, is the boundary between these two worlds, and it is the single most important quantity for choosing a communication strategy. We will name those two worlds, latency-bound and bandwidth-bound, in Section 4 and use the boundary to explain a measured crossover.

The model deliberately ignores a great deal: network congestion, contention when many messages share a link, the topology of the switches, and the overlap of communication with computation. Those refinements matter for precise performance tuning, and Chapter 4 brings the relevant ones back when it studies real interconnects and topology-aware placement. For the purpose of deciding "will this collective be fast enough, and how does its cost grow with the number of workers?", the two-constant line is accurate enough to be the right first tool, and wrong only in ways that make it conservative.

2. From One Message to a Collective Intermediate

A collective operation involves all $K$ workers and combines their data into a shared result. The all-reduce you met in Section 1.1, where every worker contributes a vector and every worker ends up holding the elementwise sum, is the collective that synchronizes gradients in data-parallel training, so it is the one whose cost we most want to predict. A naive implementation sends every worker's vector to a single coordinator, sums there, and broadcasts the result back; that coordinator's link carries $K$ vectors in and $K$ vectors out, so the cost grows linearly with $K$ and the coordinator becomes a bottleneck. The whole art of collective algorithms is to avoid that linear-in-$K$ bandwidth term.

The algorithm that made large-scale data-parallel deep learning practical is ring all-reduce. The $K$ workers are arranged in a logical ring; each sends only to its right neighbor and receives only from its left. The vector of $n$ bytes is split into $K$ slices. In a first phase of $K-1$ steps (reduce-scatter), each worker forwards and accumulates one slice at a time, so that after the phase each worker owns the fully summed value of exactly one slice. In a second phase of $K-1$ steps (all-gather), those completed slices circulate around the ring until every worker holds all of them. Across both phases each worker sends $2(K-1)$ messages, and every message carries one slice of size $n/K$ bytes.

Multiplying message count by per-message cost gives the ring all-reduce time under the alpha-beta model. Each of the $2(K-1)$ messages costs $\alpha + (n/K)\beta$, so

The bandwidth term is the remarkable one. The factor $2(K-1)/K = 2 - 2/K$ rises from $1$ at $K=2$ toward $2$ as $K$ grows, and then stays there: doubling the number of workers from 512 to 1024 barely changes it. So the bytes-on-the-wire cost of a ring all-reduce is essentially $2n\beta$, independent of how many workers participate. That near-independence is exactly why ring all-reduce scaled deep learning to thousands of GPUs. The price you pay for it is the latency term $2(K-1)\alpha$, which grows linearly with $K$: more workers means more hops around the ring, each costing one $\alpha$. The whole behavior of the collective is a tug-of-war between a bandwidth term that ignores $K$ and a latency term that scales with it.

3. Modeling All-Reduce in Code Intermediate

The formula is easy to mistrust until you watch the two terms move. The program below fixes a representative interconnect ($\alpha = 5$ microseconds, $1/\beta = 100$ gigabytes per second), implements $T_{\text{ring}}(n, K)$ directly, and then does two things: it holds the message size fixed and sweeps the worker count $K$ to show the bandwidth term flattening, then it holds $K$ fixed and sweeps the message size $n$ to show the crossover from latency-bound to bandwidth-bound. No network is involved; this is the cost model itself, evaluated.

import numpy as np

# alpha-beta model parameters for one representative GPU interconnect.
alpha = 5e-6        # per-message latency: 5 microseconds
beta  = 1.0 / 100e9 # inverse bandwidth: 1 / (100 GB/s), seconds per byte

def ring_allreduce_time(n_bytes, K):
    """Ring all-reduce of an n_bytes buffer across K workers.

    2*(K-1) steps total (reduce-scatter then all-gather), each moving a
    1/K slice. Bandwidth term ~ 2*(K-1)/K * n*beta (nearly K-independent);
    latency term 2*(K-1)*alpha grows with K.
    """
    lat = 2 * (K - 1) * alpha
    bw  = 2 * (K - 1) / K * n_bytes * beta
    return lat, bw, lat + bw

# (1) Bandwidth term is nearly independent of K; latency term grows with K.
n = 100 * 1024**2   # 100 MiB gradient buffer
print(f"Ring all-reduce of a {n//1024//1024} MiB buffer, latency vs bandwidth split:")
print(f"{'K':>5} {'latency(ms)':>12} {'bandwidth(ms)':>14} {'total(ms)':>11} {'BW factor 2(K-1)/K':>20}")
for K in [2, 4, 8, 16, 64, 256, 1024]:
    lat, bw, tot = ring_allreduce_time(n, K)
    print(f"{K:>5} {lat*1e3:>12.4f} {bw*1e3:>14.3f} {tot*1e3:>11.3f} {2*(K-1)/K:>20.4f}")

# (2) Crossover from latency-bound to bandwidth-bound as message size grows.
K = 16
crossover = None
for n in [64, 1024, 16*1024, 256*1024, 4*1024**2, 64*1024**2, 1024**3]:
    lat, bw, tot = ring_allreduce_time(n, K)
    regime = "latency-bound" if lat > bw else "bandwidth-bound"
    if crossover is None and bw >= lat:
        crossover = n
    # ... printed per row in the full script

alpha (latency)        : 5.0 us
beta  (inverse BW)     : 1.00e-11 s/byte  (100 GB/s)

Ring all-reduce of a 100 MiB buffer, latency vs bandwidth split:
    K  latency(ms)  bandwidth(ms)   total(ms)   BW factor 2(K-1)/K
    2       0.0100          1.049       1.059               1.0000
    4       0.0300          1.573       1.603               1.5000
    8       0.0700          1.835       1.905               1.7500
   16       0.1500          1.966       2.116               1.8750
   64       0.6300          2.064       2.694               1.9688
  256       2.5500          2.089       4.639               1.9922
 1024      10.2300          2.095      12.325               1.9980

Crossover for K=16: regime is latency-bound until n*beta per slice
       bytes  latency(ms)  bandwidth(ms)           regime
          64       0.1500         0.0000    latency-bound
        1024       0.1500         0.0000    latency-bound
       16384       0.1500         0.0003    latency-bound
      262144       0.1500         0.0049    latency-bound
     4194304       0.1500         0.0786    latency-bound
    67108864       0.1500         1.2583  bandwidth-bound
  1073741824       0.1500        20.1327  bandwidth-bound

Latency and bandwidth terms cross near n = 65536 KiB for K=16.
Below the crossover, more messages (latency) dominate; above it, bytes (bandwidth) dominate.

Read the first block as a story about scaling out. For a large gradient buffer the bandwidth term is the same 2 milliseconds whether you use 8 workers or 1024, which is the property that lets data-parallel training add machines almost for free as far as the payload is concerned. The total time still grows, but only through the latency term, which climbs from 0.07 ms at $K=8$ to 10.2 ms at $K=1024$. For small buffers, where the bandwidth term is tiny, that latency growth is the entire cost, and it is why synchronizing many small tensors separately is far slower than fusing them into one large transfer, a real optimization that Chapter 4 calls gradient bucketing.

4. Bandwidth-Bound and Latency-Bound Regimes Intermediate

The second block of Output 3.8.1 is the practical heart of the section. Holding $K$ fixed and growing the message, the cost is flat (set entirely by $2(K-1)\alpha$) until the message is large, then rises linearly (set by $2n\beta/K \cdot K$, the bandwidth term). The label flips from latency-bound to bandwidth-bound between a 4 MiB and a 64 MiB buffer, which is the crossover that Figure 3.8.1 drew abstractly. A workload that lives to the left of this crossover, exchanging many small messages, is latency-bound: its time is dominated by message count, and the remedy is to send fewer, larger messages or to use an algorithm with fewer hops. A workload to the right is bandwidth-bound: its time is dominated by total bytes, and the remedy is to move fewer bytes (gradient compression, lower precision) or to buy more bandwidth.

This single distinction decides which collective algorithm you should choose, and the choice flips with scale. Ring all-reduce minimizes the bandwidth term but pays $2(K-1)\alpha$ in latency, so it is the right tool for large messages on moderate worker counts but degrades when $K$ is huge and messages are small. A tree- or recursive-halving all-reduce has a latency term that grows only like $\log K$, so it wins in the latency-bound regime even though it moves more bytes. There is no universally best collective; there is only the algorithm whose dominant term matches the regime your message size and worker count put you in, and the alpha-beta model is what tells you which regime that is before you run anything.

# Build once, then run an all-reduce sweep across the visible GPUs.
# -b start size, -e end size, -f doubling factor, -g GPUs per process.
./build/all_reduce_perf -b 8 -e 1G -f 2 -g 8
# Output columns: size(B)  time(us)  algbw(GB/s)  busbw(GB/s)
#  small sizes  -> time ~ constant   (you are reading alpha, latency-bound)
#  large sizes  -> busbw -> plateau  (you are reading 1/beta, bandwidth-bound)

5. Why This Is the Backbone for Later Chapters Advanced

The alpha-beta model is not a self-contained curiosity; it is the costing function that every later parallelism decision plugs into. When Chapter 4 compares ring, tree, and recursive-halving all-reduce, it is comparing their $\alpha$ and $\beta$ terms under the model you just built. When Chapter 16 chooses how to split a model across data, tensor, pipeline, and expert dimensions (the so-called 3D parallelism), the trade-off between those dimensions is fundamentally a trade-off between collectives with different message sizes and worker counts, and the alpha-beta cost of each is what makes one layout faster than another. Tensor parallelism does frequent small all-reduces (latency-sensitive, so it wants the fastest intra-node links), while data parallelism does infrequent large ones (bandwidth-sensitive, so it tolerates slower inter-node links). That entire placement logic is the alpha-beta model applied to each collective in turn.

You now have the third performance wall to set beside compute and memory: the network, modeled as $\alpha + n\beta$ per message and assembled into collective costs whose dominant term you can read off in advance. The next section, Section 3.9, combines this communication cost with the compute and scaling laws of the rest of the chapter into a single accounting of scaling efficiency and dollars, so that the question "how many machines should I use?" becomes one you answer with a cost curve rather than a hunch.