Memory Hierarchy — Computer Organization & Architecture

Introduction

Here's the fundamental problem of computer design: we want memory that is simultaneously fast, large, and cheap. Unfortunately, physics says you can only pick two. Fast memory (SRAM) is expensive and small. Cheap memory (DRAM, disk) is large but slow. The memory hierarchy is the brilliant engineering solution — layer memories of different speeds and sizes so that the system *appears* to have large, fast, cheap memory. This illusion works because of a property called locality of reference.

The Speed-Cost-Size Dilemma

Notice: each level is roughly 10× slower but 10-100× larger than the one above.

The Hierarchy Pyramid

Locality of Reference

The memory hierarchy works because programs don't access memory randomly — they exhibit locality:

Temporal Locality

If a memory location is accessed now, it's likely to be accessed again soon.

• Examples: Loop variables, frequently-called functions, hot data
• Implication: Keep recently accessed data in fast memory (cache)

Spatial Locality

If a memory location is accessed, nearby locations are likely to be accessed soon.

• Examples: Array traversal, sequential instruction execution, struct fields
• Implication: When loading from memory, bring neighboring data too (cache lines)

Why Locality Exists

• Loops: Execute the same instructions repeatedly (temporal)
• Arrays: Access elements sequentially (spatial)
• Instructions: Execute sequentially most of the time (spatial)
• Stack: Local variables clustered near stack pointer (spatial)

How the Hierarchy Works

The Inclusion Principle

Data at level N is typically a subset of data at level N+1:

• Registers ⊂ L1 Cache ⊂ L2 Cache ⊂ L3 Cache ⊂ Main Memory ⊂ Disk

Hit and Miss

• Hit: Requested data found at the current level → fast access
• Miss: Data not found → must fetch from the next (slower) level

Hit Rate and Miss Rate

Typical hit rates: L1 cache ~95%, L2 cache ~99% of remaining misses

Average Memory Access Time (AMAT)

For a two-level hierarchy (cache + memory):

Compare to 100 ns without cache — the hierarchy delivers 16× improvement!

Multi-level AMAT

Design Considerations

Block Size (Cache Line Size)

How much data to bring from a lower level on a miss:

• Too small: doesn't exploit spatial locality
• Too large: wastes bandwidth, causes contention, increases miss penalty
• Typical: 64 bytes (modern CPUs)

Capacity

How much total data each level can hold:

• Larger = lower miss rate but slower access and higher cost
• Balance: enough to capture working set without being too slow

Replacement Policy

When the cache is full and new data arrives, what gets evicted?

• LRU (Least Recently Used): Evict the oldest untouched data
• Random: Surprisingly effective and simple to implement
• FIFO: First in, first out

Performance Impact

Without hierarchy (direct memory access):

Every access takes 100 ns → all programs are painfully slow

With hierarchy (modern system):

95% of accesses served by L1 cache in 1 ns Average access time ≈ 3-6 ns → programs run 20-30× faster

The 90/10 Rule

Programs spend 90% of their time accessing 10% of their data. This is why the hierarchy works — that 10% fits comfortably in cache.

Key Takeaways

1. The memory hierarchy solves the speed-cost-size trilemma by layering memories
2. It works because of locality — temporal (same data reused) and spatial (nearby data used)
3. Each level is ~10× slower but 10-100× larger than the level above
4. AMAT = Hit_time + Miss_rate × Miss_penalty — the key performance equation
5. Hit rates of 95%+ at L1 cache make the hierarchy highly effective
6. Block/line size exploits spatial locality by fetching neighboring data together
7. Modern computers would be ~20-30× slower without the memory hierarchy