Average memory access time (AMAT): Worked examples

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

Scenario matrix

Har AMAT problem in cells mein se ek (ya blend) hoti hai. Neeche har worked example ko us cell ke saath tag kiya gaya hai jis par woh land karta hai.

Cell	Kya cheez ise special banati hai	Example
A. Baseline single-level	plain $H T + m \cdot M P$ , ordinary numbers	Ex 1
B. Degenerate $m = 0$	perfect cache, kabhi miss nahi karta	Ex 2
C. Degenerate $m = 1$	har access miss karta hai (limiting worst case)	Ex 2
D. Unit mismatch	formula ke sabhi terms ek hi unit share karni chahiye combine karne se pehle — cycles aur ns mix karna classic trap hai	Ex 3
E. Two-level nesting (local rates)	L1 ka penalty = L2 ka AMAT	Ex 4
F. Global-vs-local trap	global rate diya hai, convert karna padega	Ex 5
G. Solve backwards	AMAT pata hai, unknown $m$ ya $M P$ dhundho	Ex 6
H. Real-world word problem	ek story ko formula mein translate karo	Ex 7
I. Exam twist — design tradeoff	bada cache $m$ ko lower karta hai par $H T$ raise karta hai; kaun jeetha?	Ex 8

Hum inhe order mein walk karenge. Yahan har numeric answer verify block mein machine-checked hai.

Woh picture jo poore page ko chalati hai

Figure 1 — AMAT ki anatomy.

Figure — Average memory access time (AMAT)

Figure 1 mein split dekho: har access left mein flat green "hit" bar pay karta hai. Sirf $m$ fraction of accesses hi lambe coral "penalty" bar mein continue karte hain. AMAT green bar plus coral bar hai $m$ se scale down karke. Yeh image dimag mein rakhho — har example bas un dono bars ke liye numbers choose karna hai.

Worked examples

Worked example Ex 1 — Cell A: baseline single-level

Ek cache ka hit time $H T = 2$ ns, miss rate $m = 4% = 0.04$ , miss penalty $M P = 80$ ns hai. AMAT nikalo.

Forecast: Compute karne se pehle guess karo — AMAT 2 ns ke karib hoga ya 80 ns ke? (Hint: misses rare hain.)

Formula likho: $AMAT = H T + m \cdot M P$ . Yeh step kyun? Yeh expected time hai: flat hit cost plus miss probability se gate kiya gaya penalty.
Plug in karo: $AMAT = 2 + 0.04 \times 80$ . Yeh step kyun? $0.04 \times 80 = 3.2$ ns woh average extra time hai jo misses har access mein add karte hain.
Add karo: $2 + 3.2 = 5.2$ ns. Yeh step kyun? Unconditional aur conditional costs combine karo.

Verify: $5.2$ ns, $2$ ns hit time se thoda upar hai — fast case ke karib, jaise forecast kiya tha, kyunki zyaadatar accesses hit karte hain. Bounds check: $5.2$ , $[H T, H T + M P] = [2, 82]$ ns mein hai. ✅

Worked example Ex 2 — Cells B & C: do degenerate extremes

Same cache jaise Ex 1 ( $H T = 2$ ns, $M P = 80$ ns), par limits test karo: (B) miss rate $m = 0$ , (C) miss rate $m = 1$ .

Forecast: Jab cache kabhi miss na kare to AMAT kya equal hona chahiye? Jab hamesha miss kare?

Case B, $m = 0$ : $AMAT = 2 + 0 \times 80 = 2$ ns. Yeh step kyun? Agar kuch kabhi miss nahi karta, coral penalty bar disappear ho jaata hai — tum sirf hit hi pay karte ho. AMAT $H T$ tak collapse ho jaata hai, band ka lower end.
Case C, $m = 1$ : $AMAT = 2 + 1 \times 80 = 82$ ns. Yeh step kyun? Har access miss karta hai, toh har access hit phir penalty pay karta hai: $H T + M P$ . Yeh band ka upper end hai, absolute worst case.

Verify: Yeh exactly band ke $[H T, H T + M P] = [2, 82]$ ns ke do endpoints hain jo upar promise kiye gaye the. Ex 1 ka $5.2$ ns strictly unke beech mein rehta hai. ✅

Worked example Ex 3 — Cell D: unit mismatch (cycles vs ns)

Ek cache 1 clock cycle mein hit karta hai. Miss rate $= 5%$ . Ek miss 100 cycles cost karta hai. CPU clock period $0.5$ ns hai. AMAT nanoseconds mein nikalo.

Forecast: Kya tum clock period se combine karne se pehle multiply karte ho ya baad mein? Kya isse fark padta hai?

Pehle units check karo: $H T$ aur $M P$ dono cycles mein hain, toh woh already ek unit share karte hain — combine karna safe hai. (Agar ek ns mein hota aur ek cycles mein, to add karne se pehle convert karna padta.) Yeh step kyun? AMAT formula tab hi sense deta hai jab $H T$ aur $M P$ same unit carry karein; cycle count ko nanosecond count mein add karna nonsense hoga.
Cycles mein AMAT compute karo: $AMAT = 1 + 0.05 \times 100 = 6$ cycles. Yeh step kyun? Saare inputs cycles mein hain, toh formula ka output cycles mein hoga.
ns mein convert karo: $6 cycles \times 0.5 \frac{ns}{cycle} = 3$ ns. Yeh step kyun? Ek cycle $0.5$ ns ka rehta hai, toh cycle count ko period se multiply karo. Beginners yeh bhool jaate hain ya sirf ek term convert karte hain.

Verify: Kyunki conversion ek single multiply hai, pehle convert karna phir combine karna same deta hai: $(1 \times 0.5) + 0.05 \times (100 \times 0.5) = 0.5 + 2.5 = 3$ ns. Same answer → order ne koi fark nahi kiya. ✅ Units: cycles × (ns/cycle) = ns. ✅

Worked example Ex 4 — Cell E: two-level cache, local rates

$H T_{L 1} = 1$ ns, $m_{L 1} = 8%$ ; $H T_{L 2} = 8$ ns, $m_{L 2} = 25%$ (local); DRAM penalty $M P_{L 2} = 150$ ns. AMAT nikalo.

Pattern (yahan rakha gaya hai taaki page na chodna pade): multi-level AMAT bas single-level formula nested hai. "L1 ka miss penalty" koi fixed DRAM number nahi hai — woh khud ek AMAT hai: $H T_{L 2} + m_{L 2} \cdot M P_{L 2}$ . Toh tum pehle inner (L2) subsystem ka AMAT compute karte ho, phir use L1 ke penalty ke roop mein feed karte ho: $AMAT = H T_{L 1} + m_{L 1} (L1 ka real miss penalty H T_{L 2} + m_{L 2} \cdot M P_{L 2}) .$

Forecast: L1 miss penalty 150 ns nahi hai — woh jo bhi ek L1 miss actually cost karta hai woh hai. Guess karo: 150 se bada ya chhota?

Inner subsystem (ek L1 miss actually kya cost karta hai) $= H T_{L 2} + m_{L 2} \cdot M P_{L 2} = 8 + 0.25 \times 150 = 8 + 37.5 = 45.5$ ns. Yeh step kyun? Ek L1 miss L2 mein drop karta hai: yeh hamesha L2 ka hit time pay karta hai, aur sirf woh $25%$ jo L2 bhi miss karte hain woh DRAM trip pay karte hain. Yeh apne aap mein ek AMAT hai — yeh L1 ka effective penalty ban jaata hai.
L1 mein plug karo: $AMAT = H T_{L 1} + m_{L 1} \times 45.5 = 1 + 0.08 \times 45.5 = 1 + 3.64 = 4.64$ ns. Yeh step kyun? Ab L1 ka formula apna real penalty $45.5$ ns use karta hai, raw DRAM $150$ ns nahi.

Verify: Scary $150$ ns DRAM cost CPU tak sirf global fraction $m_{L 1} \times m_{L 2} = 0.08 \times 0.25 = 0.02$ par pahunchti hai, contribute karta hai $0.02 \times 150 = 3$ ns. L2 ka apna hit cost $0.08 \times 8 = 0.64$ aur flat $1$ add karo: $1 + 0.64 + 3 = 4.64$ ns. ✅ Do tareekon se same answer.

Worked example Ex 5 — Cell F: global-vs-local trap

Tumhe bataya gaya hai: overall (global) L2 miss rate $2%$ hai, aur $m_{L 1} = 8%$ hai. L2 ki local miss rate kya hai, aur recursive AMAT formula mein local chahiye ya global?

Forecast: Kya local rate global $2%$ se bada hai ya chhota?

Link yaad karo: global $= m_{L 1} \times m_{L 2, local}$ . Yeh step kyun? L2 sirf woh accesses dekhta hai jo L1 ne forward kiye (L1 misses). Global saare CPU accesses ke against count karta hai, ek bada denominator, toh global chhota hota hai.
Local ke liye solve karo: $m_{L 2, local} = \frac{global}{m _{L 1}} = \frac{0.02}{0.08} = 0.25 = 25%$ . Yeh step kyun? Global rate ko us fraction se divide karo jo L2 tak pahuncha bhi.
Recursive AMAT term $H T_{L 2} + m_{L 2} \cdot M P_{L 2}$ local $25%$ use karta hai. Yeh step kyun? Us term ke andar hum L2 par khade hain, aur L2 sirf us traffic ke against measure karta hai jo usne actually receive kiya.

Verify: Wापas convert karo: $m_{L 1} \times m_{L 2, local} = 0.08 \times 0.25 = 0.02 = 2%$ global. ✅ Note karo yeh exactly Ex 4 ke numbers hain — local $25%$ wahi hai jo us nested term mein plug hua tha.

Worked example Ex 7 — Cell H: real-world word problem

Ek web server requests serve karta hai. $92%$ time answer already in-memory cache mein hota hai (hit), jo $0.3$ ms leta hai. Baaki $8%$ mein disk read (miss) chahiye jo cache check ke upar $12$ ms extra add karta hai. Average response time kya hai?

Forecast: Kya average $0.3$ ms ke karib hoga ya $12$ ms ke? (Socho: woh $8%$ kitna heavy hai?)

Story ko AMAT se map karo: $H T = 0.3$ ms (hamesha paid — har request cache check karta hai), $m = 0.08$ , $M P = 12$ ms (extra, "upar se"). Yeh step kyun? "Adds ... on top of" phrase confirm karta hai ki $M P$ extra cost hai, total nahi — standard definition se match karta hai.
Apply karo: $AMAT = 0.3 + 0.08 \times 12 = 0.3 + 0.96 = 1.26$ ms. Yeh step kyun? Same formula; sirf story ke words badal gaye.

Verify: Miss contribution $0.96$ ms, hit cost $0.3$ ms se teen se zyada times hai even though misses sirf $8%$ hain — rare-but-expensive misses average dominate karte hain, AMAT ka poora moral yahi hai. Bounds check: $1.26$ , $[0.3, 12.3]$ ms mein hai. ✅

Worked example Ex 8 — Cell I: exam twist, design tradeoff

Tum current cache ( $H T_{A} = 1$ ns, $m_{A} = 10%$ ) rakh sakte ho ya bade, slow cache par switch kar sakte ho ( $H T_{B} = 2$ ns, $m_{B} = 4%$ ). Dono $M P = 100$ ns share karte hain. Kaun sa lower AMAT deta hai? (Dekho Cache Associativity & Hit Time tradeoff.)

Forecast: Hit time double karo par miss rate se zyada half karo — intuition kehta hai B jeetha... par check karo!

Cache A: $AMAT_{A} = 1 + 0.10 \times 100 = 1 + 10 = 11$ ns. Yeh step kyun? Beat karne ka baseline.
Cache B: $AMAT_{B} = 2 + 0.04 \times 100 = 2 + 4 = 6$ ns. Yeh step kyun? Zyada hit time ( $+ 1$ ns), par bahut kam expensive misses ( $- 6$ ns of penalty).
Compare karo: $6 < 11$ , toh Cache B jeetta hai $5$ ns se. Yeh step kyun? Saved penalty ( $6$ ns), extra hit cost ( $1$ ns) se zyada hai.

Verify: Net change $= (H T_{B} - H T_{A}) + (m_{B} - m_{A}) M P = (+ 1) + (- 0.06) (100) = 1 - 6 = - 5$ ns. ✅ $6 - 11 = - 5$ se match karta hai. Lesson: bada cache tab hi worth it hai jab woh penalty save kare jo hit time se zyada ho — hamesha plug in karo, kabhi eyeball mat karo.

Figure 2 — Ex 8 tradeoff bars.

Figure 2 Ex 8 ko visible banata hai: Cache B ka green (hit) bar taller hai, par uska coral (penalty) bar kahin zyada shrink karta hai — total stack chhoti hai.

Recall

Recall Cover karke answer do

Jab $m = 0$ ho, AMAT kya equal hota hai? ::: Exactly hit time $H T$ (band ka lower end). Jab $m = 1$ ho, AMAT kya equal hota hai? ::: $H T + M P$ — worst case, har access dono pay karta hai (upper end). AMAT hamesha kin do values ke beech bounded hota hai? ::: $[H T, H T + M P]$ . Global L2 miss rate aur $m_{L 1}$ diye hone par, local L2 rate kaise nikalen? ::: Divide karo: $m_{L 2, local} = global / m_{L 1}$ . Ex 8 mein, bada, slow cache phir bhi kyun jeeta? ::: Usne jo penalty save ki ( $6$ ns) woh extra hit time se zyada thi jo usne cost ki ( $1$ ns).

Connections

Average memory access time (AMAT) (parent)
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