29.2 Modern CPUs: memory hierarchy, parallelism, and what it takes to go fast🔗⧉

A blur spends time both computing weighted sums and moving pixels. The same formula can run very differently when each intermediate is stored as a full image, computed in small tiles, or recomputed where it is needed. Understanding that difference requires distinguishing arithmetic throughput, dependency latency, and memory traffic.

A processor may start several independent multiply-add instructions per cycle even though each result takes several cycles to become available. A dependent load from DRAM can take far longer, but many independent loads can overlap. Comparing “one cycle per multiply” with “hundreds per load” mixes throughput with latency and does not predict the cost of streaming an image.

Browser experiments can illustrate these effects under the browser's execution model. They do not recover a processor specification. Reported hardware concurrency may be capped; timings include compiler, runtime, operating-system, and thermal effects.

29.2.1 Why moving data, not doing math, is the bottleneck🔗⧉

Memory latency is the delay for an individual access; bandwidth is the volume transferred per second. Independent requests can overlap latency, but their total traffic still consumes bandwidth. Patterson describes the historical divergence between latency, bandwidth, and computation Patterson 2004.

Suppose a point operation reads one 32-bit sample and writes one 32-bit result. Its minimum explicit traffic is eight bytes per sample. At a sustained 20 GB/s across the relevant memory interface, that gives an upper bound of 2.5 billion samples/s before extra traffic or other limits. Write allocation, additional inputs, and temporary buffers can raise the byte count. Cache reuse can lower traffic at DRAM without reducing the number of instructions that load from cache.

Data movement also costs energy. Horowitz's technology-specific estimates Horowitz 2014 illustrate how an off-chip access can cost much more than a simple arithmetic operation. The ratio depends on technology, operation, precision, and memory level; it is not a universal camera power budget.

29.2.2 The memory hierarchy and locality🔗⧉

Registers hold the values instructions operate on. Caches keep copies of recently used memory close to a core; larger shared caches and DRAM provide progressively more capacity, usually at higher latency. Sizes, sharing, and speeds vary. There is no fixed tenfold ratio between levels.

Caches transfer data in lines, commonly 64 bytes on many CPUs, though other sizes exist. Reading adjacent values uses more of each fetched line: spatial locality. Reusing values before eviction provides temporal locality. Cached accesses still consume load/store bandwidth and take time; locality makes them cheaper, not free.

Inspect the actual image strides. In a row-major planar array, adjacent horizontal samples are contiguous. In interleaved RGB, channels and pixels have different strides. Views, crops, and padding can change the layout. Prefer an inner loop that follows contiguous storage; a column sweep may repeatedly access distinct lines before returning to useful neighbors.

A randomized dependent pointer chase limits overlap between loads and can expose changes as its working set grows. Page translation, prefetching, cache conflicts, and runtime effects also influence the curve, so a timing step is evidence of a transition rather than an exact cache-capacity measurement. On the laptop this chapter was written on, the first step appears near 128 KB, consistent with that chip's L1 data cache, and the far end settles near 100 ns, about sixty times the L1 access it started from. Those numbers describe one machine in one browser session; the figure measures yours.

Compare row, column, and scattered access on the same data and arithmetic. Consume the result so the compiler cannot remove the work. Separate any permutation-generation overhead from the timed access loop. On the machine this was written on, the column sweep took about five times as long as the row sweep and the scattered order longer still, the difference spent fetching 64-byte lines to use four bytes of each.

The row/column experiment is useful because the numerical answer stays the same. A row sweep consumes adjacent floats from a fetched line. A column sweep jumps by the row stride, so the other samples on that line may be evicted before they are used. Scattered access also makes upcoming addresses difficult to predict. Changing a loop order has altered how useful each memory transfer is, without removing a single addition. On a small image that remains in cache, the penalty can shrink; enlarging the image tests whether capacity is what made the first case forgiving.

The dependent-load experiment asks a different question. Each load supplies the address for the next, so the processor cannot start that next load until the preceding one finishes. A long plateau followed by a rise as the buffer grows suggests that a faster storage level no longer holds the working set. An ordinary image sweep can overlap loads and exploit prefetching, so multiplying this pointer-chase latency by the number of image pixels would predict the wrong running time.

Tiling processes a small region through several stages while useful intermediates remain in cache. A stencil needs a halo around each output tile; adjacent tiles may recompute overlapping halo values. The useful trade is less long-distance traffic for some extra work and scheduling overhead. Include all live intermediates and halos when estimating the working set.

Pointwise stages can often fuse directly without a stored intermediate. Stencil stages need neighborhoods and may benefit from tile or row buffers instead. Test these arrangements at several thread counts: a memory interface that serves one worker comfortably may become the shared limit for many workers.

Consider the four pointwise stages in Figure 29.2.7⛶ fullscreen. A straightforward implementation makes four full-image passes, leaving a complete image between each pair. A strip implementation passes a small group of rows through all four stages before advancing. A fully fused implementation carries one pixel through the four formulas in a register and writes only the final result. The formulas are identical; the lifetime and location of their intermediate values differ.

Run this comparison with one worker and then with many. If one worker cannot saturate memory bandwidth, the full-image passes may look surprisingly competitive. Several workers sharing the same interface can expose the cost of their extra traffic: adding cores raises the demand for bytes without raising the interface's capacity. Increasing the arithmetic per stage can make the curves converge again because computation now occupies more of the elapsed time. These changes help distinguish a bandwidth explanation from a claim that fusion must always be faster.

For example, compare two stages that each apply a three-tap horizontal filter. Computing the first stage over the full image and then the second requires a full intermediate. To produce 64 consecutive final pixels in a tile, the second stage instead needs 66 intermediate pixels, and those intermediates need 68 input pixels. The two extra intermediate values are the halo. A neighboring tile recomputes some of them, but most intermediate accesses now refer to a small region that can remain in cache.

Increasing the tile size reduces the fraction of halo work but increases live storage. Decreasing it does the reverse and may add task overhead. Include all simultaneously live channels and stages when estimating the working set; a tile dimension by itself does not guarantee a cache hit. The benefit is avoided transfers when the original intermediate would have exceeded cache capacity, not a universal speedup from introducing tile loops.

With a 64-byte cache line and 32-bit samples, one line holds sixteen samples. A scan along contiguous samples can use all sixteen after bringing in that line. A widely strided scan may use only one before moving elsewhere. The unused samples still occupied transfer bandwidth and cache space. Returning to a sample before eviction gives temporal reuse; reading its neighbors gives spatial reuse. Neither eliminates the cost of loads, but both can reduce traffic to a slower level of the hierarchy. Array strides tell you which loop order offers that opportunity.

29.2.3 The roofline: is my kernel compute- or memory-bound?🔗⧉

The roofline model Williams et al. 2009 compares the work done with bytes transferred across a specified memory interface. Let $F$ be the operation count, $Q$ the byte count, and $\mathcal I=F/Q$ the arithmetic intensity. If sustained bandwidth is $B$ and the relevant compute ceiling is $P_{\max}$, then

The first bound is a rate; the second is a minimum time. Count a floating-point multiply-add as two operations when using conventional FLOP/s. The bandwidth term limits low-intensity work. The compute term limits sufficiently high-intensity work. The crossover is $\mathcal I=P_{\max}/B$.

These are bounds, not predictions that a kernel reaches either ceiling. A serial dependency, poor vectorization, branch behavior, launch overhead, or insufficient concurrent memory requests can leave it far below both. A kernel on the nominal memory side can still benefit from vectorization if its scalar code never generated enough traffic to reach the bandwidth limit.

A microbenchmark can estimate attainable rates for an execution environment. Use independent arithmetic chains to measure throughput; repeatedly updating one value can measure dependency latency instead. Choose working sets deliberately and distinguish warm cache traffic from DRAM traffic. On the laptop here, WebAssembly gave a compute roof near 12 GFLOP/s and a streaming bandwidth near 36 GB/s, so a ridge at about 0.34 FLOPs per byte. The execution environment moves that ridge: native code with the chip's full vector width raises the compute roof far more than the bandwidth roof, which slides the ridge right and pushes kernels that looked compute-bound back into the memory-bound camp.

29.2.4 The forms of parallelism🔗⧉

Instruction-level parallelism overlaps independent operations within a core. Data dependencies constrain it: ten independent accumulators expose more overlap than ten updates to the same accumulator.

SIMD applies an operation to several lanes of a vector instruction. For 32-bit floats, 128, 256, and 512 bits hold four, eight, and sixteen lanes. The instruction set and enabled target determine the available widths. Contiguous access and independent iterations make vectorization easier; gathers, masks, and reductions permit other patterns at additional cost.

The two SIMD tests separate benefits that are easily confused. The polynomial repeatedly computes on a 32 KB working set; the streaming sum visits 16 MB. Four float lanes offer the polynomial more arithmetic throughput. For the sum, reducing the number of arithmetic instructions helps only until fetching the samples becomes the limiting rate. The original measurements recorded about 2.7× for the polynomial and 1.4× for the sum with four-lane WebAssembly SIMD. Those are examples from the manuscript's measurement session, not promises for the reader's processor. The experiment above lets you test the distinction again.

Even for the polynomial, four lanes need not give a fourfold speedup. The scalar build can overlap independent instructions, the vector build still has loop and load overhead, and the two compilations may make different optimization choices. Compare generated work as well as vector width. A small SIMD gain on a streaming kernel can be evidence that scalar execution already approaches the available bandwidth.

Threads expose larger independent tasks, such as tiles. Physical cores may run them concurrently; simultaneous hardware threads share parts of a core. Scaling can stop at memory bandwidth, synchronization, load imbalance, or task overhead. Avoid having workers write different values in the same cache line, which can cause false sharing.

The core-scaling experiment makes the same comparison at a larger granularity. In the cache-resident case, each worker has its own small buffer and mostly uses resources local to a core. In the streaming case, each worker sweeps 16 MB and competes for a shared supply of data. Plot aggregate completed work per second, rather than assuming that the number of workers is the speedup.

In the original manuscript's sixteen-thread laptop measurement, cache-resident arithmetic scaled by about nine, while streaming throughput peaked around eight threads and then decreased. The recorded numbers illustrate a possible outcome; the manuscript did not preserve enough machine configuration to make them a reproducible processor benchmark. The interpretation remains useful when reading your own curves: shared execution resources, unequal core speeds, and overhead can keep the arithmetic curve below ideal scaling, while a flat streaming curve says that additional workers are failing to obtain more data per second. More threads can then add contention without increasing useful throughput.

GPU SIMT groups threads for execution and combines multithreading with caches and other local storage; it does not replace caching altogether. Distributed execution adds communication among machines. Asynchronous execution can overlap independent transfers and computation, provided buffers remain valid and dependencies are synchronized.

Amdahl’s law adds a limit even before memory contention: work that remains serial cannot be divided among more cores. If one tenth of the original execution time remains unchanged, accelerating the rest without bound still gives at most a tenfold overall speedup. Thread launch, synchronization, and imbalance can reduce that gain further. This is why a fast parallel inner loop is not enough; measure the fraction of the complete pipeline it actually accelerates.

29.2.5 Measuring and improving a kernel🔗⧉

Start from a release build, a representative input, and a correctness check. Profile to find expensive stages, then test a specific explanation: too much traffic, poor reuse, limited vectorization, a serial reduction, or too little work per task. Change one factor and measure again.

Benchmark both the kernel and the complete path that matters to the application. For steady-state timing, warm up JIT compilation and allocate reusable buffers beforehand; report cold-start compilation and allocation separately when they affect the user. Synchronize asynchronous work before stopping the timer. Run enough repetitions for stable measurements, consume outputs, and report variation as well as a central value. Record hardware, compiler, target flags, dimensions, precision, thread count, and whether inputs were cache-resident. Sustained camera workloads also need thermal steady-state measurements.

A profile becomes useful when it identifies a mechanism. False sharing, for example, means workers update different values on one cache line, causing coherence traffic between cores even though the program shares no individual value. Padding or assigning contiguous disjoint regions can change that traffic. Load imbalance is different: one worker receives more work and holds up completion. More threads do not repair either problem automatically. They need changes to data layout or task assignment.

29.2.6 Why photography is hard for the machine🔗⧉

A pipeline couples many stages, often with neighborhoods, reductions, pyramids, and branches to several consumers. A 12-megapixel RGB float image alone occupies about 144 MB, before intermediates or burst frames. Whether that fits in cache depends on the machine, but storing many such intermediates is expensive.

The scheduling problem is to keep useful regions available while supplying enough independent work. Materializing a producer once avoids recomputation but retains its storage; inlining it avoids a buffer but may repeat its work at every use. Tiling can compromise between them. This producer-consumer trade is central to Halide [@ragan-kelley-etal-2012; @ragan-kelley-etal-2013].

The difficult choice is often across stages rather than within one loop. A producer may feed both a pyramid and a full-resolution branch, so storing its output helps reuse but lengthens its lifetime. Fusing it into one consumer can require recomputing it for the other. Small tiles improve locality yet increase overlapping halo work and scheduling overhead. Large tasks expose less parallelism. These interacting choices explain why the schedule deserves its own representation instead of being buried in a single hand-written loop nest.

29.2.7 Keep the comparison valid🔗⧉

Compare candidate changes at the same output contract: boundary rules, precision, and acceptable numerical error. After an optimization, run the checks in Chapter 9.1, Developing, testing and debugging and inspect image differences. An apparent speedup from omitted work, an unfinished GPU dispatch, or a changed approximation does not measure the same implementation task.