- Atlas
- Computer Science
- Memory Hierarchy
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
- Virtual Memory 1962-Present
- CPU cache 1965-Present
- Locality-Based Program Behavior Modeling 1965-Present
- Working set 1968-1990
- Consistency model 1979-Present
- Cache coherence 1983-Present
- Cache Coherence and Memory Consistency 1985-Present
- Cache hierarchy 1985-Present
- Three C's Miss Taxonomy 1989-Present
- Latency-Hiding Techniques 1990-Present
- Scratchpad Memory 1990-Present
- Software-Managed and Heterogeneous Memory 2005-Present
- Heterogeneous Memory Systems 2010-Present
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
- Memory hierarchy, Wikipedia
- Cache (computing), Wikipedia
- CPU cache, Wikipedia
- Static random-access memory, Wikipedia
- Locality of reference, Wikipedia
- Virtual memory (History, introduction), Wikipedia
- Page (computer memory), Wikipedia
- Demand paging, Wikipedia
- Memory management unit, Wikipedia
- Cache hierarchy (Background, introduction), Wikipedia
- Cache performance measurement and metric, Wikipedia
- Memory coherence, Wikipedia
- Cache coherence, Wikipedia
- Directory-based cache coherence, Wikipedia
- Consistency model, Wikipedia
- 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.
- 1962-Present
- 1965-Present
- 1965-Present
Locality-Based Program Behavior Modeling
Why are program memory references non-random?
- 1968-1990
- 1979-Present
Consistency model
In what order do writes become visible to all processors?
- 1983-Present
- 1985-Present
Cache Coherence and Memory Consistency
How do coherence and consistency fit together?
- 1985-Present
- 1989-Present
- 1990-Present
Latency-Hiding Techniques
How can memory latency be hidden from the processor?
- 1990-Present
- 2005-Present
Software-Managed and Heterogeneous Memory
How should software manage diverse memory technologies?
- 2010-Present
Heterogeneous Memory Systems
How should systems combine memory technologies of different kinds?
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.
Working set influenced by Virtual Memory
Denning's working set model was formulated to explain and manage demand paging in virtual memory systems, giving a precise account of which pages must stay resident.
Carried by Peter Denning.
Cache coherence influenced by CPU cache
Cache coherence arose directly from the spread of private caches in multiprocessors: once each core held its own cache, protocols were needed to keep copies of shared blocks consistent.
Cache hierarchy grew out of CPU cache
Multilevel cache hierarchies were built by stacking the single cache of the 1960s and 1970s into L1/L2/L3 levels, each filtering misses for the next.
Three C's Miss Taxonomy influenced by CPU cache
Hill and Smith's three C's taxonomy was created to diagnose why the caches that had become universal in the 1980s were missing, decomposing misses into compulsory, capacity and conflict causes.
Carried by Mark Hill; Alan Smith.
Cache Coherence and Memory Consistency grew out of Consistency model
The combined treatment of cache coherence and memory consistency grew out of Lamport's 1979 sequential consistency model, which supplied the ordering framework coherence protocols had to respect.
Carried by Leslie Lamport.
Cache Coherence and Memory Consistency grew out of Cache coherence
Cache coherence protocols such as snooping and MESI were the concrete mechanisms that the later unified coherence-and-consistency framework organized and analyzed.
CPU cache influenced by Virtual Memory
Virtual memory demonstrated that a small fast store could be made to appear large and uniform by exploiting locality, and Wilkes's 1965 'slave memory' proposal explicitly framed the cache as the same idea applied between processor and main memory.
Carried by Maurice Wilkes; Manchester Atlas.
Locality-Based Program Behavior Modeling influenced by CPU cache
Cache measurements of real program traces in the late 1960s and 1970s showed references were non-random, and this empirical work fed directly into formal locality models of program behavior.
Scratchpad Memory reacted against CPU cache
Scratchpad memory was adopted in embedded and DSP processors as an explicit alternative to hardware-managed caches, giving the compiler or programmer direct control over what resides in fast storage.
Three C's Miss Taxonomy influenced by Working set
The capacity-miss category in the three C's is essentially the working set idea restated: a miss is capacity if the cache is too small to hold the program's active set.
Carried by Mark Hill; Alan Smith.
Latency-Hiding Techniques influenced by Cache hierarchy
The widening gap between cache hits and main-memory accesses in multilevel hierarchies, the memory wall, motivated prefetching, out-of-order execution and multithreading as ways to hide that latency.
Heterogeneous Memory Systems influenced by Cache hierarchy
The clean multilevel cache hierarchy of the 1990s blurred into a spectrum of memory technologies with different latencies and persistence, which heterogeneous memory systems then had to manage.
Software-Managed and Heterogeneous Memory grew out of Scratchpad Memory
Software-managed and heterogeneous memory extended the scratchpad model of explicit, programmer- or compiler-controlled placement to GPUs and to systems mixing DRAM with other technologies.
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.
Virtual Memory influenced Hypervisor in Operating Systems
The hypervisor depends on virtual memory's address translation and protection to give each virtual machine its own isolated address space. Without hardware paging the isolation the hypervisor provides would not be practical.
CPU cache grew out of Memory Hierarchy in Computer Systems
The general memory hierarchy idea, formulated with the Atlas and IBM 360 era machines, was made concrete in the CPU cache: a small fast level automatically managed by hardware. Cache design is the hardware branch of the hierarchy concept.
Carried by Maurice Wilkes.
Cache coherence led to Cache-Coherent Shared Memory in Computer Systems
Cache-coherent shared memory is the large-scale generalisation of cache coherence protocols developed for small multiprocessors from the 1980s onward, extended to systems with many nodes and distributed directories.
Cache coherence grew out of Cache hierarchy in Microarchitecture
Cache coherence grew directly out of cache hierarchy design: once several caches hold copies of the same block, a protocol is needed to keep them consistent. Coherence protocols are the multi-cache extension of the hierarchy.
Cache Coherence and Memory Consistency grew out of Memory hierarchy in Digital Systems
Cache coherence is a refinement of the memory hierarchy: it specifies how the multiple cached copies in a hierarchy stay coherent. The coherence frameworks of the 1980s presuppose the hierarchy of levels.
Cache Coherence and Memory Consistency grew out of Memory Hierarchy in Computer Systems
The computer-systems memory hierarchy of the early 1960s is the model that cache coherence later had to make consistent across processors. Coherence and consistency are refinements of that hierarchy for the shared-memory case.
Cache Coherence and Memory Consistency grew out of Memory Hierarchy and Caching in Computer Architecture
Cache coherence protocols were developed to keep the caches of a shared-memory multiprocessor consistent, so the coherence problem only exists because of the cache hierarchy. The coherence and consistency work of the 1980s built directly on the cache/memory hierarchy model established in the 1960s.
Cache Coherence and Memory Consistency influenced by Consistency model in Instruction Set Architecture
Consistency models such as sequential consistency were formulated in the late 1970s for shared-memory multiprocessors and were then taken up by the cache-coherence and memory-consistency work of the 1980s. The coherence framework adopted the consistency-model vocabulary and questions.
Carried by Leslie Lamport.
Cache Coherence and Memory Consistency grew out of Cache hierarchy in Microarchitecture
Coherence protocols govern the cache hierarchy of a multiprocessor, so the coherence framework grew directly out of the cache hierarchy concept. Without multiple cache levels there would be nothing to keep coherent.
Cache Coherence and Memory Consistency led to Cache-Coherent Shared Memory in Computer Systems
Cache-coherent shared memory grew out of work on cache coherence and memory consistency models, combining coherence protocols with a chosen consistency model to present a shared address space across nodes.
Three C's Miss Taxonomy grew out of Memory Hierarchy in Computer Systems
The three C's taxonomy is a refinement of the computer-systems memory hierarchy, explaining cache misses within it. It grew directly out of that hierarchy model.
Latency-Hiding Techniques grew out of Memory hierarchy in Digital Systems
Latency-hiding techniques exist to bridge the latency gaps between levels of the memory hierarchy. They are a refinement of that layered model.

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 HierarchyRelated fields
Fields its ideas are linked to
- Computer Systems 17 links
- Microarchitecture 11 links
- Computer Architecture 8 links
- Digital Systems 7 links
- Storage Systems 7 links
- Distributed Algorithms 3 links
- Instruction Set Architecture 2 links
- Operating Systems 2 links
- Hardware Accelerators 1 link
- Parallel Computing 1 link
- Distributed Databases 1 link
- Concurrency Models 1 link
More in Computer Architecture
- Computer Architecture
- Embedded Systems
- Hardware Accelerators
- Instruction Set Architecture
- Microarchitecture
- Parallel Computing
See where Memory Hierarchy sits on the Map of Human Knowledge