Multi-level cache hierarchy (L1 - L2 - L3): Worked examples

This page is one thing: practice until no case can surprise you. The parent note built the AMAT formula. Here we hit every kind of number it can throw at you — perfect caches, useless caches, missing levels, real workloads, and exam traps.

Everything below rests on one recursive idea, so let us restate it in plain words before any symbol appears.

Let us name the pieces once (the parent defined these; we keep them so line one is readable).

Because we have three cache levels, we tag each rate with the level it belongs to. This is just the same $h$ and $m$ written three times over:

The scenario matrix

Before working problems, here is the full space of cases. Every example below is tagged with the cell it covers, so you can see nothing is skipped.

Cell	What makes it special	Where it can bite you
A0. Single level	only L1 exists	the base scenario the whole recursion grows from
A. Baseline	ordinary numbers, all levels present	the "vanilla" 3-level AMAT
B. Zero miss (perfect cache)	some $m = 0$	whole levels below vanish — does the formula still work?
C. Full miss (useless cache)	some $m = 1$	cache adds latency but no benefit — cost goes up
D. Missing level	no L3 at all	collapse the 3-level formula to 2-level
E. Limiting behaviour	$m \to 0$ vs $m \to 1$	AMAT bounded between $T_{1}$ and $T_{1} +$ full chain
F. Solve backwards	AMAT given, find a hit rate	algebra, not just plug-in
G. Word problem	wall-clock seconds, GHz	cycles ↔ time unit conversion
H. Exam twist	global vs local miss rate	the classic mistake that loses marks

The figure below is this matrix drawn as a pipeline: every access enters at the left (Cell A0 lives entirely in the first box), the shrinking "still hasn't found it" stream flowing rightward is what Cells A–E track, and the labelled arrows are precisely the miss rates $m_{1}, m_{2}, m_{3}$ we tag in each example. Read a worked example, then find its box in the picture.

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

The picture shows why: $100%$ of accesses hit the L1 box, only $5%$ survive to L2, only $1%$ to L3, only $0.1%$ to DRAM. Those percentages are the products of miss rates we will compute in Cell H. Keep the box widths in mind — the deeper you go, the thinner the stream.

Cell A0 — The single-level base case (L1 only)

Forecast: With just one cache, every miss goes straight to DRAM. Will the answer be bigger or smaller than the 3-level case? (Think before reading — no L2/L3 to catch anything.)

Pick the one-level formula. $AMAT = T_{1} + m_{1} T_{mem}$ Why this step? There is no bracket to nest — an L1 miss has nowhere to go but memory, so its penalty is $T_{mem}$ . This is the simplest, non-recursive doll.
Plug in. $AMAT = 4 + 0.05 \cdot 100 = 4 + 5 = 9 cycles$ Why this step? Every access pays the $4$ -cycle L1 look. Only $5%$ miss, each paying $100$ , contributing $5$ cycles on average.

Verify: $9$ sits between $T_{1} = 4$ (if nothing missed) and $T_{1} + T_{mem} = 104$ (if everything missed). It leans toward $4$ because $95%$ hit. ✓ This is the seed: every richer formula below is built by replacing $T_{mem}$ with the average cost of a cache level. (This is Cell A0.)

Cell A — The baseline three-level AMAT

Forecast: Guess now — will it be closer to $4$ or closer to $200$ ? (Most people over-guess; the answer will feel shockingly small.)

Innermost bracket: L3's average cost. $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ Why this step? L3 always costs $40$ to look in. Only $10%$ of the accesses that reach L3 fall through to DRAM's $200$ . So on average an "L3-region" access costs $60$ . This number replaces DRAM for the level above.
Middle bracket: L2's average cost. $T_{2} + m_{2} \cdot 60 = 12 + 0.2 \cdot 60 = 24$ Why this step? We just said "reaching L3 costs $60$ on average," so from L2's point of view a miss penalty is $60$ , not $200$ . L2 looks cost $12$ ; $20%$ of them fall through to that $60$ .
Outer: the final answer. $T_{1} + m_{1} \cdot 24 = 4 + 0.05 \cdot 24 = 4 + 1.2 = 5.2 cycles$ Why this step? Every access pays L1's $4$ . Only $5%$ ever wake up the deeper machinery, and for them that machinery averages $24$ .

Verify: Sanity check — $5.2$ sits between $T_{1} = 4$ (best possible) and $4 + 0.05 \cdot 200 = 14$ (if L1's misses went straight to DRAM). It is much nearer $4$ because L2/L3 do heavy filtering. ✓ (This is Cell A.)

Cell B — A perfect level (zero miss rate)

Forecast: If L2 catches everything it is asked, do L3 and DRAM matter at all?

Innermost still evaluates — but gets multiplied by zero. $T_{3} + m_{3} T_{mem} = 60 (unchanged)$ Why this step? We compute it, but watch what happens to it next.
Middle bracket kills it. $T_{2} + m_{2} \cdot 60 = 12 + 0 \cdot 60 = 12$ Why this step? $m_{2} = 0$ means no access ever leaves L2. The $60$ we computed is real but reaches no one. The formula multiplies it away — exactly what "perfect L2" should do.
Outer. $4 + 0.05 \cdot 12 = 4 + 0.6 = 4.6 cycles$ Why this step? This is the standard outer layer: every access pays L1's $4$ , and the $5%$ that miss L1 now hit a level whose entire cost is just L2's $12$ (since L2 never fails). Multiplying $0.05 \cdot 12 = 0.6$ and adding gives the average.

Verify: With a perfect L2, the deepest thing any access can touch is L2 at $12$ cycles. So AMAT must be at most $T_{1} + m_{1} T_{2} = 4 + 0.05 \cdot 12 = 4.6$ . Matches. ✓ (This is Cell B — a zero miss rate truncates the hierarchy at that point.)

Cell C — A useless cache (miss rate of one)

Forecast: If L2 never finds anything, is it doing anything except costing time?

Innermost. $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ Why this step? L3 and DRAM behaviour has not changed from Cell A, so the average cost of "reaching L3" is still $60$ cycles. We must re-establish this number because the outer levels below will need it as their miss penalty — even a broken L2 still hands its misses down to this same L3.
Middle — full pass-through. $T_{2} + 1 \cdot 60 = 12 + 60 = 72$ Why this step? $m_{2} = 1$ means every L2 lookup fails, so every one pays the full $60$ of the level below plus the wasted $12$ cycles it spent looking in L2. L2 became pure overhead.
Outer. $4 + 0.05 \cdot 72 = 4 + 3.6 = 7.6 cycles$

Verify: Compare to a machine with no L2 at all (accesses go L1 → L3): $4 + 0.05 (40 + 0.1 \cdot 200) = 4 + 0.05 \cdot 60 = 7.0$ . The useless L2 gives $7.6 > 7.0$ — it made things worse by exactly the wasted $0.05 \cdot 12 = 0.6$ cycles. ✓ A cache with $m = 1$ is worse than no cache. (This is Cell C.)

Cell D — A level is missing (2-level machine)

Forecast: Which of our three formulas do we grab? (Hint: count the caches, not the memory.)

Use the two-level formula. $AMAT = T_{1} + m_{1} (T_{2} + m_{2} T_{mem})$ Why this step? With no L3, an L2 miss goes straight to DRAM, so L2's miss penalty is $T_{mem}$ itself — no middle doll.
Inside-out. $T_{2} + m_{2} T_{mem} = 12 + 0.2 \cdot 200 = 52$ Why this step? This inner bracket is L2's average cost. L2 always costs $12$ to look in, and $20%$ of accesses that reach it fall all the way through to DRAM's $200$ (there is no L3 to catch them), giving $12 + 0.2 \cdot 200 = 52$ . This $52$ becomes L1's miss penalty.
Outer. $4 + 0.05 \cdot 52 = 4 + 2.6 = 6.6 cycles$

Verify: Sanity check the magnitude, not by mangling the 3-level formula. (Beware the trap: reusing the 3-level expression by faking an L3 with $T_{3} = 0$ and $m_{3} = 1$ would give L3's cost as $0 + 1 \cdot 200 = 200 = T_{mem}$ correctly, but faking it with $T_{3} = T_{mem}$ and $m_{3} = 1$ instead pays DRAM twice — $200 + 1 \cdot 200 = 400$ — which is wrong. The safe way to "remove L3" is to drop its bracket entirely, which is just the 2-level formula we used.) Instead: $6.6$ lies above the full 3-level $5.2$ (Cell A) and below the useless-L2 $7.6$ (Cell C). Adding a real L3 (Cell A) should help, and it does: $5.2 < 6.6$ . ✓ (This is Cell D.)

Cell E — Limiting behaviour (the two extremes)

Forecast: What is the floor? What is the ceiling? Guess the two numbers before reading.

Best case, every $m \to 0$ . $AMAT \to T_{1} = 4 cycles$ Why this step? If nothing ever misses L1, the $m_{1} (\dots)$ term vanishes entirely. AMAT can never be less than $T_{1}$ — you always pay the first lookup.
Worst case, every $m \to 1$ . $AMAT \to T_{1} + T_{2} + T_{3} + T_{mem} = 4 + 12 + 40 + 200 = 256 cycles$ Why this step? If every level misses, each access walks the whole chain, paying each hit time on the way plus the final DRAM. This is the absolute ceiling.

Verify: Cell-A's real answer $5.2$ obeys $4 \leq 5.2 \leq 256$ . Every AMAT you ever compute must live in $[T_{1}, T_{1} + T_{2} + T_{3} + T_{mem}]$ . Any answer outside that range means an arithmetic error. ✓ (This is Cell E.)

Cell F — Solve backwards (given AMAT, find a hit rate)

Forecast: Cell A had $m_{1} = 0.05$ giving $5.2$ . To lower AMAT to $5.0$ , must $m_{1}$ go up or down?

Write the equation with $m_{1}$ unknown. $5.0 = 4 + m_{1} \cdot 24$ Why this step? Everything except $m_{1}$ is fixed, so this is one linear equation in one unknown.
Isolate $m_{1}$ . $m_{1} = \frac{5.0 - 4}{24} = \frac{1.0}{24} \approx 0.04167$ Why this step? Subtract the always-paid $T_{1}$ , then divide by the miss penalty. This "undoes" the formula.
Convert to hit rate. $h_{1} = 1 - m_{1} \approx 0.9583 = 95.83%$ Why this step? The question asked for the hit rate, but our formula is written in terms of the miss rate. By definition $m = 1 - h$ , so $h = 1 - m$ ; subtracting the miss rate from $1$ converts the quantity we solved for into the quantity the designer wants.

Verify: Plug back: $4 + 0.04167 \cdot 24 = 4 + 1.0 = 5.0$ . ✓ And it makes sense: to beat Cell-A's $5.2$ we needed a lower miss rate ( $0.0417 < 0.05$ ), i.e. a slightly better L1. (This is Cell F.)

Cell G — Word problem (cycles to wall-clock seconds)

Forecast: $2 GHz$ means $2 \times 1 0^{9}$ cycles per second. Will the cached version take seconds or milliseconds?

Total cycles, cached. $4 \times 1 0^{9} accesses \times 5.2 \frac{cycles}{access} = 2.08 \times 1 0^{10} cycles$ Why this step? AMAT has units cycles-per-access; multiply by the access count and the "access" unit cancels, leaving cycles.
Cycles to seconds. $\frac{2.08 \times 1 0 ^{10} cycles}{2 \times 1 0 ^{9} cycles/s} = 10.4 s$ Why this step? Dividing cycles by (cycles per second) leaves seconds — a clean unit check.
No-cache comparison. $\frac{4 \times 1 0 ^{9} \times 200}{2 \times 1 0 ^{9}} = \frac{8 \times 1 0 ^{11}}{2 \times 1 0 ^{9}} = 400 s$ Why this step? We repeat the exact same two-stage conversion (accesses × cycles-per-access, then ÷ cycles-per-second) but with the baseline cost of $200$ cycles per access instead of $5.2$ . Building the no-cache number in the same units is what lets us take an honest ratio in the Verify line.

Verify: Speedup $= 400/10.4 \approx 38.46 \times$ , matching the parent's $200/5.2 \approx 38.5 \times$ (the ratio is unit-free, so GHz cancels — good). ✓ (This is Cell G.)

Cell H — Exam twist: global vs local miss rate

Forecast: Is the local L2 miss rate bigger or smaller than $1%$ ? (Only $5%$ of accesses even reach L2…)

Relate global and local. $GMR_{2} = m_{1} \cdot m_{2} \Rightarrow m_{2} = \frac{GMR _{2}}{m _{1}} = \frac{0.01}{0.05} = 0.2$ Why this step? An access misses L2 globally only if it first missed L1 (rate $m_{1}$ ) and then missed L2 (rate $m_{2}$ ). Probabilities of the two independent hurdles multiply. Solving gives the local $m_{2} = 0.2$ — much bigger than $1%$ , because its base is the small $5%$ stream, not everyone. (This is exactly the "thinning stream" in the figure: the L3 box holds $m_{1} m_{2} = 1%$ of the original width.)
Now plug the local $m_{2}$ into the standard formula (inside-out). $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ $T_{2} + m_{2} \cdot 60 = 12 + 0.2 \cdot 60 = 24$ $T_{1} + m_{1} \cdot 24 = 4 + 0.05 \cdot 24 = 5.2 cycles$ Why this step? Once $m_{2}$ is the correct local $0.2$ , this is identical to Cell A — proving the given global figure was just Cell A in disguise.

Verify: Global check the other way: $m_{1} m_{2} = 0.05 \cdot 0.2 = 0.01 = GMR_{2}$ . ✓ Had you wrongly used $m_{2} = 0.01$ , you'd get $4 + 0.05 (12 + 0.01 \cdot 60) = 4.63$ — a different, wrong answer that would look plausible on an exam. (This is Cell H.)

Pull it together

Recall Which formula and which numbers?

What does the subscript in $m_{2}$ mean? ::: "Level 2's local miss rate" — the fraction of accesses that reached L2 which miss it. How many brackets does a 3-level cache formula have? ::: Three nested brackets (L1 outside, L2 middle, L3+DRAM inside). A level with $m = 0$ does what to the levels below it? ::: Truncates them — their cost is multiplied by zero and never reached. A cache with $m = 1$ compared to having no cache at all? ::: Worse — it adds its hit time as pure overhead with no benefit. The absolute minimum any AMAT can be? ::: $T_{1}$ , the L1 hit time you always pay. The absolute maximum? ::: $T_{1} + T_{2} + T_{3} + T_{mem}$ , every level missing. Global miss rate relates to local how? ::: $GMR_{k} = m_{1} m_{2} \dots m_{k}$ (product of local miss rates above and including it).

Prerequisites & neighbours: the hit/miss counts here come from Cache Organization and Cache Replacement Policies; the "shared L3" reasoning connects to Cache Coherence; miss rates depend on your Memory Access Patterns; and where these cycles fit in execution is CPU Pipeline and DRAM Architecture.