Visual walkthrough — Cache miss types (compulsory, capacity, conflict)

5.4.9 · D2 · Hardware › Memory Hierarchy & Caches › Cache miss types (compulsory, capacity, conflict)

Parent: Cache miss types. Hum Cache Associativity & Set Mapping, LRU and Replacement Policies, aur Spatial and Temporal Locality ka sahara lenge jaate jaate, aur end mein Average Memory Access Time (AMAT) ki taraf point karenge.

---

Step 1 — Cache actually kya hota hai (numbered boxes ki ek row)

KYA. Cache ek chhota sa storage boxes ka set hai. Har box mein ek block hota hai — memory ka ek fixed-size chunk (maano 64 bytes) jo hamesha ek unit ki tarah move karta hai. Hum har block ko ek plain integer se label karenge, uska block number $B$ (0, 1, 2, …). $B$ ko socho "memory ka kaunsa 64-byte chunk hai yeh."

KYUN. Isse pehle ki hum miss ki baat karein, humein us cheez ki ek picture chahiye jo full ya empty ho sakti hai. Cache sirf boxes hai; hit ka matlab hai "jo block aapne maanga woh pehle se kisi box mein baithe hai"; miss ka matlab hai "woh nahi hai — jaake slow memory se fetch karo."

PICTURE. Neeche: memory numbered chunks ki ek lambi strip hai left mein. Cache char boxes hai right mein. Ek arrow dikha raha hai ek block copy in ho raha hai.

---

Step 2 — Mapping rule: ek block kahan baithne ki permission hai?

KYA. Cache ek block ko kisi bhi box mein jaane nahi deta. Ek direct-mapped cache har block ko exactly ek legal box deta hai, ek rule se choose kiya hua. Agar $S$ boxes hain (jinhe sets kehte hain), toh block $B$ ka legal box hai:

$\underset{\text{kaunsa box}}{\underbrace{\text{index}}}=\underset{\text{block number}}{\underbrace{B}}\mathrm{mod}\underset{\text{sets ki sankhya}}{\underbrace{S}}$

Yahan $\mathrm{mod}$ ka matlab hai "divide karne ke baad remainder." Term by term: block number $B$ lo, boxes ki sankhya $S$ se divide karo, aur jo bachta hai woh aapka box batata hai.

KYUN yeh operation aur koi nahi? Humein ek aisa rule chahiye jo (a) hardware mein instant compute ho aur (b) blocks ko saare boxes mein spread kare. Remainder-after-division dono karta hai: consecutive blocks $0,1,2,3$ boxes $0,1,2,3$ mein jaate hain, phir yeh wrap around karta hai — block $4$ wapas box $0$ mein jaata hai. Yeh wrap-around har conflict miss ka beej hai, toh iss par nazar rakho.

PICTURE. Blocks $0,1,2,3,4,5$ mein se har ek ko uske forced box ki taraf arrow dikhaaya gaya hai. Notice karo ki $0$ aur $4$ ek hi box ki taraf point karte hain (dono remainder $0$ dete hain).

---

Step 3 — Teen imaginary caches (humare measuring instruments)

KYA. Yeh poochhne ke liye ki "kya ek better cache is miss se bach sakta tha?" hum teen reference caches banate hain aur usi request sequence ko har ek mein se chalate hain:

1. Infinite cache — unlimited boxes, kabhi kuch evict nahi karta.
2. Fully-associative, finite — exactly $C$ boxes lekin koi mapping rule nahi; ek block kahin bhi baith sakta hai, aur hum LRU use karte hain evict karne ke liye (sabse kam recently-used block ko bahar karo).
3. Real cache — $C$ boxes aur ek mapping rule (e.g. direct-mapped).

KYUN. Har imaginary cache misses ka ek cause switch off karta hai:

• Infinite cache "room khatam ho gaya" aur "mapping clash" ko remove karta hai — sirf truly-first-touch misses bachti hain.
• Fully-associative finite cache sirf "mapping clash" remove karta hai — first-touch aur room-khatam-ho-gaya dono bachte hain.
• Real cache teeno ko hone deta hai.

Toh har cache ek filter hai, aur do filters ka farak exactly ek cause ko isolate karta hai. Yeh subtraction trick hi 3 C's ka poora engine hai.

PICTURE. Teen cache diagrams side by side, har ek par likha hai ki woh abhi bhi kaun se miss causes allow karta hai (green = survive karne ki permission, faded = filtered out).

---

Step 4 — Teen causes ko unke answers se naam dena

KYA. Ek real miss ke liye, yes/no questions ki ek chain chalao:

1. Is block ko pehli baar kabhi reference kiya gaya? → Compulsory (a.k.a. cold miss). Yeh infinite cache mein bhi miss hota.
2. Pehli baar nahi, lekin kya fully-associative finite cache bhi miss karta? → Capacity. Block sirf isliye evict hua kyunki $C$ boxes aapke poore working set ko hold nahi kar sake.
3. Fully-associative hit karta, real cache missed? → Conflict. Sirf mapping rule ne eviction cause ki.

KYUN chain safe hai. Questions order mein pooche jaate hain aur mutually exclusive hain: ek miss compulsory hai, nahi toh capacity, nahi toh conflict — koi miss bachta nahi, koi do baar count nahi hota.

PICTURE. Ek decision tree: ek miss upar se enter karta hai, teen questions se flow karta hai, type ke hisaab se coloured hokar exit karta hai.

---

Step 5 — Ek pure conflict ko bante dekho (thrash)

KYA. Direct-mapped, $S=4$ boxes. Block stream request karo 0, 4, 0, 4, 0, 4. Kyunki $0\mathrm{mod}4=0$ aur $4\mathrm{mod}4=0$, blocks $0$ aur $4$ dono box 0 maangते hain aur ek doosre ko hamesha ke liye evict karte rehte hain.

KYUN yeh conflict hai capacity nahi. Sirf do distinct blocks kabhi bhi use hote hain. $C=4$ boxes wala fully-associative cache ke paas bahut room hai — woh dono ko rakhega aur pehle do ke baad har baar hit karega. Real cache sirf mapping clash ki wajah se miss karta hai. Subtract karo: $M_{\text{full}}=2$, $M_{\text{real}}=6$, toh $M_{\text{conflict}}=6-2=4$.

PICTURE. Box 0 $0$ aur $4$ ke beech flip-flopping kar raha hai; ek red "thrash" arrow waapis peeche jaate hue jab ki boxes 1–3 khaali baithे hain (woh wasted room jo prove karta hai ki yeh capacity nahi hai).

Access	Result	Kyun
0	Compulsory	0 ka pehla touch
4	Compulsory	4 ka pehla touch (0 ko evict karta hai)
0	Conflict	pehle dekha; fully-assoc mein fit hota → clash
4	Conflict	thrash
0	Conflict	thrash
4	Conflict	thrash

Cure: sirf 2-way associativity dono ko set 0 mein rehne deti hai → saare conflicts khatam, koi bada cache nahi chahiye.

---

Step 6 — Ek pure capacity ko bante dekho (room nahi, clash nahi)

KYA. Fully-associative, $C=2$ boxes, LRU. Stream 0, 1, 2, 0, 1, 2. Teen distinct blocks, sirf do boxes.

KYUN yeh capacity hai conflict nahi. Yahan koi mapping rule nahi hai — ek block kahin bhi baith sakta hai — toh "clash" construction se impossible hai. Phir bhi cache {1,2} se fill hone ke baad, 0 request karne par miss hota hai kyunki use room banane ke liye bahar dhakela gaya tha. Working set (3 blocks) cache se bada hai (2 boxes).

PICTURE. Ek 2-box LRU cache ek revolving door ke saath: har naya block sabse purane ko bahar dhakelta hai; jis block ki zaroorat hai woh hamesha wohi hota hai jo abhi abhi nikla.

Access	Cache (LRU→MRU)	Result
0	[0]	Compulsory
1	[0,1]	Compulsory
2	[1,2]	Compulsory (0 ko evict karta hai)
0	[2,0]	Capacity
1	[0,1]	Capacity
2	[1,2]	Capacity

Cure: bada cache ($\ge 3$ boxes) ya chhota working set. Associativity yahan kuch nahi karti.

---

Step 7 — Trap: ek re-touch jo conflict lagta hai lekin capacity hai

KYA. Direct-mapped, $S=2$, index $=B\mathrm{mod}2$. Stream 0, 1, 2, 0, 3, 0. Access #4 (doosra 0) par dhyan do. Yeh pehla touch nahi hai, aur real cache miss karta hai — "conflict" stamp karne ka mann karta hai.

KYUN simulate karna padega, sirf dekhne se kaam nahi chalega. Usi stream ko fully-associative $C=2$ LRU cache par chalao: 0→[0], 1→[0,1], 2→[1,2] (0 evict hua), phir 0 → woh bhi miss kyunki 0 pehle se ja chuka tha. Kyunki fully-associative cache bhi miss karta hai, access #4 capacity hai, conflict nahi. Teen distinct blocks {0,1,2} live the lekin sirf do boxes the — yeh room ki problem hai, clash ki tarah disguise hokar aayi.

PICTURE. Do lanes identical stream chala rahi hain: upar = direct-mapped, neeche = fully-associative. Dono access #4 par red light up karte hain → verdict: capacity.

---

Step 8 — Degenerate aur limiting cases (taaki kuch surprise na kare)

KYA / KYUN / PICTURE, char corner cases lined up:

• Khaali stream / single access. Har block ek baar dikhta hai → saari misses compulsory hain; capacity aur conflict exactly zero hain. Yeh floor hai: ek perfect infinite cache bhi inhe pay karta hai.
• Working set poori tarah fit hoti hai ($\text{distinct blocks}\le C$) fully-associative cache mein. Tab $M_{\text{full}}=M_{\text{infinite}}$, toh capacity $=0$; sirf compulsory (plus real cache mein conflict bhi shayad) bachti hai.
• Fully-associative real cache. Koi mapping rule nahi ⇒ $M_{\text{real}}=M_{\text{full}}$ ⇒ conflict $\equiv 0$ by definition. Ek fully-associative cache mein conflict misses ho hi nahi sakti.
• Infinite real cache. Kabhi evict nahi karta ⇒ $M_{\text{real}}=M_{\text{infinite}}$ ⇒ capacity aur conflict dono zero hain; sirf compulsory bachti hain.

Recall Corner-case quick check (answers chhupao)

Fully-associative cache — kabhi kitne conflict misses hote hain? ::: Zero, hamesha. Infinite cache — kaun se types bachte hain? ::: Sirf Compulsory. Fully-assoc mein Distinct blocks $\le C$ — capacity count? ::: Zero. Ek stream jahan har block unique hai — split kya hoga? ::: 100% compulsory.

---

Ek-picture summary

Sab kuch ek canvas par. Ek request stream teen imaginary caches mein se flow karti hai; har cache ek cause filter out karta hai; baaki misses teen coloured buckets mein jaati hain — orange compulsory, blue capacity, red conflict — unke beech pipes par subtraction identities likhi hain.

Recall Feynman retelling (seedhe words mein)

Teen copies ki ek dukaan imagine karo. Pehli dukaan mein storeroom infinite hai — aap sirf tab kuch nahi bech sakte jab koi customer pehli baar ek bilkul naye item ke liye poochhe jo aapne kabhi stock nahi kiya. Woh hain compulsory misses. Doosri dukaan mein storeroom chhota hai lekin aap koi bhi item kisi bhi shelf par rakh sakte ho — ab aap tab bhi fail karte ho jab storeroom itna bada nahi hota ki customers jo maangte rehte hain woh sab rakha ja sake. Woh extra failures hain capacity misses. Teesri, real dukaan mein storeroom utna hi chhota hai lekin har item ki ek assigned shelf hai — ab do popular items ek hi shelf par force hoke ek doosre ko giraaते rehte hain chahe doosri shelves khaali baithein. Woh aur extra failures hain conflict misses. Usi din ke customers ko teeno dukaanon mein chalao, failures count karo, aur subtract karo: dukaan 1 se dukaan 2 ka jump aapki capacity problem hai, dukaan 2 se dukaan 3 ka jump aapki shelving (mapping) problem hai, aur jo dukaan 1 ke paas pehle se tha woh unavoidable coldness hai. Har ek ko uske apne tool se fix karo — bada storeroom, ya azaad shelving, ya customers ke poochhne se pehle nayi stock order karna.