Visual walkthrough — Multi-level cache hierarchy (L1 - L2 - L3)

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

Yeh page multi-level cache result ko pictures mein rebuild karta hai. Hum ek single memory access se shuru karte hain — ek request, ek safar — aur famous Average Memory Access Time (AMAT) formula ko step by step badhate hain. Har symbol ko use karne se pehle draw kiya jaata hai.

---

Step 1 — Ek access, ek clock, ek "cycle" ka matlab

KYA. Kisi bhi formula se pehle, hum apna time unit fix karte hain. Ek cycle CPU clock ki ek tick hai — processor jis sabse chhote time chunk mein kaam karta hai. Agar clock 1 GHz pe chale, toh ek cycle ek arb second ka ek hissa hai.

KYUN. Hum sab kuch — cache kitna fast jawab deta hai, DRAM kitna time leta hai — cycles mein measure karenge, taaki numbers ko saath mein add kiya ja sake. Nanoseconds ki jagah cycles use karne se picture clock-speed-independent rehti hai.

PICTURE. Figure dekho: CPU (amber block) pipe se ek request bhejta hai. Pipe equal ticks mein marked hai — woh ticks cycles hain. Data jitni door rehti hai, request ko answer wapas aane se pehle utni zyada ticks wait karni padti hai.

---

Step 2 — Sabse simple duniya: CPU seedha DRAM se baat karta hai

KYA. Saare caches hata do. Har request main memory, yani DRAM, mein jaati hai aur apni poori latency $T_{\text{mem}}$ bharta hai.

KYUN. Yeh hamara baseline hai — bina kisi help ke worst case. Baad mein jo kuch bhi banate hain woh is baseline se kitna fast hai, usi se measure hota hai.

PICTURE. CPU se DRAM tak ek lamba unbroken pipe. Koi shortcut nahi, koi jagah nahi jahan request ko pehle hi pakda ja sake. Har arrow poori distance travel karta hai: $T_{\text{mem}}$ cycles, har baar.

$$\underset{\text{average wait}}{\underbrace{{\text{AMAT}}_{\text{baseline}}}}=\underset{\text{every access pays the full DRAM trip}}{\underbrace{T_{\text{mem}}}}$$

$T_{\text{mem}}=200$ ke saath, average wait flat 200 cycles hai — abhi koi averaging nahi, kyunki sirf ek hi possible journey hai.

---

Step 3 — L1 Insert karo: "usually / sometimes" ka split

KYA. Ek chhoti fast cache, L1, CPU ke bilkul paas rakh do. Ab ek request ke do possible fates hain: L1 mein mili (ek hit), ya nahi mili (ek miss, DRAM ko bhejo).

KYUN. L1 common case ko instantly answer karne ke liye exist karta hai. Kyunki ab do outcomes hain, "ek access mein kitna time lagta hai?" ka koi ek jawab nahi — hume do paths par average karna hoga, weighted by kitni baar har path hota hai. Woh weighted average pehla real AMAT hai.

PICTURE. Pipe ab fork karti hai. Green hit path chhota hai (L1 pe ruk jaata hai). Red miss path poore raaste DRAM tak jaata hai. Dhyan do: har request pehle L1 hit time pay karti hai — tumhara door dhakdhakana zaroori hai L1 ka pehle — aur sirf fraction $m_{\text{L1}}$ aage jaata hai.

$$\text{AMAT}=\underset{\begin{array}{c}\text{paid by }100\%\\ \text{always check L1}\end{array}}{\underbrace{T_{\text{L1}}}}+\underset{\begin{array}{c}\text{fraction that}\\ \text{misses L1}\end{array}}{\underbrace{m_{\text{L1}}}}\cdot \underset{\begin{array}{c}\text{cost of the}\\ \text{DRAM trip}\end{array}}{\underbrace{T_{\text{mem}}}}$$

Numbers. $T_{\text{L1}}=4$, $h_{\text{L1}}=0.95\Rightarrow m_{\text{L1}}=0.05$, $T_{\text{mem}}=100$:

$$\text{AMAT}=4+0.05\cdot 100=4+5=9\text{ cycles}$$

Woh 5% jo miss karte hain, average ko exactly 5 cycles upar le jaate hain.

---

Step 4 — L2 Insert karo: miss ke andar ek doosra sawaal nest karna

KYA. L1 aur DRAM ke beech, L2 add karo: L1 se bada, L1 se slow, DRAM se fast. Ab L1 ke miss path mein khud fork hoti hai — L2 hit ya L2 miss mein.

KYUN. Hum nahi chahte ki ek L1 miss seedha slow DRAM tak giraye. L2 un zyaadatar misses ko saste mein pakad leta hai. Key idea: ek L1 miss ki cost ab $T_{\text{mem}}$ nahi hai — woh ban jaati hai "L2 se shuru karke answer milne ka average time." Hum bas ek AMAT ko doosre ke andar substitute karte hain.

PICTURE. Ek fork ke andar ek fork. Outer fork (L1 hit / miss) Step 3 jaisi hi hai. Lekin red L1-miss branch ab L2 pe ek doosri fork mein chalti hai: green L2 pe ruk jaata hai, red DRAM tak jaata hai. Poora L2 sub-tree Step 3 picture ki chhoti copy hai.

$$\text{AMAT}=T_{\text{L1}}+m_{\text{L1}}\cdot \underset{\text{average cost of an L1 miss}=\text{"AMAT starting at L2"}}{\underbrace{\left(T_{\text{L2}}+m_{\text{L2}}\cdot T_{\text{mem}}\right)}}$$

Term by term:

• $T_{\text{L1}}$ — sabhi pay karte hain.
• $m_{\text{L1}}$ — woh fraction jo L2 tak pahunchi.
• $T_{\text{L2}}$ — jo L2 tak pahunche woh sabhi yeh pay karte hain.
• $m_{\text{L2}}\cdot T_{\text{mem}}$ — unme se jo L2 miss karte hain woh DRAM trip pay karte hain.

Numbers. $T_{\text{L1}}=4$, $m_{\text{L1}}=0.05$, $T_{\text{L2}}=12$, $m_{\text{L2}}=0.2$, $T_{\text{mem}}=100$:

$$12+0.2\cdot 100=32\text{(cost of an L1 miss)}$$ $$\text{AMAT}=4+0.05\cdot 32=4+1.6=5.6\text{ cycles}$$

AMAT 9 → 5.6 ho gaya — L2 ne L1 ke 80% misses ko DRAM se pehle hi pakad liya.

---

Step 5 — L3 Insert karo: wohi nesting, ek level aur deep

KYA. L3 add karo, DRAM se pehle ki aakhri cache. L2-miss branch ab ek aakhri baar fork karti hai.

KYUN. Wohi logic jaise Step 4 mein, dobara apply karo. Yeh pattern reveal karta hai: har level ki miss penalty sirf next level ka AMAT hai. Formula recursive hai — forks ki Russian doll.

PICTURE. Teen nested forks. Kisi bhi request ko follow karo: woh hamesha L1 check karta hai; bachne wale L2 check karte hain; woh bachne wale L3 check karte hain; aakhri bachne wale DRAM tak pahunchte hain. Har fork zyaadatar traffic shed kar deta hai, toh DRAM almost kisi ko nahi dekhta.

$$\text{AMAT}=T_{\text{L1}}+m_{\text{L1}}(T_{\text{L2}}+m_{\text{L2}}(\underset{\text{innermost: AMAT at L3}}{\underbrace{T_{\text{L3}}+m_{\text{L3}}{T}_{\text{mem}}}}\left)\right)$$

---

Step 6 — Inside-out evaluate karo (kyun hume sabse deep level se shuru karna chahiye)

KYA. Nested formula mein numbers plug karo, innermost bracket se bahar ki taraf.

KYUN. Innermost bracket mein koi unknown nahi hota — woh sirf L3 aur DRAM pe depend karta hai. Jab isse ek single number mein collapse karte hain, toh bahar wale bracket mein bhi koi unknown nahi rehta. Bahar se andar kaam karne se un-simplified brackets bachenge; inside-out hamesha plain numbers deta hai.

PICTURE. Dekho innermost fork collapse hokar ek amber number "60" ban jaata hai, jo phir L2 ke fork ke andar miss cost ban jaata hai, "24" collapse hota hai, jo L1 ki miss cost ban jaata hai, aakhir mein "5.2" pe collapse hota hai.

$T_{\text{L1}}=4,m_{\text{L1}}=0.05,T_{\text{L2}}=12,m_{\text{L2}}=0.2,T_{\text{L3}}=40,m_{\text{L3}}=0.1,T_{\text{mem}}=200$ use karte hue:

$$\text{L3 layer:}40+0.1\cdot 200=60$$ $$\text{L2 layer:}12+0.2\cdot 60=24$$ $$\text{L1 layer:}4+0.05\cdot 24=5.2\text{ cycles}$$

DRAM 200 cycles door hai, phir bhi average access 5.2 cycles hai — kyunki deep forks almost khaali hain.

---

Step 7 — Degenerate cases (kabhi bhi reader ko ek un-shown scenario se mat takraao)

KYA. Formula ko uski extremes par test karo taaki tum isse har jagah trust karo.

KYUN. Ek formula jo tumne sirf beech mein test kiya hai, edges par jhooth bol sakta hai. Hum chaar boundary worlds check karte hain.

PICTURE. Chaar mini-panels: ek "perfect L1" duniya (saara traffic pehle hi fork par ruk jaata hai), ek "useless caches" duniya (saara traffic DRAM tak pahunchta hai), ek "no caches at all" duniya (Step 2), aur ek "one level" duniya (Step 3). Formula har ek ko reproduce karna chahiye.

• Perfect L1 ($m_{\text{L1}}=0$): doosra term vanish ho jaata hai, $\text{AMAT}=T_{\text{L1}}$. Best possible — har access L1 hit hai.
• Useless caches ($m_{\text{L1}}=m_{\text{L2}}=m_{\text{L3}}=1$): har request saari forks se slide karta hai, $\text{AMAT}=T_{\text{L1}}+T_{\text{L2}}+T_{\text{L3}}+T_{\text{mem}}$ — baseline se bhi worse, kyunki tum neeche jaate waqt har level ka toll pay karte ho. Isliye ek cache jo kabhi hit nahi karta woh tumhe actively hurt karta hai.
• No caches (saare levels hata do): Step 2 ka $\text{AMAT}=T_{\text{mem}}$ wapas aa jaata hai.
• $h$ ki boundary: $h$ ko $[0,1]$ mein rehna chahiye; $m=1-h$ ensure karta hai ki har fork ki do branches milke 100% traffic sum hoti hain — kuch nahi khota ya double-count nahi hota.

---

Step 8 — AMAT se speedup tak

KYA. Cached world (Step 6) ko baseline (Step 2) se compare karo.

KYUN. AMAT akela abstract hai; "kitne times faster" woh number hai jo log feel karte hain.

PICTURE. Do bars — ek lamba 200-cycle baseline aur ek chhota 5.2-cycle cached bar — ratio ek amber multiplier ke roop mein draw kiya gaya hai.

$$S=\frac{T_{\text{baseline}}}{\text{AMAT}}=\frac{200}{5.2}\approx 38.5\times$$

Ek 1 GHz CPU jo raw DRAM par stall kar raha hai woh ek 26 MHz machine ki tarah behave karta; hierarchy use near full speed par restore karti hai.

---

Ek-picture summary

Upar sab kuch ek single funnel mein compress kiya gaya: 100% traffic L1 pe enter karta hai, zyaadatar wahan ruk jaata hai, har fork se ek patli stream survive karti hai, aur sirf ek trickle DRAM tak pahunchti hai. AMAT is funnel mein average path length hai.

Recall Feynman retelling — plain words mein bolo

Socho har memory request ek aisa insaan hai jo ek building mein jaata hai jisme line mein chaar rooms hain: L1, L2, L3, aur peeche door, DRAM. Sab pehle L1 mein chalte hain aur ek chhota entry fee pay karte hain ($T_{\text{L1}}$). Sau mein se ninyanave ko wahan jo chahiye mil jaata hai aur woh nikal jaate hain — sasta aur done. Jo paanch nahi milta woh L2 mein aage chalte hain, ek aur chhota fee pay karte hain; un paanch mein se chaar succeed karte hain. Ek straggler L3 mein jaata hai, aur almost hamesha wahan succeed karta hai. Sirf ek bahut chhota fraction, average mein, kabhi slow back room DRAM tak pahunchta hai. Kyunki bheed har darwaze pe kam hoti jaati hai, average walk chhoti hoti hai — lagbhag 5 cycles — chahe back room 200 cycles door kyun na ho. Poora formula bas yeh hai: "is room ka fee sab pay karte hain, plus jo yahan fail hote hain woh jo kuch bhi next room ka average cost hai woh pay karte hain." Uss idea ko teen baar nest karo aur tumhare paas poora multi-level cache hai.

Recall

Single-cache AMAT mein $m_{\text{L1}}\cdot T_{\text{mem}}$ kya represent karta hai? ::: L1 misses se per access ka average extra cost — miss fraction times DRAM trip, saari accesses mein spread. Hum nested AMAT ko inside-out evaluate kyun karte hain? ::: Innermost bracket sirf deepest level aur DRAM pe depend karta hai, isliye woh pehle ek plain number mein collapse ho jaata hai; phir har bahari bracket mein koi unknown nahi rehta. Agar har cache level ki miss rate 1 ho toh AMAT ka kya hoga? ::: Tum har level ka hit time plus DRAM pay karte ho — koi cache na hone se bhi worse.

---

See also: Cache Organization · Cache Replacement Policies · Write Policies · Cache Coherence · Memory Access Patterns · TLB and Virtual Memory · CPU Pipeline · DRAM Architecture