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

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

Definition Is page par use hone wale symbols aur conventions

Kisi bhi question se pehle, har symbol ko plain words mein pin kar lo taaki kuch ambiguous na ho:

$H T$ = hit time = cache ko search karne aur data deliver karne ka time jab data present ho. Yeh har access par pay karna padta hai, hit ho ya miss.
$m$ = miss rate = un accesses ka fraction (0 aur 1 ke beech) jo is cache mein nahi milte aur next level par jaana padta hai.
$M P$ = miss penalty = hit access se ==aage ka extra time== jo block ko next level se fetch karne mein lagta hai. Convention (yahan sab jagah use hoti hai): $M P$ additional cost hai, isliye miss par total time $= H T + M P$ hai, sirf $M P$ nahi.
Single-level formula: $AMAT = H T + m \cdot M P$ .
Multi-level subscripts: $H T_{L 1}, H T_{L 2}$ = L1 / L2 ka hit time. $m_{L 1}$ = L1 miss rate (saare CPU accesses mein se L1 miss karne waale ka fraction). $m_{L 2, l oc a l}$ = L2 ka local miss rate (L2 tak pahunche accesses mein se miss karne waale ka fraction). $M P_{L 2}$ = L2 miss penalty = L2 se main memory (DRAM) tak pahunchne ka extra time.

Formula Multi-level AMAT — conditional expectation se derive kiya gaya

Har access $H T_{L 1}$ pay karta hai. Extra cost sirf L1 miss par hoti hai, jo probability $m_{L 1}$ ke saath hoti hai. Ek L1 miss par average mein kitna lagta hai? Exactly L2 subsystem ka AMAT: L2 ko probe karne ke liye $H T_{L 2}$ pay karo, aur probability $m_{L 2, l oc a l}$ ke saath (L2 tak pahunchne ki condition par) DRAM tak pahunchne ke liye aur $M P_{L 2}$ pay karo. Toh har access par expected extra cost $m_{L 1} \times [H T_{L 2} + m_{L 2, l oc a l} \cdot M P_{L 2}]$ hai. Unconditional $H T_{L 1}$ add karke: $AMAT = H T_{L 1} + m_{L 1} (H T_{L 2} + m_{L 2, l oc a l} \cdot M P_{L 2})$ Counting check (figure se match karta hai). 1000 accesses lo, $m_{L 1} = 0.1$ , $m_{L 2, l oc a l} = 0.2$ . Toh $1000 \cdot H T_{L 1}$ sab pay karte hain; $100$ accesses (10%) $H T_{L 2}$ bhi pay karte hain; un $100$ mein se $20$ (L2 tak pahunche waale ka 20%) $M P_{L 2}$ bhi pay karte hain. Total time ko 1000 se divide karne par formula exactly reproduce hota hai — nesting ek bookkeeping fact hai, koi convention ki appeal nahi.

L2 ka Local miss rate: $m_{L 2, l oc a l} = \frac{L2 misses}{L2 tak pahunche accesses}$ — sirf neeche forward kiye accesses par measure kiya jaata hai.
L2 ka Global miss rate: $m_{L 2, g l o ba l} = \frac{L2 misses}{saare CPU accesses} = m_{L 1} \times m_{L 2, l oc a l}$ . Recursive formula ka inner rate local rate $m_{L 2, l oc a l}$ hai — kyunki yeh conditional "given we reached L2" fraction hai aur outer $m_{L 1}$ already set up kar deta hai.

True or false — justify

Hit time ko standard AMAT formula mein hit rate se multiply kiya jaata hai.

False. Expected value

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

se shuru karo;

H T

dono branches mein appear karta hai, isliye yeh

H T [(1 - m) + m] = H T

ke roop mein factor out ho jaata hai. Hit time unconditional hai; sirf

M P

par

m

ka factor hota hai.

Lower miss rate hamesha AMAT ko lower karti hai, baaki sab equal ho.

True. AMAT

= H T + m \cdot M P

m

ka function maano; iska slope

\frac{d ( AMAT )}{d m} = M P > 0

ek positive constant hai, isliye AMAT strictly

m

mein increasing hai aur

m

mein koi bhi decrease AMAT ko strictly decrease karti hai.

Agar miss rate 0 hai, toh AMAT hit time ke barabar hai.

True.

m = 0

substitute karne par

H T + 0 \cdot M P = H T

milta hai; koi miss nahi hone par penalty term identically zero hai, isliye har access exactly ek cache access jitna lagta hai.

Agar miss rate 100% hai, toh AMAT miss penalty ke barabar hai.

False.

m = 1

substitute karne par

H T + 1 \cdot M P = H T + M P

milta hai, sirf

M P

nahi — kyunki hamari convention mein

M P

extra cost hai, ek guaranteed miss bhi pehle hit access pay karta hai. Dekho Miss Penalty & Main Memory Latency.

L2 cache add karne se AMAT kabhi worse nahi ho sakta.

False. No-L2 AMAT

= H T_{L 1} + m_{L 1} \cdot M P_{D R A M}

ko two-level

= H T_{L 1} + m_{L 1} (H T_{L 2} + m_{L 2} M P_{D R A M})

se compare karo. L2 tabhi help karta hai jab

H T_{L 2} + m_{L 2} M P_{D R A M} < M P_{D R A M}

ho, yaani

H T_{L 2} < (1 - m_{L 2}) M P_{D R A M}

; yeh violate karo toh AMAT badhta hai.

Recursive multi-level AMAT inner levels ke liye global miss rates use karta hai.

False. Outer factor

m_{L 1}

already L2 tak pahunche accesses tak scale down karta hai, isliye inner

m_{L 2}

local hona chahiye; global rate

m_{L 1} m_{L 2, l oc a l}

andar plug karne par

m_{L 1}

discount do baar apply ho jaata. Dekho Multi-level Cache Hierarchy.

Cache ko faster banana (lower

H T

) AMAT reduce karne ka sabse accha lever hai.

Zyada tar false. Concretely

H T = 1

m = 0.05

M P = 100

ke saath: AMAT

= 6

;

H T

ko aadha karke

0.5

karne par

5.5

milta hai (−0.5), lekin

m

ko aadha karke

0.025

karne par

3.5

milta hai (−2.5).

m \cdot M P

term (

= 6

ns mein se

5

) dominate karta hai, isliye

m

M P

par attack karna kaafi better hai.

Bahut high hit rate wale level ke liye, uska hit time essentially poora AMAT hota hai.

True. Jaise

m \to 0

hota hai,

m \cdot M P \to 0

ho jaata hai, toh AMAT

\to H T

; jaise

m = 0.01

M P = 100

H T + 1

milta hai, jo

H T

ke kuch ns hone par

H T

se dominate hota hai. Isliye fast

H T

L1 ke liye matter karta hai, jo Locality of Reference se near-total-hit rakha jaata hai.

L2 ka global miss rate uske local miss rate se bada ho sakta hai.

False. Global

= m_{L 1} \times m_{L 2, l oc a l}

aur

0 \leq m_{L 1} \leq 1

; ek non-negative number ko

\leq 1

factor se multiply karne par yeh increase nahi ho sakta, isliye global

\leq

local (sirf degenerate case

m_{L 1} = 1

mein equal).

Spot the error

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

— dono outcomes ka weighted average."

Miss branch galat hai: ek miss par

H T + M P

lagta hai, sirf

M P

nahi, kyunki aap ne cache pehle search kiya tha. Correct expected value

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

collapse karke

H T + m \cdot M P

deta hai.

"L2 miss penalty 200 ns hai, toh recursive formula mein L1 miss penalty bhi 200 ns hai."

L1 miss penalty poore L2 subsystem ka AMAT hai (

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

), raw DRAM latency nahi — zyada tar L1 misses L2 mein catch ho jaate hain aur DRAM tak kabhi nahi pahunchte.

"Main global L2 miss rate

H T_{L 1} + m_{L 1} (H T_{L 2} + m_{L 2} M P_{L 2})

ke andar use karunga."

Inner

m_{L 2}

local hona chahiye; global rate

m_{L 1} m_{L 2, l oc a l}

plug karne par L1 filtering jo outer

m_{L 1}

factor mein already hai, dobaara apply ho jaati hai.

"Miss penalty mein hit time already include hai, isliye miss par total access sirf

M P

hai."

Hamari convention mein

M P

hit access se aage ka extra time hai, isliye miss time

H T + M P

hai;

M P

ko inclusive maanna formula se contradict karta hai aur exactly

H T

se undercount karta hai.

"Kyunki L1 misses sirf 10% hain, DRAM latency AMAT ke liye koi baat nahi karta."

Yeh product

m_{L 1} \times m_{L 2}

ke through matter karta hai, lekin jaise

m_{L 1} m_{L 2} = 0.02

aur

M P = 300

ns ke saath DRAM trips

6

ns add karte hain — often

H T

se bhi zyada, isliye compute karo, andaze mat lagao.

"Bada cache add karne se miss rate kam hui, toh AMAT zaroor drop hoga."

Zaroor nahi — bada cache often slower

H T

hota hai (dekho Cache Associativity & Hit Time tradeoff); agar

H T

jitna

m \cdot M P

gira usse zyada badhta hai, toh AMAT better hit rate ke bawajood badhta hai.

Why questions

Hit time unconditionally kyun add hota hai, sirf hits par kyun nahi?

Kyunki har request pehle cache probe karta hai yeh jaane bina ki hit hai ya miss,

H T

dono branches mein pay hota hai; expected value

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

mein woh shared term ek constant

+ H T

ban jaata hai,

m

se independent.

Caches layer karne par miss rates multiply kyun hote hain, penalties add kyun nahi?

DRAM tak pahunchne ke liye L1 aur phir L2 miss karna padta hai; local rates use karte hue, saare accesses mein se DRAM tak pahunchne waalon ka fraction (L1 miss karne waalon ka fraction)

\times

(unme se L2 miss karne waalon ka fraction)

= m_{L 1} \times m_{L 2, l oc a l}

hai — yeh nested conditional fractions ke baare mein ek definitional counting fact hai, koi statistical independence assumption nahi.

AMAT rare misses par kyun "obsess" karta hai common hits ki jagah?

H T + m \cdot M P

mein, agar

M P

H T

se 100–200× bada ho, toh chota

m

bhi

m \cdot M P

H T

se zyada bana deta hai; jaise

m = 0.05, M P = 100, H T = 1

mein

5

ns miss contribution versus

1

ns hit milta hai — rare-but-huge term mean ko dominate karta hai.

AMAT define karne ke liye hum expected value (probability average) use kyun karte hain?

N

accesses mein, total time

= (1 - m) N \cdot H T + m N \cdot (H T + M P)

;

N

se divide karke per-access average nikaalte hain toh exactly

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

milta hai — AMAT literally long-run mean time per access hai, jo expected value ki definition hai.

Recursive formula ke andar local miss rate sahi quantity kyun hai?

Outer

m_{L 1}

already L2 ko forward kiye accesses tak restrict karta hai, isliye inner probability "given we reached L2, do we miss?" condition par honi chahiye — woh conditional fraction precisely local miss rate hai; global use karne par double-condition ho jaata.

High hit rate L2 ko pointless kyun nahi banata?

5%

L1 miss rate bhi

200

ns DRAM trip se multiply hoke

0.05 \times 200 = 10

ns per access add karta hai; un misses ko ek fast L2 se route karna (maan lo

H T_{L 2} = 10

m_{L 2} = 0.2

)

200

10 + 0.2 \times 200 = 50

se replace karta hai, contribution

10

2.5

ns tak cut karta hai.

CPU performance equation AMAT ki kyun parwah karta hai?

AMAT average memory-stall time per access set karta hai; accesses-per-instruction se multiply karne par stall cycles per instruction milta hai, jise CPU Performance Equation base CPI mein add karta hai — isliye AMAT directly total execution time badhata hai.

Edge cases

Agar ek program perfect locality rakhta ho aur har level par 0% miss rate ho, toh AMAT kya hoga?

Sirf

H T_{L 1}

—

m_{L 1} = 0

ke saath poora penalty bracket zero se multiply hota hai, isliye aap hamesha sirf fastest access time pay karte ho. Yeh theoretical floor hai.

Agar miss rate L1 par 100% ho lekin L2 par 0% ho, toh AMAT kya ho jaata hai?

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

— har access L1 miss karta hai aur L2 hit karta hai, isliye aap hamesha dono levels ka hit time pay karte ho aur DRAM kabhi nahi touch karte.

Jab miss penalty zero ho (next level utna hi fast ho jitna yeh level), toh AMAT kya hoga?

AMAT

= H T + m \cdot 0 = H T

, kyunki misses mein koi extra cost nahi — ek degenerate case jahan hierarchy koi penalty nahi deta aur miss rate irrelevant ho jaata hai.

Ek workload jo har address exactly ek baar touch karta hai (koi reuse nahi) — AMAT mein kya dominate karta hai?

Miss rate compulsory (cold) misses se near

100%

drive hoti hai, isliye AMAT

\approx H T + M P

— caches reuse ke bina koi khaas help nahi karte. Dekho Cache Miss Rate & Miss Types (3 Cs).

Agar

H T_{L 2}

itna bada ho jaaye ki purani DRAM penalty se bhi exceed kare, toh kya L2 add karna ab bhi worth it hai?

Nahi — L2 tabhi help karta hai jab

H T_{L 2} + m_{L 2} M P_{D R A M} < M P_{D R A M}

ho; agar

H T_{L 2} \geq M P_{D R A M}

toh woh inequality outright fail hoti hai, isliye har L1 miss slower ho gaya aur AMAT badhta hai, hierarchy ka purpose defeat ho jaata hai.

Jaise miss rate zero ke paas jaata hai, AMAT ka kaunsa term vanish hota hai aur kaunsa survive karta hai?

H T + m \cdot M P

mein,

m \cdot M P

term

\to 0

hota hai jabki

H T

fixed rehta hai — confirm karta hai ki hit time floor hai aur misses sirf uske upar add hote hain.

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