The Roofline Model

The Roofline Model is a bound, not a simulation. It asks: given a chip's two hard physical limits — how many floating-point operations per second its arithmetic units can retire, and how many bytes per second its memory system can supply — what is the best performance any kernel could possibly achieve? The answer depends on one property of the kernel itself: its arithmetic intensity (AI), defined as ``` AI = Total Floating-Point Operations / Total Bytes Moved from Memory ``` measured in FLOPs per byte. A kernel with high AI reuses each byte it loads many times (e.g., dense matrix multiply, where each element participates in many multiply-adds). A kernel with low AI touches memory once or twice per operation (e.g., a vector addition, or a sparse matrix-vector product with poor locality). Crucially, "bytes moved from memory" means traffic across the boundary of interest — typically DRAM traffic after cache effects, not the algorithm's naive data footprint. This makes AI a property of the actual memory traffic pattern on a given machine, not just the algorithm's asymptotic complexity. Given AI, the model asserts an upper bound on attainable performance $P$ (in FLOP/s):

where $P_{\text{peak}}$ is the chip's peak floating-point throughput and $BW_{\text{peak}}$ is its peak sustained memory bandwidth. The first term says you can never exceed the hardware's raw compute rate no matter how efficient your memory access is. The second term says: if the kernel is starved for data, its performance is capped by how fast bytes arrive, scaled by how many operations each byte buys you. This single inequality, plotted on log-log axes with AI on the x-axis and performance on the y-axis, produces the characteristic "roofline" shape — a horizontal line at height $P_{\text{peak}}$, and a line of slope 1 (in log-log space, since $BW \times AI$ is linear in $AI$) rising from the origin, with the two meeting at the ridge point $AI_{\text{ridge}} = P_{\text{peak}} / BW_{\text{peak}}$. A kernel is memory-bound if its AI is left of the ridge point: no matter how well-optimized its arithmetic is, it cannot rise above the slanted memory roof, and the only way to improve performance is to increase AI or increase effective bandwidth. A kernel is compute-bound if its AI is right of the ridge point: it has enough arithmetic work per byte that memory bandwidth is not the constraint, and the only way to improve performance is to increase compute utilization — better vectorization (GPUs and SIMD Execution), more instruction-level parallelism, or fewer wasted cycles. The model turns a vague complaint ("my kernel is slow") into a precise, falsifiable diagnostic question: which side of the ridge point am I on, and how far below my roof do I sit?

Building and using a roofline analysis proceeds in four stages: characterize the hardware, characterize the kernel, plot the two together, and interpret the gap between the measured point and the roof.

Stage 1 — Characterize the machine. Measure $P_{\text{peak}}$ from the chip's specification (cores × clock × FLOPs/cycle per core, accounting for SIMD width and fused multiply-add) or empirically via a compute-saturating microbenchmark. Measure $BW_{\text{peak}}$ empirically using a bandwidth-saturating benchmark such as STREAM (large-array copy/scale/add/triad), since real sustained bandwidth is reliably lower than the theoretical pin bandwidth.

Stage 2 — Characterize the kernel. Instrument or model the kernel to obtain total floating-point operations $F$ and total bytes moved from the memory level of interest $B$ (often DRAM, but the model composes across cache levels too). Compute $AI = F / B$.

Stage 3 — Plot. On log-log axes (x = AI in FLOPs/byte, y = performance in FLOP/s), draw the flat compute roof at $P_{\text{peak}}$ and the memory roof as the line $y = BW_{\text{peak}} \cdot x$. Plot the kernel's measured performance at its measured AI.

Stage 4 — Interpret. If the point sits far below the roof directly above it, the gap is inefficiency — something other than the fundamental hardware limit is holding performance back (poor vectorization, cache conflicts, insufficient parallelism, load imbalance). If the point sits close to the roof, the kernel is near-optimal for its AI, and the only path to further speedup is changing the AI itself (algorithmic reuse) or upgrading hardware. ```

# ROOFLINE ANALYSIS — computing the bound and classifying a kernel function ROOFLINE_BOUND(P_peak, BW_peak, kernel): F <- count_flops(kernel) # total floating-point ops executed B <- count_bytes_moved(kernel) # total bytes crossing the memory

# boundary of interest (e.g. DRAM) AI <- F / B # arithmetic intensity, FLOPs/byte ridge <- P_peak / BW_peak # AI at which the two roofs meet bound <- min(P_peak, BW_peak * AI) # the attainable-performance ceiling if AI < ridge: regime <- "MEMORY-BOUND"

# bound is governed by the slanted roof: bound = BW_peak * AI else: regime <- "COMPUTE-BOUND"

# bound is governed by the flat roof: bound = P_peak measured <- F / measured_time(kernel) # actual achieved FLOP/s efficiency <- measured / bound # how close to the roof we are return (AI, bound, regime, measured, efficiency)

function OPTIMIZE_GUIDANCE(regime, efficiency, threshold=0.7): if efficiency >= threshold: if regime == "MEMORY-BOUND": return "Near roof: only fix is raise AI (blocking, fusion, reuse)" else: return "Near roof: only fix is faster hardware or lower precision" else: if regime == "MEMORY-BOUND": return "Below roof: fix memory access pattern, prefetch, alignment" else: return "Below roof: fix vectorization, ILP, branch/stall overhead" ``` The core plotting step — drawing $\min(P_{\text{peak}}, BW_{\text{peak}} \cdot AI)$ as a function of $AI$ — is exactly what produces the two-segment shape in the figure below. Real rooflines often add extra ceilings beneath the top ones (e.g., a lower roof for scalar, non-vectorized code, or a lower bandwidth roof for a slower cache level), turning the single-roof diagram into a stack of achievable ceilings that captures partial optimizations (vectorized-but-not-multithreaded, cache-resident-but-not-vectorized, etc.).

The Roofline Model is not an algorithm with a running-time complexity in the usual sense; it is an analytic bound, so "complexity" here means the cost of computing the bound, and "correctness" means proving the inequality actually holds and characterizing when it is tight.

Cost of computing the roofline. Determining $P_{\text{peak}}$ and $BW_{\text{peak}}$ requires $O(1)$ microbenchmarks per machine (amortized across every kernel analyzed on it). Determining a kernel's $AI$ requires counting FLOPs and bytes moved, which for a kernel with a known access pattern is a static, closed-form calculation — $O(1)$ given the kernel's loop structure — or, for arbitrary code, an $O(n)$ instrumentation pass over the $n$ dynamic instructions executed (hardware performance counters give this essentially for free at run time). So building a roofline plot for a kernel costs asymptotically nothing beyond running the kernel once with counters enabled.

Correctness of the bound. The inequality $P \le \min(P_{\text{peak}}, BW_{\text{peak}} \cdot AI)$ follows from two independent physical constraints, each individually tight: 1. Compute constraint. The chip can retire at most $P_{\text{peak}}$ FLOP/s by definition of peak throughput (it is derived from the number of functional units, SIMD lanes, and clock rate). No sequence of instructions can exceed this, since it is the maximum issue-and-execute rate of the hardware. Hence $P \le P_{\text{peak}}$ always. 2. Bandwidth constraint. In time $T$, the memory system can deliver at most $BW_{\text{peak}} \cdot T$ bytes. The kernel needs $B$ bytes total to do its $F$ operations, so it needs at least $T \ge B / BW_{\text{peak}}$ seconds just to receive its data (assuming compute cannot get ahead of arriving data — true unless data is stale/reused without arriving anew, which is exactly what AI already accounts for). Therefore

Both constraints must hold simultaneously — the chip cannot compute faster than its ALUs allow, and it cannot compute faster than data arrives — so the true bound is the minimum of the two, and the roofline's $\min(\cdot,\cdot)$ shape is not a modeling choice but a direct consequence of two simultaneously-necessary conditions. This is why the roofline is called a bound: it is provably an upper limit, derived from physical resource limits, and any measured performance satisfies $P \le \text{roof}(AI)$ by construction. It says nothing by itself about whether that bound is achieved — achieving it requires perfect overlap of computation and communication, perfect utilization of all functional units, and zero stalls, which real code rarely attains perfectly.

Honesty about assumptions and tradeoffs.

• The bound assumes compute and memory transfer can be fully overlapped (double-buffered/pipelined). If a kernel is instead alternately compute-then-wait-then-compute with no overlap, actual time is $F/P_{\text{peak}} + B/BW_{\text{peak}}$, which is strictly worse than $\max$ of the two terms and can be far worse than the roofline's $\min$-based bound — the classical roofline is an optimistic (best-case) bound, not a worst-case one.
• $AI$ is not a fixed property of an algorithm; it depends on the memory hierarchy level chosen as the boundary. A kernel might have low AI relative to DRAM but high AI relative to L1 cache, since a well-blocked algorithm reuses data heavily once it is resident on-chip. This is why "cache-aware" rooflines draw multiple memory roofs (one per cache level), each with its own bandwidth.
• Peak bandwidth and peak compute are themselves idealized numbers; sustained bandwidth measured by STREAM is typically 60-90% of the theoretical pin bandwidth, and using the theoretical peak makes the roof optimistic (kernels may appear "more memory-bound" than they practically are). Careful roofline studies always use empirically measured ceilings.
• The model captures only FLOPs and bytes; it says nothing about latency-bound kernels (e.g., pointer-chasing with poor prefetchability) where neither bandwidth nor compute is the bottleneck, but rather memory latency combined with insufficient concurrency to hide it. Extensions (e.g., adding a "concurrency roof" based on Little's Law) are needed for such cases.

Consider a machine with

so the ridge point is $AI_{\text{ridge}} = 200/50 = 4$ FLOPs/byte. We analyze three kernels operating on double-precision (8-byte) arrays of size $n$.

Kernel A — SAXPY-like vector update `y[i] = a*x[i] + y[i]` for $i = 0 \ldots n-1$. Per iteration: 2 FLOPs (one multiply, one add). Memory traffic per iteration (assuming compulsory misses only, streaming access, write-allocate ignored for simplicity): read `x[i]` (8B), read `y[i]` (8B), write `y[i]` (8B) = 24 bytes.

This is far left of the ridge point (0.083 ≪ 4), so Kernel A is memory-bound. Its bound is

Even a perfectly-vectorized, perfectly-pipelined implementation cannot exceed about 4.2 GFLOP/s on this machine — roughly 2% of the chip's peak compute rate. If a benchmark measures 3.9 GFLOP/s for this kernel, that is excellent (93% of its roof), even though it looks abysmal (2%) relative to peak FLOP/s. The naive metric "% of peak FLOPs" is the wrong way to judge this kernel; "% of its own roofline bound" is the right one.

Kernel B — Dense matrix multiply $C = AB$ for $n \times n$ matrices, with a cache-blocked (tiled) implementation. Total FLOPs: $2n^3$ (one multiply + one add per inner-product term). With good blocking, each matrix element is reused across a tile of size $b$, and the DRAM traffic is approximately $O(n^3/b)$ instead of the naive $O(n^3)$ — this is the entire point of tiling. Suppose blocking achieves effective DRAM traffic of $B \approx 4n^3/b$ bytes with a tile factor $b = 64$ elements (a realistic cache-blocking factor):

This is right of the ridge point (32 > 4), so Kernel B is compute-bound. Its bound is simply

A good blocked GEMM implementation should approach 200 GFLOP/s, limited now only by vectorization efficiency, instruction scheduling, and register blocking — not by memory traffic at all.

Kernel C — Naive (unblocked) matrix multiply, same $2n^3$ FLOPs, but with poor locality: the inner loop repeatedly reloads rows/columns from DRAM because the working set does not fit in cache. Suppose this results in DRAM traffic close to $O(n^3)$ bytes (each of the $n^3$ inner-loop iterations effectively misses to DRAM), say $B \approx 8n^3$ bytes (reading two 8-byte operands per iteration with no reuse):

Despite doing identical arithmetic to Kernel B, Kernel C is now far left of the ridge point and memory-bound:

This is the pedagogically crucial case: same algorithm, same FLOP count, same hardware — but a data-layout/blocking decision moves the kernel from a 200 GFLOP/s ceiling down to a 12.5 GFLOP/s ceiling, a 16× loss, purely from memory traffic. No amount of instruction-level tuning of Kernel C's inner loop can push it past 12.5 GFLOP/s; the fix must be algorithmic (blocking/tiling to raise AI), not micro-optimization.

The Roofline Model was formalized in the mid-2000s at UC Berkeley as multicore and manycore chips made the compute/bandwidth gap acute and existing performance models too coarse to guide optimization. It built on decades of prior insight — most directly the recognition, going back to computer architecture's earliest performance equations, that memory access cost and compute cost are separate resources that must both be accounted for, an idea foundational to Performance Metrics and the CPU Time Equation.

The Roofline Model is now a standard diagnostic in high-performance computing centers, where scientists profile simulation codes (climate models, molecular dynamics, computational fluid dynamics) to decide whether to invest engineering time in cache blocking, data layout changes, or instruction-level tuning. GPU and accelerator vendors publish roofline-style specifications explicitly, since GPUs and SIMD Execution hardware exposes an enormous compute-to-bandwidth ratio that makes the memory-bound/compute-bound distinction especially consequential — many deep learning training kernels (batch normalization, small matrix operations, attention with short sequences) are memory-bound and benefit far more from kernel fusion (raising AI by avoiding round-trips to DRAM) than from faster arithmetic units. Compiler and library authors (BLAS, cuDNN, oneDNN) design blocking strategies whose entire purpose is to push a kernel's operating point rightward past the ridge point. At data-center scale, the same reasoning about resource bottlenecks — is the system limited by compute, by memory bandwidth, by network bandwidth, or by storage I/O — recurs as the organizing question behind capacity planning and scheduling in Warehouse-Scale Computing, where the roofline's core lesson generalizes: identify the scarcest resource, and optimize toward it, not away from it.

Ask the tutor: How would the roofline diagram change if I plotted arithmetic intensity relative to on-chip cache bandwidth instead of DRAM bandwidth?