Why Most Code Is Memory Bound: The Roofline Model

Vendor specifications quote peak floating-point throughput: so many operations per second, obtained by multiplying core count, clock, vector width, and operations per instruction. It is a real ceiling and almost no code gets near it.

The reason is not that processors are dishonest. It is that peak arithmetic assumes operands are already present. Nothing in that calculation accounts for getting data from DRAM, and the previous lesson established that a DRAM access is roughly sixty times an L1 hit.

So there are two ceilings, not one. A kernel is limited by arithmetic throughput or by the rate at which memory can supply operands, whichever binds first. The useful question is never "how fast is this processor" but "which of the two limits am I actually against", because the answer determines whether optimising arithmetic is worth any effort at all.

The roofline model answers that question on a single graph.

The bridge between the two ceilings is a single ratio.

operational intensity = operations performed / bytes moved

Measured in operations per byte, it says how much arithmetic a kernel extracts from each byte it drags out of memory. It is a property of the algorithm and its implementation, not of the hardware.

Williams, Waterman and Patterson introduced the model in "Roofline: An Insightful Visual Performance Model for Multicore Architectures", Communications of the ACM, volume 52, issue 4, April 2009. Their terminology is deliberate: they use operational intensity, traffic between caches and DRAM, rather than the older arithmetic intensity, which measures traffic between the processor and cache. The distinction matters, because for anything larger than cache it is the DRAM traffic that binds.

Low intensity means the kernel is memory hungry. High intensity means it does substantial work per byte and has a chance of reaching the arithmetic ceiling.

Work three standard cases, assuming 4-byte floats and that nothing is reused from cache.

Vector addition, c[i] = a[i] + b[i]:

per element: 1 add, 12 bytes moved (read a, read b, write c)
intensity  = 1 / 12 = 0.083 ops/byte

Dot product, s += a[i] * b[i]:

per element: 2 ops (multiply, add), 8 bytes read
intensity  = 2 / 8 = 0.25 ops/byte

Dense matrix multiply, N-by-N, with good blocking:

total ops   = 2 * N^3
total bytes = 3 * N^2 * 4   (each matrix read or written once)
intensity   = 2N^3 / 12N^2 = N / 6 ops/byte

That last result is the important one. Matrix multiply's intensity grows with N, because each element loaded participates in N multiplications. Vector addition's intensity is a constant, and a small one. This is exactly why dense linear algebra can approach peak arithmetic while vector operations never do, and why blocking mattered so much in the previous lesson: without it, matrix multiply does not achieve the reuse this calculation assumes.

Plotted on log-log axes with intensity on the x-axis and attainable performance on the y-axis, the ceiling is the minimum of two lines. A diagonal, where performance equals intensity multiplied by peak memory bandwidth, and a horizontal line at peak compute. Their intersection is the ridge point. A kernel to the left of the ridge is memory bound and no amount of arithmetic optimisation will help it. A kernel to the right is compute bound. The ridge point is a property of the machine and is a compact statement of how badly balanced it is.

Take a machine with 200 GFLOP/s peak and 50 GB/s of memory bandwidth.

ridge point = peak compute / peak bandwidth
            = 200e9 / 50e9
            = 4 ops/byte

Any kernel below 4 operations per byte is memory bound on this machine. Now revisit the three kernels:

vector add    0.083 ops/byte -> attainable = 0.083 x 50e9 =  4.2 GFLOP/s   (2% of peak)
dot product   0.25  ops/byte -> attainable = 0.25  x 50e9 = 12.5 GFLOP/s   (6% of peak)
matmul N=1024 171   ops/byte -> compute bound, 200 GFLOP/s available

Vector addition can reach about 2% of this machine's arithmetic peak, and that is not a defect in the code. It is the ceiling. Hand-optimising its inner loop, vectorising it further, or unrolling it cannot move the number, because the constraint is bandwidth.

This is the model's real value. It tells you which optimisations are pointless before you spend a week on them.

The roofline models bandwidth, and it is worth being precise that this is not the same constraint as latency, which the previous lesson measured.

• Latency is how long one access takes. Roughly 246 cycles to DRAM on the Skylake part measured earlier.
• Bandwidth is how many bytes per second arrive when many accesses are in flight at once.

They relate through Little's Law: the concurrency needed to sustain a given bandwidth equals bandwidth multiplied by latency. To keep 50 GB/s flowing with an 80 ns latency you need roughly 4000 bytes, about 62 cache lines, in flight continuously.

That is why the structures from lesson two matter here. A core with 192 load queue entries can track that many outstanding accesses; a core with 8 could not, and would be latency bound long before reaching its bandwidth ceiling.

The practical consequence: a program can fail to reach peak bandwidth simply by not having enough independent accesses outstanding. Pointer chasing is the extreme, with exactly one access in flight at a time, so it achieves a tiny fraction of bandwidth regardless of how much the hardware could deliver.

Processors try to hide latency by fetching lines before they are requested. Hardware prefetchers detect regular patterns and issue speculative loads ahead of the access stream.

What they handle well is narrow, and worth knowing precisely:

• Sequential forward and backward traversal.
• Constant-stride access, up to a limit, within a page boundary.

What defeats them:

• Indirect access, a[b[i]], where the address depends on loaded data.
• Pointer chasing through a linked structure.
• Random access.
• Strides that cross page boundaries, since a hardware prefetcher generally will not prefetch across pages without a translation for the next one.

This is the mechanical reason an array of structs traversed linearly outruns a linked list holding identical data. The complexity is the same and the operation count is the same, but one pattern the prefetcher can follow and the other it cannot.

Once you accept that intensity and access pattern govern performance, data layout becomes a first-order decision rather than a style preference.

// Array of Structs: fields interleaved per particle
struct Particle { float x, y, z, vx, vy, vz, mass, charge; };
struct Particle particles[N];        // 32 bytes each

// Struct of Arrays: each field contiguous
struct Particles {
    float x[N], y[N], z[N];
    float vx[N], vy[N], vz[N];
    float mass[N], charge[N];
};

Now suppose a loop reads only x. With the array of structs, each 64-byte line holds two whole particles, so it carries 8 bytes of wanted x and 56 bytes of fields the loop never touches. You use one eighth of the bandwidth you paid for. With the struct of arrays, a line holds 16 consecutive x values and every byte is used.

Neither layout is correct in general. If the loop touches every field of one particle at a time, the array of structs wins for exactly the same reason reversed. The rule is to lay data out along the direction it is traversed, which requires knowing the access pattern before choosing the type.

Putting the cursus together, here is the order in which to attack a slow kernel.

1. Measure intensity first. Count operations and bytes moved. If you are far below the ridge point, the kernel is memory bound and arithmetic optimisation is wasted effort. This step costs minutes and routinely saves days.
2. Raise intensity if you can. Fusing two passes over an array into one halves the traffic and doubles intensity. Blocking creates reuse that was not there before. These move the kernel rightward on the graph, which is the only way a memory-bound kernel gets faster.
3. Reduce bytes moved. Smaller types, better layout, dropping unused fields from the hot structure. A float32 instead of float64 halves the traffic exactly.
4. Improve the access pattern. Make it something a prefetcher can follow, and make sure enough independent accesses are outstanding to fill the latency-bandwidth product.
5. Only then optimise arithmetic. Vectorisation, instruction selection and unrolling matter once, and only once, you are actually against the flat part of the roof.

The general lesson of all four lessons is one sentence: on a modern processor, arithmetic is nearly free and data movement is what you pay for.