5.4.8 · D5Memory Hierarchy & Caches
Question bank — Multi-level cache hierarchy (L1 - L2 - L3)
This page hunts the misconceptions that hide inside the multi-level cache hierarchy. Every item is one line. Cover the answer, say your reasoning out loud, then reveal. If a word here is new to you, build it first from the parent note and from Cache Organization.
Before any trap, pin down the four symbols that appear everywhere below. Each is a latency, measured in CPU cycles.
The other letters are rates. Below, is the local L1 miss rate — the fraction of all CPU accesses that miss L1 (since every access reaches L1, "local" and "global" coincide only for L1). The parent note's running example uses , so ; keep that number in mind, several traps below reuse it.
And here is the single formula every "Spot the error" item is checked against — read it once so nothing below is a surprise:
The flowchart below traces one access through that formula, so you can see which multiplier attaches to which penalty.
Two pipeline words used repeatedly are defined inline here so no trap forces a context switch:
True or false — justify
L2's miss rate of means 20% of all CPU accesses miss L2
False — that is a local rate, measured only over accesses that reached L2. Using the parent example where , the fraction of all accesses that miss L2 is the global rate .
Adding an L3 always lowers AMAT
Mostly true but not guaranteed — L3 helps only if its hit rate on incoming L2 misses saves more than its own hit-time overhead adds; a useless L3 (near-zero hit rate) just tacks onto the path.
A 99% L1 hit rate means L1 is "basically doing all the work," so L2/L3 barely matter
False — that surviving 1% hits penalties of 100+ cycles, so it can dominate AMAT; the levels catching that tail are exactly what keep average time low.
L1 is split into I-cache and D-cache mainly to store more data
False — the split exists to remove a structural hazard (instruction fetch and data access competing for one cache port in the same cycle), letting both happen simultaneously; total capacity is not the point.
Making L1 bigger always makes the CPU faster
False — a larger L1 has longer wires and slower access, raising which is paid on every access; the hit-rate gain rarely outweighs slowing down the common case.
In an inclusive hierarchy, L3's capacity fully adds to L1 and L2 capacity
False — inclusive L3 duplicates everything in L1/L2, so those bytes are counted twice; effective new capacity is less than L3's raw size.
The miss penalty of L2 includes L2's own hit time
False — the miss penalty is the cost of going to the next level; L2's hit time is paid separately, once, whether L2 hits or misses.
A shared L3 is slower than a private L3 would be, so sharing is a mistake
False — sharing trades a little latency for cheap inter-core data sharing and far less Cache Coherence traffic; for multithreaded code that is a net win.
Doubling L3 associativity always improves hit rate
False — it only helps if conflict misses dominate; if misses are capacity or compulsory, more ways buy nothing and cost power and latency (see Cache Replacement Policies).
Every L1 miss is a full trip to DRAM
False — an L1 miss first tries L2, then L3; only the fraction that miss all caches, , actually reaches DRAM.
Spot the error
""
The last term is un-weighted — reaching DRAM requires L1 and L2 to both miss, so its probability is the product , not alone; that "and" is why the correct form nests as , keeping every deeper penalty inside the previous miss rate.
"L1 hit rate is 0.95, so AMAT "
Wrong — the hit time is paid on every access (you must always look in L1 before you can know it missed), so it is unconditional and must not be weighted by ; the correct form is .
"Speedup "
Speedup is a ratio, not a difference: ; a subtraction has the wrong units — it yields cycles-saved-per-access, whereas a factor must be dimensionless (cycles ÷ cycles).
"We work the AMAT nest outside-in, starting from L1"
You evaluate inside-out because each bracket is the miss penalty feeding the level above it: compute (L3 + DRAM) average first, feed it up as L2's miss penalty, then feed that up as L1's miss penalty — going outside-in would use a penalty you haven't computed yet.
"L2 is unified because splitting it would cause structural hazards like L1"
Backwards — hazards need two simultaneous accesses, and only ~5% of accesses even reach L2, so simultaneous I/D collisions are rare; with little to gain from splitting, L2 unifies to avoid wasting space on two structures.
"A NINE cache is a fourth level below L3"
No — NINE (Non-Inclusive Non-Exclusive) names an inclusion policy applied to an existing level: unlike inclusive it doesn't force copies, unlike exclusive it doesn't forbid them, it just keeps hot lines when convenient.
"Since L3 is 40 cycles away, wire delay is the reason we keep it small"
The opposite — because we've already accepted those 40 cycles of latency, shaving wire delay buys nothing, so the design goal flips to maximizing hit rate, which means making L3 large.
Why questions
Why is each outer level larger and slower, never larger and faster?
A memory cell is reached through address-decode logic and metal wires whose length grows with capacity; signals travel at finite speed, so more bits literally means a longer round trip. The hierarchy accepts that physics by making distant, rarely-touched levels roomy and near levels tiny.
Why does the AMAT formula nest recursively instead of summing independent terms?
Because a level's miss penalty is the average access time of the next level, and you only reach that next level given the current one missed — so the costs are conditional, and conditional probabilities multiply, which is exactly the nesting of 's.
Why can a small drop in L3 miss rate matter more than a big drop in L1 miss rate?
Every L3 miss triggers a 100+ cycle DRAM fetch, so each avoided L3 miss removes a huge penalty; an avoided L1 miss only saves the small extra cost of asking L2, since L2/L3 already cushion it.
Why is high associativity emphasized more at L3 than at L1?
A cache maps each address to a fixed set; if two hot addresses map to the same set, one evicts the other — a conflict miss. Adding ways means a set holds more lines, so both can coexist. At MB-scale L3 many addresses collide, so ways pay off; L1 stays low-associativity so its lookup stays fast (see Cache Replacement Policies).
Why does inclusion simplify coherence?
If L3 mirrors every line held in any core's L1/L2, a coherence snoop only has to check L3 to learn whether any core caches a line — one lookup replaces interrogating every private cache, cutting inter-cache traffic.
Why does the CPU still check L1 first even on a stream of guaranteed L1 misses?
The hardware has no oracle telling it a line is absent — the lookup itself (compare the address tag against the set) is how it discovers the miss, so is unavoidably spent before it can fall through to L2.
Why does the parent note's access-pattern locality make this whole hierarchy work at all?
Programs reuse the same bytes soon (temporal) and nearby bytes next (spatial), so a small L1 that caches recent and adjacent data catches the vast majority of accesses; without that locality the funnel would leak almost everything to DRAM and caches would be pointless.
Edge cases
What is AMAT if the L1 hit rate is exactly ?
It collapses to just — with every miss term vanishes, and outer levels are never consulted.
What if the L1 hit rate is (every access misses L1)?
AMAT — you still pay the L1 lookup on top of the full next-level cost, so L1 becomes pure overhead.
What happens to AMAT if you add a level whose local hit rate is ?
It strictly increases by that level's hit-time contribution — a cache that never hits still charges its lookup time before you fall through.
If , which term dominates AMAT?
The DRAM term — so the product of all miss rates (the global DRAM miss rate) becomes the only number that matters.
For a fully exclusive hierarchy, why can't a line sit in L1 and L3 at once?
By definition exclusive levels hold disjoint data — a line lives in exactly one level, which maximizes total capacity but forces coherence to check every level.
What does a write to a shared line in one core's L1 imply for the others?
It triggers Cache Coherence action so other cores' stale copies are invalidated or updated; the write policy (write-back vs write-through) decides when the new value reaches L3/DRAM.
Is the AMAT model still valid if a TLB miss occurs on the access?
Not fully — address translation via TLB and Virtual Memory adds its own miss cost before the data cache is even indexed, a latency the plain AMAT formula omits.
Recall One-line self-test
Global L2 miss rate for ? ::: , i.e. 1% of all CPU accesses.