Layered memory hierarchy

Modern processors execute instructions in nanoseconds, whereas large-capacity storage technologies are substantially slower. A processor that waits for every instruction and data item to arrive from main memory would spend much of its time idle. Memory-system design therefore exploits two observations about program behavior:

The memory hierarchy places several storage technologies between the processor and persistent storage. Small, fast, expensive memories are located near the processor, while large, slower, less expensive memories are placed farther away. Caches exploit locality by retaining recently used blocks. Virtual memory extends the apparent address space of a process and provides protection, relocation, sharing, and controlled movement between main memory and secondary storage.

At postgraduate level, memory hierarchy should be understood not merely as a collection of caches, but as an integrated performance, consistency, protection, and resource-management system. Its behavior depends on address translation, replacement policies, write policies, concurrency, workload characteristics, operating-system decisions, and application access patterns.

Learning Objectives

1. The Memory-Hierarchy Model

A typical hierarchy contains registers, one or more cache levels, main memory, solid-state or magnetic storage, and archival storage. Registers are managed directly by the instruction set and compiler. Caches are generally managed by hardware, although software can influence them through data layout and instructions. Virtual memory is jointly managed by hardware and the operating system.

Level	Typical role	Relative capacity	Relative speed	Management
Registers	Operands and intermediate results	Very small	Fastest	ISA/compiler
L1 cache	Frequently used instructions/data	Small	Very fast	Hardware
L2/L3 cache	Shared or larger working set	Medium	Fast	Hardware
Main memory	Resident process pages	Large	Slower	Hardware/OS
SSD/HDD	Backing store and files	Very large	Much slower	Operating system

The hierarchy is effective because a program usually references a comparatively small active set during a period of execution. This active set is often called the working set. If the working set fits in a nearby level, most accesses can be served quickly. If it does not, misses increase and performance may collapse.

Figure: Conceptual memory hierarchy. Moving upward generally reduces latency and capacity while increasing cost per bit.

1.1 Locality and reference behavior

A sequential array traversal has strong spatial locality because consecutive elements occupy nearby addresses. A loop repeatedly accessing a small set of variables has temporal locality. Pointer-intensive structures, randomized hash-table access, and some graph algorithms may exhibit weak locality. Consequently, the same hardware hierarchy can perform very differently for different applications.

Locality is not guaranteed by programming language semantics alone. Data structure layout, alignment, loop ordering, blocking, prefetching, and parallel scheduling all influence the physical reference stream. In matrix multiplication, for example, tiling divides a large computation into submatrices whose active data can remain in cache, reducing capacity misses.

2. Cache Organization and Address Decomposition

A cache stores fixed-size cache lines or blocks. Each line contains data and metadata, commonly including a valid bit, tag, and sometimes dirty, coherence, or replacement state. A byte address is conceptually divided into:

If the cache capacity is C bytes, line size is B bytes, and associativity is A ways, the number of sets is:

The number of offset bits is log₂ B, assuming B is a power of two and the address is byte-addressable. The number of index bits is log₂ S, assuming S is a power of two. Remaining address bits form the tag. These relationships apply to conventional physically or virtually indexed caches; actual designs can impose additional constraints to avoid synonym and timing problems.

Worked Example 1: Cache fields

Assume a 32-bit byte address, a 16 KiB cache, 64-byte lines, and 4-way set associativity. The number of sets is:

The offset requires log₂ 64 = 6 bits, and the set index requires log₂ 64 = 6 bits. Therefore, the tag contains:

2.1 Mapping organizations

In a direct-mapped cache, each memory block has exactly one possible cache location. It is simple and fast, but two heavily used blocks mapping to the same location can repeatedly evict one another.

In a fully associative cache, a block may occupy any line. This minimizes conflict misses but requires expensive parallel tag comparison and is generally used only for small structures such as some TLBs.

In an A-way set-associative cache, each block maps to one set but may occupy any of A ways within that set. This is a practical compromise between lookup cost, capacity, and conflict behavior.

2.2 Miss classification

A compulsory miss occurs on the first reference to a block. A capacity miss occurs because the cache cannot hold the active blocks needed by the workload. A conflict miss occurs because blocks compete for restricted locations, even though total capacity might be sufficient. In multicore systems, coherence misses may result when another core invalidates a cached copy.

A cache miss may be serviced by a lower cache, main memory, or—if address translation and residency are involved—by secondary storage. These events must not be conflated: a TLB miss is not necessarily a cache miss, and a cache miss is not necessarily a page fault.

3. Cache Performance and Design Policies

Here, T_hit is hit time, m is the miss rate expressed as a fraction of accesses, and T_miss is the additional miss penalty after a miss. The formula assumes every access first incurs hit time and that the miss penalty is measured beyond that hit time.

Here, T₁ and T₂ are hit times, m₁ and m₂ are local miss rates at L1 and L2, and P₂ is the penalty after an L2 miss. If an L2 miss rate is reported as a global rate relative to all processor accesses, the expression must be reformulated; local and global miss rates must not be mixed.

Worked Example 2: AMAT

Suppose L1 hit time is 1 ns, the L1 local miss rate is 5%, L2 hit time is 8 ns, and the L2 local miss rate is 20%. Main-memory penalty after an L2 miss is 80 ns. Then:

The result is an average under the stated probabilities. It does not predict the latency of every individual access, and it ignores queueing, overlap, prefetch effects, and bandwidth saturation.

3.1 Write policies

With write-through, every write updates the lower level immediately or through a write buffer. This simplifies consistency and recovery but can generate substantial traffic. With write-back, a line is updated in the cache and written to the lower level only when evicted. A dirty bit identifies modified lines. Write-back reduces traffic but requires more complex coherence and eviction handling.

With write-allocate, a write miss first loads the target line and then modifies it. This is often paired with write-back. With no-write-allocate, a write miss bypasses the cache, commonly paired with write-through. The best choice depends on whether future accesses are likely to reuse the written line.

3.2 Replacement and prefetching

When all ways in a set are occupied, a replacement policy chooses a victim. Least Recently Used (LRU) is conceptually attractive but expensive to implement exactly for high associativity. Pseudo-LRU, random, and adaptive policies reduce hardware cost or respond better to particular workloads.

Hardware prefetchers predict future accesses and fetch lines before demand. Correct prefetching can reduce apparent miss latency, but inaccurate prefetches consume bandwidth, displace useful data, and may increase energy use. Software prefetching gives the compiler or programmer more control but can be fragile under changing microarchitectures.

4. Virtual Memory and Address Translation

A virtual address is generated by a process. The memory-management unit (MMU) translates it to a physical address. Virtual memory allows each process to see a private, contiguous address space even when physical memory is fragmented. It also supports isolation, controlled sharing, relocation, memory overcommit, and demand paging.

In paging, virtual memory is divided into fixed-size pages, and physical memory is divided into same-size frames. A virtual address consists of a virtual page number (VPN) and page offset. The offset is unchanged by translation. The page table maps the VPN to a physical frame number (PFN), together with permission and status bits such as valid, readable, writable, executable, accessed, and dirty.

For page size P bytes and virtual address width w, the number of offset bits is log₂ P, assuming P is a power of two. The VPN occupies the remaining w − log₂ P bits. The physical address is formed by concatenating the PFN and unchanged offset.

4.1 Translation Lookaside Buffer

A translation lookaside buffer (TLB) caches recent virtual-to-physical translations. On a TLB hit, translation is obtained without walking the page table. On a TLB miss, hardware or software performs a page-table walk. If the page-table entry indicates that the page is not resident, a page fault is raised and the operating system must intervene.

TLB reach is the amount of virtual memory that can be translated by the TLB without replacement:

For a set-associative TLB, this is total coverage, not a guarantee that every access pattern will fit. Large pages increase reach but can waste memory and complicate allocation.

4.2 Multi-level page tables

A single page table for a large virtual address space can consume substantial memory, especially when the process uses only a small fraction of that space. Multi-level page tables allocate lower-level tables only for populated regions. A virtual address is split into several indexes and an offset; each index selects an entry at one level.

A multi-level walk reduces unused page-table storage but increases translation latency on a TLB miss. Page-walk caches and hardware walkers reduce this cost. Some systems use inverted or hashed page tables, particularly when physical memory is the natural organizing dimension.

4.3 Page faults and replacement

A page fault occurs when a referenced virtual page is not currently mapped to a usable physical frame. The operating system validates the reference, locates the page in a file or swap area, selects a victim frame if necessary, writes the victim if dirty, reads the required page, updates the page table, and restarts the faulting instruction.

where p is the page-fault probability, M is the ordinary memory-access time, and F is the complete page-fault service time, including operating-system handling and storage I/O. This simplified model assumes one memory reference per observation and treats F as inclusive of the normal access cost. Because F may be millions of nanoseconds or more, even a very small p can dominate performance.

Worked Example 3: Page-fault impact

Let ordinary memory access be 100 ns, page-fault service time be 8 ms, and page-fault probability be 10⁻⁶. Converting 8 ms to 8,000,000 ns:

EAT = (1 − 10⁻⁶) × 100 + 10⁻⁶ × 8,000,000
= 99.9999 + 8
≈ 108.0 ns

Although only one access in a million faults on average, the mean access time rises by approximately 8%. If the fault probability were 10⁻⁴, the storage term alone would be 800 ns, making the degradation much more severe.

5. Working Sets, Thrashing, and Allocation

The working-set model describes the pages actively used during a time window. If a process receives fewer frames than its current working set requires, it faults frequently. The processor then spends more time servicing faults than executing useful instructions; this condition is called thrashing.

Operating systems manage this risk through page-replacement policies, resident-set limits, admission control, and monitoring of fault rates. Global replacement allows a process to take frames from another process, whereas local replacement restricts victims to the process’s allocation. Global policies may improve overall utilization but can create interference and unpredictability.

Replacement algorithms include FIFO, optimal replacement, LRU approximations, and clock variants. The optimal algorithm requires knowledge of future references and is therefore a theoretical benchmark. FIFO is simple but can display Belady’s anomaly, in which adding frames increases faults for some reference strings. LRU has the stack property in its exact form, but exact implementation is costly; clock algorithms approximate recency using reference bits.

Page size involves competing effects. Larger pages reduce page-table size and improve TLB reach, but they increase internal fragmentation and may transfer unused data. Smaller pages reduce waste and can improve fine-grained protection, but increase page-table and TLB pressure. There is no universally optimal page size.

6. Memory Hierarchy in Multicore Systems

In a multicore processor, each core may have private L1 and L2 caches, while a last-level cache is shared. Multiple caches can hold copies of the same memory block, so a cache-coherence protocol is required. Protocols such as MESI classify a line as Modified, Exclusive, Shared, or Invalid. A write by one core may invalidate or update copies held by other cores.

Coherence is distinct from consistency. Coherence concerns the visibility and ordering of writes to a single memory location or cache line. The memory-consistency model specifies ordering relationships among operations to different locations. A programmer may observe weak ordering unless synchronization instructions, locks, atomics, or language-level memory models impose constraints.

False sharing occurs when independent variables used by different cores occupy the same cache line. Although the variables are logically independent, writes cause repeated coherence invalidations. Padding, alignment, structure-of-arrays layouts, and partitioning can reduce false sharing, but padding increases memory footprint and may harm locality elsewhere.

Non-uniform memory access (NUMA) systems make physical placement important: a core accesses local memory faster than remote memory attached to another socket. NUMA-aware allocation, thread affinity, first-touch placement, and data partitioning are therefore essential for scalable applications.

7. Performance Analysis and Optimization

A sound analysis separates latency, bandwidth, capacity, and concurrency. Latency is the delay for one access; bandwidth is the rate of data transfer; capacity determines how much data can be retained; concurrency describes how many requests can be outstanding. A streaming application may be bandwidth-bound despite low cache-miss latency, whereas a pointer-chasing application may be latency-bound because later addresses depend on earlier loads.

Useful measurements include cache miss rates, cycles per instruction, memory-level parallelism, TLB miss counts, page-fault rates, bandwidth utilization, and stalled cycles. Measurements must be interpreted carefully: hardware counters can be model-specific, sampled, multiplexed, or affected by speculation. A benchmark should report input size, thread count, compiler options, processor configuration, NUMA placement, and warm-up conditions.

Optimization must consider the entire hierarchy. A transformation that improves L1 locality can increase instruction count, register pressure, or TLB pressure. Similarly, a larger page can improve translation coverage while increasing memory waste and reducing flexibility.

8. Illustrative Case Study: Tiled Matrix Multiplication

Background. Consider a scientific application multiplying two dense matrices. A naïve implementation accesses matrix elements in an order that repeatedly evicts data from the cache. The matrices are much larger than the private L1 cache.

Problem. The application has adequate arithmetic throughput but achieves poor performance because its working data for an inner loop exceeds cache capacity. Hardware counters show high L1 and L2 miss rates and substantial memory bandwidth consumption.

Analysis. Let a square tile contain b × b elements, with each element occupying e bytes. Three tiles—one from each input/output matrix—must fit approximately in a target cache of capacity C, leaving space for other data. A simplified capacity condition is:

Here, α is a utilization factor below 1 that reserves capacity for other cache lines and metadata. This is a design estimate, not a guarantee, because associativity, replacement, alignment, and simultaneous threads also matter.

Approach. The matrices are partitioned into tiles. The algorithm loads submatrices, performs many arithmetic operations on data while it remains resident, and then advances to the next tile. Tile size is selected experimentally for each cache level. Data alignment and thread placement are controlled, and measurements are taken after warm-up.

Outcome. Tiling increases temporal reuse and reduces capacity misses. However, excessively large tiles create conflict and capacity misses, while excessively small tiles increase loop overhead. Parallel execution also requires avoiding false sharing in output tiles and balancing work across NUMA domains.

Learning points. The case demonstrates that cache capacity alone does not determine performance. Associativity, line size, TLB reach, memory bandwidth, thread placement, and synchronization all influence the result. It also illustrates why analytical bounds should guide, but not replace, measurement.

9. Security, Reliability, and Governance

Memory systems are security boundaries. Page permissions help prevent unauthorized reads, writes, and instruction execution. Address-space isolation limits direct access between processes, while privileged modes restrict operating-system structures. However, microarchitectural side channels can reveal information through timing, cache occupancy, branch prediction, or speculative execution effects even when architectural permissions are correct.

Defensive practices include constant-time implementations for sensitive operations, avoiding secret-dependent memory access where appropriate, partitioning or flushing shared resources, restricting high-resolution timers, applying validated microcode and operating-system updates, and reviewing cloud co-tenancy assumptions. No single mitigation eliminates every side channel; security depends on threat model and deployment context.

Reliability is also important. Memory errors may arise from faulty cells, electrical disturbance, aging, or radiation. Error-correcting memory can detect and correct certain errors, while scrubbing periodically reads and rewrites lines to prevent correctable errors from accumulating. Systems should log corrected and uncorrected errors and define recovery policies for poisoned or corrupt data.

Governance concerns include secure erasure, retention of sensitive pages in swap or crash dumps, isolation in virtualized environments, and accountability for performance interference in shared infrastructure. Encryption at rest does not automatically protect data while it is resident in ordinary memory; confidential-computing technologies attempt to protect memory contents from selected privileged or physical adversaries, but introduce key-management, performance, and trust-boundary questions.

10. Contemporary Developments and Research Directions

Recent systems increasingly combine heterogeneous memory technologies, including high-bandwidth memory, persistent memory, compressed memory, and tiered NUMA resources. Memory pooling and fabric-attached memory seek to separate capacity from processor location. These designs make placement and migration policies more important than in traditional uniform systems.

Machine-learning workloads motivate specialized memory hierarchies, near-memory processing, and data-movement reduction. In many such workloads, energy spent moving data can rival or exceed arithmetic energy. Compression, sparsity, scratchpad memories, and application-controlled data placement are active research areas.

Research challenges include predictable performance under contention, secure resource sharing, efficient page migration, memory disaggregation, scalable coherence, and programming models that expose locality without tying applications to one hardware implementation. A recurring methodological principle is to evaluate both average performance and tail latency: rare page faults, coherence storms, or memory congestion can dominate service-level objectives.

Best-Practice Design Principles

Chapter Summary

Memory hierarchy reduces the effective cost of storage by exploiting temporal and spatial locality. Caches organize data into lines and use mapping, associativity, replacement, and write policies to balance hit time, capacity, and miss behavior. The average memory access time combines hit costs with conditional lower-level penalties; correct use requires distinguishing local from global miss rates.

Virtual memory separates a process’s virtual address space from physical memory. Paging, page tables, TLBs, permissions, and page-fault handling provide translation, protection, sharing, and flexible allocation. TLB reach, page size, working-set size, and replacement policy strongly affect performance. Excessive demand paging causes thrashing.

Multicore systems add coherence, consistency, false sharing, and NUMA concerns. Effective optimization requires measurement of latency, bandwidth, capacity, concurrency, cache and TLB behavior, and page faults. Finally, memory systems must be designed as security and reliability mechanisms as well as performance mechanisms, because side channels, memory faults, data remnants, and shared-resource interference create important operational risks.

Key Terms

Locality: The tendency of programs to reuse recently accessed or nearby addresses.

Associativity: The number of possible locations for a block within its cache set.

AMAT: Average memory access time, including hit time and expected miss penalties.

Page fault: An exception raised when a referenced page is not presently usable in physical memory.

Working set: The pages or blocks actively required during a specified execution interval.

False sharing: Coherence interference caused by independent data sharing a cache line.

NUMA: A system in which memory-access latency depends on processor and memory location.

Write-back: A policy that delays lower-level update until a modified line is evicted.

Review Questions

Short Answer Questions

Long Answer Questions

Analytical / Application Questions

Multiple Choice Questions with Answers

Question 1

Which property explains why a recently accessed memory location is likely to be accessed again soon?

Question 2

A 16 KiB cache uses 64-byte lines and is 4-way set associative. How many sets does it contain?

Question 3

For a two-level cache, which miss-rate convention is required by the AMAT expression using a nested lower-level penalty?

Question 4

Question 5

Question 6

A page-fault probability is 10⁻⁶ and fault service time is 8 ms. Why can this probability matter significantly?

Correct Answer: B. Storage service time is much larger than ordinary memory-access time

Question 7

Which cache policy normally marks a modified line and delays writing it to the lower level until eviction?

Question 8

Correct Answer: B. Independent variables used by different cores occupy one cache line

Question 9

Correct Answer: B. They allocate lower-level tables only for populated regions

Question 10

Which transformation most directly improves reuse by keeping submatrices in cache during matrix multiplication?

Chapter 5 Memory Hierarchy and Virtual Memory

Memory Hierarchy and Virtual Memory

Introduction and Context