Multi-level cache hierarchy (L1 - L2 - L3): Question bank

5.4.8 · D5 · Hardware › Memory Hierarchy & Caches › Multi-level cache hierarchy (L1 - L2 - L3)

Yeh page un galat fahmiyon ko dhundhti hai jo multi-level cache hierarchy ke andar chhup jaati hain. Har item ek hi line ka hai. Answer cover karo, apni reasoning zyoor se bolo, phir reveal karo. Agar koi word yahaan naya lag raha hai, toh pehle parent note aur Cache Organization se usse build karo.

Kisi bhi trap se pehle, woh chaar symbols pin down kar lo jo neeche har jagah aate hain. Har ek ek latency hai, CPU cycles mein measure hoti hai.

Baaki letters rates hain. Neeche, $m_{L1}$ local L1 miss rate hai — saare CPU accesses ka woh fraction jo L1 miss karta hai (kyunki har access L1 tak pahunchta hai, sirf L1 ke liye "local" aur "global" ek hi hote hain). Parent note ka running example $h_{L1} = 0.95$ use karta hai, isliye $m_{L1} = 1 - 0.95 = 0.05$ ; yeh number yaad rakho, neeche kaafi traps isse reuse karte hain.

Figure — Multi-level cache hierarchy (L1 - L2 - L3)

Aur yahan woh single formula hai jiske against har "Spot the error" item check hota hai — ise ek baar padho taaki neeche kuch surprise na ho:

Neeche ka flowchart ek access ko us formula ke through trace karta hai, taaki tum dekh sako ki kaun sa multiplier kaun si penalty se attach hota hai.

Do pipeline words jo baar baar use hote hain, yahan inline define hain taaki koi bhi trap context switch force na kare:

True or false — justify

L2 ki miss rate

0.2

ka matlab hai ki saare CPU accesses ka 20% L2 miss karta hai

False — woh

0.2

ek local rate hai, sirf un accesses par measure ki gayi hai jo L2 tak pahunche. Parent example use karte hue jahaan

m_{L1} = 1 - 0.95 = 0.05

hai, saare accesses ka woh fraction jo L2 miss karta hai global rate hai

m_{L1} \cdot m_{L2} = 0.05 \times 0.2 = 1%

L3 add karna hamesha AMAT kam karta hai

Zyaadatar sach hai par guaranteed nahi — L3 tabhi help karta hai jab L2 misses par uski hit rate apne hit-time overhead

T_{L3}

se zyada save kare; ek bekar L3 (near-zero hit rate) sirf

m_{L1} m_{L2} T_{L3}

path par add kar deta hai.

99% L1 hit rate ka matlab hai L1 "basically saara kaam kar raha hai," isliye L2/L3 barely matter karte hain

False — woh bachne wala 1% 100+ cycles ki penalties hit karta hai, isliye woh AMAT dominate kar sakta hai; woh levels jo us tail ko catch karte hain exactly wahi hain jo average time low rakhte hain.

L1 ko I-cache aur D-cache mein split karna mainly zyada data store karne ke liye hai

False — split structural hazard (instruction fetch aur data access ek hi cycle mein ek cache port ke liye compete karna) hatane ke liye exist karta hai, taaki dono simultaneous ho sakein; total capacity point nahi hai.

L1 ko bada karna hamesha CPU ko faster banata hai

False — bade L1 ki wires lambi aur access slower hoti hai,

T_{L1}

badh jaati hai jo har access par pay hoti hai; hit-rate gain common case slow karne ki keemat rarely outweigh karta hai.

Ek inclusive hierarchy mein, L3 ki capacity fully L1 aur L2 capacity mein add ho jaati hai

False — inclusive L3 L1/L2 ki har cheez duplicate karta hai, isliye woh bytes do baar count hote hain; effective new capacity L3 ke raw size se kam hai.

L2 ki miss penalty mein L2 ka apna hit time included hai

False — miss penalty agla level jaane ki cost hai; L2 ka hit time

T_{L2}

alag, ek baar pay hota hai, chahe L2 hit kare ya miss.

Ek shared L3 private L3 se slower hai, isliye sharing ek galati hai

False — sharing thodi latency trade karta hai saste inter-core data sharing aur kaafi kam Cache Coherence traffic ke liye; multithreaded code ke liye yeh net win hai.

L3 associativity double karna hamesha hit rate improve karta hai

False — yeh tabhi help karta hai jab conflict misses dominate karein; agar misses capacity ya compulsory hain, toh zyada ways kuch nahi khareedte aur power aur latency cost karte hain (dekho Cache Replacement Policies).

Har L1 miss DRAM ka full trip hota hai

False — ek L1 miss pehle L2 try karta hai, phir L3; sirf woh fraction jo saare caches miss karta hai,

m_{L1} m_{L2} m_{L3}

, actually DRAM tak pahunchta hai.

Spot the error

AMAT = T_{L1} + m_{L1} T_{L2} + m_{L2} T_{mem}

Last term un-weighted hai — DRAM tak pahunchne ke liye L1 aur L2 dono miss hone chahiye, isliye uski probability product

m_{L1} m_{L2}

hai, na ki sirf

m_{L2}

; woh "aur" hi reason hai ki correct form nest hoti hai as

m_{L1} (T_{L2} + m_{L2} T_{mem})

, har deeper penalty ko previous miss rate ke andar rakhte hue.

"L1 hit rate 0.95 hai, isliye AMAT

= 0.95 \times 4 + 0.05 \times 100

Galat — hit time har access par pay hoti hai (L1 mein dekhna zaroori hai pehle, tab hi pata chalta hai ki miss hua), isliye yeh unconditional hai aur

0.95

se weight nahi honi chahiye; correct form hai

T_{L1} + m_{L1} T_{mem} = 4 + 0.05 \times 100

"Speedup

= T_{mem} - AMAT

Speedup ek ratio hai, difference nahi:

S = T_{baseline} / AMAT

; subtraction ke wrong units hain — yeh cycles-saved-per-access deta hai, jabki ek factor dimensionless hona chahiye (cycles ÷ cycles).

"Hum AMAT nest ko outside-in evaluate karte hain, L1 se shuru karke"

Tum inside-out evaluate karte ho kyunki har bracket woh miss penalty hai jo uske upar wale level ko feed hoti hai: pehle (L3 + DRAM) average compute karo, use L2 ki miss penalty ke roop mein upar bhejo, phir use L1 ki miss penalty ke roop mein upar bhejo — outside-in jaane par tum ek aise penalty use karoge jo tumne abhi compute hi nahi ki.

"L2 unified hai kyunki ise split karna L1 ki tarah structural hazards paida karta"

Ulta hai — hazards ke liye do simultaneous accesses chahiye, aur sirf ~5% accesses L2 tak pahunchte hain, isliye simultaneous I/D collisions rare hain; split karne se zyada gain nahi, toh L2 unify ho jaata hai do structures par space waste karne se bachne ke liye.

"NINE cache L3 ke neeche ek fourth level hai"

Nahi — NINE (Non-Inclusive Non-Exclusive) ek inclusion policy ka naam hai jo kisi existing level par apply hoti hai: inclusive ki tarah copies force nahi karta, exclusive ki tarah forbid bhi nahi karta, bas convenient hone par hot lines rakhta hai.

"Kyunki L3 40 cycles door hai, wire delay woh reason hai jiske liye hum ise small rakhte hain"

Ulta hai — kyunki humne pehle se ही 40 cycles ki latency accept kar li hai, wire delay shave karna kuch nahi khareedt, isliye design goal flip ho jaata hai hit rate maximize karne ki taraf, matlab L3 ko bada banana.

Why questions

Har outer level larger aur slower kyun hoti hai, kabhi larger aur faster nahi?

Ek memory cell address-decode logic aur metal wires ke through reach hoti hai jinki length capacity ke saath badhti hai; signals finite speed se travel karte hain, isliye zyada bits literally lambi round trip ka matlab hai. Hierarchy yeh physics accept karti hai door, rarely-touched levels ko roomy aur paas wale levels ko tiny rakh kar.

AMAT formula independent terms ko sum karne ki jagah recursively nest kyun karta hai?

Kyunki ek level ki miss penalty is next level ka average access time, aur tum us next level tak tabhi pahunchte ho jab current wala miss ho — isliye costs conditional hain, aur conditional probabilities multiply hoti hain, jo exactly

m

's ki nesting hai.

L3 miss rate mein small drop, L1 miss rate mein bade drop se zyada kyun matter kar sakti hai?

Har L3 miss ek 100+ cycle DRAM fetch trigger karta hai, isliye har avoided L3 miss ek badi penalty hatata hai; ek avoided L1 miss sirf L2 poochhne ki chhoti extra cost bachata hai, kyunki L2/L3 pehle se cushion karte hain.

High associativity L1 se zyada L3 par kyun emphasize hoti hai?

Ek cache har address ko ek fixed set mein map karta hai; agar do hot addresses same set mein map hon, ek doosre ko evict karta hai — ek conflict miss. Ways add karne ka matlab hai ek set zyada lines hold kar sakta hai, isliye dono coexist kar sakte hain. MB-scale L3 par kaafi addresses collide karte hain, isliye ways pay off karte hain; L1 low-associativity rehta hai taaki uska lookup fast rahe (dekho Cache Replacement Policies).

Inclusion coherence kyun simplify karta hai?

Agar L3 kisi bhi core ke L1/L2 mein rakhhi har line mirror karta hai, toh ek coherence snoop sirf L3 check karke yeh jaaan sakta hai ki koi bhi core ek line cache karta hai ya nahi — ek lookup har private cache interrogate karne ki jagah le leta hai, inter-cache traffic kam karta hai.

CPU L1 guaranteed L1 misses ki stream par bhi pehle L1 kyun check karta hai?

Hardware ke paas koi oracle nahi jo bata sake ki line absent hai — lookup khud (address tag ko set ke against compare karna) woh tarika hai jisse pata chalta hai ki miss hai, isliye

T_{L1}

unavoidably spend hoti hai L2 par fall through karne se pehle.

Parent note ki access-pattern locality is poori hierarchy ko kaam kyun karti hai?

Programs jald hi same bytes reuse karte hain (temporal) aur agale baad nearby bytes (spatial), isliye ek chhota L1 jo recent aur adjacent data cache karta hai zyaadatar accesses catch kar leta hai; is locality ke bina funnel almost sab kuch DRAM ko leak kar deta aur caches pointless hote.

Edge cases

Agar L1 hit rate exactly

1.0

ho toh AMAT kya hai?

Yeh sirf

T_{L1}

par collapse ho jaata hai —

m_{L1} = 0

ke saath har miss term vanish ho jaata hai, aur outer levels kabhi consult nahi hote.

Agar L1 hit rate

0

ho (har access L1 miss kare) toh kya?

AMAT

= T_{L1} + (T_{L2} + \dots)

— tum phir bhi L1 lookup par full next-level cost ke upar pay karte ho, isliye L1 pure overhead ban jaata hai.

Agar tum ek aisa level add karo jiska local hit rate

0

ho toh AMAT ka kya hoga?

Yeh strictly badh jaata hai us level ke hit-time contribution se — ek cache jo kabhi hit nahi karta phir bhi apna lookup time charge karta hai fall through karne se pehle.

Agar

T_{mem} \to \infty

, toh AMAT mein kaun sa term dominate karta hai?

DRAM term

m_{L1} m_{L2} m_{L3} T_{mem}

— isliye saari miss rates ka product (global DRAM miss rate) ek hi number ban jaata hai jo matter karta hai.

Fully exclusive hierarchy mein, ek line L1 aur L3 mein ek saath kyun nahi reh sakti?

Definition se exclusive levels disjoint data hold karte hain — ek line exactly ek level mein rehti hai, jo total capacity maximize karta hai par coherence ko har level check karne par force karta hai.

Ek core ke L1 mein shared line par write karne ka doosre cores ke liye kya matlab hai?

Yeh Cache Coherence action trigger karta hai taaki doosre cores ki stale copies invalidate ya update ho sakein; write policy (write-back vs write-through) decide karta hai ki naya value L3/DRAM tak kab pahunchta hai.

Kya AMAT model still valid hai agar access par TLB miss ho jaaye?

Poori tarah se nahi — TLB and Virtual Memory ke through address translation apna miss cost pehle add karta hai, data cache index hone se bhi pehle, ek latency jo plain AMAT formula omit karta hai.

Recall One-line self-test

$m_{L1} = 0.05, m_{L2} = 0.2$ ke liye global L2 miss rate? ::: $0.05 \times 0.2 = 0.01$ , yaani saare CPU accesses ka 1%.