Memory Hierarchy

Every computer program wants two things from memory that cannot both be true: a vast space to store data, and instant access to any of it.

13 frameworks, from 1962 to today · Computer Architecture · Computer Science

still a working view ended · each leads to its entry below

Overview

Every computer program wants two things from memory that cannot both be true: a vast space to store data, and instant access to any of it. Fast memory is expensive and small; cheap memory is large and slow1234. The memory hierarchy is computer architecture's answer to that contradiction1. It is a stack of storage levels — registers, caches, main memory, disk or flash — arranged so that the small, fast levels hold what is being used right now, and the large, slow levels hold everything else13. The whole edifice rests on one empirical fact, locality of reference: programs tend to reuse recently touched data and to touch nearby addresses next25. The history of the subfield is the history of discovering that fact, exploiting it in hardware and software, and then discovering all the ways it breaks.

Virtual memory and the birth of the hierarchy (1950s–1960s)

Early computers had no hierarchy at all: a program addressed a single level of memory directly. As machines grew, two problems appeared. First, programs became larger than the fast memory available6. Second, programmers had to manage overlays by hand — explicitly loading and unloading code segments — which was error-prone and tied software to a particular machine's memory size.

The Manchester Atlas, completed in 1962, solved this with virtual memory: programs address a fictitious, uniform address space, and hardware plus an operating system translate those addresses to physical locations, moving data between a fast main store and a slower backing store (a magnetic drum) automatically6. The key mechanism was paging — dividing memory into fixed-size blocks, called pages, so that any page could live anywhere and be swapped in on demand76. A page fault occurs when a program touches a page not currently in fast memory; the hardware traps, the operating system fetches the page, and the program resumes as if nothing happened89. Atlas's designers, working under Tom Kilburn at Manchester, also built one of the first associative memories to hold the page table, so translation could be fast.

The idea spread quickly. The IBM System/360 of the mid-1960s, designed as a family of compatible machines, made virtual memory a mainstream commercial feature, and the concept of a translation lookaside buffer (TLB) — a small cache of recent address translations — became standard. Virtual memory's deeper consequence was conceptual: it proved that a small fast memory could be made to appear large and uniform, provided the access pattern had enough locality6. That is the template for everything that follows.

Caches and the discovery of locality (1960s–1970s)

Main memory itself was still far slower than the processor. The next step was to insert a small, fast buffer between processor and main memory: the cache3. Maurice Wilkes, in a 1965 paper on "slave memories," described the idea of a small high-speed store that automatically holds recently used blocks of main memory10. The IBM System/360 Model 85, shipped in 1968, was among the first commercial machines with a cache, and it introduced a design still used today: the cache is set-associative, meaning each memory block can go into one of a small set of slots, balancing the simplicity of direct mapping against the flexibility of full associativity.

The 1970s brought the empirical foundation. Working with measurements of real programs, researchers found that memory references are strikingly non-random. Peter Denning had formalized the working set model in 1968: at any moment a program actively uses a small, slowly changing set of pages, and performance depends on keeping that set resident. This was locality made precise, and it justified both virtual memory and caches. The decade also produced the analytical tools: the study of cache miss rates as a function of size, associativity, and block size, and the recognition that a cache's replacement policy (which block to evict) matters far less than its capacity and organization.

The three C's and the science of misses (1980s)

By the 1980s, caches were universal, and the question became: why do caches miss, and what can be done about it? In 1989, Mark Hill and Alan Smith published a taxonomy that organized the field's thinking. A miss is compulsory if the block has never been accessed (unavoidable), capacity if the cache is simply too small to hold the working set, and conflict if the block was evicted because too many blocks mapped to the same set. The "three C's" gave designers a diagnostic: a high conflict rate argues for more associativity; a high capacity rate argues for a bigger cache. The model was later extended (with coherence misses in multiprocessors), but its core insight — that miss behavior decomposes into causes with different fixes — shaped a generation of cache design.

Multilevel hierarchies and the memory wall (1980s–1990s)

As processors got faster, a single cache could not keep up: it had to be large enough to hold the working set but fast enough to match the clock10. The resolution was to stack caches10. The first level (L1) is tiny and fast, close to the pipeline; the second (L2) is larger and slower; later a third (L3) is shared among cores3. Each level filters misses for the next, so the average access time approaches the L1 speed while the effective capacity approaches the largest level. This multilevel hierarchy became standard in the 1990s, and the design questions — inclusion versus exclusion between levels, where to place the TLB, how to share L3 among cores — remain active.

The stakes rose sharply because of what became known as the memory wall: processor speed was growing much faster than DRAM latency, so the gap between a cache hit and a main-memory access widened from a few cycles to hundreds. Memory became the bottleneck, and architecture increasingly became the art of hiding or avoiding that latency1110.

Coherence and consistency in multiprocessors (1980s–1990s)

When multiple processors share memory, caches create a new problem: each core may hold a private copy of a block, and a write by one core must not leave another core reading stale data1213. Cache coherence is the set of protocols that keep these copies consistent1213. The dominant approach, snooping, has each cache watch a shared bus and invalidate or update its copy when another core writes. The MESI protocol (named for its four states: Modified, Exclusive, Shared, Invalid) became the canonical example, developed in the 1980s and widely implemented thereafter. Directory-based coherence, which tracks which caches hold which blocks in a central structure, scaled better to large machines1214.

Coherence is about individual locations; memory consistency is about the order in which writes become visible across the whole system15. The strongest model, sequential consistency (Lamport, 1979), requires all processors to see memory operations in one global order — intuitive but costly. Weaker models (total store order, release consistency) relax the ordering to allow performance, pushing the burden onto programmers and compilers to insert fences where order matters. The tension between programmer convenience and hardware speed has driven this area ever since.

Hiding latency: prefetching, multithreading, and speculation (1990s–2000s)

If memory is slow, one response is to overlap the wait with other work. Prefetching brings data into cache before it is requested, either in hardware (predicting strides in access patterns) or in software (the compiler inserts prefetch instructions). Out-of-order execution lets the processor continue past a stalled load and execute independent instructions16. Simultaneous multithreading (SMT) lets several threads share one core so that when one stalls on memory, another runs. These latency-hiding techniques are microarchitectural, but they exist because of the hierarchy: their whole purpose is to keep the pipeline busy while the memory system catches up. The cost is complexity and, increasingly, energy.

Software-managed and heterogeneous memory (2000s–present)

Not all memory management is automatic. Scratchpad memory — small, fast, explicitly addressed storage with no cache hardware — is common in embedded and digital-signal processors, where the compiler or programmer decides what goes where. GPUs use a similar model with shared memory and explicit synchronization. More recently, the hierarchy has become heterogeneous: systems combine DRAM with non-volatile memory (such as Intel's Optane, introduced in 2017 and discontinued in 2022), high-bandwidth memory stacked beside the processor, and increasingly, memory shared across chiplets and accelerators. The old clean levels — registers, cache, DRAM, disk — have blurred into a spectrum of technologies with different latencies, bandwidths, and persistence properties, and the operating system, runtime, and programmer now share the management job that hardware once did alone.

Where the field stands

Today the memory hierarchy is the central organizing fact of processor design. Caches remain the default, but they are supplemented by prefetchers, compression, and sophisticated replacement policies; coherence protocols are being rethought for chiplet-based systems where a shared bus no longer exists; and the boundary between memory and storage is dissolving as persistent memory technologies mature. The open questions are the old ones in new clothes: how to model locality when workloads are data-intensive and irregular, how to share memory fairly and securely among many cores and tenants, and how to build a hierarchy that is fast, large, cheap, and energy-efficient at once. The Atlas machine's insight — that a small fast store can impersonate a large slow one — still governs every answer.

References

  1. Memory hierarchy, Wikipedia
  2. Cache (computing), Wikipedia
  3. CPU cache, Wikipedia
  4. Static random-access memory, Wikipedia
  5. Locality of reference, Wikipedia
  6. Virtual memory (History, introduction), Wikipedia
  7. Page (computer memory), Wikipedia
  8. Demand paging, Wikipedia
  9. Memory management unit, Wikipedia
  10. Cache hierarchy (Background, introduction), Wikipedia
  11. Cache performance measurement and metric, Wikipedia
  12. Memory coherence, Wikipedia
  13. Cache coherence, Wikipedia
  14. Directory-based cache coherence, Wikipedia
  15. Consistency model, Wikipedia
  16. Out-of-order execution, Wikipedia

The frameworks of Memory Hierarchy

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1962-Present

    Virtual Memory

    How can a small fast memory appear large and uniform?

    Fly to its tower in Nousfarer

  2. 1965-Present

    CPU cache

    How can a small fast buffer speed up main memory access?

    Fly to its tower in Nousfarer

  3. 1965-Present
  4. 1968-1990

    Working set

    Which pages must stay resident for good performance?

    Fly to its tower in Nousfarer

  5. 1979-Present

    Consistency model

    In what order do writes become visible to all processors?

    Fly to its tower in Nousfarer

  6. 1983-Present

    Cache coherence

    How do caches keep shared data consistent?

    Fly to its tower in Nousfarer

  7. 1985-Present

    Cache Coherence and Memory Consistency

    How do coherence and consistency fit together?

    Fly to its tower in Nousfarer

  8. 1985-Present

    Cache hierarchy

    How should caches be stacked into levels?

    Fly to its tower in Nousfarer

  9. 1989-Present
  10. 1990-Present

    Latency-Hiding Techniques

    How can memory latency be hidden from the processor?

    Fly to its tower in Nousfarer

  11. 1990-Present

    Scratchpad Memory

    When should software manage fast memory explicitly?

    Fly to its tower in Nousfarer

  12. 2005-Present

    Software-Managed and Heterogeneous Memory

    How should software manage diverse memory technologies?

    Fly to its tower in Nousfarer

  13. 2010-Present

    Heterogeneous Memory Systems

    How should systems combine memory technologies of different kinds?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Virtual MemoryCPU cacheLocality-Based Program Behavior Model…Working setConsistency modelCache coherenceCache Coherence and Memory ConsistencyCache hierarchyThree C's Miss TaxonomyLatency-Hiding TechniquesScratchpad MemorySoftware-Managed and Heterogeneous Me…Heterogeneous Memory Systems

Beyond the field

Where Memory Hierarchy's ideas came from in other fields, and what they led to there: the strongest 12 of 64 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Memory Hierarchy is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Memory Hierarchy

Related fields

Fields its ideas are linked to

More in Computer Architecture

See where Memory Hierarchy sits on the Map of Human Knowledge