Bandwidth-Bound and Latency-Bound Work

Two kernels can both be limited by memory and require opposite fixes. One is limited by how many bytes per second the memory system can deliver, and needs fewer bytes moved or a higher-bandwidth path. The other is limited by how long a single access takes, and needs more accesses in flight or a shorter dependency chain. The distinction is not academic: applying a bandwidth fix to a latency-bound kernel, or the reverse, produces no improvement and consumes the effort that would otherwise have found one.

The two regimes are distinguishable before any code is changed, from three numbers: the bytes moved per unit of work, the machine’s sustainable bandwidth, and the achievable concurrency of outstanding accesses. This article sets out how those numbers combine, what each regime looks like in a profile, and where the shared hardware resources sit that make the boundary shift with load.

The two ceilings

Memory performance is bounded by two independent constraints. The bandwidth ceiling is the maximum rate at which data can cross the path between the core and the memory devices, on the order of tens of gigabytes per second per socket for current server parts, with substantially less per core on multi-socket systems once the shared path is divided. The latency ceiling is set by the round-trip time of a single access, on the order of a hundred or a few hundred cycles for main memory, and it applies to accesses that cannot be overlapped.

A kernel is bandwidth-bound when the useful work per byte is low enough that the core waits on data arrival even though many accesses are outstanding. It is latency-bound when the work per byte is high but the accesses are serialised, so the core waits on a specific access rather than on a queue.

The distinction can be expressed as a single ratio. Let B be bytes moved per operation, b the sustainable bandwidth in bytes per cycle, and L the latency in cycles. If n accesses can be outstanding, the memory system can sustain n bytes in flight per latency period, giving a concurrency-limited throughput of n / L bytes per cycle. The effective throughput is the smaller of b and n / L divided by B per operation. A kernel is latency-bound exactly when n / L < b for its achievable n.

That inequality is the whole of the model. For a core that sustains sixteen outstanding misses and has a 200-cycle memory latency, n / L is 0.08 bytes per cycle, which is far below the per-core share of DRAM bandwidth on a typical server. The latency ceiling binds unless the kernel has many independent accesses in flight. The arithmetic intensity of the kernel decides whether it can.

Arithmetic intensity and the roofline

Arithmetic intensity is operations performed per byte moved from memory. Dividing the machine’s peak compute rate by its peak bandwidth gives a ridge point: kernels with intensity above the ridge are compute-bound, below it are memory-bound. Within the memory-bound region, the achievable rate rises linearly with intensity until it saturates at the bandwidth ceiling.

The model’s value here is that the memory-bound region splits further once latency is introduced. A kernel with enough independent accesses to keep the memory system busy sits on the bandwidth ceiling; one without sits below it, on a line whose slope is set by n / L rather than by b. Two kernels with identical intensity can therefore land on different lines, and the difference between them is purely a property of their access independence.

The practical implication is that raising intensity and raising concurrency are different operations with different costs. Raising intensity means doing more work per byte, which requires an algorithmic change: blocking to reuse data in cache, fusing passes, or changing the representation. Raising concurrency means restructuring the same work so that independent accesses are issued together, which requires no algorithmic change but does require buffers, unrolled loops, or independent chains.

Symptoms in a profile

The two regimes leave different traces. Counters for cache misses and memory bandwidth show what the hierarchy is doing; the ratio of cycles to misses shows whether each miss is being paid for individually or overlapped.

A bandwidth-bound kernel shows a high miss count and a memory subsystem already saturated: increasing concurrency further does nothing, because the path is full. The tell is that the achieved bandwidth measured by the counters is close to the platform’s sustainable figure, and the kernel’s own cycles track bytes moved. A latency-bound kernel shows a lower miss count and an achieved bandwidth well below the platform’s figure, with memory-level parallelism low: each miss stalls the core for close to the full latency.

/* Copy with a stride of one cache line, four independent streams.
 * The four streams are independent, so a single core can keep several loads
 * in flight; the kernel should approach the bandwidth ceiling. */
void copy4(float *restrict d, const float *restrict s, size_t n)
{
    for (size_t i = 0; i < n; i += 16) {
        d[i +  0] = s[i +  0];
        d[i +  4] = s[i +  4];
        d[i +  8] = s[i +  8];
        d[i + 12] = s[i + 12];
    }
}

Replacing the four independent statements with a single dependent chain over the same addresses, for instance by making each load’s address derive from the previously loaded value, keeps the bytes identical and destroys the concurrency. The time difference between the two versions measures the latency ceiling directly, with no change in bytes moved. This is the cleanest isolation of the effect available without a simulator.

Where the boundary moves

The boundary between the regimes is not a property of the program alone. Three factors shift it.

The number of threads or cores sharing the memory path. On a single core, per-core concurrency is limited by the reorder capacity and the miss buffers, and the latency ceiling usually binds. Across many cores the aggregate concurrency rises, and the bandwidth ceiling becomes the binding constraint. A kernel that is latched at the latency ceiling when run on one core can be purely bandwidth-bound when run on all of them. That is why per-core speedup curves flatten before the memory system is nominally saturated: the last cores add concurrency without adding bandwidth.

The access size. A single core’s outstanding-request capacity is counted in cache lines, and a 128-byte access may occupy two line fill buffers. Wider accesses increase bytes in flight per outstanding request, which raises the n / L line, but they also consume more of the finite concurrency budget. Vector accesses widen each request rather than increasing the count, so they move a kernel toward the bandwidth ceiling without increasing how many independent chains it must have.

Whether the accesses are reads or writes. Reads can be prefetched, reordered, and speculated on. Writes consume store buffer and must eventually be written back; a write-heavy kernel contends for the same path but with less ability to hide latency, because the store must retire and the line may need to be read first if it is partially written. Kernels that build output in place at line granularity avoid the read-for-ownership traffic that partial-line writes incur, which is a bandwidth saving of up to half the traffic on the write stream.

Diagnosing without hardware counters

Counters are the direct route, but two structural clues are available from the code and a clock.

The first is the ratio of elements processed to elements moved. A kernel that reads each input element once and writes each output element once has an intensity of two accesses per element and cannot be helped by blocking. A kernel that reads a neighbourhood of each element has a reuse opportunity, and blocking it so the neighbourhood fits is a bandwidth fix. If the kernel already reads each byte once, no cache-blocking scheme reduces traffic, and the only bandwidth levers are representation changes, such as narrower types or compressed encodings.

The second is whether the kernel has a long dependent chain. A traversal that must know the result of the previous step to compute the next address is latency-bound by construction, no matter how few bytes it moves. The chain-length arithmetic in Dependent Loads and the Cost of Pointer Chasing gives the bound directly: cycles per element is at least the sum of the levels’ latencies along the chain.

A useful field test combines both. Run the kernel at two problem sizes whose working sets straddle the last-level cache. If per-element time is unchanged, the kernel is neither bandwidth- nor capacity-bound; if it degrades sharply, it is capacity-bound, and the right first fix is footprint or blocking rather than either of the two regimes discussed here. The measurement that establishes the knee is described in Working Set Size and the Miss-Rate Cliff.

Why bandwidth scales and latency does not

The two ceilings have improved at very different rates over the life of the processor, and that divergence is the reason this distinction became central rather than marginal. Bandwidth has grown roughly with process and signalling improvements, while latency has been nearly flat for decades: signals travel at a fixed speed, and the physical distance between core and DRAM does not shrink with transistor scaling.

The cumulative effect is a widening gap between the two ceilings, which means that workloads migrate from the bandwidth-bound regime into the latency-bound one over time, not the other way around. A kernel whose per-core accesses were enough to saturate memory two decades ago now needs many times more outstanding requests to reach the same fraction of the bandwidth ceiling. Software that was written against the older balance and never revisited tends to accumulate in the latency-bound regime, where its throughput is set by its access graph rather than by the machine.

The corollary for tuning is that the two fixes have different longevity. Reducing bytes moved keeps paying until the latency ceiling binds; increasing concurrency keeps paying until the bandwidth ceiling binds. The highest-value change is usually the one that raises the ceiling currently in force, and identifying which ceiling is in force requires only the intensity and concurrency numbers above, not a full microarchitectural study.