The machine under the bound: locality, the memory hierarchy and the constant that is not small

Unit one showed that a complexity bound is a theorem about a stated machine, and this unit supplies the machine. The bound is usually stated for a random-access model, in which every memory reference costs the same, and no computer of the past half-century satisfies that description: between the register file and a backing store sit several cache levels, each an order of magnitude slower than the one above. When two algorithms share an asymptotic operation count, the hierarchy decides which runs faster, and it often inverts the ranking the bound predicts.

The claim is narrow: the hardware rewards locality of reference, not the operation count, and a bound that ignores locality describes a machine nobody uses.

The uniform-cost model, and the machine it describes

The random-access model counts each memory reference as one step. Denning (1968) formalised the working set as the pages a running program references in a recent window, and named the assumption that makes any hierarchy worth building: locality of reference, the tendency of a running program to concentrate its references in a small region of the address space. The uniform-cost model is therefore not a harmless simplification: it describes a machine in which locality is assumed irrelevant, while the hardware is built on the opposite assumption.

Aggarwal and Vitter (1988) replaced the operation count with a measurement of the hierarchy: their input/output model counts transfers of blocks of size B between an internal memory of size M and a slower store, and they give tight bounds for sorting, the FFT and matrix transposition. The sorting bound is proportional to N divided by B times the base-(M/B) logarithm of N divided by B, which is not the random-access bound at all: substituting M = 2 and B = 1 recovers O(N log N).

Frigo, Leiserson, Prokop and Ramachandran (1999) removed the parameters. Their cache-oblivious algorithms reach asymptotically optimal cache complexity for matrix transposition, the FFT and sorting, using no variable that depends on cache size or line length, and the bound holds at every level. Read one way this supports the thesis; read the other way it is the sharpest objection.

The constant is not small

Unit one noted that a bound hides a constant, and the hierarchy is where that constant lives. Gray and Shenoy (2000) report a disk of their time that stored over 70 GB, with an access time of about 10 milliseconds and a transfer rate of about 25 MB per second, so a full scan took 45 minutes. Their decomposition matters more than the figures: a random access pays a seek, then half a rotation, then the transfer, while a sequential transfer pays neither.

The processor side of the ratio is the memory wall. Wulf and McKee (1995) took microprocessor performance to grow by roughly 80 per cent a year, on Baskett's estimate, and DRAM by about 7 per cent a year, on Hennessy's figures, and noted that the gap between two diverging exponentials grows exponentially. On those assumptions they projected an average of 1.52 cycles per memory access in 2000, 8.25 in 2005 and 98.8 in 2010: even at a 99.8 per cent hit rate, they found, performance would hit a five-cycle-per-access wall within eleven or twelve years.

Drepper (2007) supplies the measured middle of the hierarchy: an L1 data cache hit at about 3 cycles, an L2 hit at about 14 and a main-memory access at about 240, and prefetching hides that latency only while the access pattern is predictable. Ruemmler and Wilkes (1994) make the point about the device: their calibrated disk model has an error fourteen times smaller than a first-order model's, and the disk's own cache is the most important feature to model. The constants are properties of the device, and a low-cost phone in a reader's hand has the same hierarchy with smaller numbers throughout.

Locality is something the hardware exploits

The hardware is built to detect and reward locality. Falsafi and Wenisch (2014) survey hardware prefetching, which predicts a future address and fetches it early to hide the latency of the miss; irregular, pointer-chasing workloads are precisely the ones that baffle the policies built into modern processors, and a wrong guess wastes bandwidth and pollutes the cache.

The clearest measured evidence is Chilimbi, Hill and Larus (1999). They reorganised dynamically allocated pointer structures by clustering elements used together into the same cache block and colouring heavily used elements into non-conflicting regions. In microbenchmarks their cache-conscious trees ran four to five times faster than naive trees and 1.5 times faster than B-trees; on full applications the same idea gave 42 per cent to RADIANCE, 27 per cent to VIS and 28 to 194 per cent across the Olden suite, beating prefetching by 3 to 194 per cent. Nothing there changes an operation count: a contiguous array is prefetchable, a linked list scattered across the heap is not.

Contested question: is the memory wall a law or a constraint?

The literature agrees about the mechanism and divides about its status. Wulf and McKee (1995) write that under each of their scenarios system speed is dominated by memory performance, framing it as an unavoidable consequence of two rates: if the gap keeps growing, an access will soon cost tens or hundreds of cycles. On this reading the hierarchy is a first-order design constraint.

McKee (2004) treats the trend as a question rather than a law. Returning to the note a decade later, she asks for which applications the wall actually binds, answers that it binds for many but not all, and writes that the prediction is probably wrong and that the only contribution available is to look for architectural solutions. The mechanism is not in dispute, only whether the constraint is fixed.

A second disagreement cuts underneath the first. If locality is what matters, must an algorithm know the hierarchy's parameters? Frigo and colleagues (1999) answer no. Their cache-oblivious algorithms reach optimal cache complexity without being told a block size or a cache size. Ghosh, Martonosi and Malik (1999) answer that the parameters can be known and used. Their cache miss equations characterise the misses of a loop nest analytically for a given cache configuration, and they choose array padding, offsets and blocking factors from it.

A study of a particular shape would settle the disagreement. It would state the memory model, derive the predicted misses, and measure the same algorithm on the same machine, reporting the residual and the distribution of misses rather than only the mean. Ruemmler and Wilkes (1994) show the comparison is possible for a device model, and Ghosh and colleagues (1999) for a loop nest, but no paper here performs it on an interface workload.

Rate the sides by their evidence. Wulf and McKee (1995) project the wall from two growth rates, an argument from extrapolation rather than a measurement, and McKee (2004) revises it a decade later, finding the wall binds for many applications but not all. The strongest objection is that locality belongs to the access pattern a designer chooses, so a bound ignoring it still ranks two pointer-chasing algorithms correctly. While the dispute is open, a designer measures the miss rate on the workload that runs, not on a benchmark the wall was named for.

Where the argument is heading

Williams, Waterman and Patterson (2009) propose the roofline model, which bounds attainable performance by the lower of peak compute and the product of memory bandwidth and operational intensity, so a workload is either compute-bound or memory-bound and a low-intensity kernel stays memory-bound however much arithmetic is added. Mutlu (2013) argues the memory system is a fundamental bottleneck, recording that DRAM capacity grew about sixteenfold while latency fell by only about a fifth. The hierarchy has also left the box. Das Sharma, Blankenship and Berger (2024) survey the Compute Express Link, an open interconnect that gives a processor coherent cache-line access to memory buffers and accelerators over a PCIe-class link, at a latency well above local DRAM, so capacity can be pooled without adding a memory channel and the second tier becomes a fabric tier with its own cost.

Borkar and Chien (2011) explain why. Energy efficiency, rather than transistor count, now limits processor performance, so frequencies rise slowly and gains come from parallelism and specialisation, and the memory wall is not a temporary lag a faster clock will close because the clock is no longer speeding up. The bound survives as the opening move while the memory model becomes the second.

The sources this unit rests on

• Aggarwal, A. and Vitter, J. (1988). The input/output complexity of sorting and related problems. Communications of the ACM. doi:10.1145/48529.48535 Aggarwal and Vitter prove tight upper and lower bounds on block transfers between fast and slow memory for sorting, the FFT, permuting and matrix transposition. It is a theorem inside a stated I/O model, and it supplies the unit's cost model.
• Borkar, S. and Chien, A. A. (2011). The future of microprocessors. Communications of the ACM. doi:10.1145/1941487.1941507 Borkar and Chien argue that energy efficiency, not transistor count, now limits processor performance, so gains must come from heterogeneity and specialisation. It argues from technology trends rather than measuring applications, and it explains why the memory gap persists.
• Chilimbi, T. M., Hill, M. D. and Larus, J. R. (1999). Cache-conscious structure layout. Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation. doi:10.1145/301618.301633 Chilimbi, Hill and Larus reorganise pointer structures, clustering elements used together into one cache block and colouring hot elements into non-conflicting regions, and report speedups from the layout change alone. It is a measured study, and it shows layout is a design decision.
• Denning, P. J. (1968). The working set model for program behaviour. Communications of the ACM. doi:10.1145/363095.363141 Denning defines the working set as the pages a program references in a recent window, and derives the behaviour of a demand-paging system from it. It is the primary source behind the locality claim.
• Denning, P. J. (1970). Virtual Memory. ACM Computing Surveys. doi:10.1145/356571.356573 Denning's survey of virtual memory names locality of reference as the property that makes a hierarchy work, and formalises the working set as the pages a program references in a recent window. It supplies the concept the uniform-cost model assumes away.
• Das Sharma, D., Blankenship, R. and Berger, D. (2024). An Introduction to the Compute Express Link (CXL) Interconnect. ACM Computing Surveys. doi:10.1145/3669900 Das Sharma, Blankenship and Berger survey CXL versions 1.0 to 3.0, an open interconnect giving processors coherent cache-line access to memory and accelerators over a PCIe-class link. It adds a fabric tier to the modelled hierarchy.
• Drepper, U. (2007). What Every Programmer Should Know About Memory. Red Hat, Inc. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf Drepper's practitioner's report describes how caches, prefetchers, the translation lookaside buffer and non-uniform memory access behave, with measurements and code from one machine. It is a technical report, and it connects the hierarchy to mechanisms a programmer can influence.
• Falsafi, B. and Wenisch, T. F. (2014). A Primer on Hardware Prefetching. Synthesis Lectures on Computer Architecture. doi:10.1007/978-3-031-01743-8 Falsafi and Wenisch set out the design space of hardware prefetchers, explaining how they guess future addresses and how they fail through wasted bandwidth and cache pollution. It is a primer synthesising published designs, and it shows the machine exploits an access pattern.
• Frigo, M., Leiserson, C. E., Prokop, H. and Ramachandran, S. (1999). Cache-oblivious algorithms. 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). doi:10.1109/sffcs.1999.814600 Frigo, Leiserson, Prokop and Ramachandran give algorithms for matrix transposition, the FFT and sorting whose cache complexity is optimal without any variable depending on cache size or line length. It is an asymptotic construction, and the unit's sharpest objection.
• Ghosh, S., Martonosi, M. and Malik, S. (1999). Cache miss equations: a compiler framework for analysing and tuning memory behaviour. ACM Transactions on Programming Languages and Systems. doi:10.1145/325478.325479 Ghosh, Martonosi and Malik derive linear Diophantine equations that characterise the cache misses of a loop nest for a stated cache configuration. It is an analytic model for loop nests rather than an arbitrary workload, and it makes the memory model precise.
• Gray, J. and Shenoy, P. (2000). Rules of thumb in data engineering. Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073). doi:10.1109/icde.2000.839382 Gray and Shenoy reassess rules of thumb for storage design, reporting latencies and throughputs for registers, cache, memory, disk and network, and decomposing a random disk access into seek, rotation and transfer. It is a practitioner's review, and it supplies the unit's constants.
• McKee, S. A. (2004). Reflections on the memory wall. Proceedings of the 1st conference on Computing frontiers. doi:10.1145/977091.977115 McKee revisits the memory wall a decade after the note that named it, asking which applications it binds, and answers that it binds for many but not all. It reflects on a prediction rather than testing one.
• Mutlu, O. (2013). Memory scaling: A systems architecture perspective. 2013 5th IEEE International Memory Workshop. doi:10.1109/imw.2013.6582088 Mutlu argues that the memory system is now a fundamental performance and energy bottleneck, and surveys designs that change the organisation of memory rather than only its speed, noting that capacity grew sixteenfold while latency fell a fifth. It broadens what the unit counts as the second model.
• Ruemmler, C. and Wilkes, J. (1994). An introduction to disk drive modelling. Computer. doi:10.1109/2.268881 Ruemmler and Wilkes explain how a disk drive works, then test how much complexity a model needs to predict performance, and find that seek and rotational latency dominate. It is a calibrated device model, and it shows the constants are properties of the device.
• Williams, S., Waterman, A. and Patterson, D. (2009). Roofline: an insightful visual performance model for multicore architectures. Communications of the ACM. doi:10.1145/1498765.1498785 Williams, Waterman and Patterson introduce the roofline model, which bounds attainable performance by the lower of peak compute and memory bandwidth against operational intensity, so a low-intensity kernel stays memory-bound. It is a diagnostic model that makes the bandwidth ceiling visible.
• Wulf, W. A. and McKee, S. A. (1995). Hitting the memory wall: implications of the obvious. ACM SIGARCH Computer Architecture News. doi:10.1145/216585.216588 Wulf and McKee observe that processor performance had been improving faster than memory latency, and project that the gap would dominate system performance. It is an essay arguing from two growth rates, and it named the memory wall.