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

YEH KYA hai: $m_{L1}$ ek pure fraction hai (koi units nahi); $T_{L2}$ cycles mein hai. Unka product cycles mein hai. KYUN: $m_{L1}$ = un accesses ka fraction jo L1 miss karte hain aur isliye L2 visit karna padta hai. Pay karne ki chance ko pay karne ki cost se multiply karne par milta hai average (expected) cycles per access jo sirf L2 enter karne mein kharch hote hain. Yeh total AMAT ka ek term hai — "woh extra cost jo L2 guaranteed L1 hit time ke upar add karta hai."

Formula (one level): $\text{AMAT}=T_{L1}+m_{L1}{T}_{\text{mem}}$. YEH shape KYUN hai: har access $T_{L1}=4$ pay karta hai (hum hamesha pehle L1 mein dekhte hain). Ek fraction $m_{L1}=1-0.90=0.10$ miss karta hai aur poora $T_{\text{mem}}=100$ pay karta hai. $\text{AMAT}=4+0.10\cdot 100=4+10=\boxed{14\text{ cycles}}$

Andar se bahar. Pehle: ek L1-miss ka average cost kya hai? Woh L2 tak pahunchta hai (14 pay karo), aur un mein se ek chauthaai DRAM par miss karta hai (120 pay karo): $T_{L2}+m_{L2}{T}_{\text{mem}}=14+0.25\cdot 120=14+30=44\text{ cycles}$ KYUN: yeh "44" ek L1 miss ki average price hai. Ab ise weight karo ki L1 kitni baar miss karta hai: $\text{AMAT}=T_{L1}+m_{L1}\cdot 44=3+0.08\cdot 44=3+3.52=\boxed{6.52\text{ cycles}}$

Brackets ko sabse deep se bahar ki taraf build karo. Innermost (L2 miss ki cost): $T_{L3}+m_{L3}{T}_{\text{mem}}=38+0.15\cdot 180=38+27=65$ Middle (L1 miss ki cost): $T_{L2}+m_{L2}\cdot 65=12+0.30\cdot 65=12+19.5=31.5$ Outer (poori cheez): $\text{AMAT}=T_{L1}+m_{L1}\cdot 31.5=4+0.06\cdot 31.5=4+1.89=\boxed{5.89\text{ cycles}}$

Option A — better L3 (baaki sab same): Innermost: $38+0.075\cdot 180=38+13.5=51.5$ Middle: $12+0.30\cdot 51.5=12+15.45=27.45$ Outer: $4+0.06\cdot 27.45=4+1.647=\boxed{5.647}$ cycles. $5.89$ se improvement: roughly $0.243$ cycles.

Option B — faster L1 ($T_{L1}=3$, baaki sab 2.2 jaisa): Nested brackets unchanged hain (abhi bhi $31.5$), sirf base badla hai: $3+0.06\cdot 31.5=3+1.89=\boxed{4.89}$ $5.89$ se improvement: exactly $1.0$ cycle.

KYUN B itna decisively jeetta hai: L1 hit time 100% accesses pay karte hain, isliye 1 cycle off = 1 cycle off AMAT, full stop. L3 improvement sirf $m_{L1}\cdot m_{L2}=0.06\cdot 0.30=1.8\%$ accesses ko touch karta hai jo kabhi L3 tak pahunchte hi hain — wahan ek huge relative gain front par aakar ek tiny absolute gain ban jaata hai. Common case ko faster banana rare misses ko beat karta hai.

KYUN ek alag formula: ek global miss rate $g_{Lk}$ pehle se hi us level tak pahunchne ki probability include karta hai (yeh saari accesses ke against measure hota hai). Toh global language mein hum har level ki extra cost directly add karte hain, apni global rate se weighted — hum nest-multiply nahi karte. Poora additive global formula: ek access hamesha $T_{L1}$ pay karta hai. Jab bhi woh ek level globally miss karta hai, usse next level probe karna padta hai aur us next level ki hit time pay karni padti hai — aur aisa karne wale accesses ka fraction exactly us level ki global miss rate hai jo abhi chhoot gayi: $\text{AMAT}=T_{L1}+g_{L1}{T}_{L2}+g_{L2}{T}_{L3}+g_{L3}{T}_{\text{mem}}$ Values plug in karo: $\text{AMAT}=4+0.06\cdot 12+0.018\cdot 38+0.0027\cdot 180$ $=4+0.72+0.684+0.486=\boxed{5.89\text{ cycles}}$ Local rates ke zariye cross-check: $m_{Lk}^{\text{local}}=g_{Lk}/g_{L(k-1)}$ se convert karo aur Ex. 2.2 reuse karo:

• $m_{L1}=g_{L1}=0.06$.
• $m_{L2}=g_{L2}/g_{L1}=0.018/0.06=0.30$.
• $m_{L3}=g_{L3}/g_{L2}=0.0027/0.018=0.15$. Ye exactly Exercise 2.2 ki local rates hain, isliye nested formula bhi $5.89$ deta hai. Lesson: global aur local ek hi hierarchy ki do languages hain — additive global form aur nested local form hamesha agree karte hain.

Speedup = (no-cache time per access) / (cached time per access): $S=\frac{T_{\text{mem}}}{\text{AMAT}}=\frac{180}{5.89}\approx \boxed{30.6\times }$ KYUN yeh sahi ratio hai: bina kisi cache ke, har access full 180-cycle DRAM trip hai; hierarchy ke saath average trip 5.89 cycles hai. Ratio yeh hai ki memory system kitni baar faster data deliver karta hai. Peak performance ka fraction jo uncached machine retain karti hai: agar CPU otherwise apni clock rate par useful work issue kar sakta par har memory access use access latency ke liye stall karta hai, toh throughput $1/(\text{access latency})$ ke scale par hota hai. Uncached machine ki memory $S\approx 30.6\times$ slower hai, isliye memory-bound stream par woh sirf roughly $\frac{1}{S}=\frac{5.89}{180}\approx 0.0327\approx \boxed{3.3\%}$ throughput retain karti hai jo cached machine achieve karta hai. Ise padhna: hierarchy ~97% ka heavy lifting kar raha hai — ise nikaalo aur ek memory-bound workload roughly one-thirtieth speed par crawl karta hai. (Hum jaanbujhkar ek single "effective MHz" number quote karne se bache hain, kyunki woh exactly compute vs. memory work ke mix par depend karta hai; clean, assumption-free statement $30.6\times$ speedup itself hai.)

Ex. 2.1 yaad karo: $T_{L1}=3,m_{L1}=0.08,T_{L2}=14,m_{L2}=0.25,T_{\text{mem}}=120$.

Option A (L3 add karo): L2-miss tail ab L3 se guzarti hai: Innermost: $T_{L3}+m_{L3}{T}_{\text{mem}}=40+0.20\cdot 120=40+24=64$ Middle: $T_{L2}+m_{L2}\cdot 64=14+0.25\cdot 64=14+16=30$ Outer: $3+0.08\cdot 30=3+2.4=\boxed{5.40}$ cycles.

Option B (bigger L2): 2-level rahega, $T_{L2}=16,m_{L2}=0.12$: Middle: $16+0.12\cdot 120=16+14.4=30.4$ Outer: $3+0.08\cdot 30.4=3+2.432=\boxed{5.432}$ cycles.

Verdict: A deta hai $5.40$, B deta hai $5.432$ — Option A (L3 add karo) barely jeetta hai. KYUN: L3 poore DRAM tail (woh expensive 120) ko ek 20%-only escape ke peeche shield karta hai, jabki L2 enlarge karne se uski miss rate help hui lekin surviving 12% abhi bhi full DRAM pay karta hai. Jab DRAM penalty large ho, toh ek filtering level insert karna ek existing one ko improve karne se better hota hai. Neeche ka figure dono AMATs ko directly stacked bars ke roop mein comparable banata hai.

Do tails compare karo jo ek L2-miss le sakta hai:

• Seedha DRAM: cost $=T_{\text{mem}}$.
• L3 se: cost $=T_{L3}+m_{L3}{T}_{\text{mem}}$. L3 add karna tab help karta hai jab: $T_{L3}+m_{L3}{T}_{\text{mem}}<T_{\text{mem}}$ Break-even miss rate $m^{\star }$ ke liye solve karo (equal set karo): $T_{L3}+m^{\star }{T}_{\text{mem}}=T_{\text{mem}}\Rightarrow m^{\star }=\frac{T_{\text{mem}}-T_{L3}}{T_{\text{mem}}}=1-\frac{T_{L3}}{T_{\text{mem}}}$ Ise padhna: L3 tab tak pay off karta hai jab tak uski actual miss rate $m_{L3}<m^{\star }$ ho. Example: $T_{L3}=40,T_{\text{mem}}=180\Rightarrow m^{\star }=1-40/180\approx 0.778$. Toh L3 ek whopping 77.8% miss rate tak help karta hai — koi bhi real L3 (10–30% miss) easily worth it hai. KYUN itna lenient: ek mostly-missing L3 bhi zyaadatar trips ko ek cheap 40-cycle probe mein turn karta hai, aur sirf misses 180 pay karti hain. Detour cheap hai; woh kabhi kabhi provide karta hai shortcut huge hai.

Load cost (stream ka 70%). Ek load poora Ex. 2.1 two-level path leta hai: $T_{\text{load}}=T_{L1}+m_{L1}(T_{L2}+m_{L2}{T}_{\text{mem}})=3+0.08\cdot (14+0.25\cdot 120)=6.52\text{ cycles}$ (Yeh exactly wahi AMAT hai jo Exercise 2.1 mein compute ki gayi thi — units: cycles.)

Store cost (stream ka 30%). Write-through ka matlab hai har store L2 tak propagate karta hai, toh ek store L1 hit time plus L2 hit time pay karta hai: $T_{\text{store}}=T_{L1}+T_{L2}=3+14=17\text{ cycles}$ No-write-allocate ka matlab hai ki ek missing store line ko L1 mein fetch nahi karta — woh simply L2 par land karta hai — toh koi additional DRAM term nahi hai. Units: cycles.

Frequency se blend karo. Loads aur stores do populations hain alag costs ke saath; stream average har cost ko kitni baar occur hoti hai us se weighted hoti hai: $T_{\text{eff}}=0.70T_{\text{load}}+0.30T_{\text{store}}=0.70\cdot 6.52+0.30\cdot 17$ $=4.564+5.1=\boxed{9.664\text{ cycles}}$ Ise padhna: stores minority hain (30%) phir bhi average mein zyada se zyada contribute karte hain, kyunki write-through constant L2 traffic force karta hai ($17$ cycles each). Yahi wajah hai ki real designs write buffers add karte hain store latency ko useful work ke peeche hide karne ke liye.

Shared L3 (line wahan hai): B apne private L1/L2 miss karta hai, phir shared L3 hit karta hai. Us access ki tail cost — B ke apne private levels se aage ka part — exactly L3 hit time hai: $T_{\text{tail, shared}}=T_{L3}=\boxed{40\text{ cycles}}$ A ne jo data produce kiya woh common L3 mein baitha hai, B ke liye ready.

Private L3 (line sirf A ke caches mein hai): B apne saare levels miss karta hai, aur coherence protocol ko A ki copy interconnect ke across fetch karni padti hai — yahan full memory-latency trip ki tarah model ki gayi hai: $T_{\text{tail, private}}=180\text{ cycles}$

Saving: $T_{\text{tail, private}}-T_{\text{tail, shared}}=180-40=\boxed{140\text{ cycles per shared read}}$

KYUN sharing yahan jeetti hai: ek shared last-level cache ek inter-core coherence miss (≈180, near DRAM) ko ek ordinary L3 hit (40) mein turn karta hai. Producer→consumer data ek ek jagah rehta hai jahan har core saste mein pahunch sakta hai, bajay ek core ke private cache mein phansa rehne aur on demand interconnect ke across haule jaane ke. Real designs LLC ko shared isliye banate hain (dekho Cache Coherence): multicore mein jo latency matter karti hai woh sirf apne-data-tak latency nahi balki dusre-core-ke-data-tak latency hai, aur L3 sharing baad wale ko ek coherence miss se ek cache hit mein collapse karta hai.

Ex 1.2 ::: 14 cycles Ex 2.1 ::: 6.52 cycles Ex 2.2 ::: 5.89 cycles Ex 3.1 ::: faster L1 jeetta hai (4.89 vs 5.647) Ex 3.2 ::: 5.89 cycles (additive global form aur local form agree karte hain) Ex 4.1 ::: speedup ≈ 30.6×, uncached ≈ 3.3% throughput retain karta hai Ex 4.2 ::: L3 add karo (5.40) bigger L2 (5.432) ko beat karta hai Ex 5.1 ::: m★ = 1 − T_L3/T_mem ≈ 0.778 Ex 5.2 ::: 9.664 cycles (loads 6.52, stores 17) Ex 5.3 ::: 140-cycle saving (40 vs 180)