Multi-level cache hierarchy (L1 - L2 - L3)

Overview

Modern processors use multiple levels of cache (L1, L2, L3) between the CPU and main memory to bridge the massive speed gap. Each level trades off size for speed: smaller, faster caches closer to the core, larger, slower caches further away.

The Memory Hierarchy — Deriving Average Access Time

Why Do We Need Multiple Levels?

Goal: Keep data close to the CPU without paying the cost/power/space penalty of making all storage fast.

Problem: Fast memory (SRAM) is expensive per bit. Slow memory (DRAM) is cheap but100× slower.

Solution: Build a pyramid:

• L1 cache: 32-64 KB, 1-4 cycles, per-core
• L2 cache: 256-512 KB, ~10 cycles, per-core
• L3 cache: 8-32 MB, ~40 cycles, shared across cores
• Main memory (DRAM): GB-scale, ~100-200 cycles

Deriving Average Memory Access Time (AMAT)

Start with a single-level cache:

Why this formula?

• Every access pays $T_{\text{L1\_hit}}$ (we always check L1 first)
• Fraction $m_{\text{L1}}$ of accesses miss → pay $T_{\text{mem}}$ to fetch from DRAM

Example: $T_{\text{L1}} = 4$ cycles, $h_{\text{L1}} = 0.95$, $T_{\text{mem}} = 100$ cycles.

Why this step? L1 hit time is fixed (4 cycles). 5% of accesses miss (0.05), each miss costs 100 cycles → average miss penalty is 5 cycles.

Now add L2:

Why this structure?

• Every access checks L1 ($T_{\text{L1}}$)
• If L1 mises ($m_{\text{L1}}$), check L2 ($T_{\text{L2}}$)
• If L2 also misses ($m_{\text{L2}}$), go to DRAM ($T_{\text{mem}}$)

Example: $T_{\text{L1}} = 4$, $m_{\text{L1}} = 0.05$, $T_{\text{L2}} = 12$, $m_{\text{L2}} = 0.2$, $T_{\text{mem}} = 100$.

Why this step?

• L1 miss rate5% → 5% of accesses check L2
• Of those 5%, L2 hits 80% (in 12 cycles) and misses 20% (costing 100 more cycles)
• L2's average cost: $12 + 0.2 \cdot 100 = 32$ cycles
• Weighted by L1 miss rate: $0.05 \cdot 32 = 1.6$ cycles

Key insight: Adding L2 reduced AMAT from 9 to 5.6 cycles — 40% improvement — because L2 caught 80% of L1's misses before they hit slow DRAM.

Full 3-level hierarchy:

$\text{AMAT} = T_{\text{L1}} + m_{\text{L1}} \cdot \left( T_{\text{L2}} + m_{\text{L2}} \cdot \left( T_{\text{L3}} + m_{\text{L3}} \cdot T_{\text{mem}} \right) \right)$

Example: $T_{\text{L1}} = 4$, $m_{\text{L1}} = 0.05$, $T_{\text{L2}} = 12$, $m_{\text{L2}} = 0.2$, $T_{\text{L3}} = 40$, $m_{\text{L3}} = 0.1$, $T_{\text{mem}} = 200$.

Inner term (L3 + mem):

Middle term (L2 + [L3+mem]):

Full AMAT:

Why this step?

• Work inside-out: L3 sees 0.1 miss rate to DRAM → averages to 60 cycles
• L2 sees 0.2 miss rate to L3 → averages to 24 cycles
• L1 sees 0.05 miss rate to L2 → adds 1.2 cycles to the base4

Result: Only 5.2 cycles average — even though DRAM is 200cycles away — because most accesses never leave L1.

Why Each Level Is Designed Differently

L1 Cache (Data + Instruction)

Goal: Feed the CPU every cycle.

Design:

• Size: 32-64 KB (per core)
• Latency: 1-4 cycles
• Associativity: 8-way set-associative
• Split: Separate I-cache (instructions) and D-cache (data) to allow simultaneous instruction fetch and data access

Why so small? Speed. SRAM cell area grows with capacity. Larger cache → longer wire delays → slower access. At 3GHz (0.33 ns/cycle), light travels only 10 cm per cycle. Signal propagation across a large cache takes multiple cycles.

Why split I/D? The CPU needs to fetch the next instruction and load/store data in the same cycle (Harvard architecture benefit). A unified L1 would create a structural hazard.

L2 Cache

Goal: Catch L1 misses without going to slow L3/DRAM.

Design:

• Size: 256-512 KB (per core)
• Latency: ~10-12 cycles
• Associativity: 8-16 way
• Unified: Holds both instructions and data (I$and D$ mises compete for space)

Why unified? At L2, access conflicts are rare (only ~5% of accesses reach here), so the benefit of not duplicating cache resources outweighs the structural hazard cost.

Why 10× larger than L1? We've already paid10 cycles of latency to get here. We can afford a bigger structure because speed pressure is lower. The goal shifts from "fastest possible" to "high hit rate to avoid L3."

L3 Cache (Last-Level Cache, LLC)

Goal: Final filter before expensive DRAM access. Shared resource for coherence.

Design:

• Size: 8-32 MB (shared across all cores)
• Latency: ~40-50 cycles
• Associativity: 16-24 way
• Shared: All cores access the same L3 (enables efficient inter-core data sharing)

Why shared? If core A writes data that core B needs (common in multithreaded programs), that data sits in L3 where B can access it quickly. Per-core L3 would require expensive cache coherence protocol traffic between private caches.

Why so large? We're already40+ cycles from the CPU. Wire delay is no longer the bottleneck (we've accepted it). Now hit rate is king: every L3 miss costs 100+ DRAM cycles, so even a 1% improvement in L3 hit rate saves massive time.

Why highly associative? With MB-scale caches, conflict misses (where useful data is evicted because another address maps to the same set) become the dominant miss type. High associativity (16-24 ways) gives the replacement policy freedom to keep the hotest data.

Calculating Effective Speedup

Question: How much faster is a 3-level hierarchy than direct DRAM access?

Baseline (no cache): Every access costs $T_{\text{mem}} = 200$ cycles.

With 3-level cache: AMAT = 5.2 cycles (from earlier example).

Speedup:

Why this matters: A 1GHz CPU with no cache would effectively run at 26 MHz due to memory stalls. Caches make the memory system 38× faster, enabling the CPU to run near its clock speed for most workloads.

Result: Caches save 194.8 seconds. The program runs 38× faster.

Why this step? This quantifies the benefit of the hierarchy. Without these numbers, "caches make things faster" is vague. Now we know: caches are the reason modern CPUs are usable at all.

Global vs. Local Miss Rates

Why distinguish? Local rates tell you how well a specific cache performs. Global rates tell you the system-level impact.

Example: L1 local miss rate = 5%, L2 local miss rate = 20%.

L2 global miss rate:

Why this step? Only 5% of accesses reach L2 (L1's mises). Of those 5%, L2 mises 20%. So globally, $0.05 \times 0.2 = 0.01$ (1%) of all CPU accesses miss L2.

Insight: A "bad" L2 local miss rate (20%) has small system impact if L1 is good (95% hit rate), because most accesses never reach L2.

Common Mistakes

Why it feels right: More space means more data cached, higher hit rate.

The fix: Larger caches have longer access times (wire delays, addressing complexity). A 1 MB L1 might take 20 cycles to access — slower than hitting L2! The goal is to minimize AMAT, not maximize hit rate in isolation.

Correct thinking: Each level is sized to balance hit rate and access time at that level's position in the hierarchy.

Why it feels right: "The access could go through all levels, so add them all up."

The fix: Most accesses stop at L1. You only pay L2's cost if L1 misses. Use weighted sums:

Why this step? The miss rates are the weights. Only a fraction $m_{\text{L1}}$ of accesses see L2's cost.

Why it feels right: The miss rate is 20%, so 20% miss.

The fix: L2's local miss rate is 20% of L2 accesses, not all CPU accesses. If only 5% of CPU accesses reach L2, the global L2 miss rate is $0.05 \times 0.2 = 1\%$.

Correct thinking: Always track whether a miss rate is local (per-level) or global (system-wide). Use global rates when calculating AMAT impact.

Memory Hierarchy Design Tradeoffs

| Level | Size | Latency | Associativity | Why? | |-------|---------|---------------|---| | L1 | 32-64 KB | 1-4 cyc | 8-way | Speed-critical: small and fast | | L2 | 256-512 KB | 10-12 cyc | 8-16 way | Balance: catch L1 misses without L3 cost | | L3 | 8-32 MB | 40-50 cyc | 16-24 way | Hit rate-critical: last stop before DRAM |

Why associativity increases with level? Conflict misses hurt more at lower levels (closer to CPU). Higher associativity costs area and power. L3 can afford it (already slow, large). L1 can't (needs to be tiny and fast).

Why L1 is split (I$/D$) but L2/L3 unified? Structural hazards (simultaneous instruction fetch + data access) are critical at L1 (happens every cycle). At L2/L3, accesses are rare (only on mises), so unification saves area.

Feynman Recall — Explain to a 12-Year-Old

Here's the trick: you keep the facts you use most on the sticky note. When you need a new fact, you check the sticky note first (almost always there!). If not, you check the notebook. If still not there, you walk to the bookshelf. Only if the bookshelf doesn't have it do you bike to the library.

Because you use the same facts over and over (like multiplication tables), the sticky note has what you need 95% of the time. You almost never have to go to the library. That's why you finish homework in 5 minutes instead of 5 hours — even though the library is slow, you barely use it!

Caches work the same way: L1 is tiny but super close to the CPU's "brain," so it holds the data the CPU uses right now. L2 and L3 are bigger but farther away. Main memory is huge but far. The CPU almost always finds data in L1, so it runs at full speed.

Mnemonic

The S's go up: Small → Slower → Slowest.

Connections

• Cache Organization — how each level's sets/ways/blocks are structured
• Cache Coherence — how L1/L2/L3 stay consistent across multiple cores
• Memory Access Patterns — why spatial/temporal locality makes caching effective
• Cache Replacement Policies — LRU/LFU for choosing eviction victims in each level
• Write Policies — write-through vs. write-back at each level
• TLB and Virtual Memory — the address translation cache that sits alongside L1
• CPU Pipeline — how cache misses cause pipeline stalls
• DRAM Architecture — what happens when all caches miss

Flashcards

What are the three levels of cache in a modern CPU hierarchy? :: L1 (smallest, fastest, per-core), L2 (medium, per-core), L3 (largest, slowest, shared across cores).

Concept Map

Hinglish (regional understanding)