Multi-level cache hierarchy (L1 - L2 - L3) — Hinglish notes

5.4.8 · Hardware › Memory Hierarchy & Caches

Overview

Modern processors multiple levels of cache (L1, L2, L3) use karte hain CPU aur main memory ke beech mein, taaki bade speed gap ko bridge kiya ja sake. Har level size aur speed ke beech tradeoff karti hai: core ke paas wali caches chhoti aur tez hoti hain, aur door wali caches badi aur thodi slow hoti hain.

The Memory Hierarchy — Average Access Time Derive Karna

Multiple Levels Ki Zaroorat Kyun Hai?

Goal: Data ko CPU ke paas rakho bina fast storage banana ke cost/power/space penalty diye.

Problem: Fast memory (SRAM) per bit mahanga hai. Slow memory (DRAM) sasta hai lekin 100× slow hai.

Solution: Ek pyramid banao:

L1 cache: 32-64 KB, 1-4 cycles, per-core
L2 cache: 256-512 KB, ~10 cycles, per-core
L3 cache: 8-32 MB, ~40 cycles, cores ke beech shared
Main memory (DRAM): GB-scale, ~100-200 cycles

Average Memory Access Time (AMAT) Derive Karna

Single-level cache se shuru karte hain:

AMAT_{1-level} = T_{L1_hit} + m_{L1} \cdot T_{mem}

Yeh formula kyun?

Har access $T_{L1_hit}$ pay karta hai (hum hamesha pehle L1 check karte hain)
$m_{L1}$ fraction of accesses miss ho jaate hain → DRAM se fetch karne ke liye $T_{mem}$ pay karo

Example: $T_{L1} = 4$ cycles, $h_{L1} = 0.95$ , $T_{mem} = 100$ cycles.

AMAT = 4 + 0.05 \cdot 100 = 4 + 5 = 9 cycles

Yeh step kyun? L1 hit time fixed hai (4 cycles). 5% accesses miss hote hain (0.05), har miss ki cost 100 cycles hai → average miss penalty 5 cycles hai.

Ab L2 add karte hain:

AMAT_{2-level} = T_{L1} + m_{L1} \cdot (T_{L2} + m_{L2} \cdot T_{mem})

Yeh structure kyun?

Har access L1 check karta hai ( $T_{L1}$ )
Agar L1 miss ho jaaye ( $m_{L1}$ ), L2 check karo ( $T_{L2}$ )
Agar L2 bhi miss ho jaaye ( $m_{L2}$ ), DRAM jaao ( $T_{mem}$ )

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

AMAT = 4 + 0.05 \cdot (12 + 0.2 \cdot 100) = 4 + 0.05 \cdot 32 = 4 + 1.6 = 5.6 cycles

Yeh step kyun?

L1 miss rate 5% → 5% accesses L2 check karte hain
Un 5% mein se, L2 80% ko hit karta hai (12 cycles mein) aur 20% ko miss karta hai (100 aur cycles ki cost)
L2 ki average cost: $12 + 0.2 \cdot 100 = 32$ cycles
L1 miss rate se weighted: $0.05 \cdot 32 = 1.6$ cycles

Key insight: L2 add karne se AMAT 9 se ghatkar 5.6 cycles ho gayi — 40% improvement — kyunki L2 ne L1 ke 80% misses ko slow DRAM tak pahunchne se pehle hi catch kar liya.

Full 3-level hierarchy:

$AMAT = T_{L1} + m_{L1} \cdot (T_{L2} + m_{L2} \cdot (T_{L3} + m_{L3} \cdot T_{mem}))$

Example: $T_{L1} = 4$ , $m_{L1} = 0.05$ , $T_{L2} = 12$ , $m_{L2} = 0.2$ , $T_{L3} = 40$ , $m_{L3} = 0.1$ , $T_{mem} = 200$ .

Inner term (L3 + mem):

T_{L3} + m_{L3} \cdot T_{mem} = 40 + 0.1 \cdot 200 = 40 + 20 = 60

Middle term (L2 + [L3+mem]):

T_{L2} + m_{L2} \cdot 60 = 12 + 0.2 \cdot 60 = 12 + 12 = 24

Full AMAT:

T_{L1} + m_{L1} \cdot 24 = 4 + 0.05 \cdot 24 = 4 + 1.2 = 5.2 cycles

Yeh step kyun?

Andar se bahar kaam karo: L3 ko DRAM ki taraf 0.1 miss rate milti hai → average 60 cycles
L2 ko L3 ki taraf 0.2 miss rate milti hai → average 24 cycles
L1 ko L2 ki taraf 0.05 miss rate milti hai → base mein 1.2 cycles add hote hain

Result: Sirf 5.2 cycles average — jabki DRAM 200 cycles door hai — kyunki zyaadatar accesses L1 se bahar nahi jaate.

Har Level Alag Kyun Design Hota Hai

L1 Cache (Data + Instruction)

Goal: CPU ko har cycle data feed karna.

Design:

Size: 32-64 KB (per core)
Latency: 1-4 cycles
Associativity: 8-way set-associative
Split: Alag I-cache (instructions) aur D-cache (data) taaki ek saath instruction fetch aur data access ho sake

Itna chhota kyun? Speed ke liye. SRAM cell area capacity ke saath badhta hai. Bada cache → lambe wire delays → slow access. 3GHz (0.33 ns/cycle) par, light sirf 10 cm per cycle travel karti hai. Ek bade cache mein signal propagation multiple cycles le sakta hai.

I/D split kyun? CPU ko next instruction aur load/store data same cycle mein chahiye hota hai (Harvard architecture ka faayda). Unified L1 ek structural hazard create kar deta.

Worked example L1 Split Example

Cycle 1: Fetch ADD instruction (I$) + Load operand from memory (D$)
Cycle 2: Fetch SUB instruction (I$) + Store result (D$)

Split caches ke bina, ek access stall kar deta.

L2 Cache

Goal: L1 misses ko slow L3/DRAM tak jaane se pehle catch karna.

Design:

Size: 256-512 KB (per core)
Latency: ~10-12 cycles
Associativity: 8-16 way
Unified: Dono instructions aur data rakhta hai (I $a u r D$ misses space ke liye compete karte hain)

Unified kyun? L2 par, access conflicts rare hote hain (sirf ~5% accesses yahan pahunchte hain), isliye cache resources duplicate na karne ka faayda structural hazard ki cost se zyaada hota hai.

L1 se 10× bada kyun? Hum yahan pahunchne ke liye pehle se 10 cycles ki latency pay kar chuke hain. Hum ek bada structure afford kar sakte hain kyunki speed ka pressure kam hai. Goal ab "fastest possible" se shift hokar "L3 avoid karne ke liye high hit rate" ho jaata hai.

L3 Cache (Last-Level Cache, LLC)

Goal: Expensive DRAM access se pehle final filter. Coherence ke liye shared resource.

Design:

Size: 8-32 MB (sabhi cores ke beech shared)
Latency: ~40-50 cycles
Associativity: 16-24 way
Shared: Sabhi cores ek hi L3 access karte hain (efficient inter-core data sharing enable karta hai)

Shared kyun? Agar core A koi data likhta hai jo core B ko chahiye (multithreaded programs mein common), woh data L3 mein baithta hai jahan B use quickly access kar sakta hai. Per-core L3 ke liye private caches ke beech mehenga cache coherence protocol traffic chahiye hota.

Itna bada kyun? Hum CPU se pehle se 40+ cycles door hain. Wire delay ab bottleneck nahi hai (hum ise accept kar chuke hain). Ab hit rate sabse zaroori hai: har L3 miss 100+ DRAM cycles ki cost laata hai, isliye L3 hit rate mein 1% ka improvement bhi bahut bada time bachata hai.

Itna highly associative kyun? MB-scale caches mein, conflict misses (jahan useful data evict ho jaata hai kyunki doosra address same set mein map karta hai) dominant miss type ban jaate hain. High associativity (16-24 ways) replacement policy ko hotest data rakhne ki azaadi deta hai.

Effective Speedup Calculate Karna

Sawaal: 3-level hierarchy direct DRAM access se kitna fast hai?

Baseline (no cache): Har access $T_{mem} = 200$ cycles ki cost leta hai.

3-level cache ke saath: AMAT = 5.2 cycles (pehle ke example se).

Speedup:

S = \frac{T _{baseline}}{T _{with_cache}} = \frac{200}{5.2} \approx 38.5 \times

Yeh kyun matter karta hai: Bina cache ke 1GHz CPU effectively 26 MHz par run karta memory stalls ki wajah se. Caches memory system ko 38× faster banate hain, jisse CPU zyaadatar workloads ke liye apni clock speed ke paas run kar sake.

Result: Caches 194.8 seconds bachate hain. Program 38× faster run karta hai.

Yeh step kyun? Yeh hierarchy ke benefit ko quantify karta hai. In numbers ke bina, "caches cheezein faster banate hain" vague hai. Ab hum jaante hain: caches hi reason hain ki modern CPUs bilkul usable hain.

Global vs. Local Miss Rates

Distinguish kyun karte hain? Local rates batate hain ki ek specific cache kitna achha perform karta hai. Global rates system-level impact batate hain.

Example: L1 local miss rate = 5%, L2 local miss rate = 20%.

L2 global miss rate:

m_{L2_global} = m_{L1} \cdot m_{L2_local} = 0.05 \cdot 0.2 = 0.01 = 1%

Yeh step kyun? Sirf 5% accesses L2 tak pahunchte hain (L1 ke misses). Un 5% mein se, L2 20% miss karta hai. Toh globally, $0.05 \times 0.2 = 0.01$ (1%) saare CPU accesses L2 ko miss karte hain.

Insight: Ek "bura" L2 local miss rate (20%) ka system impact chhota hota hai agar L1 achha hai (95% hit rate), kyunki zyaadatar accesses L2 tak pahunchte hi nahi.

Common Mistakes

Yeh sahi kyun lagta hai: Zyaada space matlab zyaada data cached, higher hit rate.

Fix: Bade caches ki access time lambi hoti hai (wire delays, addressing complexity). 1 MB L1 ko access karne mein 20 cycles lag sakte hain — L2 hit karne se bhi slow! Goal sirf hit rate maximize karna nahi, AMAT minimize karna hai.

Sahi soch: Har level ko is tarah size kiya jaata hai ki hierarchy mein us level ki position par hit rate aur access time ka balance bane.

Yeh sahi kyun lagta hai: "Access sabhi levels se guzar sakta hai, toh sabhi ko add kar do."

Fix: Zyaadatar accesses L1 par ruk jaate hain. L2 ki cost tab hi pay hoti hai jab L1 miss ho. Weighted sums use karo:

AMAT = T_{L1} + m_{L1} \cdot (T_{L2} + m_{L2} \cdot (\dots))

Yeh step kyun? Miss rates weights hain. Sirf $m_{L1}$ fraction of accesses L2 ki cost dekhte hain.

Yeh sahi kyun lagta hai: Miss rate 20% hai, toh 20% miss hote hain.

Fix: L2 ki local miss rate 20% hai L2 accesses ke, na ki sabhi CPU accesses ke. Agar CPU ke sirf 5% accesses L2 tak pahunchte hain, toh global L2 miss rate $0.05 \times 0.2 = 1%$ hai.

Sahi soch: Hamesha track karo ki miss rate local (per-level) hai ya global (system-wide). AMAT impact calculate karte waqt global rates use karo.

Memory Hierarchy Design Tradeoffs

Level	Size	Latency	Associativity	Kyun?
L1	32-64 KB	1-4 cyc	8-way	Speed-critical: chhota aur fast
L2	256-512 KB	10-12 cyc	8-16 way	Balance: L1 misses catch karo bina L3 cost ke
L3	8-32 MB	40-50 cyc	16-24 way	Hit rate-critical: DRAM se pehle last stop

Associativity L1 se L3 tak kyun badhti hai? Conflict misses lower levels par zyaada hurt karte hain (CPU ke zyaada paas). Higher associativity area aur power ki cost leta hai. L3 afford kar sakta hai (pehle se slow, large). L1 nahi kar sakta (tiny aur fast rehna zaroori hai).

L1 split (I $/ D$ ) kyun hai lekin L2/L3 unified? Structural hazards (ek saath instruction fetch + data access) L1 par critical hote hain (har cycle hota hai). L2/L3 par, accesses rare hote hain (sirf misses par), isliye unification area bachata hai.

Feynman Recall — Ek 12-Saal Ke Bachche Ko Samjhao

Recall Tum ise ek 12-saal ke bachche ko kaise samjhaoge?

Socho tum homework kar rahe ho aur tumhe facts dhundhne hain. Tumhare paas hai:

Desk par ek sticky note (L1) — bahut paas, kuch facts rakhta hai
Ek notebook (L2) — desk par, zyaada facts rakhti hai lekin pages palthne padte hain
Ek bookshelf (L3) — kamre ke doosri taraf, bahut saari books rakhti hai
Library (DRAM) — cycle chalake jaana padta hai, lekin sab kuch hai wahan

Trick yeh hai: tum sabse zyaada use hone wale facts sticky note par rakhte ho. Jab tumhe naya fact chahiye, pehle sticky note check karo (lagbhag hamesha wahan milega!). Agar nahi mila, notebook check karo. Agar wahan bhi nahi, bookshelf par jaao. Sirf tabhi library jaate ho jab bookshelf par nahi milta.

Kyunki tum baar baar same facts use karte ho (jaise multiplication tables), sticky note par 95% time jo chahiye woh milta hai. Tumhe library jaana hi nahi padta. Isliye tum homework 5 minutes mein khatam karte ho 5 ghante ki jagah — chaahe library slow ho, tum use barely use karte ho!

Caches usi tarah kaam karte hain: L1 chhota hai lekin CPU ke "brain" ke bahut paas hai, isliye woh data rakhta hai jo CPU abhi use kar raha hai. L2 aur L3 bade hain lekin door hain. Main memory bahut badi hai lekin bahut door. CPU ko data lagbhag hamesha L1 mein milta hai, isliye woh full speed par run karta hai.

Mnemonic

S's upar jaate hain: Small → Slower → Slowest.

Connections

Cache Organization — har level ke sets/ways/blocks kaise structured hote hain
Cache Coherence — L1/L2/L3 multiple cores mein consistent kaise rehte hain
Memory Access Patterns — spatial/temporal locality caching ko effective kyun banati hai
Cache Replacement Policies — har level mein eviction victims choose karne ke liye LRU/LFU
Write Policies — har level par write-through vs. write-back
TLB and Virtual Memory — address translation cache jo L1 ke saath baithta hai
CPU Pipeline — cache misses pipeline stalls kaise cause karte hain
DRAM Architecture — kya hota hai jab sabhi caches miss ho jaate hain

Flashcards

Modern CPU hierarchy mein cache ke teen levels kya hain? :: L1 (sabse chhota, sabse fast, per-core), L2 (medium, per-core), L3 (sabse bada, sabse slow, cores ke beech shared).

2-level cache ke liye Average Memory Access Time (AMAT) formula kya hai?

AMAT = T_{L1} + m_{L1} \cdot (T_{L2} + m_{L2} \cdot T_{mem})

L1 cache ko I-cache aur D-cache mein kyun split kiya jaata hai?

Taaki same cycle mein ek saath instruction fetch aur data access ho sake, structural hazards se bachne ke liye.

L3 cache per-core ki jagah sabhi cores mein shared kyun hai?

Efficient inter-core data sharing enable karne ke liye (ek core likhta hai, doosra padhta hai) bina private caches ke beech mehenga coherence traffic ke.

Local aur global miss rate mein kya fark hai?

Local miss rate level

i

par misses divided by level

i

par accesses hai. Global miss rate level

i

par misses divided by total CPU memory accesses hai.

Agar L1 ki 5% miss rate hai aur L2 ki 20% local miss rate hai, toh L2 ki global miss rate kya hai?

0.05 \times 0.2 = 0.01 = 1%

L1 se L3 tak associativity kyun badhti hai?

Higher associativity conflict misses reduce karta hai lekin area/power ki cost leta hai. L3 afford kar sakta hai (pehle se slow/large) jabki L1 nahi kar sakta (tiny/fast rehna zaroori hai).

Inclusive cache hierarchy kya hoti hai?

Outer caches (L3) inner caches (L1/L2) ke saare data ki copies rakhte hain. Coherence simple hoti hai lekin data duplicate hota hai.

T_{L1} = 4

cycles,

m_{L1} = 0.05

T_{mem} = 100

cycles diye hain (no L2), AMAT kya hai?

4 + 0.05 \cdot 100 = 9

cycles

L1 ko 1 MB kyun nahi banate agar hit rate improve ho?

Bada L1 lambe wire delays aur access time (20+ cycles) le sakta hai, fast L1 ka purpose hi khatam ho jaata. Hit rate akela metric nahi hai; AMAT important hai.