Memory Hierarchy and Virtual Memory

Introduction and context

A microprocessor rarely obtains every instruction and operand from one uniform memory. Fast storage is expensive and limited; large storage is slower and cheaper. Computer systems therefore organize storage as a hierarchy: processor registers, one or more cache levels, main memory, and secondary storage. The hierarchy works because programs usually exhibit locality—they repeatedly use recently accessed items and nearby addresses.

This chapter develops the principles used to analyze and design memory systems. It covers cache organization, SRAM and DRAM, ROM, address decoding, write and replacement policies, protection, paging, translation lookaside buffers (TLBs), and virtual-to-physical address translation.

Learning objectives

By the end of this chapter, a student should be able to:

• explain temporal and spatial locality;
• compare registers, cache, main memory, and secondary storage;
• calculate cache fields, hit rate, miss rate, and average memory access time (AMAT);
• distinguish direct-mapped, set-associative, and fully associative caches;
• evaluate replacement and write policies;
• compare SRAM, DRAM, and ROM technologies;
• explain address decoding and memory-mapped organization;
• describe memory protection, paging, TLBs, and virtual-to-physical translation;
• analyze practical trade-offs in embedded and general-purpose processors.

1. The memory hierarchy

A typical hierarchy is:

Figure: The hierarchy trades access speed and cost per bit against capacity; capacity increases downward toward secondary and archival storage.

Registers are inside or immediately adjacent to the processor and are normally accessed in a few cycles. Caches hold recently used blocks. Main memory stores the active program and data. Secondary storage is persistent but has much higher access latency.

Locality

Temporal locality means that an item used recently is likely to be used again soon. A loop repeatedly accessing the same instructions is an example. Spatial locality means that addresses near a recently accessed address are likely to be accessed soon; sequential instruction fetches illustrate it.

A cache transfers a block (or line), not merely one byte or word. Blocks exploit spatial locality and can reduce the frequency of misses for nearby accesses. However, an excessively large block may waste bandwidth and increase miss penalty.

A useful classification is:

• Compulsory miss: the first reference to a block.
• Capacity miss: the cache cannot hold all actively used blocks.
• Conflict miss: blocks compete for the same location in a restricted mapping.

2. Cache organization

A memory address is divided into a tag, index (or set number), and block offset. If the cache contains C bytes, block size is B bytes, and associativity is W ways, the number of sets is:

For a byte-addressable memory with A address bits, the offset field has log₂(B) bits, the index field has log₂(S) bits, and the remaining bits form the tag. These expressions assume B and S are powers of two.

Mapping methods

Direct mapping assigns each memory block to one cache line:

It is inexpensive and fast, but conflict misses can be frequent.

In a W-way set-associative cache, a block maps to one set but may occupy any of W ways in that set. This reduces conflicts while requiring multiple tag comparisons.

A fully associative cache allows a block to occupy any line. It minimizes index-based conflicts but needs parallel tag comparison and is costly for large caches.

Each line normally contains a valid bit, tag, data block, and often a dirty bit. The valid bit distinguishes initialized contents from meaningless contents.

Worked cache-field example

Suppose a 32-bit byte-addressed processor has a 16 KiB, four-way cache with 64-byte blocks. Then:

• C = 16,384 bytes;
• B = 64 bytes;
• W = 4;
• S = 16,384 ÷ (64 × 4) = 64 sets;
• offset bits = log₂(64) = 6;
• index bits = log₂(64) = 6;
• tag bits = 32 − 6 − 6 = 20.

Thus an address contains a 20-bit tag, a 6-bit set index, and a 6-bit byte offset.

3. Cache performance and AMAT

The hit rate is the fraction of accesses found in the cache; the miss rate is 1 - hit ext{ rate}. For a single cache level:

Here, hit time is the time to determine whether the access hits and obtain the data, while miss penalty is the additional time required after a miss. The formula assumes the stated hit time and miss penalty are measured consistently and that the miss penalty is conditional on a miss.

For several levels, a two-level expression is:

where T₁ and T₂ are lookup times, m₁ and m₂ are local miss rates, and P₂ is the penalty to obtain data from the next level. Definitions must be kept consistent: a local L2 miss rate is measured among L2 accesses, whereas a global L2 miss rate is measured among processor accesses.

Worked AMAT example

Assume L1 hit time = 1 ns, L1 miss rate = 4%, and miss penalty = 50 ns. Then:

If a second cache is inserted with L2 access time 8 ns, L2 local miss rate 25%, and main-memory penalty 80 ns:

The L2 reduces the effective penalty from 80 ns to 28 ns, assuming the access-time conventions stated above.

4. Replacement and write policies

When a set is full, a replacement policy chooses a victim. Least recently used (LRU) approximates temporal locality but requires metadata and becomes expensive at high associativity. Random replacement is simple and can perform well in some workloads. FIFO replaces the oldest resident block but does not necessarily reflect recent use.

Write policies address how stores update cache and lower memory:

• Write-through: update the lower level on every write. It simplifies coherence and recovery but increases traffic; a write buffer can hide some latency.
• Write-back: update only the cache initially and mark the line dirty. On eviction, the dirty line is written lower in the hierarchy. This reduces traffic but requires dirty bits and careful coherence handling.
• Write-allocate: on a store miss, fetch the block into the cache, then modify it. It commonly accompanies write-back.
• No-write-allocate (write-around): send a store miss directly to the lower level. It can avoid fetching data that will not be reused and commonly accompanies write-through.

Policy selection depends on workload, coherence protocol, energy budget, and reliability requirements.

5. SRAM, DRAM, and ROM

SRAM stores each bit in a bistable circuit, commonly a six-transistor cell. It needs no refresh while powered, has low latency, and occupies more silicon area per bit. It is therefore used for caches and register files.

DRAM stores charge in a capacitor controlled by a transistor. Charge leaks, so rows must be refreshed. A DRAM access typically involves activating a row, selecting columns, and possibly precharging the array. DRAM provides high density and low cost per bit but has greater and more variable latency than SRAM.

ROM technologies include mask ROM, PROM, EPROM, EEPROM, and flash. Flash is electrically erasable and programmable, but has finite write/erase endurance and erase-block granularity. Nonvolatile memory is essential for boot firmware, while RAM is required for rapidly changing working data.

6. Address decoding and memory organization

Address decoding converts address bits into chip-select signals. A memory device with 2^k locations requires k address inputs, subject to its organization. For example, a 4 KiB byte-wide device requires 12 address inputs because 2¹² = 4096. Higher address bits can select among devices.

A full decoder uses all relevant high-order address bits and assigns a unique address range to each device. A partial decoder uses fewer bits; multiple address ranges then select the same device, producing address aliasing. Partial decoding reduces hardware but may create software hazards.

A memory map should specify base address, range, data width, read/write control, chip-select logic, and wait states. In memory-mapped I/O, peripherals occupy ordinary address space and are accessed by load/store instructions. Correct timing is important: address setup, enable signals, data validity, and hold times must satisfy the memory and processor specifications.

7. Protection and reliability

Memory protection prevents one process or privilege level from improperly accessing another's data or code. Common mechanisms include read/write/execute permission bits, user/supervisor modes, base-and-bound checks, page tables, and execute-never attributes.

Protection must be enforced by hardware on every relevant access. A page-table entry may contain a physical frame number, valid bit, read/write permission, user permission, execute permission, accessed bit, and dirty bit. Violations generate a protection fault rather than silently returning data.

Protection is not identical to confidentiality. Encryption, secure boot, trusted execution mechanisms, and access auditing may also be required. Designers must consider side channels: cache timing can reveal information even when architectural permissions are correct. Mitigations can include partitioning, constant-time code, barriers, and controlled speculation, although each may reduce performance.

8. Virtual memory and paging

Virtual memory gives each process a private virtual address space. Paging divides virtual memory into fixed-size pages and physical memory into equal-size frames. A virtual address is divided into a virtual page number (VPN) and page offset. With page size P bytes:

The offset is unchanged during translation. A page table maps the VPN to a physical frame number (PFN); the physical address is formed by concatenating PFN and offset.

Worked translation example

Assume 32-bit virtual addresses and 4 KiB pages. Since 4 KiB = 4096 bytes = 2¹², the offset is 12 bits and the VPN is 20 bits. Let virtual address be hexadecimal 0x12345ABC. The offset is the low 12 bits, 0xABC, and the VPN is 0x12345. If the page table maps VPN 0x12345 to PFN 0x06789, the physical address is:

This assumes the mapping is valid and permissions allow the requested operation.

A page fault occurs when the page is not currently in physical memory or when the access violates permissions. The operating system may locate the page on storage, select a victim frame, write it back if dirty, update the page table, and restart the faulting instruction. Because storage latency is many orders of magnitude above cache latency, excessive page faults cause thrashing.

Paging avoids external fragmentation because any page can occupy any free frame, but it introduces page-table memory overhead and internal fragmentation within the final partially used page. Larger pages reduce page-table size and may improve transfer efficiency, but can increase wasted space and fault cost.

9. TLBs and translation performance

A TLB is a small associative cache of recent VPN-to-PFN translations. On a TLB hit, translation is obtained rapidly; on a TLB miss, hardware or software consults the page table. A TLB entry usually includes permissions, address-space identity or process identifier, and status bits.

If TLB lookup time is t, memory access time after a TLB hit is m, and a TLB miss requires an additional page-table-walk cost w before the memory access, a simplified effective access time is:

where h is the TLB hit ratio. This model assumes the TLB lookup is serialized with the memory access and that w excludes the final data-memory access. Real processors may overlap operations, use multi-level TLBs, or incur different costs for instruction and data accesses; their documented timing model should therefore be used for precise analysis.

For t = 1 ns, m = 80 ns, h = 0.98, and w = 80 ns:

A page-table walk involving several memory references can make w substantially larger than 80 ns.

10. Integrated case: an embedded image-processing controller

Background. Consider an illustrative ARM-based controller acquiring camera frames, executing filtering code, and storing results in flash. The processor has a small instruction cache, a data cache, DRAM, and memory-mapped peripherals.

Problem. Profiling shows slow filtering and occasional corrupted peripheral transfers. The image loop scans pixels sequentially, while status registers are accessed sparsely. A write-back cache is used for ordinary data, but peripheral registers must not be cached.

Analysis. Sequential scanning has strong spatial locality, so an appropriately sized cache block can reduce instruction and data misses. A write-back cache reduces DRAM traffic for repeatedly modified image tiles, but dirty data must be cleaned before a DMA engine reads it. Peripheral regions require uncached or device memory attributes because speculative or repeated accesses could trigger unintended hardware actions. Page permissions should mark code executable and image buffers non-executable where supported.

Approach and outcome. The designer aligns image tiles to cache-block boundaries, uses non-temporal or write-through handling for data with little reuse, performs explicit cache maintenance around DMA, and assigns device memory attributes to peripheral registers. Address-decoding logic is verified with boundary tests to prevent aliasing. The result is improved throughput and correct DMA visibility, while the design documentation records cache, TLB, protection, and coherency assumptions.

Learning points. Performance depends on the entire path—not merely cache size. Correctness requires coordination among the processor, caches, MMU, DMA hardware, operating system, and device-memory rules.

11. Design trade-offs and contemporary practice

Increasing cache capacity can improve hit rate but may increase access time, leakage power, and die area. Higher associativity reduces conflict misses but increases comparison and replacement complexity. Larger pages reduce translation overhead but may waste memory. TLB reach—the amount of virtual memory covered by TLB entries—is increased by more entries or larger pages, but larger pages are not universally beneficial.

Modern processors commonly use multiple cache levels, hardware prefetching, nonuniform memory access, multi-level TLBs, and coherence protocols for multicore systems. Prefetching can exploit predictable spatial locality, but inaccurate prefetches consume bandwidth and cache capacity. AI accelerators and high-performance systems may use scratchpad memories instead of, or in addition to, hardware-managed caches when predictable data movement is valuable.

Best practice is to measure representative workloads, document address maps and memory attributes, validate boundary conditions, test protection faults, and analyze worst-case latency—not only average performance. Safety-critical systems additionally require traceability, isolation, diagnostic coverage, and compliance with applicable engineering standards.

Chapter Summary

Memory hierarchies combine small, fast storage with progressively larger, slower storage. Temporal and spatial locality make caching effective; cache blocks exploit spatial locality, while cache mapping determines conflict behavior. Direct mapping is simple, set associativity balances cost and flexibility, and full associativity is flexible but expensive. AMAT combines hit time, miss rate, and conditional miss penalty.

SRAM is fast and dense enough for caches, DRAM provides economical main memory but requires refresh, and ROM/flash preserves firmware without power. Address decoding determines which device responds to an address and must avoid unintended aliasing. Write-back, write-through, write-allocate, and replacement policies affect traffic, latency, and correctness.

Virtual memory separates virtual and physical addresses through page tables. Page offsets remain unchanged during translation, while VPNs map to PFNs. TLBs cache translations and reduce page-table overhead. Protection attributes, device-memory rules, cache coherence, and DMA coordination are essential to secure and reliable systems.

Key Terms

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

Temporal locality: Likelihood that a recently used item will be used again.

Spatial locality: Likelihood that nearby addresses will be accessed soon.

Cache line/block: Unit transferred between a cache and a lower memory level.

Hit rate: Fraction of accesses found at a memory level.

Miss penalty: Additional time incurred after a cache miss.

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

Direct mapping: Mapping in which each block has one possible cache line.

Set associativity: Organization in which a block maps to one set and any way in that set.

LRU: Replacement policy selecting the least recently used entry.

Write-through: Policy that propagates each cache write to a lower level.

Write-back: Policy that delays lower-level update until dirty-line eviction.

SRAM: Static volatile memory commonly used for caches.

DRAM: Dynamic volatile memory requiring periodic refresh.

Address decoding: Logic that generates device-selection signals from addresses.

Virtual page: Fixed-size region of a virtual address space.

Page table: Data structure mapping virtual pages to physical frames.

TLB: Associative cache of recent address translations.

Page fault: Exception caused by absent or unauthorized page access.

Memory protection: Hardware-enforced control of permitted memory operations.

Review Questions

Short Answer Questions

1. Define temporal and spatial locality and give one example of each.
2. What are the tag, index, and block-offset fields used for?
3. Distinguish write-through from write-back caching.
4. Why does DRAM require refresh while SRAM normally does not?
5. What information is stored in a TLB entry?

Long Answer Questions

1. Compare direct-mapped, set-associative, and fully associative caches, including their performance and hardware trade-offs.
2. Explain SRAM, DRAM, ROM, EEPROM, and flash in terms of volatility, density, speed, and applications.
3. Derive and interpret the single-level AMAT equation, stating its assumptions.
4. Explain paging, page faults, protection bits, and the causes and effects of thrashing.
5. Describe address decoding and explain the risks of partial decoding and address aliasing.

Analytical / Application Questions

1. A 32-bit processor has a 32 KiB, two-way cache with 64-byte blocks. Determine the number of sets and the tag, index, and offset widths.
2. A cache has a 2 ns hit time, 5% miss rate, and 60 ns miss penalty. Calculate AMAT and explain how reducing the miss rate would affect it.
3. A DMA device reads a buffer while the processor uses a write-back cache. Identify the coherency problem and propose a correct cache-maintenance and memory-attribute strategy.

Multiple Choice Questions with Answers

Question 1

Which locality principle is most directly exploited when a cache transfers an entire block containing adjacent addresses?

A. Temporal locality

B. Spatial locality

C. Privilege locality

D. Instruction serialization

Correct Answer: B. Spatial locality

Question 2

A 16 KiB cache is four-way associative with 64-byte blocks. How many sets does it contain?

A. 32

B. 64

C. 128

D. 256

Correct Answer: B. 64

Question 3

A cache has a 2 ns hit time, a 5% miss rate, and a 40 ns miss penalty. What is its AMAT under the single-level model?

A. 2 ns

B. 2.05 ns

C. 4 ns

D. 42 ns

Correct Answer: C. 4 ns

Question 4

Which cache organization permits a memory block to occupy any cache line?

A. Direct-mapped

B. Two-way set-associative

C. Fully associative

D. Sector-mapped only

Correct Answer: C. Fully associative

Question 5

Which statement about DRAM is correct?

A. It is nonvolatile and needs no power to retain data.

B. It stores charge and requires periodic refresh.

C. It uses bistable cells and is normally used for processor registers.

D. It can be written indefinitely without timing constraints.

Correct Answer: B. It stores charge and requires periodic refresh.

Question 6

What is the principal function of an address decoder?

A. Compressing instructions

B. Generating device-selection signals from address bits

C. Refreshing every DRAM row

D. Predicting branch outcomes

Correct Answer: B. Generating device-selection signals from address bits

Question 7

For a 4 KiB page, how many bits are required for the page offset?

A. 8

B. 10

C. 12

D. 16

Correct Answer: C. 12

Question 8

During ordinary paging translation, which part of a virtual address remains unchanged?

A. Virtual page number

B. Page offset

C. Page-table index only

D. Process identifier

Correct Answer: B. Page offset

Question 9

What is the main purpose of a TLB?

A. To cache recent virtual-to-physical translations

B. To store all secondary-storage files

C. To replace the processor register file

D. To decode peripheral interrupt vectors

Correct Answer: A. To cache recent virtual-to-physical translations

Question 10

Which policy generally writes a modified cache line to lower memory only when that line is evicted?

A. Write-through

B. Write-back

C. No-write-allocate

D. Read-around

Correct Answer: B. Write-back