Exercises — Average memory access time (AMAT)

• $HT=2$ ns — you always look inside the cache, so this is paid on every access.
• $m=\frac{4}{100}=0.04$ — the "not found" fraction.
• $MP=80$ ns — the word "extra" is the giveaway: it's the additional cost beyond the look-up.

Paid every access: $HT$. The other two only matter when you miss.

Correct: (b) $HT+m\cdot MP$. Why (b) is the right one — build it from the two possible outcomes. Split every access into its two cases and take the average (the definition of "expected time"):

• With probability $1-m$ you hit and pay just $HT$.
• With probability $m$ you miss: you still looked in the cache first ($HT$) and then paid the fetch ($MP$), so you pay $HT+MP$. $\text{AMAT}=(1-m)HT+m(HT+MP)=HT+m\cdot MP.$ The two $m\cdot HT$ terms cancel, leaving $HT$ standing alone (paid every access) and $MP$ gated by $m$ (paid only on misses). That is exactly form (b).
• (a) forgets you pay $HT$ on the miss path too, so it drops one $HT$ (see the L1 mistake below).
• (c) multiplies the wrong thing — hit time is unconditional, not gated by $m$.
• (d) forgets that only a fraction $m$ of accesses pay the penalty.

$\text{AMAT}=HT+m\cdot MP=2+0.04\times 80=2+3.2=5.2\text{ns}$ Read it: of the $5.2$ ns, $3.2$ ns ($\approx 62\%$) came from the rare misses. Rare ≠ cheap.

Convert first: $2\%=0.02$. $\text{AMAT}=1+0.02\times 150=1+3=4\text{ns}$

Step 1 — cost of one L1 miss (= AMAT of the L2 subsystem). What: treat L2 as its own little cache. Why: an L1 miss doesn't cost "DRAM time", it costs "whatever the L2 subsystem takes". $M{P}_{L1}^{\text{eff}}=H{T}_{L2}+m_{L2}\cdot M{P}_{L2}=8+0.25\times 200=8+50=58\text{ns}$ Step 2 — plug that into L1. $\text{AMAT}=H{T}_{L1}+m_{L1}\cdot M{P}_{L1}^{\text{eff}}=1+0.08\times 58=1+4.64=5.64\text{ns}$ Sanity: the $200$ ns DRAM trip is scaled by the product $m_{L1}\times m_{L2}=0.08\times 0.25=0.02$, adding only $0.02\times 200=4$ ns of the total.

Baseline: $\text{AMAT}=2+0.10\times 100=12$ ns.

• A: $1+0.10\times 100=11$ ns (saved $1$ ns).
• B: $2+0.05\times 100=7$ ns (saved $5$ ns). Winner: B, by $4$ ns over A. Attacking the penalty-weighted term ($m\cdot MP=10$ ns) beats shaving the flat $HT$, because the miss term dominates the average here.

How to read the figure below. It is a bar chart. The horizontal axis simply names the three designs (Baseline, Option A, Option B) — it is not a number line, just three labelled slots. The vertical axis is AMAT in nanoseconds. Each bar's height is that design's computed AMAT, with the exact value printed on top: Baseline $=12$, A $=11$, B $=7$. Two bars are black (Baseline and A); the one red bar is Option B — the accent colour marks the winner, and you can see at a glance it is the shortest bar. Compare heights vertically: A barely dips below Baseline (shaving flat $HT$ moves the top down by only $1$ ns), while B drops far lower (halving $m$ removes $5$ ns of the penalty term).

Old: $1+0.06\times 100=7$ ns. New: $3+0.03\times 100=6$ ns. Worth it — barely ($7\to 6$ ns). The miss saving ($0.03\times 100=3$ ns dropped) outweighs the $HT$ rise ($+2$ ns). This is the Cache Associativity & Hit Time tradeoff in action: lower $m$ can cost you $HT$, and you must weigh both.

Turning point: if the new $HT$ had risen to $5$ ns instead, new AMAT $=5+3=8>7$ — the trade would lose.

(a) $m_{L1}=\frac{120}{1000}=0.12$. (b) L2 only sees the $120$ forwarded accesses: $m_{L2,\text{local}}=\frac{30}{120}=0.25$. (c) Global = misses that reach DRAM over all accesses: $m_{\text{global}}=\frac{30}{1000}=0.03$. Check: $m_{L1}\times m_{L2,\text{local}}=0.12\times 0.25=0.03$ ✅. This is why the recursive AMAT uses the local rate inside the nested term — L2 is blind to accesses L1 satisfied. See Multi-level Cache Hierarchy.

First, define the symbols this problem borrows (they come from the CPU Performance Equation):

• CPI = cycles per instruction = how many clock cycles the CPU spends, on average, to finish one instruction.
• ${\text{CPI}}_{\text{base}}$ = the CPI you'd get if memory were free (every access an L1 hit, no stalls) = $1.0$ here.
• ${\text{CPI}}_{\text{eff}}$ = the effective (real) CPI once you add the cycles the CPU wastes waiting on memory misses.
• ns/cycle = the clock period, $0.5$ ns — the wall-clock duration of one cycle. Dividing a time in ns by ns/cycle converts it into a count of cycles (the ns cancel).

Step 1 — stall time per access. What: the extra (stall) part of AMAT. Why: the flat $HT$ is already covered by the pipeline's base CPI (the CPU assumes an L1 hit each cycle), so only the penalty term is a true stall. $m\cdot MP=0.05\times 100=5\text{ns per access}.$ Step 2 — stall time per instruction. What: multiply per-access stall by accesses per instruction. Why: each instruction issues $1.5$ memory accesses on average, and every one of them carries the same expected $5$ ns stall, so the stalls add up — total stall time per instruction is (stall per access) $\times$ (accesses per instruction). $5\text{ns/access}\times 1.5\text{accesses/instr}=7.5\text{ns/instr}.$ Step 3 — convert ns to cycles. Why: CPI is measured in cycles, so divide the stall time by the clock period ($0.5$ ns/cycle); the ns units cancel, leaving cycles. $\frac{7.5\text{ns/instr}}{0.5\text{ns/cycle}}=15\text{stall cycles/instr}.$ Step 4 — effective CPI. What: add stalls onto the base. Why: real CPI = the work the CPU would do anyway plus the cycles it sits idle waiting on memory. ${\text{CPI}}_{\text{eff}}={\text{CPI}}_{\text{base}}+\text{stall cycles}=1.0+15=\mathrm{16.0.}$ This is the bridge to the CPU Performance Equation: AMAT's penalty term becomes memory-stall cycles.

Set the formula to the limit and solve for $m$: $HT+m\cdot MP\le 4\Rightarrow 2+100m\le 4\Rightarrow m\le \frac{2}{100}=\mathrm{0.02.}$ So $m\le 2\%$. Any higher and you blow the $4$ ns budget. Note: if $HT$ alone already exceeded $4$ ns, no miss rate (not even $m=0$) could meet the target — the flat cost already fails.

(a) $m=0$ (perfect cache, always a hit): $\text{AMAT}=HT$. The penalty vanishes — the best case; you only ever pay the look-up. This is the "perfect cache" baseline used in L4-Q2. (b) $m=1$ (never hits — every access misses): $\text{AMAT}=HT+MP$. You pay the look-up and the full fetch every single time. Worst case. (c) $MP\to \infty$: $\text{AMAT}\to \infty$ for any $m>0$. Even a tiny miss rate, if the penalty is unbounded, makes average time explode — the "rare but ruinous" regime AMAT is built to expose. (d) $HT\to 0$: $\text{AMAT}\to m\cdot MP$. The floor is the miss cost alone; making the cache infinitely fast still can't beat the penalty-weighted term.

How to read the figure below and tie it to the formula. The horizontal axis is the miss rate $m$, running from $0$ (left) to $1$ (right) — this is a genuine number line. The vertical axis is AMAT in ns, with $HT=2$ ns and $MP=100$ ns fixed. Because $\text{AMAT}=HT+m\cdot MP$ is linear in $m$ (a "$y=c+\text{slope}\cdot x$" straight line), the red curve is a straight line whose height at any $m$ is literally $2+100m$. Trace it: the left endpoint ($m=0$) sits at height $HT=2$ ns — that is case (a), where the $m\cdot MP$ term is zero and only the look-up remains. The right endpoint ($m=1$) reaches height $HT+MP=102$ ns — that is case (b), the full look-up-plus-fetch worst case. The slope of the line (how fast it rises as you move right) equals $MP$ itself, $100$ ns per unit of $m$: a bigger $MP$ (case c) tilts the line steeper toward infinity; shrinking $HT$ (case d) slides the whole line straight down toward the origin without changing its slope.

Subtract; the common $H{T}_{L1}$ and the $m_{L1}$ factor cancel out of the comparison: ${\text{AMAT}}_{\text{L2}}<{\text{AMAT}}_{\text{no L2}}$ $⟺H{T}_{L2}+m_{L2}\cdot M{P}_{\text{DRAM}}<M{P}_{\text{DRAM}}$ $⟺H{T}_{L2}<M{P}_{\text{DRAM}}(1-m_{L2}).$ Reading it: L2 helps iff its hit time is smaller than the DRAM penalty scaled by L2's hit rate $(1-m_{L2})$. Since DRAM is slow (hundreds of ns) and L2 hit time is small (a few ns), this is virtually always true — but if $m_{L2}$ were near $1$ (L2 useless, almost everything misses through it), the right side shrinks toward $0$ and L2 could actually hurt (you'd pay $H{T}_{L2}$ for nothing). Worked check: $H{T}_{L2}=8$, $M{P}_{\text{DRAM}}=200$, $m_{L2}=0.25\Rightarrow$ need $8<200(0.75)=150$ ✅ — L2 helps by a mile.

1. In L2-Q3, why is the L1 miss penalty $58$ ns and not $200$ ns?
2. In L3-Q1, why did halving miss rate beat halving hit time?
3. State the exact inequality for "L2 is worth adding" (L5-Q3).
4. Why is memory-stall time $m\cdot MP$ and not the full AMAT (L4-Q2)?
5. What is AMAT when $m=0$? When $m=1$?