Multi-level cache hierarchy (L1 - L2 - L3): Worked examples

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

Yeh page ek kaam ke liye hai: practice karo jab tak koi bhi case surprise na kar sake. Parent note ne AMAT formula banaya. Yahan hum har tarah ke numbers uthate hain jo woh formula throw kar sakta hai — perfect caches, useless caches, missing levels, real workloads, aur exam traps.

Neeche ka sab kuch ek recursive idea par tikaa hai, toh koi bhi symbol aane se pehle use plain words mein dobaara bol lete hain.

Pieces ko ek baar name kar lete hain (parent ne yeh define kiye hain; hum inhe rakhte hain taaki line one readable rahe).

Kyunki hamare paas teen cache levels hain, hum har rate ko us level ke saath tag karte hain jis se woh belong karta hai. Yeh sirf wahi $h$ aur $m$ hai jo teen baar likhee gayi hai:

The scenario matrix

Problems solve karne se pehle, yahan cases ka pura space hai. Neeche har example us cell ke saath tagged hai jo woh cover karta hai, taaki tum dekh sako kuch skip nahi hua.

Cell	Kya isse special banata hai	Kahan yeh bite kar sakta hai
A0. Single level	sirf L1 hai	woh base scenario jis se puri recursion grow hoti hai
A. Baseline	ordinary numbers, saare levels present	"vanilla" 3-level AMAT
B. Zero miss (perfect cache)	koi $m = 0$	neeche ke pure levels gayab ho jaate hain — kya formula phir bhi kaam karta hai?
C. Full miss (useless cache)	koi $m = 1$	cache latency add karta hai par koi fayda nahi — cost badh jaati hai
D. Missing level	L3 bilkul nahi	3-level formula ko 2-level mein collapse karo
E. Limiting behaviour	$m \to 0$ vs $m \to 1$	AMAT $T_{1}$ aur $T_{1} +$ full chain ke beech bounded
F. Solve backwards	AMAT diya, hit rate nikalo	algebra, sirf plug-in nahi
G. Word problem	wall-clock seconds, GHz	cycles ↔ time unit conversion
H. Exam twist	global vs local miss rate	classic galti jo marks khaata hai

Neeche ki figure is matrix ko ek pipeline ki tarah draw karti hai: har access left se enter karta hai (Cell A0 pehle box mein hi rehta hai), "abhi tak nahi mila" wala shrinking stream rightward flow karta hai jo Cells A–E track karte hain, aur labelled arrows precisely wahi miss rates $m_{1}, m_{2}, m_{3}$ hain jo hum har example mein tag karte hain. Ek worked example padho, phir picture mein uska box dhundho.

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

Picture dikhati hai kyun: $100%$ of accesses hit the L1 box, only $5%$ survive to L2, only $1%$ to L3, only $0.1%$ to DRAM. Those percentages are the products of miss rates we will compute in Cell H. Box widths dhyan mein rakho — jitna gehre jaao, stream utni hi patli.

Cell A0 — Single-level base case (sirf L1)

Forecast: Sirf ek cache ke saath, har miss seedha DRAM jaata hai. Kya answer 3-level case se bada hoga ya chhota? (Padhne se pehle socho — L2/L3 kuch bhi catch karne ke liye nahi hai.)

One-level formula lo. $AMAT = T_{1} + m_{1} T_{mem}$ Yeh step kyun? Koi bracket nest karne ke liye nahi hai — L1 miss ke paas memory ke alawa kaheen jaane ki jagah nahi, isliye uski penalty hi $T_{mem}$ hai. Yeh sabse simple, non-recursive doll hai.
Plug in karo. $AMAT = 4 + 0.05 \cdot 100 = 4 + 5 = 9 cycles$ Yeh step kyun? Har access $4$ -cycle L1 look pay karta hai. Sirf $5%$ miss karte hain, har ek $100$ pay karta hai, average mein $5$ cycles contribute karta hai.

Verify: $9$ $T_{1} = 4$ (agar kuch miss nahi kiya) aur $T_{1} + T_{mem} = 104$ (agar sab miss kiya) ke beech baittha hai. Yeh $4$ ki taraf jhukta hai kyunki $95%$ hit karte hain. ✓ Yeh seed hai: neeche har richer formula $T_{mem}$ ko ek cache level ke average cost se replace karke bana hai. (Yeh Cell A0 hai.)

Cell A — Baseline three-level AMAT

Forecast: Abhi andaza lagao — kya answer $4$ ke kareeb hoga ya $200$ ke kareeb? (Zyaadatar log over-guess karte hain; answer shocking roop se chhota lagega.)

Sabse inner bracket: L3 ka average cost. $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ Yeh step kyun? L3 mein dekhne mein hamesha $40$ lagta hai. L3 tak pahunchne wale sirf $10%$ accesses DRAM ke $200$ tak fall through karte hain. Toh average par ek "L3-region" access $60$ cost karta hai. Yeh number upar wale level ke liye DRAM ko replace karta hai.
Middle bracket: L2 ka average cost. $T_{2} + m_{2} \cdot 60 = 12 + 0.2 \cdot 60 = 24$ Yeh step kyun? Humne abhi kaha "L3 tak pahunchna average par $60$ cost karta hai," toh L2 ke point of view se ek miss penalty $60$ hai, $200$ nahi. L2 looks $12$ cost karti hain; unka $20%$ us $60$ tak fall through karta hai.
Outer: final answer. $T_{1} + m_{1} \cdot 24 = 4 + 0.05 \cdot 24 = 4 + 1.2 = 5.2 cycles$ Yeh step kyun? Har access L1 ka $4$ pay karta hai. Sirf $5%$ kabhi deeper machinery jagaate hain, aur unke liye woh machinery average $24$ karti hai.

Verify: Sanity check — $5.2$ $T_{1} = 4$ (best possible) aur $4 + 0.05 \cdot 200 = 14$ (agar L1 ke misses seedhe DRAM jaate) ke beech baittha hai. Yeh $4$ ke bahut kareeb hai kyunki L2/L3 heavy filtering karte hain. ✓ (Yeh Cell A hai.)

Cell B — Ek perfect level (zero miss rate)

Forecast: Agar L2 sab kuch catch karta hai jo usse poocha jaata hai, toh kya L3 aur DRAM matter karte hain?

Innermost phir bhi evaluate hota hai — par zero se multiply hota hai. $T_{3} + m_{3} T_{mem} = 60 (unchanged)$ Yeh step kyun? Hum ise compute karte hain, par dekho aage kya hota hai.
Middle bracket ise maar deta hai. $T_{2} + m_{2} \cdot 60 = 12 + 0 \cdot 60 = 12$ Yeh step kyun? $m_{2} = 0$ matlab koi access kabhi L2 nahi chodta. Humne jo $60$ compute kiya woh real hai par kissi tak pahunchta nahi. Formula ise multiply away kar deta hai — exactly wahi jo "perfect L2" karna chahiye.
Outer. $4 + 0.05 \cdot 12 = 4 + 0.6 = 4.6 cycles$ Yeh step kyun? Yeh standard outer layer hai: har access L1 ka $4$ pay karta hai, aur $5%$ jo L1 miss karte hain ab ek aise level se milte hain jiska pura cost sirf L2 ka $12$ hai (kyunki L2 kabhi fail nahi hota). $0.05 \cdot 12 = 0.6$ multiply karke add karne par average milta hai.

Verify: Ek perfect L2 ke saath, kisi bhi access ka sabse gehri cheez L2 at $12$ cycles ho sakti hai. Toh AMAT zyada se zyada $T_{1} + m_{1} T_{2} = 4 + 0.05 \cdot 12 = 4.6$ honi chahiye. Match karta hai. ✓ (Yeh Cell B hai — zero miss rate us point par hierarchy ko truncate kar deta hai.)

Cell C — Ek useless cache (miss rate of one)

Forecast: Agar L2 kabhi kuch nahi dhundta, toh kya woh time barbad karne ke alawa kuch kar raha hai?

Innermost. $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ Yeh step kyun? L3 aur DRAM ka behaviour Cell A se nahi badla, toh "L3 tak pahunchne" ka average cost abhi bhi $60$ cycles hai. Hum yeh number dobara establish karte hain kyunki neeche wale outer levels ko ise apni miss penalty ke roop mein chahiye — ek toota hua L2 bhi apne misses usi L3 ko deta hai.
Middle — full pass-through. $T_{2} + 1 \cdot 60 = 12 + 60 = 72$ Yeh step kyun? $m_{2} = 1$ matlab har L2 lookup fail hoti hai, toh har ek neeche wale level ke pure $60$ plus L2 mein dekhne mein waste hue $12$ cycles pay karta hai. L2 pure overhead ban gaya.
Outer. $4 + 0.05 \cdot 72 = 4 + 3.6 = 7.6 cycles$

Verify: Bina L2 wali machine se compare karo (accesses L1 → L3 jaate hain): $4 + 0.05 (40 + 0.1 \cdot 200) = 4 + 0.05 \cdot 60 = 7.0$ . Useless L2 deta hai $7.6 > 7.0$ — usne cheezein exactly barbad $0.05 \cdot 12 = 0.6$ cycles se worse kar diya. ✓ $m = 1$ wala cache kisi cache se bhi bura hai. (Yeh Cell C hai.)

Cell D — Ek level missing hai (2-level machine)

Forecast: Hamare teen formulas mein se kaun sa uthate hain? (Hint: memory nahi, caches gino.)

Two-level formula use karo. $AMAT = T_{1} + m_{1} (T_{2} + m_{2} T_{mem})$ Yeh step kyun? L3 nahi hai toh L2 miss seedhe DRAM jaata hai, isliye L2 ki miss penalty $T_{mem}$ hi hai — koi middle doll nahi.
Inside-out. $T_{2} + m_{2} T_{mem} = 12 + 0.2 \cdot 200 = 52$ Yeh step kyun? Yeh inner bracket L2 ka average cost hai. L2 mein dekhne mein hamesha $12$ lagta hai, aur L2 tak pahunchne wale $20%$ accesses DRAM ke $200$ tak fall through karte hain (koi L3 unhe catch karne ke liye nahi hai), deta hai $12 + 0.2 \cdot 200 = 52$ . Yeh $52$ L1 ki miss penalty ban jaata hai.
Outer. $4 + 0.05 \cdot 52 = 4 + 2.6 = 6.6 cycles$

Verify: Magnitude ka sanity check karo, 3-level formula ko manipulate karke nahi. (Trap se bachke raho: $T_{3} = 0$ aur $m_{3} = 1$ se fake L3 banaa ke 3-level expression reuse karna L3 ka cost $0 + 1 \cdot 200 = 200 = T_{mem}$ correctly deta, par $T_{3} = T_{mem}$ aur $m_{3} = 1$ se fake karne par DRAM do baar pay hota — $200 + 1 \cdot 200 = 400$ — jo galat hai. "L3 remove karne" ka safe tarika uski bracket drop karna hai, jo bas 2-level formula hai jo humne use kiya.) Bajaay: $6.6$ full 3-level $5.2$ (Cell A) se upar aur useless-L2 $7.6$ (Cell C) se neeche hai. Ek real L3 add karna (Cell A) help karta hai, aur karta hai: $5.2 < 6.6$ . ✓ (Yeh Cell D hai.)

Cell E — Limiting behaviour (do extremes)

Forecast: Floor kya hai? Ceiling kya hai? Padhne se pehle do numbers guess karo.

Best case, har $m \to 0$ . $AMAT \to T_{1} = 4 cycles$ Yeh step kyun? Agar L1 se kuch kabhi miss nahi karta, toh $m_{1} (\dots)$ term bilkul gayab ho jaata hai. AMAT kabhi $T_{1}$ se kam nahi ho sakta — tum hamesha pehla lookup pay karte ho.
Worst case, har $m \to 1$ . $AMAT \to T_{1} + T_{2} + T_{3} + T_{mem} = 4 + 12 + 40 + 200 = 256 cycles$ Yeh step kyun? Agar har level miss karta hai, toh har access puri chain chalke jaata hai, raaste mein har hit time pay karta hai aur finally DRAM. Yeh absolute ceiling hai.

Verify: Cell-A ka real answer $5.2$ yeh satisfy karta hai: $4 \leq 5.2 \leq 256$ . Tumhara compute kiya hua har AMAT $[T_{1}, T_{1} + T_{2} + T_{3} + T_{mem}]$ mein hona chahiye. Is range ke bahar koi bhi answer arithmetic error hai. ✓ (Yeh Cell E hai.)

Cell F — Solve backwards (AMAT diya, hit rate nikalo)

Forecast: Cell A mein $m_{1} = 0.05$ tha jo $5.2$ deta tha. AMAT ko $5.0$ tak lower karne ke liye, kya $m_{1}$ upar jaana chahiye ya neeche?

$m_{1}$ unknown ke saath equation likho. $5.0 = 4 + m_{1} \cdot 24$ Yeh step kyun? $m_{1}$ ke alawa sab fixed hai, toh yeh ek linear equation hai ek unknown mein.
$m_{1}$ isolate karo. $m_{1} = \frac{5.0 - 4}{24} = \frac{1.0}{24} \approx 0.04167$ Yeh step kyun? Hamesha pay hone wala $T_{1}$ subtract karo, phir miss penalty se divide karo. Yeh formula ko "undo" karta hai.
Hit rate mein convert karo. $h_{1} = 1 - m_{1} \approx 0.9583 = 95.83%$ Yeh step kyun? Sawaal hit rate ke liye tha, par hamaara formula miss rate ke terms mein likha hai. Definition se $m = 1 - h$ , toh $h = 1 - m$ ; miss rate ko $1$ se subtract karna us quantity ko convert karta hai jo humne solve ki woh quantity mein jo designer chahta hai.

Verify: Wapas plug karo: $4 + 0.04167 \cdot 24 = 4 + 1.0 = 5.0$ . ✓ Aur sense bhi banta hai: Cell-A ka $5.2$ beat karne ke liye humhe ek lower miss rate chahiye tha ( $0.0417 < 0.05$ ), yani thoda better L1. (Yeh Cell F hai.)

Cell G — Word problem (cycles se wall-clock seconds)

Forecast: $2 GHz$ matlab $2 \times 1 0^{9}$ cycles per second. Kya cached version seconds lega ya milliseconds?

Total cycles, cached. $4 \times 1 0^{9} accesses \times 5.2 \frac{cycles}{access} = 2.08 \times 1 0^{10} cycles$ Yeh step kyun? AMAT ki units cycles-per-access hain; access count se multiply karo aur "access" unit cancel ho jaata hai, cycles bachte hain.
Cycles ko seconds mein. $\frac{2.08 \times 1 0 ^{10} cycles}{2 \times 1 0 ^{9} cycles/s} = 10.4 s$ Yeh step kyun? Cycles ko (cycles per second) se divide karne par seconds bachte hain — clean unit check.
No-cache comparison. $\frac{4 \times 1 0 ^{9} \times 200}{2 \times 1 0 ^{9}} = \frac{8 \times 1 0 ^{11}}{2 \times 1 0 ^{9}} = 400 s$ Yeh step kyun? Hum exact same two-stage conversion repeat karte hain (accesses × cycles-per-access, phir ÷ cycles-per-second) par $5.2$ ki jagah $200$ cycles per access ke baseline cost ke saath. No-cache number usi units mein banana hi honest ratio lene deta hai Verify line mein.

Verify: Speedup $= 400/10.4 \approx 38.46 \times$ , parent ka $200/5.2 \approx 38.5 \times$ match karta hai (ratio unit-free hai, toh GHz cancel ho jaata hai — good). ✓ (Yeh Cell G hai.)

Cell H — Exam twist: global vs local miss rate

Forecast: Kya local L2 miss rate $1%$ se bada hai ya chhota? (Sirf $5%$ accesses L2 tak pahunchte hain…)

Global aur local ko relate karo. $GMR_{2} = m_{1} \cdot m_{2} \Rightarrow m_{2} = \frac{GMR _{2}}{m _{1}} = \frac{0.01}{0.05} = 0.2$ Yeh step kyun? Ek access globally L2 miss karta hai tabhi jab usne pehle L1 miss kiya ho (rate $m_{1}$ ) aur phir L2 miss kiya ho (rate $m_{2}$ ). Do independent hurdles ki probabilities multiply hoti hain. Solve karne par local $m_{2} = 0.2$ milta hai — $1%$ se bahut bada, kyunki iska base chhota $5%$ stream hai, sab nahi. (Yeh exactly figure mein "thinning stream" hai: L3 box $m_{1} m_{2} = 1%$ original width rakhta hai.)
Ab local $m_{2}$ ko standard formula mein plug karo (inside-out). $T_{3} + m_{3} T_{mem} = 40 + 0.1 \cdot 200 = 60$ $T_{2} + m_{2} \cdot 60 = 12 + 0.2 \cdot 60 = 24$ $T_{1} + m_{1} \cdot 24 = 4 + 0.05 \cdot 24 = 5.2 cycles$ Yeh step kyun? Ek baar $m_{2}$ correct local $0.2$ ho, yeh Cell A se identical hai — prove karta hai ki diya gaya global figure sirf Cell A disguise mein tha.

Verify: Global check doosre taraf se: $m_{1} m_{2} = 0.05 \cdot 0.2 = 0.01 = GMR_{2}$ . ✓ Agar tumne galti se $m_{2} = 0.01$ use kiya hota, tum $4 + 0.05 (12 + 0.01 \cdot 60) = 4.63$ paate — ek alag, galat answer jo exam mein plausible lagta. (Yeh Cell H hai.)

Pull it together

Recall Which formula and which numbers?

$m_{2}$ mein subscript ka kya matlab hai? ::: "Level 2 ka local miss rate" — jo accesses L2 tak pahunche unka woh fraction jo use miss kare. 3-level cache formula mein kitne brackets hote hain? ::: Teen nested brackets (L1 bahar, L2 middle, L3+DRAM andar). $m = 0$ wala level neeche wale levels ke saath kya karta hai? ::: Unhe truncate karta hai — unka cost zero se multiply ho jaata hai aur kabhi reach nahi hota. $m = 1$ wale cache vs bilkul koi cache nahi — kaun better? ::: $m = 1$ wala cache worse hai — woh apna hit time pure overhead ki tarah add karta hai bina kisi benefit ke. Koi bhi AMAT ka absolute minimum? ::: $T_{1}$ , L1 hit time jo tum hamesha pay karte ho. Absolute maximum? ::: $T_{1} + T_{2} + T_{3} + T_{mem}$ , har level missing. Global miss rate local se kaise relate karta hai? ::: $GMR_{k} = m_{1} m_{2} \dots m_{k}$ (us level tak ke local miss rates ka product).

Prerequisites & neighbours: yahan hit/miss counts Cache Organization aur Cache Replacement Policies se aate hain; "shared L3" reasoning Cache Coherence se connect karta hai; miss rates tumhare Memory Access Patterns par depend karte hain; aur yeh cycles execution mein kahan fit hote hain woh hai CPU Pipeline aur DRAM Architecture.