Average memory access time (AMAT): Visual walkthrough

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

Hum assume karte hain ki tumhe sirf itna pata hai: memory woh jagah hai jahan computer data rakhta hai, aur kuch memory close/fast hoti hai jabki kuch door/slow. Baaki sab hum aage define karte jaate hain.

Step 1 — Ek single memory access hota kya hai

KYA: Hum picture karte hain ki CPU ek request ek fork mein bhej raha hai — ek hit path aur ek miss path.

KYUN: Kuch bhi average karne se pehle, hume exactly woh do cheezein pata honi chahiye jinhe hum average kar rahe hain. Har access in mein se ek hi hogi — koi teesra outcome nahi hota.

PICTURE: Green door (hit) jaldi data deta hai; red road (miss) slow box tak ek lamba detour hai.

Step 2 — Do time costs ko naam dena

KYA: Hum har path par ek stopwatch value lagate hain.

KYUN yeh split, aur "miss par total time" nahi? Kyunki miss par bhi tumhe pehle cache check karna hi pada — tum ne woh step skip nahi kiya. Toh miss path hai "cache check, phir detour" = $H T + M P$ , sirf $M P$ nahi. Is bookkeeping ko sahi karna hi poora game hai; Miss Penalty & Main Memory Latency dekho.

PICTURE: Green path ek bar hai jiska length $H T$ hai. Red path wahi same bar $H T$ hai jiske baad ek bahut lamba bar $M P$ hai — detour baad mein juda hota hai, kabhi instead of nahi.

Step 3 — Har path kitni baar hota hai? (Enter miss rate)

KYA: Hum fork ko probabilities se label karte hain: red road $m$ fraction of time liya jaata hai, green door $1 - m$ fraction.

KYUN fractions aur counts nahi? Kyunki "average time per access" ko is baat par depend nahi karna chahiye ki humne kitne accesses chalaye — sirf proportions par. Ek fraction "har path kitna likely hai" ko total volume se independent capture karta hai. Real life mein hit rates high kyun hoti hain, yeh Locality of Reference ka kaam hai.

PICTURE: Fork mein pour ho rahe $100$ chhote request-dots mein se, $1 - m$ green door se jaate hain aur $m$ red road par trickle karte hain.

Step 4 — "Average" yahan matlab kya hai (weighted, plain nahi)

KYA: Hum ek tool yaad karte hain jo humein chahiye — weighted average — aur batate hain kyun yeh sahi tool hai.

KYUN yeh tool aur plain average nahi? Plain average $(a + b) /2$ maanta hai ki dono outcomes equally common hain. Woh nahi hain: hits common hain, misses rare hain. Hume har cost ko uski frequency se weight karna hi hoga, warna rare-but-huge miss wildly over- ya under-count ho jaayegi. Weighted average exactly woh machine hai jo kehti hai "har cost ko utna count karo jitni baar tum use pay karte ho."

PICTURE: Coins ke do stacks — ek tall stack (hits) jिनमें se har ek thodi worth ka, ek short stack (misses) jिनमें se har ek bahut worth ka. Average wahan hai jahan see-saw balance karta hai, tall stack ki taraf khicha hua par heavy kuch se tugged.

Step 5 — AMAT ko do paths se assemble karna

KYA: Apne do paths ko weighted-average machine mein plug karo.

Hit path: weight $(1 - m)$ , cost $H T$
Miss path: weight $m$ , cost $H T + M P$

AMAT = fraction of hits (1 - m) cost of a hit H T + fraction of misses m cost of a miss (H T + M P)

KYUN is tarah likha? Yeh Step 4 ki picture ka literal readout hai: har stopwatch value ko us fraction se multiply kiya jaata hai jitni baar woh path liya jaata hai, phir sum karo. Kuch bhi invent nahi kiya — sirf do forks, weighted.

PICTURE: Step 4 ke do coin-stacks hamari actual times se relabel hoke ek balance point "AMAT" mein feed karte hain.

Step 6 — Simplify: hit time ko collapse hote dekho

KYA: Multiply out karo aur like terms collect karo.

AMAT = (1 - m) H T + m H T + m M P

Pehle do terms dekho — woh pieces jo $H T$ carry karte hain:

H T on the (1 - m) hits (1 - m) H T + H T on the m misses m H T = [(1 - m) + m] H T = every access! 1 \cdot H T = H T

$- m H T$ aur $+ m H T$ cancel ho jaate hain. Jo bachta hai:

AMAT = H T + m \cdot M P

KYUN $H T$ apni weighting kho deta hai? Kyunki $H T$ dono paths par pay hoti hai — hits aur misses. "Hits par $H T$ " plus "misses par $H T$ " add karna bas "sab accesses par $H T$ " hai = ek flat, unconditional $H T$ . Sirf penalty $M P$ solely miss path par rehti hai, toh sirf usi ke saath weight $m$ rehta hai.

PICTURE: Dono paths ke $H T$ bars saath slide karke ek single unavoidable block mein merge ho jaate hain; sirf red $M P$ bar ek fractional-height $m$ shadow rakhta hai.

Step 7 — Edge cases: kya formula extremes mein survive karta hai?

KYA: $m$ ko uski do boundaries par push karo aur check karo ki answer sane rehta hai.

Case	Set	Result	Matlab
Kabhi miss nahi	$m = 0$	$AMAT = H T + 0 = H T$	Har access instant-ish hai — tum sirf fast hit pay karte ho.
Hamesha miss	$m = 1$	$AMAT = H T + M P$	Har access cache check karta hai aur detour leta hai — poora miss path, har baar.
Chhota $m$ , huge $M P$	e.g. $m = 0.01$ , $M P = 200$	$H T + 2$	Rare misses phir bhi real time add karti hain — isliye hum care karte hain.

KYUN test karo? Jo formula tum stress-test nahi kar sakte, woh formula tum samjhe nahi ho. $m = 0$ par ise pure hit time reduce karna chahiye (no misses = no penalty). $m = 1$ par ise full miss cost $H T + M P$ equal karni chahiye (Step 2 ka red bar). Dono hold karte hain — formula poori range $0 \leq m \leq 1$ par trustworthy hai.

PICTURE: $m$ ke liye $0$ se $1$ tak ek slider; AMAT $H T$ se (left par) $H T + M P$ tak (right par) ek straight line ki tarah badhta hai. Iska slope exactly $M P$ hai.

Step 8 — Nesting: miss penalty khud ek AMAT hai

KYA: Single slow box ko do boxes se replace karo — DRAM ke aage ek L2 cache (Multi-level Cache Hierarchy dekho). Ab ek L1 miss seedha DRAM nahi jaati; pehle L2 se poochti hai.

Toh L1 miss penalty ab ek fixed number nahi hai — yeh hai "L2 se shuru karke request satisfy karne ka average time," jo ki khud ek AMAT hai:

M P_{L 1} = always check L2 H T_{L 2} + fraction of L2 misses m_{L 2} \cdot DRAM detour M P_{L 2}

Step 6 ke formula mein substitute karo:

AMAT = H T_{L 1} + m_{L 1} (H T_{L 2} + m_{L 2} \cdot M P_{L 2})

KYUN yeh average ko crush karta hai? DRAM term multiply out karo: woh $m_{L 1} \cdot m_{L 2} \cdot M P_{L 2}$ ke roop mein aata hai. Do chhote fractions multiply hoke ek tiny fraction banate hain — toh terrifying DRAM cost almost kisi access par pay nahi hoti. Woh product $m_{L 1} \cdot m_{L 2}$ L2 ki global miss rate hai. Formula ke andar hum $m_{L 2}$ local use karte hain (sirf woh accesses jo L2 tak pahunche), kyunki L2 sirf L1 ke leftover accesses dekhti hai.

PICTURE: Ek Russian-doll diagram: L1 ka red "miss" road ek doosri chhoti fork mein khulta hai (L2 hit vs DRAM detour) — Step 1 ki wahi picture, apne andar nested.

Ek-picture summary

Upar sab kuch, ek canvas par: fork (Step 1), do glued time-bars (Step 2), fractions (Step 3), weighted balance (Step 4–5), $H T + m \cdot M P$ par collapse (Step 6), $m$ par straight-line dependence (Step 7), aur nested L2 fork (Step 8).

Recall Feynman retelling — poora walkthrough plain words mein

Jab bhi computer ko data chahiye, woh fast cache door par knock karta hai. Zyaadatar baar data wahan hi hota hai — jaldi! Yeh ek hit hai, aur knock karne mein $H T$ time laga. Kabhi kabhi data wahan nahi hota — ek miss — toh knock karne ke baad use slow warehouse tak bhagna padta hai aur wापas aana padta hai, ek extra cost $M P$ . Average wait nikalne ke liye, hum hits aur misses ko equally common nahi treat karte, kyunki woh hain nahi: hum har ek ko uski frequency se weight karte hain ( $1 - m$ hits, $m$ misses). Jab hum sab add karte hain, knock ( $H T$ ) har trip par pay hua — hit ho ya miss — toh woh akela flat cost ke roop mein khada rehta hai. Sirf warehouse run ( $M P$ ) rare misses par hota hai, toh sirf usi par chhota fraction $m$ lagta hai. Yahi poora formula hai: $AMAT = H T + m \cdot M P$ . Test karo: agar tum kabhi miss nahi karte, tum sirf knock pay karte ho; agar tum hamesha miss karte ho, tum knock-plus-run har baar pay karte ho — dono exactly sahi nikalta hai. Aur agar warehouse door hai, ek medium shelf (L2) beech mein rakho: ab door trip almost kisi request par nahi hoti (do chhote fractions multiply ho gaye), aur average warehouse ko almost notice hi nahi karta.

Recall Quick self-check

$H T$ ke aage $m$ kyun nahi hai? ::: Tum cache har access par check karte ho, toh hit time unconditionally pay hoti hai; yeh flat $+ H T$ ke roop mein factor out ho jaata hai. AMAT-vs- $m$ line ka slope kya equal hai? ::: Miss penalty $M P$ . $m = 1$ par AMAT kya hai? ::: $H T + M P$ — poora miss path, har access. Nested L2 parentheses ke andar kaunsi miss rate jaati hai? ::: Local L2 miss rate. L2 DRAM cost ko itna kyun shrink karta hai? ::: DRAM detour ab product $m_{L 1} \times m_{L 2}$ se weighted hai, jo ek tiny number hai.

Connections

Parent: Average memory access time (AMAT)
Cache Miss Rate & Miss Types (3 Cs) — $m$ kahan se aata hai
Miss Penalty & Main Memory Latency — $M P$ kya measure karta hai
Multi-level Cache Hierarchy — Step 8 ka nesting
Cache Associativity & Hit Time tradeoff — kyun $H T$ freely shrink nahi ho sakta
Locality of Reference — kyun $m$ chhota hota hai
CPU Performance Equation — AMAT runtime mein kahan feed hota hai