Cache hierarchy

Lore & Background

In the history of computer and electronic chip development, there was a period when increases in CPU speed outpaced the improvements in memory access speed. The gap between the speed of CPUs and memory meant that the CPU would often be idle. This issue motivated the creation of memory models with higher access rates. The concept of cache memory was first proposed by Maurice Wilkes, a British computer scientist at the University of Cambridge in 1965, who called such memory models 'slave memory'. Between roughly 1970 and 1990, papers and articles by Anant Agarwal, Alan Jay Smith, Mark D. Hill, Thomas R. Puzak, and others discussed better cache memory designs. The first cache memory models were implemented at the time, but the need for faster memory models continued because early cache models improved data access latency, yet it was not feasible for a cache to approach the size of main memory due to cost and technical limitations. From 1990 onward, ideas such as adding a second-level cache as a backup for the first-level cache were proposed by Jean-Loup Baer, Wen-Hann Wang, Andrew W. Wilson, and others. When simulations and implementations demonstrated the advantages of two-level cache models, the concept of multi-level caches caught on as a new and generally better model. Since 2000, multi-level cache models have received widespread attention and are currently implemented in many systems, such as the three-level caches present in Intel's Core i7 products.

Reader's Guide

Cache hierarchy is significant because it addresses the bottleneck created by the growing gap between CPU speed and main memory access speed. By using multiple levels of cache, each with different sizes and access times, the average access time (AAT) for data retrieval is significantly reduced compared to accessing main memory directly. The AAT formula—hit time plus (miss rate times miss penalty)—shows that even with a small, fast L1 cache having a 10% miss rate, the AAT drops dramatically from 50 ns (main memory only) to 6 ns. Adding an L2 cache further reduces AAT to 1.55 ns, and an L3 cache brings it to 1.5101 ns. This design allows CPU cores to process faster despite memory latency. However, cache memory comes at an increased marginal cost than main memory, increasing overall system cost. Cached data is stored only so long as power is provided. Increased on-chip area is required for the memory system. Benefits may be minimized or eliminated in the case of large programs with poor temporal locality that frequently access main memory. The number of cache levels can be designed by architects according to their requirements after checking for trade-offs between cost, AATs, and size. Modern processors have up to three or four cache levels, with the general trend being to keep L1 small and at 1–2 CPU clock cycles from the processor, while lower levels increase in size to store more data, resulting in a better AAT.

Did You Know?

• Cache hierarchy was first proposed by Maurice Wilkes in 1965, who called it 'slave memory'.
• The average access time (AAT) for a memory hierarchy is calculated as hit time plus (miss rate times miss penalty).
• In an example with main memory at 50 ns, adding L1, L2, and L3 caches reduced AAT from 50 ns to 1.5101 ns.
• Intel's Core i7 products implement three-level caches.

The Four Tiers and the Online, Nearline, and Offline Distinction

The memory hierarchy organizes computer storage into distinct levels based on response time, with each successive level being larger but slower than the one above it. At the top sit processor registers and cache, followed by system RAM and its controller cards, then secondary (on-line mass) storage, and finally tertiary or off-line bulk storage. Below the processor and main memory, the hierarchy is often called tiered storage, and a formal distinction separates three categories: online storage is immediately available for input/output operations; nearline storage is not instantly accessible but can be brought online quickly without human intervention; offline storage requires manual action to become available. Always-on spinning disks qualify as online, while massive arrays of idle disk (MAID) that spin down represent nearline. Removable media like tape cartridges in an automated tape library are nearline, whereas cartridges that must be loaded by hand are offline. Some architectures also insert a nearline level between online and offline, or treat a paging algorithm as an additional virtual-memory level.

Latency, Pressure, and the Cost of Reaching Deeper

Two key metrics define performance at every level of the hierarchy: latency and bandwidth. Neither is uniform across the system; each value is specific to a particular component. The central design goal is to minimize how far down the hierarchy a computation must reach to manipulate its data, because adding complexity at any level slows the overall structure. When a higher level cannot supply data quickly enough, a lower level fills a buffer and then signals the transfer to begin, limiting the waiting time imposed on faster components. The consequences of failing to stay in fast memory are captured by the term pressure: register pressure forces data to spill from registers into cache, cache pressure produces a cache miss that pulls from main memory, and memory pressure triggers a hard page fault that reaches into mass storage. This cascade is sometimes called the space cost, because a larger working set is more likely to overflow a small, fast level and demand the slower one below it.

The Programmer's Burden and the Division of Labor

Because modern CPUs are so fast relative to memory, the bottleneck for most workloads is the locality of reference in memory accesses and the efficiency of data movement between hierarchy levels. The processor often idles while waiting for I/O to complete. Tackling this problem requires coordinated effort across three parties: programmers handle moving data between disk and main memory through file I/O; hardware manages transfers between memory and caches; and optimizing compilers generate code that steers the hardware toward efficient use of registers and caches. Most high-level languages abstract the hierarchy down to just two levels—working memory and mass storage—leaving only assembly or inline assemblers, as in C, to expose prefetch instructions that preload the cache. Many developers assume a single memory level and hit a performance wall only when their access patterns clash with cache behavior. A classic illustration is changing the iteration order over a three-dimensional array to improve spatial locality, a topic explored in depth in the textbook Computer Systems: A Programmer's Perspective.

Memory Tiering in Heterogeneous Modern Systems

What once appeared as a single, uniform main memory is now frequently a patchwork of heterogeneous components: NUMA nodes, CXL-attached memory on PCIe slots, Optane DCPMMs, and memory embedded in coprocessors or GPUs. Memory tiering is the practice of partitioning this physical address space into performance-based levels and migrating content among them. On Linux, tiering is implemented as an extension of the existing NUMA framework: each memory provider is represented as a CPU-less NUMA node carrying an abstract distance that reflects its relative speed. The mechanism for moving pages between nodes, originally driven by page-fault hotness, has been adapted for tiering by Huang Ying, though Al Maruf's TPP scheme has not been merged into the mainline kernel. A weighted-interleave allocation policy further guides initial placement. Swapping to disk can also be viewed as the lowest form of tiering, completing a picture in which the boundary between main memory and storage has become deliberately blurred.