Network Congestion as the Dominant Factor in Cache Coherence Latency — Epoche C1
Where the time goes in a large machine Take a chip with 1024 cores connected as a 32-by-32 grid, each core attached to a router and each router joined to its four neighbours — the two-dimensional mesh, which is the topology most large many-core chips use. A coherence message sent between two randomly chosen cores traverses, on average, 21 routers. At one nanosecond of delay per router, which is representative of current designs, that is $21\ \mathrm{ns}$ spent in the network before any queue is entered, against perhaps two or three nanoseconds spent in the coherence controller deciding what to do. The claim of this essay is that this ratio, and its behaviour as the machine grows, is the fact that governs coherence latency, and that optimising the protocol state machine addresses the smaller term. The average of 21 is a count, not an estimate. For two positions drawn uniformly from $\{0, 1, \dots, k-1\}$, the mean of $|x_1 - x_2|$ is $(k^2-1)/3k$, and a mesh has two independent dimensions, so the mean Manhattan distance is twice that. For $k = 32$ this gives $2 \times 1023/96 = 21.3$ hops. The quantity grows as $\tfrac{2}{3}\sqrt{N}$ in the number of cores $N$: doubling the core count multiplies the average distance by about $1.41$, while the protocol's work per transaction does not change at all. The latency decomposition, made usable The original version of this essay wrote the latency of a coherence operation as a sum of a protocol term, a network term and a memory term. That division is correct but too coarse to support the argument, because it hides the fact that the network term is itself a sum of one part that is unavoidable and one that is not. The standard model in the interconnection-network literature separates them: $$ T = H\,t_r + \frac{L}{b} + T_c , $$ where $H$ is the number of hops, $t_r$ the per-router delay, $L$ the message length in bits, $b$ the channel bandwidth in bits per unit time, and $T_c$ the contention delay. The first two terms together are the zero-load latency: what a message would experience on an otherwise idle network. The first is the routing delay, the second is the serialisation delay — the time simply to push the bits of a message onto a channel, which is why coherence protocols distinguish short control messages from full 64-byte data transfers. Only $T_c$ depends on what other traffic is doing, and it is the term that makes the difference between a machine that scales and one that does not. The queueing term, and how it actually diverges To reason about $T_c$ one needs a queueing model, and the simplest usable one treats a channel as a single server with random arrivals. Call it M/M/1: arrivals form a Poisson process of rate $\lambda$, service times are exponentially distributed with mean $T_s$, and there is one server with an unbounded queue. Write $\rho = \lambda T_s$ for the utilisation, the fraction of time the server is busy. The original essay gave the mean queueing delay as $T_s\,\rho/(1-\rho)$ and attributed the formula to Little's Law. The formula is right and the attribution is wrong, and separating them shows where each piece comes from. Little's Law, which holds for any stable queueing system whatever its distributions, states only that the mean number of items in a system equals the arrival rate times the mean time each spends there, $\bar{n} = \lambda W$. It does not by itself give a delay. What supplies the delay is the stationary distribution of the M/M/1 queue, $P(n) = (1-\rho)\rho^n$, from which the mean occupancy is $\bar{n} = \rho/(1-\rho)$. Dividing by $\lambda$ as Little's Law directs gives a mean time in system of $T_s/(1-\rho)$, and subtracting the service time itself leaves the mean wait $$ D_q = T_s \cdot \frac{\rho}{1-\rho} . $$ The second correction concerns the shape of the divergence. The original essay described the growth of $D_q$ as $\rho$ approaches one as exponential. It is not: $\rho/(1-\rho)$ has a simple pole at $\rho = 1$ and grows hyperbolically. The distinction matters because the two shapes give different design rules. An exponential blow-up would be negligible until very close to saturation; a pole is felt much earlier. Utilisation $\rho$ 0.3 0.5 0.7 0.8 0.9 0.95 0.99 $D_q / T_s$ 0.43 1.0 2.3 4.0 9.0 19 99 At half utilisation a message already waits as long as it takes to serve, and at 80 per cent it waits four times as long. This is the arithmetic behind the engineering rule that interconnects are provisioned to run at well under half their theoretical capacity, and it is why the original essay's condition for congestion — that the message rate exceed the network capacity — is far too permissive. Latency has become unacceptable long before the rate reaches capacity. Why utilisation rises with machine size: the bisection argument Everything so far concerns a single channel. What makes congestion a scaling problem rather than a provisioning problem is that the utilisation a given per-core message rate produces depends on the topology, and for the topologies that can actually be built it worsens with size. The relevant quantity is bisection bandwidth: the smallest total bandwidth crossing any cut that separates the network into two halves with equal numbers of nodes. It matters because under traffic with no locality — every core equally likely to address every other — half of each core's messages have a destination on the other side of the cut, so if each core injects at rate $r$ the demand across the bisection is $Nr/2$. Sustained operation requires that this not exceed the bisection bandwidth $B$. Now compute $B$ for two topologies. A $k$-by-$k$ mesh is cut in half by severing the $k$ links that cross the middle column, so $B = k\,b = \sqrt{N}\,b$. A hypercube of $N = 2^n$ nodes, in which each node is joined to every node differing in one bit of its address, is cut in half by severing the $N/2$ links that flip the top bit, so $B = (N/2)\,b$. Substituting each into $Nr/2 \le B$: Mesh: $r \le 2b/\sqrt{N}$. Th