Visual walkthrough — Multi-level cache hierarchy (L1 - L2 - L3)

This page rebuilds the multi-level cache result in pictures. We start from a single memory access — one request, one journey — and grow the famous Average Memory Access Time (AMAT) formula step by step. Every symbol is drawn before it is used.

---

Step 1 — One access, one clock, the meaning of a "cycle"

WHAT. Before any formula, we fix our unit of time. A cycle is one tick of the CPU clock — the smallest chunk of time the processor works in. If the clock runs at 1 GHz, one cycle is one billionth of a second.

WHY. We will measure everything — how fast a cache answers, how long DRAM takes — in cycles, so the numbers can be added together. Using cycles instead of nanoseconds keeps the picture clock-speed-independent.

PICTURE. Look at the figure: the CPU (amber block) sends one request down the pipe. The pipe is marked off in equal ticks — those ticks are cycles. The further the data lives, the more ticks the request must wait through before the answer returns.

---

Step 2 — The simplest world: CPU talks straight to DRAM

WHAT. Remove all caches. Every request goes to main memory, called DRAM, and pays its full latency $T_{\text{mem}}$.

WHY. This is our baseline — the worst case with no help. Everything we build later is measured against how much faster than this we get.

PICTURE. One long unbroken pipe from CPU to DRAM. There is no shortcut, no place to catch the request early. Every arrow travels the whole distance: $T_{\text{mem}}$ cycles, every single time.

$$\underset{\text{average wait}}{\underbrace{{\text{AMAT}}_{\text{baseline}}}}=\underset{\text{every access pays the full DRAM trip}}{\underbrace{T_{\text{mem}}}}$$

With $T_{\text{mem}}=200$, the average wait is a flat 200 cycles — no averaging yet, because there is only one possible journey.

---

Step 3 — Insert L1: the "usually / sometimes" split

WHAT. Put one small fast cache, L1, right next to the CPU. Now a request has two possible fates: found in L1 (a hit), or not found (a miss, sent on to DRAM).

WHY. L1 exists to answer the common case instantly. Because two outcomes now exist, "how long does an access take?" no longer has a single answer — we must average over the two paths, weighted by how often each happens. That weighted average is the first real AMAT.

PICTURE. The pipe now forks. The green hit path is short (stops at L1). The red miss path continues all the way to DRAM. Notice: every request pays the L1 hit time first — you always knock on L1's door before finding out — and only the fraction $m_{\text{L1}}$ continues.

$$\text{AMAT}=\underset{\begin{array}{c}\text{paid by }100\%\\ \text{always check L1}\end{array}}{\underbrace{T_{\text{L1}}}}+\underset{\begin{array}{c}\text{fraction that}\\ \text{misses L1}\end{array}}{\underbrace{m_{\text{L1}}}}\cdot \underset{\begin{array}{c}\text{cost of the}\\ \text{DRAM trip}\end{array}}{\underbrace{T_{\text{mem}}}}$$

Numbers. $T_{\text{L1}}=4$, $h_{\text{L1}}=0.95\Rightarrow m_{\text{L1}}=0.05$, $T_{\text{mem}}=100$:

$$\text{AMAT}=4+0.05\cdot 100=4+5=9\text{ cycles}$$

The 5% who miss drag the average up by exactly 5 cycles.

---

Step 4 — Insert L2: nesting a second question inside the miss

WHAT. Between L1 and DRAM, add L2: bigger, slower than L1, faster than DRAM. Now the miss path from L1 itself forks — into an L2 hit or an L2 miss.

WHY. We do not want an L1 miss to fall all the way to slow DRAM. L2 catches most of those misses cheaply. The key idea: the price of an L1 miss is no longer $T_{\text{mem}}$ — it becomes "the average time to get an answer starting at L2." We simply substitute one AMAT inside another.

PICTURE. A fork inside a fork. The outer fork (L1 hit / miss) is the same as Step 3. But the red L1-miss branch now runs into a second fork at L2: green stops at L2, red continues to DRAM. The whole L2 sub-tree is a smaller copy of the Step 3 picture.

$$\text{AMAT}=T_{\text{L1}}+m_{\text{L1}}\cdot \underset{\text{average cost of an L1 miss}=\text{"AMAT starting at L2"}}{\underbrace{\left(T_{\text{L2}}+m_{\text{L2}}\cdot T_{\text{mem}}\right)}}$$

Term by term:

• $T_{\text{L1}}$ — paid by everyone.
• $m_{\text{L1}}$ — the fraction that reaches L2.
• $T_{\text{L2}}$ — everyone who reached L2 pays this.
• $m_{\text{L2}}\cdot T_{\text{mem}}$ — the fraction of those who miss L2 pay the DRAM trip.

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

$$12+0.2\cdot 100=32\text{(cost of an L1 miss)}$$ $$\text{AMAT}=4+0.05\cdot 32=4+1.6=5.6\text{ cycles}$$

AMAT fell from 9 → 5.6 — L2 caught 80% of L1's misses before they hit DRAM.

---

Step 5 — Insert L3: the same nesting, one level deeper

WHAT. Add L3, the last cache before DRAM. The L2-miss branch now forks one final time.

WHY. Same logic as Step 4, applied again. This reveals the pattern: each level's miss penalty is just the AMAT of the next level. The formula is recursive — a Russian doll of forks.

PICTURE. Three nested forks. Follow any request: it always checks L1; the survivors check L2; those survivors check L3; the last survivors reach DRAM. Each fork sheds most of the traffic, so DRAM sees almost nobody.

$$\text{AMAT}=T_{\text{L1}}+m_{\text{L1}}(T_{\text{L2}}+m_{\text{L2}}(\underset{\text{innermost: AMAT at L3}}{\underbrace{T_{\text{L3}}+m_{\text{L3}}{T}_{\text{mem}}}}\left)\right)$$

---

Step 6 — Evaluate inside-out (why we must start at the deepest level)

WHAT. Plug numbers into the nested formula, from the innermost bracket outward.

WHY. The innermost bracket has no unknowns — it only depends on L3 and DRAM. Once we collapse it to a single number, the next bracket out has no unknowns either. Working outside-in would leave us with un-simplified brackets; inside-out always leaves plain numbers.

PICTURE. Watch the innermost fork collapse to a single amber number "60", which then becomes the miss cost inside L2's fork, collapsing to "24", which becomes L1's miss cost, collapsing to the final "5.2".

Using $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$:

$$\text{L3 layer:}40+0.1\cdot 200=60$$ $$\text{L2 layer:}12+0.2\cdot 60=24$$ $$\text{L1 layer:}4+0.05\cdot 24=5.2\text{ cycles}$$

DRAM is 200 cycles away, yet the average access is 5.2 cycles — because the deep forks are almost empty.

---

Step 7 — The degenerate cases (never let the reader hit an unshown scenario)

WHAT. Test the formula at its extremes so you trust it everywhere.

WHY. A formula you only tested in the middle can lie at the edges. We check the four boundary worlds.

PICTURE. Four mini-panels: a "perfect L1" world (all traffic stops at the first fork), a "useless caches" world (all traffic reaches DRAM), a "no caches at all" world (Step 2), and a "one level" world (Step 3). The formula must reproduce each.

• Perfect L1 ($m_{\text{L1}}=0$): the second term vanishes, $\text{AMAT}=T_{\text{L1}}$. Best possible — every access is an L1 hit.
• Useless caches ($m_{\text{L1}}=m_{\text{L2}}=m_{\text{L3}}=1$): every request slides through all forks, $\text{AMAT}=T_{\text{L1}}+T_{\text{L2}}+T_{\text{L3}}+T_{\text{mem}}$ — worse than baseline, because you pay every level's toll on the way down. This is why a cache that never hits actively hurts you.
• No caches (drop all levels): back to $\text{AMAT}=T_{\text{mem}}$ of Step 2.
• Boundary of $h$: $h$ must live in $[0,1]$; $m=1-h$ keeps every fork's two branches summing to 100% of the traffic — nothing is lost or double-counted.

---

Step 8 — From AMAT to speedup

WHAT. Compare the cached world (Step 6) with the baseline (Step 2).

WHY. AMAT alone is abstract; "how many times faster" is the number people feel.

PICTURE. Two bars — a tall 200-cycle baseline and a tiny 5.2-cycle cached bar — with the ratio drawn as an amber multiplier.

$$S=\frac{T_{\text{baseline}}}{\text{AMAT}}=\frac{200}{5.2}\approx 38.5\times$$

A 1 GHz CPU stalling on raw DRAM would behave like a 26 MHz machine; the hierarchy restores it to near full speed.

---

The one-picture summary

Everything above compressed into a single funnel: 100% of traffic enters at L1, most stops there, a thin stream survives each fork, and only a trickle reaches DRAM. The AMAT is the average path length through this funnel.

Recall Feynman retelling — say it in plain words

Imagine every memory request as a person entering a building with four rooms in a line: L1, L2, L3, and far at the back, DRAM. Everyone walks into L1 first and pays a small entry fee ($T_{\text{L1}}$). Ninety-five out of a hundred find what they need and leave — cheap and done. The five who don't walk deeper to L2, paying another small fee; four of those five succeed. The one straggler goes to L3, and almost always succeeds there. Only a tiny fraction of a person, on average, ever reaches the slow back room DRAM. Because the crowd thins out at every doorway, the average walk is short — about 5 cycles — even though the back room is 200 cycles away. The whole formula is just "everyone pays this room's fee, plus the fraction who fail here pay for whatever the next room costs on average." Nest that idea three times and you have the entire multi-level cache.

Recall

What does $m_{\text{L1}}\cdot T_{\text{mem}}$ represent in the single-cache AMAT? ::: The average extra cost per access from L1 misses — miss fraction times the DRAM trip, spread over all accesses. Why do we evaluate the nested AMAT inside-out? ::: The innermost bracket depends only on the deepest level and DRAM, so it collapses to a plain number first; each outer bracket then has no unknowns. What happens to AMAT if every cache level has miss rate 1? ::: You pay every level's hit time plus DRAM — worse than having no cache at all.

---

See also: Cache Organization · Cache Replacement Policies · Write Policies · Cache Coherence · Memory Access Patterns · TLB and Virtual Memory · CPU Pipeline · DRAM Architecture