Worked examples — Cache miss types (compulsory, capacity, conflict)

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

Ye page 3 C's ka drill floor hai. Parent note ne definitions build ki hain; yahan hum har tarah ki situation dhundte hain jo miss-classification problem throw kar sakti hai, aur har ek ko poori tarah solve karte hain.

Koi bhi example touch karne se pehle, hum us ek machine par agree karte hain jo hum apne dimaag mein chalate hain, kyunki miss classify karne ka matlab hai idealized caches simulate karna.

Upar ke do idealized caches blocks evict karte hain, aur kaun sa block evict hota hai ye counts ko change karta hai. Isliye kisi bhi example se pehle hum eviction rule pin down karte hain.

Ek quick reminder us ek arithmetic rule ka jo conflicts hone deta hai, kyunki neeche ke har direct-mapped example mein iska use hota hai. Pehle hum un do quantities ko naam dete hain jinki use hoti hai, aur un do arithmetic operators ko jo inpar depend karte hain.

---

The scenario matrix

Har miss-classification problem jo tumhare saamne aayegi woh in cells mein se ek hai (ya blend hai). Baad ke har example ko us cell ke saath tag kiya gaya hai jise woh cover karta hai.

Cell	Kya khaas hai	Covered by
A. Pure compulsory	Har access ek brand-new block hai; cache size irrelevant	Ex 1
B. Pure conflict	Sirf 2–3 blocks use hote hain, lekin mapping ek fight force karti hai	Ex 2
C. Pure capacity	Working set > cache, mapping ko blame nahi (fully-assoc)	Ex 3
D. The trap: "looks conflict, is capacity"	Non-cold miss jo ek fully-assoc bhi miss karta	Ex 4
E. Associativity turns conflict → hit	Same trace, ways badhao, conflicts gayab hote dekho	Ex 5
F. Degenerate input	Empty trace / single block / warm-up ke baad all-hits	Ex 6
G. Block-size / spatial-locality effect	Bada block compulsory aur capacity counts dono badalta hai	Ex 7
H. Real-world word problem	Row-major vs column-major array walk (2D loop)	Ex 8
I. Exam twist: full 3-way decomposition	Ek trace, subtraction se teeno C's report karo	Ex 9

---

Example 1 — Cell A: pure compulsory

Steps.

1. Har index compute karo $=B\mathrm{mod}4$: $0\to 0,1\to 1,2\to 2,3\to 3$. Ye step kyun? Hume jaanna hai ki koi do blocks ek home share karte hain ya nahi. Charo indices alag hain ⇒ koi collision nahi.
2. Trace chalao. Har block ko pehli baar touch kiya ja raha hai, isliye har ek miss hai ek khali home slot ke saath. Ye step kyun? Pehli kabhi na dekhi reference compulsory hai by definition — koi bhi cache, chahe kitni bhi clever ho, us data ko hold nahi karti jo usne kabhi dekha hi nahi.

Access	Index	Home pehle	Result
0	0	empty	Compulsory
1	1	empty	Compulsory
2	2	empty	Compulsory
3	3	empty	Compulsory

Answer: 4 compulsory, 0 capacity, 0 conflict.

---

Example 2 — Cell B: pure conflict

Steps.

1. Indices: $0\mathrm{mod}4=0$ aur $8\mathrm{mod}4=0$. Dono blocks set 0 chahte hain. Ye step kyun? Yahi conflict ka mechanical origin hai — same remainder ⇒ same single home.
2. Real cache simulate karo — kyunki set 0 mein sirf ek line hai, har newcomer doosre ko evict karta hai.

Access	Result	Reason
0	Compulsory	pehli touch
8	Compulsory	pehli touch, 0 ko evict karta hai
0	Conflict	pehle dekha gaya ⇒ cold nahi
8	Conflict	thrash
0	Conflict	thrash
8	Conflict	thrash

3. Prove karo ki ye conflict hai (capacity nahi): same trace par fully-associative 4-line cache chalao. Woh $\{0,8\}$ aaram se hold karta hai (2 blocks $\le$ 4 slots), isliye har repeat ek hit hai — 0 non-compulsory misses. Ye step kyun? Conflict $=M_{\text{real}}-M_{\text{full}}$. Yahan $M_{\text{real}}=6$, $M_{\text{full}}=2$, isliye conflict $=4$. ✅

Answer: 2 compulsory, 0 capacity, 4 conflict.

---

Example 3 — Cell C: pure capacity

Steps.

1. Cache ko LRU list [LRU … MRU] ki tarah track karo (rule page ke top par define hai). Ye step kyun? Koi index restriction nahi hone par, evict karne ki wajah sirf "jagah nahi" hai, aur LRU decide karta hai kaun jaata hai — leftmost (least-recently-used) block.

Access	Cache after	Result	Reason
0	[0]	Compulsory	pehli touch
1	[0,1]	Compulsory	pehli touch
2	[1,2]	Compulsory	pehli touch, 0 ko evict karta hai (LRU)
0	[2,0]	Capacity	0 pehle dekha gaya, lekin 3-block working set ke liye sirf 2 slots
1	[0,1]	Capacity	2 ko evict karta hai
2	[1,2]	Capacity	0 ko evict karta hai

2. Conflict kyun nahi? Ek fully-associative cache mein koi mapping nahi hoti, isliye $M_{\text{real}}=M_{\text{full}}$ hamesha ⇒ conflict $=0$ by definition. Ye step kyun? Ye rule nail karta hai: fully-associative caches mein conflict misses nahi ho sakte.

Answer: 3 compulsory, 3 capacity, 0 conflict.

---

Example 4 — Cell D: the trap ("looks conflict, is capacity")

Steps.

1. Indices: $0\to 0,1\to 1,2\to 0,3\to 1$. Toh set 0 par $\{0,2\}$ ka fight hai aur set 1 par $\{1,3\}$ ka. Ye step kyun? Simulate karne se pehle identify karo ki kaun sa home share karta hai.
2. Real direct-mapped cache simulate karo (har set mein exactly ek line hai):

Access	Index	State (set0 / set1) pehle	Result
0	0	– / –	Compulsory (set0 mein 0 fill karo)
1	1	0 / –	Compulsory (set1 mein 1 fill karo)
2	0	0 / 1	Compulsory (0 ko evict karta hai)
0	0	2 / 1	miss — type? (2 ko evict karta hai)
3	1	0 / 1	Compulsory (1 ko evict karta hai)
0	0	0 / 3	Hit

Ye step kyun? Real misses gino: accesses #1,#2,#3,#4,#5 sab miss karte hain ⇒ $M_{\text{real}}=5$; access #6 hit karta hai. Access #4 mystery wala hai.

3. Access #4 ko type karne ke liye, poore trace 0,1,2,0,3,0 par fully-associative 2-line LRU simulate karo, har step dikhao taaki $M_{\text{full}}$ black box na rahe:

Access	Cache after [LRU … MRU]	Result	Reason
#1 0	[0]	miss	pehli touch
#2 1	[0,1]	miss	pehli touch
#3 2	[1,2]	miss	full, 0 ko evict karo (LRU)
#4 0	[2,0]	miss	0 ko #3 par evict kiya gaya tha ⇒ resident nahi
#5 3	[0,3]	miss	full, 2 ko evict karo (LRU)
#6 0	[3,0]	hit	0 abhi bhi resident hai (#4 par touch kiya tha)

Ye step kyun? Fully-assoc cache bhi access #4 par miss karta hai, aur iska total $M_{\text{full}}=5$ hai (#1–#5 par miss, #6 par hit). Rule "conflict sirf tab agar same-size fully-assoc hit karta" se, access #4 conflict nahi ho sakta — ye capacity hai.

4. Chhai access classify karo:

Access	Real result	Type
#1 0	miss	Compulsory
#2 1	miss	Compulsory
#3 2	miss	Compulsory
#4 0	miss	Capacity (fully-assoc ne bhi miss kiya)
#5 3	miss	Compulsory
#6 0	hit	—

Answer: 4 compulsory, 1 capacity, 0 conflict, 1 hit (total 5 real misses).

---

Example 5 — Cell E: associativity conflict ko hits mein badal deta hai

Steps.

1. Indices: $0\mathrm{mod}2=0$, $8\mathrm{mod}2=0$. Dono set 0 mein jaate hain, lekin set 0 mein ab 2 ways (2 lines) hain. Ye step kyun? Conflict tab hota hai jab set overflow hota hai. Ek 2-way set dono rivals ko hold kar sakta hai.
2. Simulate karo (har set apni choti LRU list hai):

Access	Set 0 ways [LRU … MRU]	Result
0	[0]	Compulsory
8	[0,8]	Compulsory
0	[8,0]	Hit
8	[0,8]	Hit
0	[8,0]	Hit
8	[0,8]	Hit

Answer: 2 compulsory, 0 capacity, 0 conflict, 4 hits. Example 2 ke 4 conflict misses zyada associativity ke saath gayab ho gaye aur same total size ke saath.

---

Example 6 — Cell F: degenerate inputs

Steps.

1. (a) Empty trace. Koi access nahi ⇒ $0$ misses har type ke. Kyun: miss counts trace par hain; ek empty trace mein miss karne ko kuch nahi.
2. (b) 7,7,7,7. Pehla 7 compulsory hai; woh resident rehta hai (koi usse evict nahi karta), isliye baaki hit karte hain. Kyun: temporal locality extreme mein — same block, kabhi displaced nahi. ⇒ 1 compulsory, 3 hits.
3. (c) 1,2,1,2, indices $1\mathrm{mod}4=1$, $2\mathrm{mod}4=2$ (alag homes). Kyun: alag homes ⇒ koi collision nahi; dono pehli touch ke baad resident hain. ⇒ 2 compulsory, 2 hits, 0 conflict, 0 capacity.

Answer: (a) sab zero; (b) 1 compulsory; (c) 2 compulsory. Koi capacity/conflict nahi kahin bhi.

---

Example 7 — Cell G: block size counts badal deta hai

Steps.

1. Block number $=\lfloor \text{address}/\text{block size}\rfloor$ (floor = round down, page ke top par define kiya gaya). Ye step kyun: block number hi map hota hai aur "already fetched" block numbers mein measure hota hai.
2. 4 B blocks: addresses 0,4,8,12 → block numbers $\lfloor 0/4\rfloor ,\lfloor 4/4\rfloor ,\lfloor 8/4\rfloor ,\lfloor 12/4\rfloor =0,1,2,3$ — chaar distinct blocks ⇒ 4 compulsory. Ye step kyun: har address apna block hai, koi fetch share nahi karta.
3. 16 B blocks: $\lfloor 0/16\rfloor =\lfloor 4/16\rfloor =\lfloor 8/16\rfloor =\lfloor 12/16\rfloor =0$ — sab block 0 mein ⇒ sirf pehla access miss karta hai ⇒ 1 compulsory, 3 hits. Ye step kyun: ek fetch bytes 0–15 pull karta hai, isliye 4,8,12 "free mein" aa jaate hain — spatial locality bade block se capture hoti hai.

Answer: 4 B block → 4 compulsory; 16 B block → 1 compulsory.

---

Example 8 — Cell H: real-world word problem (2D array walk)

Steps.

1. Har row ek 16 B block hai ⇒ block number = row number $\in \{0,1,2,3\}$. Index $=\text{row}\mathrm{mod}2$: rows 0,2 → set 0; rows 1,3 → set 1. Ye step kyun: data structure ko blocks par map karo count karne se pehle.
2. Row-major row 0 ke sare 4 elements padhta hai (ek block: 1 miss + 3 hits), phir row 1, etc. Ye step kyun: consecutive elements ek block share karte hain ⇒ spatial locality capture hoti hai. Block visit order: 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3. Har naya block ek baar touch hota hai phir turant reuse hota hai jab bhi resident hai ⇒ 4 misses (sab compulsory), 12 hits.
3. Column-major (0,0),(1,0),(2,0),(3,0) padhta hai — rows 0,1,2,3 → blocks 0,1,2,3 — phir column 1 rows 0,1,2,3 revisit karta hai, aur aage bhi. Ye step kyun: kharab locality — ek block fetch hota hai, reuse se pehle evict ho jaata hai, aur refetch hota hai. Block visit order: 0,1,2,3, 0,1,2,3, 0,1,2,3, 0,1,2,3.
4. Direct-mapped 2-set cache par column-major count karo. Set 0 blocks 0 aur 2 ke beech alternate karta hai; set 1 blocks 1 aur 3 ke beech. Set 0 ke visits simulate karo (0,2,0,2,0,2,0,2): pehla 0 aur pehla 2 compulsory hain, har baad ki visit mein doosra block resident milta hai ⇒ miss. Set 1 ke liye bhi same (1,3,1,3,…). Ye step kyun: set per sirf ek line hone aur do blocks ke uss par fight karne se, do first-touches ke baad har access thrashes karta hai. Result: sare 16 accesses miss karte hain — do first-touches per set (total 4) compulsory hain, baaki 12 conflict hain.

Answer: Row-major = 4 misses (4 compulsory, 0 conflict). Column-major = 16 misses (4 compulsory + 12 conflict). Same data, sirf galat walk order se 4× zyada misses.

---

Example 9 — Cell I: full 3-way decomposition by subtraction

Steps.

1. Indices: $0,2,4\mathrm{mod}2=0,0,0$ — teeno set 0 share karte hain (ek line). Ye step kyun: set up karo kaun collide karta hai.
2. $M_{\text{real}}$ (direct-mapped, set 0 mein 1 block): 0 miss, 2 miss(0 evict), 4 miss(2 evict), 0 miss, 2 miss, 4 miss ⇒ 6 misses. Ye step kyun: real machine ka total.
3. $M_{\text{full}}$ (fully-assoc, 2 lines, LRU) same trace par, har step dikhaya:

Access	Cache after [LRU … MRU]	Result
0	[0]	miss
2	[0,2]	miss
4	[2,4]	miss, 0 evict (LRU)
0	[4,0]	miss, 2 evict
2	[0,2]	miss, 4 evict
4	[2,4]	miss, 0 evict

⇒ 6 misses. Ye step kyun: finite-but-unrestricted machine. Working set = 3 > 2 slots, isliye ye bhi thrash karta hai. 4. $M_{\infty }$ = distinct blocks = $|\{0,2,4\}|=3$. Ye step kyun: compulsory count. 5. Decompose karo: $M_{\text{compulsory}}=3,M_{\text{capacity}}=M_{\text{full}}-M_{\infty }=6-3=3,M_{\text{conflict}}=M_{\text{real}}-M_{\text{full}}=6-6=0.$ Ye step kyun: har subtraction exactly ek cause strip out karta hai.

Answer: 3 compulsory, 3 capacity, 0 conflict (total 6). Blocks ek set share karte hain, lekin ek fully-associative cache bhi 2 lines mein teeno nahi rakh sakti — isliye blame capacity ka hai, conflict ka nahi, shared index ke bawajood. Yahan associativity badhana help nahi karega; sirf badi cache help karegi.

---

The decision flow (yahi yaad karo, tables nahi)

Recall Ek-line self-test (answers cover karo)

Same-index blocks hamesha conflict misses cause karte hain? ::: Nahi — agar working set cache se bada ho toh ye capacity misses hain (Ex 9). Column-major vs row-major matrix walk — kaun zyada miss karta hai? ::: Column-major, kyunki ye spatial locality defeat karta hai (Ex 8). Fully-associative cache mein kitne conflict misses hote hain? ::: Zero, by definition (Ex 3). Bigger block hamesha total misses ghataata hai? ::: Nahi — compulsory ghataata hai lekin capacity/conflict badha sakta hai (Ex 7). Ye kaise prove karte hain ki miss conflict hai capacity nahi? ::: Same-size fully-associative cache simulate karo; conflict sirf tab jab woh hit karta (Ex 4).

Ye examples seedha Average Memory Access Time (AMAT) mein plug hote hain: har miss count ko uske penalty se multiply karo dekhne ke liye ki kaun sa C tumhare runtime par dominant hai.