7. Memory Hierarchy and Data Movement

Introduction and Context

A processor can perform arithmetic and logical operations in a few clock cycles, yet the data required for those operations may reside in a memory system that is orders of magnitude slower. Computer performance is therefore determined not only by the speed of the processor but also by how effectively the system moves instructions and data through the memory hierarchy. The central design problem is to provide the processor with the illusion of a large, inexpensive, and fast memory, even though practical systems combine small high-speed storage with much larger and slower technologies.

Memory hierarchy is the organized arrangement of storage levels according to capacity, cost per bit, latency, bandwidth, volatility, and proximity to the processor. Registers, caches, main memory, and secondary storage form the traditional hierarchy. Modern systems add translation lookaside buffers, scratchpad memories, high-bandwidth memory, persistent memory, and distributed or remote memory. Data movement among these levels is governed by hardware mechanisms, operating-system policies, compiler transformations, and application behavior.

The effectiveness of a hierarchy depends primarily on locality. Programs tend to reuse recently accessed data and to access data near recently accessed addresses. Cache design exploits this behavior, while virtual memory extends the hierarchy to storage devices. At postgraduate level, it is important to view memory not as a collection of isolated devices but as a performance system involving latency, bandwidth, concurrency, coherence, consistency, reliability, security, and energy.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain temporal and spatial locality and relate them to memory performance.

2. Analyze cache organization using blocks, sets, associativity, tags, and replacement policies.

3. Distinguish write-through and write-back caches and compare write-allocation strategies.

4. Evaluate multilevel caches, TLBs, virtual memory, DRAM, and non-volatile memory.

5. Calculate average memory access time and identify latency or bandwidth bottlenecks.

6. Explain cache coherence, memory consistency, and the implications of multicore data movement.

7. Assess prefetching, blocking, data layout, and other optimization techniques.

8. Make informed architectural decisions while considering correctness, energy, cost, security, and reliability.

Locality as the Basis of the Hierarchy

Locality is the empirical tendency of programs to access a relatively small working set of instructions and data during a given interval. Temporal locality means that an item accessed recently is likely to be accessed again soon. A loop repeatedly reading the same control variables demonstrates temporal locality. Spatial locality means that an address near one recently accessed is likely to be accessed soon. Sequential traversal of an array is the usual example.

A cache transfers data in blocks, also called cache lines. If a processor requests one word and the block containing that word is fetched, nearby words may be used subsequently at little additional miss cost. Block size must be selected carefully. A larger block can exploit spatial locality and reduce tag overhead, but it also consumes bandwidth, increases miss penalty, and may fetch unused data. Very large blocks can be harmful when accesses are sparse or competing data are displaced.

The working set is the collection of memory blocks actively used by a program during a period. If the working set fits in a cache, the miss rate can be low. If it exceeds the cache capacity, capacity misses increase. Other misses arise because a block is referenced for the first time (compulsory misses) or because different blocks compete for the same location (conflict misses). In a multicore system, coherence actions can also invalidate a previously cached block, producing coherence-related misses.

Locality is not automatic. Pointer-rich structures, randomized access patterns, large data sets, and poor data layout may have weak locality. Conversely, loop interchange, tiling, structure-of-arrays layouts, and reuse-aware algorithms can substantially improve it.

Cache Organization and Address Mapping

A cache divides its storage into lines of equal size. A memory address is interpreted as an offset within a block, an index identifying a set, and a tag used to determine whether the requested block is present. In a direct-mapped cache, each memory block maps to exactly one cache line. Direct mapping is simple and fast, but two frequently used blocks mapping to the same line can repeatedly evict one another.

A set-associative cache divides lines into sets. A block maps to one set but may occupy any of the ways within that set. An n-way set-associative cache therefore provides n candidate positions. Greater associativity reduces conflict misses but increases tag-comparison hardware, energy consumption, and sometimes hit latency. A fully associative cache permits a block to occupy any line and minimizes mapping conflicts, but parallel comparison and replacement are expensive; this organization is more common for small structures such as TLBs.

For a cache with capacity C bytes, block size B bytes, and associativity A ways, the number of sets is:

Sets = C / (B × A).

If the physical or virtual address width is W bits, the block offset requires log₂B bits, the set index requires log₂(Sets) bits, and the remaining bits form the tag. Real systems may include sectoring, way prediction, banking, or skewed indexing to reduce cost or conflict behavior.

A cache hit occurs when the tag of the requested block matches a valid line in the selected set. A miss requires data to be obtained from a lower level. The miss penalty includes lookup and transfer time, possible eviction of a dirty block, and contention for interconnects or memory banks. Thus, cache performance cannot be judged by hit rate alone; line size, miss penalty, hit time, and access frequency must all be considered.

The basic average memory access time model is:

AMAT = hit time + miss rate × miss penalty.

For multiple levels, a two-level formulation is often written as:

AMAT = L1 hit time + L1 miss rate × (L2 access time + L2 local miss rate × main-memory penalty).

Definitions vary across texts, especially concerning whether an access time includes the preceding lookup. The model is useful only when its terms are defined consistently.

Replacement and Write Policies

When a set is full and a new block must be installed, a replacement policy selects a victim. Least recently used (LRU) replaces the block that has not been accessed for the longest time. True LRU becomes expensive for high associativity, so practical systems often use pseudo-LRU, random replacement, or adaptive policies. Random replacement can perform surprisingly well and avoids certain pathological patterns. The best policy depends on workload characteristics rather than on a universal rule.

Write policies determine how stores propagate through the hierarchy. In a write-through cache, every write updates the next memory level, simplifying coherence and recovery but increasing traffic. A write buffer can allow the processor to continue while lower-level updates complete. In a write-back cache, a modified block is written to the next level only when it is evicted. A dirty bit records whether the cached copy differs from the lower-level copy. Write-back reduces traffic for repeated writes but complicates eviction, coherence, and failure handling.

On a write miss, write-allocate fetches the block into the cache before modifying it. It is suitable when the processor is likely to write the block repeatedly. No-write-allocate, also called write-around, sends the write to the lower level without installing the block and can avoid filling the cache with data that will not be reused. Write-back caches are commonly paired with write-allocate, whereas write-through caches may use either strategy depending on the design.

Stores can also be merged in write buffers, and non-temporal or streaming stores can deliberately bypass parts of the cache hierarchy. Such mechanisms are valuable for data that will not be reused soon, but incorrect use can increase traffic or undermine expected locality.

Multilevel Caches and TLBs

A modern processor commonly uses a small, private level-one cache for very low latency, followed by larger level-two and level-three caches. L1 caches are often split into instruction and data caches, allowing simultaneous instruction fetch and data access. Lower levels may be unified and shared among cores. Private caches reduce contention and provide fast access, while shared caches facilitate communication and reduce duplication. These benefits create trade-offs involving capacity, coherence traffic, access latency, and fairness among cores.

Inclusive caches guarantee that a block present in a private upper-level cache is also present in a lower-level cache. Evicting a lower-level block may therefore require invalidating copies above it. Exclusive designs try to avoid duplication, increasing effective aggregate capacity but requiring movement of blocks between levels. Non-inclusive designs provide a compromise and are common in complex processors.

Virtual memory gives each process an apparently private address space and allows physical memory to be extended by storage. A virtual address is translated into a physical address using page tables. Because page-table walks are expensive, processors use a translation lookaside buffer (TLB), a cache of recent virtual-to-physical translations. A TLB miss does not necessarily imply a data-cache miss; it means that translation must be obtained, often through a hardware or software page-table walk.

The order of translation and cache lookup influences latency and protection. Physically indexed, physically tagged caches avoid ambiguity but may require translation before indexing. Virtually indexed, physically tagged caches can begin access early, although constraints on page size, cache size, and associativity are needed to prevent synonym problems. A synonym occurs when different virtual addresses refer to the same physical page. Operating systems and hardware must ensure that aliases do not create inconsistent cached copies.

A page fault occurs when the required page is not in main memory. The operating system must obtain it from storage, possibly evicting another page. Page faults are vastly more expensive than ordinary cache misses, so excessive paging, known as thrashing, can dominate execution time. Working-set management, page replacement, huge pages, and locality-aware allocation can reduce translation and paging overhead.

DRAM, Non-Volatile Memory, and Data Movement

Dynamic random-access memory stores bits using electrical charge in capacitors and requires periodic refresh. DRAM is organized into channels, ranks, banks, rows, and columns. Accessing an open row can be faster than activating a different row. Consequently, the effective latency depends on row-buffer locality, bank conflicts, request scheduling, queue occupancy, and channel contention—not merely on a nominal cycle time.

DRAM provides high capacity at relatively low cost, but its latency has not decreased as rapidly as processor performance. Memory controllers exploit parallelism by scheduling independent requests, interleaving accesses across banks, and prioritizing some requests. These optimizations must balance throughput against fairness and worst-case latency. In real-time or shared systems, maximizing average bandwidth may be inappropriate if it causes unacceptable delay for critical tasks.

Non-volatile memory retains information without power. Flash memory, including solid-state drives, uses electrical charge and is organized into pages and erase blocks. Reads are generally faster than writes, erasure occurs at larger granularities, and cells have finite endurance. Flash controllers use wear leveling, garbage collection, error-correcting codes, and mapping tables. Persistent-memory technologies seek to provide byte-addressable or near-memory access with retention, but they introduce ordering, durability, endurance, and programming-model issues.

A memory hierarchy must move data across buses, cache interconnects, memory channels, storage interfaces, and sometimes networks. Bandwidth is the rate of data transfer, while latency is the delay before a transfer begins or completes. A workload may be latency-bound when each operation waits for one dependent access, or bandwidth-bound when many accesses can proceed but the transfer capacity is saturated. Increasing cache capacity helps capacity misses but does not solve a bandwidth bottleneck caused by streaming data.

Prefetching and Performance Optimization

Prefetching brings data into a cache before the processor explicitly requests it. Hardware prefetchers may detect sequential streams, fixed strides, or more complex patterns. Software prefetch instructions allow compilers or programmers to express expected future accesses. Effective prefetching hides latency, but inaccurate or premature prefetches consume bandwidth, displace useful data, and increase energy use.

A useful prefetcher must balance coverage, accuracy, timeliness, and overhead. Coverage is the fraction of misses that are prefetched; accuracy is the fraction of prefetched lines that are actually used; timeliness measures whether the line arrives before demand. A prefetch that arrives after the demand miss provides little benefit, while one that arrives too early may be evicted before use.

Blocking, or tiling, partitions computation so that a working subset fits in a selected cache level. Matrix multiplication is a classic example: instead of repeatedly traversing entire matrices, computation is organized over small submatrices, increasing reuse. Loop interchange changes the order of nested loops to follow storage order. Data alignment can reduce split-line accesses, while compact representations reduce capacity and bandwidth demands. Structure-of-arrays layouts often benefit vectorized processing, whereas array-of-structures layouts may be preferable when complete records are accessed together.

Parallel programs require additional attention. False sharing occurs when independent variables used by different threads occupy the same cache line. Although the threads do not logically share data, writes cause coherence invalidations and transfer the line between cores. Padding, alignment, partitioning, and ownership-aware data structures can reduce false sharing. NUMA systems require threads to access memory close to their processing socket; first-touch allocation and thread placement are common optimization techniques.

Performance analysis should use measurements rather than intuition alone. Useful indicators include cache miss rates, cycles per instruction, memory-level parallelism, TLB misses, bandwidth utilization, queue occupancy, and stalled cycles. A low miss rate does not guarantee high performance if the remaining misses have large penalties or if the processor cannot overlap them. Profilers and hardware performance counters help identify the actual limiting resource.

Coherence, Consistency, and Correctness

In a multicore system, several caches may contain copies of the same block. Cache coherence concerns the visibility and ordering of writes to a single memory location. Protocols such as MSI, MESI, and MOESI track states including modified, exclusive, shared, and invalid. A write by one core may invalidate or update copies held by other cores. Snooping protocols are practical for smaller shared systems, whereas directory-based protocols scale more effectively by recording sharers and ownership.

Consistency is a broader property describing the ordering of memory operations as observed by processors. A sequentially consistent system gives the impression that operations from all processors occur in one global order consistent with each processor's program order. Weaker models permit more reordering to improve performance. Synchronization primitives, memory fences, atomic instructions, locks, and language-level memory models provide the rules needed for correct concurrent programs.

Coherence does not by itself make a program correct. A data race, inadequate synchronization, or an incorrectly placed fence can produce outcomes that are legal under the architecture but surprising to the programmer. Therefore, performance optimization must preserve the language and hardware memory-model requirements. Optimizations that reduce communication but violate visibility or ordering are not valid optimizations.

Applied Case: Improving a Multicore Analytics Service

Background

Consider an illustrative analytics service that processes batches of customer events on a four-socket NUMA server. Each event is parsed, enriched, and aggregated into counters. The service meets average throughput targets but has high tail latency during large batches.

Situation and Analysis

Profiling shows that the aggregation phase has a high last-level-cache miss rate and substantial remote-memory traffic. Each worker updates a shared array of counters. Counters belonging to different workers are interleaved in memory, so unrelated updates cause false sharing. In addition, the input records are stored as large objects, although the aggregation phase uses only three fields. The working set exceeds the local cache, and threads are not consistently placed near the memory where their input was allocated.

The problem is not simply an insufficient cache size. The application combines poor spatial selectivity, unnecessary bandwidth consumption, coherence traffic, and NUMA placement errors. Increasing processor frequency would not address these causes.

Approach and Strategy

The design is changed in four stages. First, the record representation is transformed into a structure-of-arrays layout containing only fields required by the aggregation phase. Second, each worker receives a private, cache-line-aligned counter array, eliminating false sharing during the main computation. Third, input batches are allocated using first-touch placement while worker affinity is fixed to the corresponding NUMA node. Finally, aggregation is performed locally and merged in a short reduction phase. The team measures cache misses, remote bandwidth, synchronization time, and tail latency after each change.

Outcome

The revised design reduces unnecessary data movement and allows most accesses to use local memory. The final merge introduces some additional work, but it is sequentially organized and much less expensive than continuous cross-core invalidation. Tail latency becomes more stable because remote requests and coherence bursts are reduced.

Learning Points

The case illustrates that memory performance is a system property. Data layout affects spatial locality; ownership affects coherence; placement affects NUMA latency; and measurement identifies the dominant bottleneck. A successful optimization changes the movement and reuse of data rather than merely increasing storage capacity.

Challenges, Risks, and Professional Considerations

Memory optimization is vulnerable to several common mistakes. A designer may optimize average latency while ignoring tail latency, assume that a lower miss rate always improves execution, or enlarge cache lines without considering bandwidth. Prefetching may pollute caches, and aggressive write combining may delay visibility. Measurements can also be misleading when a benchmark does not represent production working sets, concurrency, or contention.

Security is an important memory-hierarchy concern. Timing differences between cache hits and misses can reveal information through side channels. Speculative execution attacks have demonstrated that architectural permission checks do not automatically prevent microarchitectural information leakage. Mitigations may involve isolation, restricted speculation, cache partitioning, flushing, constant-time software, or stronger hardware controls, each with performance costs.

Reliability mechanisms include parity, error-correcting codes, scrubbing, memory mirroring, and fault-tolerant controllers. These mechanisms are particularly important in servers and safety-critical systems. Engineers must also consider data remanence, secure erasure, access permissions, virtualization boundaries, and the durability semantics of persistent memory.

From a governance perspective, memory decisions affect total cost of ownership, energy consumption, service-level agreements, and capacity planning. A design that maximizes throughput but violates latency guarantees or consumes excessive power may be unsuitable for an organization. Professional practice therefore requires explicit workload assumptions, reproducible benchmarks, documented trade-offs, and validation under realistic operating conditions.

Current Developments and Best Practices

Contemporary systems increasingly combine heterogeneous memory technologies, chiplet-based processors, high-bandwidth memory, near-data processing, and computational storage. GPUs and accelerators use their own memory hierarchies and often require explicit data transfers. Memory pooling and disaggregation can make capacity available across machines, but network latency and failure behavior become part of the memory model. Machine-learning methods are also being investigated for cache replacement and prefetch prediction, although their metadata, training cost, and unpredictability must be justified.

Practical best practices include:

• Begin with a measured workload model, including working-set size, reuse distance, concurrency, and latency targets.
• Distinguish capacity, latency, bandwidth, coherence, and translation problems before selecting a remedy.
• Choose block size, associativity, and replacement behavior together rather than in isolation.
• Use blocking, compact layouts, alignment, and ownership-aware partitioning to improve locality.
• Treat prefetching as a prediction problem and evaluate accuracy, coverage, timeliness, and pollution.
• Profile NUMA placement, false sharing, TLB behavior, and memory-controller contention.
• Preserve synchronization and memory-model correctness during optimization.
• Evaluate energy, reliability, security, durability, and tail latency in addition to average speed.

Chapter Summary

Memory hierarchy uses multiple storage levels to reconcile the processor's demand for low latency with practical limits on cost, capacity, energy, and technology. Temporal and spatial locality make caching effective, while working-set behavior determines whether a program benefits from a particular level. Cache organization depends on block size, mapping, associativity, tags, replacement, and write policies. Multilevel caches and TLBs reduce effective access time, whereas virtual memory provides protection and abstraction at the cost of translation and page-fault overhead.

DRAM performance depends on banks, rows, channels, scheduling, and contention. Non-volatile memory adds persistence but introduces endurance, durability, and write-management concerns. Prefetching, blocking, data-layout transformation, NUMA placement, and false-sharing avoidance can improve data movement when guided by measurement. In multicore systems, coherence and consistency are distinct requirements, and performance improvements must not compromise correctness. Effective memory design is therefore an architectural and organizational decision involving latency, bandwidth, concurrency, security, reliability, energy, and workload behavior.

Key Terms

Locality: The tendency of a program to reuse recently accessed data or access nearby addresses.

Temporal locality: The likelihood that a recently accessed item will be accessed again soon.

Spatial locality: The likelihood that addresses near a recently accessed address will be accessed soon.

Cache line: The fixed-size block transferred between a cache and a lower memory level.

Cache hit: An access for which the requested block is found in the relevant cache.

Cache miss: An access for which the requested block is absent and must be obtained from a lower level.

Associativity: The number of possible cache lines in a set where a block may be placed.

Working set: The collection of blocks actively used by a program during a defined interval.

AMAT: Average memory access time, combining hit time with miss rate and miss penalty.

Write-through: A policy that propagates each cache write to the next memory level.

Write-back: A policy that delays lower-level updates until a modified cache block is evicted.

TLB: A cache holding recently used virtual-to-physical address translations.

Page fault: An exception occurring when a referenced virtual page is not resident in main memory.

DRAM: Volatile memory that stores bits as charge and requires periodic refresh.

Bandwidth: The amount of data transferable per unit time.

Prefetching: Bringing data into a cache before a demand access is issued.

Cache coherence: The property governing the visibility of writes to a shared memory location across caches.

Memory consistency: The rules defining the ordering of memory operations observed by processors.

False sharing: Coherence traffic caused by different threads modifying distinct data in the same cache line.

NUMA: Non-uniform memory access, in which access time depends on the memory location relative to the processor.

Review Questions

Short Answer Questions

1. Distinguish temporal locality from spatial locality and give one example of each.

2. What are compulsory, capacity, conflict, and coherence-related cache misses?

3. Why does a write-back cache require a dirty bit?

4. What function does a TLB perform, and why is a TLB miss costly?

5. Define false sharing and state one method for reducing it.

Long Answer Questions

1. Explain direct-mapped, set-associative, and fully associative caches. Compare their performance and hardware costs.

2. Derive and interpret a two-level AMAT expression, explaining the meaning of each term.

3. Discuss write-through, write-back, write-allocate, and no-write-allocate policies and their interactions.

4. Explain how DRAM organization and memory-controller scheduling affect effective latency and bandwidth.

5. Describe cache coherence and memory consistency, and explain why coherence alone does not guarantee concurrent-program correctness.

Analytical / Application Questions

1. A workload has excellent L1 locality but frequently accesses data that exceeds the shared last-level cache. Determine which measurements would establish whether the main problem is capacity, bandwidth, or NUMA placement, and propose an optimization for each possibility.

2. An eight-thread program updates separate counters, but the counters are laid out consecutively and performance decreases as thread count rises. Analyze the likely cause and design a corrected data layout.

3. A sequential streaming application uses each cache line once and saturates DRAM bandwidth. Evaluate whether increasing cache associativity or enabling an aggressive prefetcher is likely to help, and justify a more appropriate optimization strategy.

22. Multiple Choice Questions with Answers

Question 1

A cache has capacity C, block size B, and associativity A. Which expression gives the number of sets?

A. C × B × A

B. C / (B × A)

C. B / (C × A)

D. A / (C × B)

Correct Answer: B. C / (B × A)

Question 2

Which situation most directly indicates a capacity miss?

A. A block is accessed for the first time

B. Two blocks repeatedly map to the same direct-mapped line

C. The active working set exceeds the cache capacity

D. Another core invalidates a shared block

Correct Answer: C. The active working set exceeds the cache capacity

Question 3

Why is write-back caching often more bandwidth-efficient than write-through caching?

A. It never writes data to lower memory

B. It combines repeated modifications and writes on eviction

C. It eliminates all cache misses

D. It does not require tags

Correct Answer: B. It combines repeated modifications and writes on eviction

Question 4

A prefetch is accurate but arrives after the processor has already requested the block. Which property is inadequate?

A. Coverage

B. Accuracy

C. Timeliness

D. Associativity

Correct Answer: C. Timeliness

Question 5

Which optimization most directly reduces false sharing?

A. Increasing page-fault frequency

B. Placing independently updated variables on separate cache lines

C. Using a smaller virtual address space

D. Disabling all write buffers

Correct Answer: B. Placing independently updated variables on separate cache lines

Question 6

What is the principal purpose of a TLB?

A. To store dirty cache lines

B. To predict branch targets

C. To cache virtual-to-physical address translations

D. To schedule DRAM row activations

Correct Answer: C. To cache virtual-to-physical address translations

Question 7

A workload has a low cache miss rate but poor performance because every miss depends on the previous miss. Which factor is most relevant?

A. Limited memory-level parallelism

B. Excessive cache associativity

C. High temporal locality

D. A large write buffer

Correct Answer: A. Limited memory-level parallelism

Question 8

Which statement best distinguishes coherence from consistency?

A. Coherence concerns one location's write visibility; consistency concerns ordering of memory operations

B. Coherence applies only to DRAM; consistency applies only to caches

C. Coherence eliminates the need for synchronization

D. Consistency measures only memory bandwidth

Correct Answer: A. Coherence concerns one location's write visibility; consistency concerns ordering of memory operations

Question 9

Why can very large cache blocks harm a workload with sparse accesses?

A. They eliminate spatial locality

B. They fetch unused data and consume bandwidth

C. They prevent virtual address translation

D. They make all caches fully associative

Correct Answer: B. They fetch unused data and consume bandwidth

Question 10

In a NUMA system, which strategy is most likely to reduce remote-memory traffic for a parallel batch computation?

A. Randomly migrating threads between sockets

B. Using first-touch allocation and fixed thread affinity

C. Disabling all private caches

D. Increasing page-fault frequency

Correct Answer: B. Using first-touch allocation and fixed thread affinity