The memory hierarchy

An NVIDIA V100, a 2017 accelerator, performs 125 trillion FP16 tensor-core floating-point operations a second and reads about 900 billion bytes a second from main memory; dividing the two gives an FP16 ops:byte ratio of 139 [S:99:18]. Arithmetic that needs more than 139 operations per byte is limited by the arithmetic, and arithmetic that needs fewer is limited by the memory.

Why does the same arithmetic run at ten speeds? Because the time of a kernel, one procedure run over a whole array, a block of numbers of one kind, is the larger of two times, the time to compute and the time to fetch the bytes. The second time depends on which level of memory supplies them [S:99:18]. The same chip's second-level cache, one step out from the processor, delivers 3.1 trillion bytes a second. Dividing the same 125 trillion by 3.1 trillion gives 40: the threshold falls, and a kernel that was limited by memory becomes limited by the arithmetic. !Each rung is the wait for one dependent load from a table of that size, with the loop's own 15.2 to 16.2 nanoseconds per load already removed. The ladder is flat to 512 KiB, jumps twelve- to fourteen-fold at 2 MiB and five- to seven-fold at 8 MiB, and ends 139 to 157 times above its first rung. The eight rungs hold four plateaus. Each rung is drawn as the span of two runs, so it is a range and not a digit. Status: published.

The levels form a ladder, from registers inside the processor, its fastest storage, through several caches, small memories that hold recently used bytes, to main memory and beyond it to disk, and each step down is larger and slower [S:100:18]. A byte that misses the first level, finding nothing there, is fetched from the second, and a byte that misses every cache comes from main memory, where the rate in the opening calculation applies. The arithmetic does not change as the byte descends, and only the wait does. That ladder is why a program's speed depends on where its data sits, and not only on how many operations it performs. !A kernel's position on the roof decides which resource limits it. The diagonal is the memory roof at 900 billion bytes a second, the flat top is 125 trillion operations a second, and the two knees are the ridges: 139 operations per byte against main memory and 40 against the second-level cache. The layer of the worked example sits at 315 operations per byte, well right of both knees. The same layer run on one example sits at 1.0, far left of both, so changing the batch changed the verdict without changing the arithmetic. Status: schematic.

A kernel, the procedure described above, has an arithmetic intensity, the number of operations it performs divided by the number of bytes it moves. The machine's ridge point is its operations per second divided by its bytes per second [S:99:18]. A kernel whose intensity sits above the ridge is compute-bound, limited by the arithmetic, and one below it is memory-bound, limited by the memory [S:99:18].

$$\text{intensity}=\frac{\text{operations performed}}{\text{bytes moved}}$$

That line says: count the work, count the traffic, and divide one by the other. [F01]

The intensity is not a property of the arithmetic alone, because the same multiplication can reuse its operands or fetch them again. A matrix product, a sum of products of rows and columns, that reloads both operands for every output has an intensity near one operation per byte. One that keeps a tile, a block of the operands small enough to stay in a cache, can raise it by orders of magnitude [S:100:18]. This is why the same number of operations can take wildly different times: the operations are fixed and the traffic is a choice.

Worked example. Take a layer, one stage of a network that maps inputs to outputs, with 4096 outputs and 1024 inputs, and run it on 512 examples. Each output needs one multiply and one add for each of its inputs, which is two operations, so the total is $2\times 512\times 4096\times 1024$, about 4,294,967,296.

The bytes are two per number for the weights, the numbers the layer learns, the inputs and the outputs, about 13,631,488, because the data are FP16 as the guide's table assumes. With four-byte FP32 data the byte counts double and the intensities halve. The byte total is $2\times (4096\times 1024+512\times 1024+512\times 4096)$, weights, inputs and outputs. The intensity is 315 operations per byte, well above the ridge of 139, so the layer is compute-bound.

Now run one example. The operations fall to 8,388,608, and the bytes fall only to 8,398,848, because the weights dominate and they are the same size. The intensity is one operation per byte, far below the ridge, so the same layer is memory-bound. The weights are read once per batch, a group of examples processed together, so a batch of one pays for the whole model to produce a single answer.

The model counts bytes and operations and assumes the machine is saturated, with every pipeline busy. A kernel with one thread, one stream of instructions, can have an intensity of 1000 and still run slowly, because nothing keeps the arithmetic pipeline, the unit that performs operations, fed [S:99:19]. It also counts bytes at one level, so a claim that a kernel is memory-bound means nothing until the claim names the level.

The formal statement. For one kernel on one machine, count the operations it performs and the bytes it moves from a named memory level. Their ratio is the intensity of the kernel. Divide the machine's peak operation rate by the bandwidth of that level, and you have its ridge. The attainable rate is the smaller of the peak rate and the bandwidth times the intensity. A kernel sits on the compute side of the ridge when its intensity exceeds the ridge, and on the memory side when it falls below [S:104:4]. The statement is an upper bound on rate. It is not a prediction of time.

$$\text{attainable rate}=\min \left(\text{peak rate},\text{bandwidth}\times \text{intensity}\right)$$

That line says: the machine gives you the arithmetic ceiling or the traffic ceiling, whichever is lower.

The derivation. The time of the kernel is the larger of two times, the work divided by the peak rate and the traffic divided by the bandwidth [S:99:18]. Rate is the work divided by that time, so the rate is at most the peak and at most the bandwidth times the intensity. Setting the two bounds equal gives the ridge. The derivation assumes the arithmetic and the traffic overlap completely. If they do not, the time is closer to the sum of the two, and the maximum is optimistic [S:99:18].

The edge case. The intensity depends on the level at which you count bytes. The roofline paper defines operational intensity as traffic to main memory, after the caches have filtered it, and it says so to keep the term apart from arithmetic intensity [S:104:3]. Counting the same kernel at the cache gives a different number, which is why one layer is memory-bound against main memory and compute-bound against a cache [S:99:18]. A claim that a kernel is memory-bound means nothing until the claim names the level. The two intensities are not two estimates of one quantity.

What the core hid. The core used arithmetic intensity for what the paper calls operational intensity, and the paper separates the two names on purpose [S:104:3]. The core also treated the ridge as a property of the chip. It is a property of the chip, the level and the arithmetic: the 125 trillion is the half-precision tensor-core rate, so 139 is an FP16 ridge, and the published figure for one accelerator runs from 40 to 139 depending on where the operands come from [S:99:18].

Where the analogy breaks. A roof suggests a ceiling you reach. This model gives a ceiling you may sit far below, and it does not say why. The paper adds lower ceilings for instruction-level parallelism, operation mix, stride and memory affinity [S:104:4]. A kernel below the roof is limited by one of those, and the roof does not name which.

Original sources. The roofline model is a Berkeley technical report by Williams, Waterman and Patterson [S:104:3]. They define operational intensity as operations per byte of traffic to main memory, and they derive the bound from the smaller of peak arithmetic and peak bandwidth times intensity [S:104:3][S:104:4]. The version you used, with the ratio called arithmetic intensity and measured against a named level, is section 4 of the NVIDIA performance guide [S:99:18].

An open question. Whether a one-level roofline predicts the time of a fused kernel is unsettled. A kernel that keeps its working set in shared memory has several traffic levels at once, and the model names one [S:104:3]. Evidence that would settle it: measured time against the prediction for the same kernel across tile sizes on one device, with the traffic at each level counted by a profiler rather than assumed. A model that holds only while the tile fits is a model of the tile, not of the kernel.

A frontier result. The roofline now sets the batch size at which a matrix multiply becomes compute-bound. The DeepMind scaling book reduces the question to a per-replica token count and gives a threshold for a bfloat16 matmul on a current accelerator [S:101:12]. The derivation is the one in the formal statement, with the bytes counted at main memory. Because the threshold is a token count, it does not move when you change the number of sequences in a batch.

What to read next. Read the report for the definition of operational intensity and for the extra ceilings [S:104:3][S:104:4]. Read section 4 of the NVIDIA guide for the same analysis applied to layers of a network [S:99:19]. Then read part 1 of the scaling book for the batch-size form of the threshold [S:101:12].