Average memory access time (AMAT): Exercises — Hinglish deep dive

5.4.10 · D4 · Hardware › Memory Hierarchy & Caches › Average memory access time (AMAT)

Level 1 — Recognition

Goal: har quantity ko pehchano, aur formula padho.

Recall Solution

$H T = 2$ ns — tum hamesha cache ke andar dekhte ho, isliye yeh har access par pay hota hai.
$m = \frac{4}{100} = 0.04$ — yeh "nahi mila" wala fraction hai.
$M P = 80$ ns — "extra" word hi giveaway hai: yeh look-up se upar ki additional cost hai.

Har access par pay hota hai: $H T$ . Baki do sirf tab matter karte hain jab miss ho.

Recall Solution

Sahi answer: (b) $H T + m \cdot M P$ . Kyun (b) sahi hai — isse do possible outcomes se build karo. Har access ko uske do cases mein split karo aur average lo ("expected time" ki definition yehi hai):

Probability $1 - m$ ke saath tum hit karte ho aur sirf $H T$ pay karte ho.
Probability $m$ ke saath tum miss karte ho: tumne cache mein pehle dekha bhi ( $H T$ ) aur phir fetch bhi kiya ( $M P$ ), isliye $H T + M P$ pay hota hai. $AMAT = (1 - m) H T + m (H T + M P) = H T + m \cdot M P .$ Dono $m \cdot H T$ terms cancel ho jaate hain, aur $H T$ akela khada rehta hai (har access par pay hota hai) aur $M P$ ko $m$ gate karta hai (sirf miss par pay hota hai). Yahi exactly form (b) hai.
(a) bhool jaata hai ki miss path par bhi $H T$ pay hota hai, isliye ek $H T$ drop ho jaata hai (neeche L1 mistake dekho).
(c) galat cheez multiply karta hai — hit time unconditional hai, $m$ se gated nahi.
(d) bhool jaata hai ki sirf fraction $m$ accesses hi penalty pay karte hain.

Level 2 — Application

Goal: single- aur two-level AMAT mein numbers daalo.

Recall Solution

$AMAT = H T + m \cdot M P = 2 + 0.04 \times 80 = 2 + 3.2 = 5.2 ns$ Isko padhte hain: us $5.2$ ns mein se, $3.2$ ns ( $\approx 62%$ ) rare misses se aaya. Rare ≠ cheap.

Recall Solution

Pehle convert karo: $2% = 0.02$ . $AMAT = 1 + 0.02 \times 150 = 1 + 3 = 4 ns$

Recall Solution

Step 1 — ek L1 miss ki cost (= L2 subsystem ka AMAT). Kya: L2 ko uski apni choti cache maano. Kyun: L1 miss ka matlab "DRAM time" nahi, balki "jo bhi L2 subsystem leta hai" woh cost hai. $M P_{L 1}^{eff} = H T_{L 2} + m_{L 2} \cdot M P_{L 2} = 8 + 0.25 \times 200 = 8 + 50 = 58 ns$ Step 2 — use karo usse L1 mein. $AMAT = H T_{L 1} + m_{L 1} \cdot M P_{L 1}^{eff} = 1 + 0.08 \times 58 = 1 + 4.64 = 5.64 ns$ Sanity check: $200$ ns DRAM trip ko product $m_{L 1} \times m_{L 2} = 0.08 \times 0.25 = 0.02$ se scale kiya gaya hai, jo total mein sirf $0.02 \times 200 = 4$ ns add karta hai.

Level 3 — Analysis

Goal: designs compare karo aur reason karo ki kaun sa knob zyaada help karta hai.

Recall Solution

Baseline: $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, A se $4$ ns zyaada se. Penalty-weighted term ( $m \cdot M P = 10$ ns) par attack karna flat $H T$ ko shave karne se behtar hai, kyunki miss term yahan average ko dominate karta hai.

Neeche wala figure kaise padhen. Yeh ek bar chart hai. Horizontal axis sirf teen designs ke naam hai (Baseline, Option A, Option B) — yeh number line nahi, sirf teen labelled slots hain. Vertical axis AMAT in nanoseconds hai. Har bar ki height us design ka computed AMAT hai, jiska exact value upar likha hai: Baseline $= 12$ , A $= 11$ , B $= 7$ . Do bars black hain (Baseline aur A); ek red bar Option B hai — accent colour winner mark karta hai, aur tum ek nazar mein dekh sakte ho yeh sabse chota bar hai. Heights vertically compare karo: A barely Baseline se neeche jaata hai (flat $H T$ shave karne se top sirf $1$ ns neeche aata hai), jabki B kaafi neeche girta hai ( $m$ halve karne se penalty term ke $5$ ns hat jaate hain).

Figure — Average memory access time (AMAT)

Recall Solution

Old: $1 + 0.06 \times 100 = 7$ ns. New: $3 + 0.03 \times 100 = 6$ ns. Worth it — barely ( $7 \to 6$ ns). Miss saving ( $0.03 \times 100 = 3$ ns drop) $H T$ rise ( $+ 2$ ns) se zyaada hai. Yeh Cache Associativity & Hit Time tradeoff in action hai: lower $m$ tumhe $H T$ cost kar sakta hai, aur dono ko weigh karna padta hai.

Turning point: agar new $H T$ badhkar $5$ ns ho jaata, toh new AMAT $= 5 + 3 = 8 > 7$ — trade lose ho jaata.

Common mistake L3 trap · "Lower miss rate hamesha better hota hai"

Kyun sahi lagta hai: misses villain hain, toh $m$ ko crush karna help karega hi. $Δ$ (delta) notation: $Δ$ ka matlab hai kisi quantity mein "change". Yahan $Δ H T$ = (new hit time) − (old hit time) = woh extra hit time jo tumne add kiya, aur $Δ m$ = (old miss rate) − (new miss rate) = woh miss rate jo tumne hatayi. Dono sirf dono effects ki sizes hain. Kyun galat hai: jo mechanism $m$ ko lower karta hai (bada / more associative cache) usually $H T$ raise kar deta hai, jo har access par pay hota hai. Agar tumne jo hit-time add ki, $Δ H T$ , penalty se zyaada ho jo tumne bachai, $Δ m \cdot M P$ , toh AMAT worse ho jaata hai. Fix: do products compare karo, do miss rates nahi. Improvement tab hi hogi jab $Δ H T < Δ m \cdot M P$ , yaani $(HT increase) < (miss-rate drop) \times M P$ . L3-Q2 mein: $Δ H T = 2$ ns, $Δ m \cdot M P = 0.03 \times 100 = 3$ ns, aur $2 < 3$ , isliye trade jeetta hai.

Level 4 — Synthesis

Goal: AMAT ko doosre formulas (CPU time, local/global rates) ke saath combine karo.

Recall Solution

(a) $m_{L 1} = \frac{120}{1000} = 0.12$ . (b) L2 sirf woh $120$ forwarded accesses dekhta hai: $m_{L 2, local} = \frac{30}{120} = 0.25$ . (c) Global = woh misses jo DRAM tak pahunche, sab accesses par: $m_{global} = \frac{30}{1000} = 0.03$ . Check: $m_{L 1} \times m_{L 2, local} = 0.12 \times 0.25 = 0.03$ ✅. Isliye recursive AMAT nested term ke andar local rate use karta hai — L2 ko un accesses ki khabar nahi jo L1 ne satisfy kar diye. Dekho Multi-level Cache Hierarchy.

Recall Solution

Pehle, is problem ke borrowed symbols define karo (yeh CPU Performance Equation se aate hain):

CPI = cycles per instruction = ek instruction finish karne mein CPU average mein kitne clock cycles spend karta hai.
$CPI_{base}$ = woh CPI jo tumhe milta agar memory free ho (har access L1 hit, koi stall nahi) = yahan $1.0$ .
$CPI_{eff}$ = effective (real) CPI, memory misses ka intezaar karne mein CPU ke barbaad hue cycles add karne ke baad.
ns/cycle = clock period, $0.5$ ns — ek cycle ki wall-clock duration. Ns mein time ko ns/cycle se divide karne par cycles ki count milti hai (ns cancel ho jaate hain).

Step 1 — stall time per access. Kya: AMAT ka extra (stall) wala hissa. Kyun: flat $H T$ pipeline ke base CPI mein already covered hai (CPU har cycle ek L1 hit assume karta hai), isliye sirf penalty term hi ek saccha stall hai. $m \cdot M P = 0.05 \times 100 = 5 ns per access .$ Step 2 — stall time per instruction. Kya: per-access stall ko accesses per instruction se multiply karo. Kyun: har instruction average mein $1.5$ memory accesses issue karta hai, aur har ek mein same expected $5$ ns stall hai, isliye stalls add up hote hain — instruction per total stall time hai (stall per access) $\times$ (accesses per instruction). $5 ns/access \times 1.5 accesses/instr = 7.5 ns/instr .$ Step 3 — ns ko cycles mein convert karo. Kyun: CPI cycles mein measure hota hai, isliye stall time ko clock period ( $0.5$ ns/cycle) se divide karo; ns units cancel ho jaate hain, cycles bachte hain. $\frac{7.5 ns/instr}{0.5 ns/cycle} = 15 stall cycles/instr .$ Step 4 — effective CPI. Kya: stalls ko base par add karo. Kyun: real CPI = woh kaam jo CPUaise bhi karta plus woh cycles jisme woh memory ka intezaar karta hua idle baithta hai. $CPI_{eff} = CPI_{base} + stall cycles = 1.0 + 15 = 16.0.$ Yeh CPU Performance Equation ka bridge hai: AMAT ka penalty term memory-stall cycles ban jaata hai.

Level 5 — Mastery

Goal: formula ko ulta karo, target ke liye design karo, aur limits par reason karo.

Recall Solution

Formula ko limit par set karo aur $m$ ke liye solve karo: $H T + m \cdot M P \leq 4 \Rightarrow 2 + 100 m \leq 4 \Rightarrow m \leq \frac{2}{100} = 0.02.$ Toh $m \leq 2%$ . Isse zyaada hoga toh $4$ ns budget blow ho jaayega. Note: agar $H T$ akele hi $4$ ns exceed kar leta, toh koi miss rate (yahan tak ki $m = 0$ ) target meet nahi kar sakta — flat cost pehle se hi fail hai.

Recall Solution

(a) $m = 0$ (perfect cache, hamesha hit): $AMAT = H T$ . Penalty gayab ho jaati hai — best case; tum sirf look-up pay karte ho. Yeh wahi "perfect cache" baseline hai jo L4-Q2 mein use hua. (b) $m = 1$ (kabhi hit nahi — har access miss): $AMAT = H T + M P$ . Tum look-up aur full fetch har baar pay karte ho. Worst case. (c) $M P \to \infty$ : kisi bhi $m > 0$ ke liye $AMAT \to \infty$ . Ek tiny miss rate bhi, agar penalty unbounded ho, average time ko explode kar deti hai — "rare but ruinous" regime yehi hai jise AMAT expose karne ke liye banaya gaya hai. (d) $H T \to 0$ : $AMAT \to m \cdot M P$ . Floor sirf miss cost hi hai; cache ko infinitely fast banana bhi penalty-weighted term ko beat nahi kar sakta.

Neeche wala figure kaise padhen aur formula se jodein. Horizontal axis miss rate $m$ hai, $0$ (left) se $1$ (right) tak — yeh ek genuine number line hai. Vertical axis AMAT in ns hai, jisme $H T = 2$ ns aur $M P = 100$ ns fixed hain. Kyunki $AMAT = H T + m \cdot M P$ m mein linear hai (ek " $y = c + slope \cdot x$ " straight line), red curve ek straight line hai jiska kisi bhi $m$ par height literally $2 + 100 m$ hai. Trace karo: left endpoint ( $m = 0$ ) height $H T = 2$ ns par baithta hai — yeh case (a) hai, jahan $m \cdot M P$ term zero hai aur sirf look-up bacha hai. Right endpoint ( $m = 1$ ) height $H T + M P = 102$ ns tak pahunchta hai — yeh case (b) hai, full look-up-plus-fetch worst case. Line ki slope (jitna fast yeh right jaane par rise karta hai) $M P$ ke equal hai, $100$ ns per unit of $m$ : bada $M P$ (case c) line ko steeper karta hai infinity ki taraf; $H T$ shrink karna (case d) poori line seedha neeche slide kar deta hai origin ki taraf, slope badlay bina.

Recall Solution

Subtract karo; common $H T_{L 1}$ aur $m_{L 1}$ factor comparison mein cancel ho jaate hain: $AMAT_{L2} < AMAT_{no L2}$ $⟺ H T_{L 2} + m_{L 2} \cdot M P_{DRAM} < M P_{DRAM}$ $⟺ H T_{L 2} < M P_{DRAM} (1 - m_{L 2}) .$ Isko padhte hain: L2 tab help karta hai iff uska hit time DRAM penalty se chota ho, jo L2 ke hit rate $(1 - m_{L 2})$ se scale ki gayi ho. Kyunki DRAM slow hai (hundreds of ns) aur L2 hit time chota hai (kuch ns), yeh practically hamesha true hota hai — lekin agar $m_{L 2}$ $1$ ke paas hota (L2 useless, almost sab kuch miss ho jaata), toh right side $0$ ki taraf shrink ho jaata aur L2 actually hurt kar sakta hai (tum $H T_{L 2}$ bina kisi fayde ke pay karte). Worked check: $H T_{L 2} = 8$ , $M P_{DRAM} = 200$ , $m_{L 2} = 0.25 \Rightarrow$ chahiye $8 < 200 (0.75) = 150$ ✅ — L2 kaafi zyaada help karta hai.

Active Recall

Recall Cover karo aur jawab do

L2-Q3 mein, L1 miss penalty $200$ ns nahi, $58$ ns kyun hai?
L3-Q1 mein, miss rate halve karna hit time halve karne se kyun jeeta?
"L2 add karna worth it hai" ki exact inequality state karo (L5-Q3).
Memory-stall time $m \cdot M P$ kyun hai, poora AMAT kyun nahi (L4-Q2)?
$m = 0$ hone par AMAT kya hota hai? $m = 1$ hone par?

Jab misses rare hon lekin

M P

bada ho, AMAT mein kaun sa term dominate karta hai?

Penalty term

m \cdot M P

phir bhi dominate kar sakta hai — rare ka matlab cheap nahi.

Effective L1 miss penalty in a two-level cache

L2 subsystem ka AMAT, yaani

H T_{L 2} + m_{L 2} M P_{L 2}

Condition for L2 to reduce AMAT

H T_{L 2} < M P_{DRAM} (1 - m_{L 2})

Memory-stall time per access

m \cdot M P

(sirf penalty term, poora AMAT kabhi nahi).

AMAT when

m = 0

Sirf

H T

(perfect cache, best case).

AMAT when

m = 1

H T + M P

(har access miss, worst case).

Connections

Cache Miss Rate & Miss Types (3 Cs)
Miss Penalty & Main Memory Latency
Multi-level Cache Hierarchy
Cache Associativity & Hit Time tradeoff
CPU Performance Equation
Locality of Reference