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

WHAT it is: $m_{L1}$ is a pure fraction (no units); $T_{L2}$ is in cycles. Their product is in cycles. WHY: $m_{L1}$ = the fraction of accesses that miss L1 and therefore must pay a visit to L2. Multiplying the chance of paying by the cost of paying gives the average (expected) cycles per access spent just entering L2. It is one term of the total AMAT — the "extra cost L2 adds on top of the guaranteed L1 hit time."

Formula (one level): $\text{AMAT}=T_{L1}+m_{L1}{T}_{\text{mem}}$. WHY this shape: every access pays $T_{L1}=4$ (we always look in L1 first). A fraction $m_{L1}=1-0.90=0.10$ miss and pay the full $T_{\text{mem}}=100$. $\text{AMAT}=4+0.10\cdot 100=4+10=\boxed{14\text{ cycles}}$

Inside-out. First: what does an L1-miss cost on average? It reaches L2 (pay 14), and a quarter of those miss on to DRAM (pay 120): $T_{L2}+m_{L2}{T}_{\text{mem}}=14+0.25\cdot 120=14+30=44\text{ cycles}$ WHY: this "44" is the average price of one L1 miss. Now weight it by how often L1 misses: $\text{AMAT}=T_{L1}+m_{L1}\cdot 44=3+0.08\cdot 44=3+3.52=\boxed{6.52\text{ cycles}}$

Build the brackets from the deepest one outward. Innermost (cost of an L2 miss): $T_{L3}+m_{L3}{T}_{\text{mem}}=38+0.15\cdot 180=38+27=65$ Middle (cost of an L1 miss): $T_{L2}+m_{L2}\cdot 65=12+0.30\cdot 65=12+19.5=31.5$ Outer (the whole thing): $\text{AMAT}=T_{L1}+m_{L1}\cdot 31.5=4+0.06\cdot 31.5=4+1.89=\boxed{5.89\text{ cycles}}$

Option A — better L3 (all else fixed): Innermost: $38+0.075\cdot 180=38+13.5=51.5$ Middle: $12+0.30\cdot 51.5=12+15.45=27.45$ Outer: $4+0.06\cdot 27.45=4+1.647=\boxed{5.647}$ cycles. Improvement vs. $5.89$: about $0.243$ cycles.

Option B — faster L1 ($T_{L1}=3$, everything else as in 2.2): The nested brackets are unchanged (still $31.5$), only the base changes: $3+0.06\cdot 31.5=3+1.89=\boxed{4.89}$ Improvement vs. $5.89$: exactly $1.0$ cycle.

WHY B wins so decisively: the L1 hit time is paid by 100% of accesses, so 1 cycle off = 1 cycle off AMAT, full stop. The L3 improvement only touches the $m_{L1}\cdot m_{L2}=0.06\cdot 0.30=1.8\%$ of accesses that ever reach L3 — a huge relative gain there shrinks to a tiny absolute gain out front. Faster common case beats rarer misses.

WHY a different formula: a global miss rate $g_{Lk}$ already includes the probability of reaching that level (it is measured against all accesses). So in the global language we add each level's extra cost directly, weighted by its own global rate — we do not nest-multiply. The complete additive global formula: an access always pays $T_{L1}$. Whenever it globally misses a level it must probe the next level, paying that next level's hit time — and the fraction of accesses doing so is exactly the global miss rate of the level just left: $\text{AMAT}=T_{L1}+g_{L1}{T}_{L2}+g_{L2}{T}_{L3}+g_{L3}{T}_{\text{mem}}$ Plugging in: $\text{AMAT}=4+0.06\cdot 12+0.018\cdot 38+0.0027\cdot 180$ $=4+0.72+0.684+0.486=\boxed{5.89\text{ cycles}}$ Cross-check via local rates: convert with $m_{Lk}^{\text{local}}=g_{Lk}/g_{L(k-1)}$ and reuse Ex. 2.2:

• $m_{L1}=g_{L1}=0.06$.
• $m_{L2}=g_{L2}/g_{L1}=0.018/0.06=0.30$.
• $m_{L3}=g_{L3}/g_{L2}=0.0027/0.018=0.15$. These are exactly the local rates of Exercise 2.2, so the nested formula also gives $5.89$. Lesson: global and local are two languages for the same hierarchy — the additive global form and the nested local form always agree.

Speedup = (no-cache time per access) / (cached time per access): $S=\frac{T_{\text{mem}}}{\text{AMAT}}=\frac{180}{5.89}\approx \boxed{30.6\times }$ WHY this is the right ratio: without any cache, every access is a full 180-cycle DRAM trip; with the hierarchy the average trip is 5.89 cycles. The ratio is how many times faster the memory system delivers data. Fraction of peak performance retained (uncached machine): if the CPU could otherwise issue useful work at its clock rate but each memory access stalls it for the access latency, then throughput scales as $1/(\text{access latency})$. The uncached machine's memory is $S\approx 30.6\times$ slower, so on a memory-bound stream it retains only about $\frac{1}{S}=\frac{5.89}{180}\approx 0.0327\approx \boxed{3.3\%}$ of the throughput the cached machine achieves. Reading it: the hierarchy is doing ~97% of the heavy lifting — strip it out and a memory-bound workload crawls at roughly one-thirtieth speed. (We deliberately avoid quoting a single "effective MHz" number, since that depends on the exact mix of compute vs. memory work; the clean, assumption-free statement is the $30.6\times$ speedup itself.)

Recall Ex. 2.1: $T_{L1}=3,m_{L1}=0.08,T_{L2}=14,m_{L2}=0.25,T_{\text{mem}}=120$.

Option A (add L3): the L2-miss tail now goes through L3: Innermost: $T_{L3}+m_{L3}{T}_{\text{mem}}=40+0.20\cdot 120=40+24=64$ Middle: $T_{L2}+m_{L2}\cdot 64=14+0.25\cdot 64=14+16=30$ Outer: $3+0.08\cdot 30=3+2.4=\boxed{5.40}$ cycles.

Option B (bigger L2): stay 2-level, $T_{L2}=16,m_{L2}=0.12$: Middle: $16+0.12\cdot 120=16+14.4=30.4$ Outer: $3+0.08\cdot 30.4=3+2.432=\boxed{5.432}$ cycles.

Verdict: A gives $5.40$, B gives $5.432$ — Option A (add L3) wins, barely. WHY: L3 shields the whole DRAM tail (that expensive 120) behind a 20%-only escape, whereas enlarging L2 helped its own miss rate but the surviving 12% still pays full DRAM. When the DRAM penalty is large, inserting a filtering level beats improving an existing one. The figure below makes the two AMATs directly comparable as stacked bars.

Compare the two tails an L2-miss could take:

• Straight to DRAM: cost $=T_{\text{mem}}$.
• Through L3: cost $=T_{L3}+m_{L3}{T}_{\text{mem}}$. Adding L3 helps when: $T_{L3}+m_{L3}{T}_{\text{mem}}<T_{\text{mem}}$ Solve for the break-even miss rate $m^{\star }$ (set equal): $T_{L3}+m^{\star }{T}_{\text{mem}}=T_{\text{mem}}\Rightarrow m^{\star }=\frac{T_{\text{mem}}-T_{L3}}{T_{\text{mem}}}=1-\frac{T_{L3}}{T_{\text{mem}}}$ Reading it: L3 pays for itself as long as its actual miss rate $m_{L3}<m^{\star }$. Example: $T_{L3}=40,T_{\text{mem}}=180\Rightarrow m^{\star }=1-40/180\approx 0.778$. So L3 helps up to a whopping 77.8% miss rate — almost any real L3 (10–30% miss) is easily worth it. WHY so lenient: even a mostly-missing L3 turns most trips into a cheap 40-cycle probe, and only the misses pay the 180. The detour is cheap; the shortcut it sometimes provides is huge.

Load cost (70% of the stream). A load takes the full Ex. 2.1 two-level path: $T_{\text{load}}=T_{L1}+m_{L1}(T_{L2}+m_{L2}{T}_{\text{mem}})=3+0.08\cdot (14+0.25\cdot 120)=6.52\text{ cycles}$ (This is exactly the AMAT computed in Exercise 2.1 — units: cycles.)

Store cost (30% of the stream). Write-through means every store propagates to L2, so a store pays the L1 hit time plus the L2 hit time: $T_{\text{store}}=T_{L1}+T_{L2}=3+14=17\text{ cycles}$ No-write-allocate means a missing store does not fetch the line into L1 — it just lands at L2 — so there is no additional DRAM term. Units: cycles.

Blend by frequency. Loads and stores are two populations with different costs; the stream average is each cost weighted by how often it occurs: $T_{\text{eff}}=0.70T_{\text{load}}+0.30T_{\text{store}}=0.70\cdot 6.52+0.30\cdot 17$ $=4.564+5.1=\boxed{9.664\text{ cycles}}$ Reading it: stores are the minority (30%) yet contribute more than half the average, because write-through forces constant L2 traffic ($17$ cycles each). This is exactly why real designs add write buffers to hide that store latency behind useful work.

Shared L3 (line is there): B misses its private L1/L2, then hits the shared L3. The tail cost of that access — the part beyond B's own private levels — is exactly the L3 hit time: $T_{\text{tail, shared}}=T_{L3}=\boxed{40\text{ cycles}}$ The data A produced is sitting in the common L3, waiting for B to grab it.

Private L3 (line only in A's caches): B misses all of its own levels, and the coherence protocol must fetch A's copy across the interconnect — modeled here as a full memory-latency trip: $T_{\text{tail, private}}=180\text{ cycles}$

The saving: $T_{\text{tail, private}}-T_{\text{tail, shared}}=180-40=\boxed{140\text{ cycles per shared read}}$

WHY sharing wins here: a shared last-level cache turns an inter-core coherence miss (≈180, near DRAM) into an ordinary L3 hit (40). Producer→consumer data lives in one place that every core can cheaply reach, instead of being trapped in one core's private cache and hauled across the interconnect on demand. This is precisely why real designs make the LLC shared (see Cache Coherence): the latency that matters in multicore is not just latency-to-your-own-data but latency-to-another-core's-data, and sharing L3 collapses the latter from a coherence miss to a cache hit.

Ex 1.2 ::: 14 cycles Ex 2.1 ::: 6.52 cycles Ex 2.2 ::: 5.89 cycles Ex 3.1 ::: faster L1 wins (4.89 vs 5.647) Ex 3.2 ::: 5.89 cycles (additive global form and local form agree) Ex 4.1 ::: speedup ≈ 30.6×, uncached retains ≈ 3.3% of throughput Ex 4.2 ::: add L3 (5.40) beats bigger L2 (5.432) Ex 5.1 ::: m★ = 1 − T_L3/T_mem ≈ 0.778 Ex 5.2 ::: 9.664 cycles (loads 6.52, stores 17) Ex 5.3 ::: 140-cycle saving (40 vs 180)