Cache miss types (compulsory, capacity, conflict): Exercises

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

Yeh page ek self-testing ladder hai. Har problem ek cache ki mini-simulation hai. Kisi bhi solution ko dekhne se pehle, access trace ko haath se run karo jaisa parent note ne sikhaya hai: har access ke liye question-chain poochho — pehli baar touch? bahut chhota? mapping fight?

Is poori page mein jo vocabulary use hoti hai (koi bhi symbol aane se pehle define ki gayi)

Neeche sab kuch char numbers ke saath bookkeeping hai. Inhe abhi, saral shabdon mein define karo, kisi bhi formula mein daalne se pehle:

Definition Char miss-counts (yeh char naam yaad karo)

Ek fixed access trace ke liye, hum ise alag-alag caches par simulate karte hain aur misses count karte hain:

$M_{real}$ = actual cache mein misses jo hum actually build karte hain (limited associativity, e.g. direct-mapped). Yahi woh number hai jo takleef deti hai.
$M_{fa}$ = same size ke fully-associative cache mein misses, LRU use karke. "Fully-associative" ka matlab hai ki ek block kisi bhi slot mein baith sakta hai — koi mapping rule nahi hai, isliye yeh cache kabhi bhi conflict suffer nahi kar sakta.
$M_{inf}$ = infinite cache mein misses (kuch bhi kabhi evict nahi hota). Yahaan sirf ek block ka pehla ever touch miss reh jaata hai.
Ek distinct block = trace mein jo block number appear hota hai, ek baar count kiya jaata hai chahe kitni bhi baar recur kare.

Subscripts ko words mein padho: real, fa = fully-associative, inf = infinite. Hum page ke baaki hisse mein sirf yahi teen symbols use karenge — koi aur spelling nahi.

Intuition Teen caches kyun, aur subtraction se har C kyun milta hai (WHY, drawn)

Har idealized cache ek cause ko switch off karta hai miss ka:

Infinite cache: bilkul eviction nahi ⇒ jo misses bachti hain, $M_{inf}$ , woh purely compulsory hain (cold, first-touch).
Fully-associative finite cache: eviction ho sakti hai (yeh finite hai) lekin kabhi mapping ki wajah se nahi (koi mapping nahi hai) ⇒ $M_{inf}$ se pare iske extra misses purely capacity hain (room khatam ho gaya).
Real cache: mapping rule wapas add karta hai ⇒ $M_{fa}$ se pare iske extra misses purely conflict hain (do blocks ek hi home slot ke liye fight karne par majboor).

Kyunki har cache ek cause hata deta hai, differences causes ko alag karte hain layers ki tarah: $M_{compulsory} = M_{inf} = (number of distinct blocks)$ $M_{capacity} = M_{fa} - M_{inf}$ $M_{conflict} = M_{real} - M_{fa}$ Neeche figure dekho: total real bar teen stacked layers mein slice hua hai, aur har subtraction literally ek layer ki height hai. Yahi is page ki poori method hai.

Figure — Cache miss types (compulsory, capacity, conflict)

Poore mein, blocks 1 word hain simplicity ke liye, isliye "block number" = trace mein jo number hai. Direct-mapped index of block $B$ hai $index = B mod S$ , jahan $S$ = number of sets. (Yahi mapping rule hai: $B mod S$ ki same value ka matlab hai ki do alag blocks ek hi home slot par bheje jaate hain aur ek doosre ko evict karna padta hai.)

Level 1 — Recognition

Problem 1.1 (L1)

Ek program yeh distinct blocks pehli baar touch karta hai, har ek exactly ek baar: 7, 3, 99, 3. Cache infinitely large hai. Kitne misses hain, aur kis type ke?

Recall Solution 1.1

Ek infinite cache kabhi room khatam nahi karta aur koi mapping rule nahi hai, isliye sirf possible miss compulsory hai (first-ever touch), yaani $M_{real} = M_{inf}$ yahaan.

7 → pehla touch → compulsory.
3 → pehla touch → compulsory.
99 → pehla touch → compulsory.
3 → pehle dekha ja chuka hai → hit (yeh kabhi evict nahi hua; cache infinite hai).

Answer: 3 compulsory misses, 0 capacity, 0 conflict. Compulsory misses ki number = distinct blocks ki number = $∣ {7, 3, 99} ∣ = 3$ .

Problem 1.2 (L1)

Cure ko cause se match karo: (a) higher associativity, (b) larger cache, (c) prefetching. Har ek kis miss type ko fix karta hai?

Recall Solution 1.2

(a) higher associativity → conflict fix karta hai (ek set mein zyada slots ka matlab hai blocks ek hi home ke liye fight karna band kar dete hain). Dekho Cache Associativity & Set Mapping.
(b) larger cache → capacity fix karta hai (zyada room ek bade working set ko hold karta hai). Dekho Working Set & Program Behavior.
(c) prefetching → compulsory fix karta hai (block ko uske pehle use se pehle fetch karo taaki cold miss hide ho jaaye). Dekho Prefetching.

Answer: a↔conflict, b↔capacity, c↔compulsory.

Level 2 — Application

Problem 2.1 (L2)

Direct-mapped, 4 lines ( $S = 4$ ). Trace: 0, 8, 0, 8. Har access classify karo.

Recall Solution 2.1

Index $= B mod 4$ : block 0 → $0 mod 4 = 0$ ; block 8 → $8 mod 4 = 0$ . Dono sirf set 0 mein rehte hain — ek mapping collision.

#	Block	State before	Result	Why
1	0	empty	Compulsory	0 ka pehla touch
2	8	{0}	Compulsory	8 ka pehla touch, 0 ko evict karta hai
3	0	{8}	Conflict	0 pehle dekha gaya (cold nahi); sirf 2 blocks use hue ⇒ ek fully-assoc 4-line cache dono hold karta ⇒ $M_{fa}$ yahaan hit karta hai ⇒ miss purely mapping ki wajah se hai
4	8	{0}	Conflict	same reasoning

Answer: 2 compulsory + 2 conflict + 0 capacity. Hardware mein fix: sirf 2-way associativity se 0 aur 8 set 0 mein saath reh sakte hain → accesses 3 aur 4 hits ban jaate hain.

Problem 2.2 (L2)

Fully-associative, 2 lines, LRU. Trace: 0, 1, 2, 0. Har access classify karo.

Recall Solution 2.2

Fully-associative ⇒ koi mapping rule nahi ⇒ conflict misses kabhi possible nahi (yeh cache hai hi $M_{fa}$ reference). Sirf compulsory aur capacity bachti hain. LRU least-recently-used block evict karta hai.

#	Block	Cache (LRU→MRU)	Result	Why
1	0	[0]	Compulsory	pehla touch
2	1	[0,1]	Compulsory	pehla touch
3	2	[1,2]	Compulsory	pehla touch; 0 ko evict karta hai (LRU)
4	0	[2,0]	Capacity	0 dekha gaya tha lekin evict sirf isliye hua kyunki 3 distinct blocks 2 slots mein fit nahi hote

Answer: 3 compulsory + 1 capacity + 0 conflict. Dekho LRU and Replacement Policies.

Level 3 — Analysis

Problem 3.1 (L3)

Direct-mapped, 2 lines ( $S = 2$ , index $= B mod 2$ ). Trace: 0, 1, 2, 0, 3, 0. Har access classify karo. Yeh parent ka Example 3 hai — subtle wala.

Recall Solution 3.1

Do sets mein se har ek ek block hold karta hai. Main ek honest walk-through table dikhata hoon jisme har step ke liye WHY hai, dono sets ko ek saath track karte hue. 0 ka index=0, 1 ka=1, 2 ka=0, 3 ka=1 (isliye 0 aur 2 set 0 share karte hain; 1 aur 3 set 1 share karte hain).

#	Block	idx	set0 before / set1 before	Result (real)	WHY this result
1	0	0	{} / {}	Compulsory	0 ka pehla ever touch; set 0 mein rakho
2	1	1	{0} / {}	Compulsory	1 ka pehla ever touch; set 1 mein rakho
3	2	0	{0} / {1}	Compulsory	2 ka pehla ever touch; set 0 mein pehle se 0 hai ⇒ 0 evict karo, 2 install karo
4	0	0	{2} / {1}	miss	0 dekha gaya tha (cold nahi), lekin set 0 ab 2 hold kar raha hai ⇒ miss; conflict hai ya capacity? Step B mein decide ⇒ capacity
5	3	1	{0} / {1}	Compulsory	3 ka pehla ever touch; set 1 mein 1 hai ⇒ 1 evict karo, 3 install karo
6	0	0	{0} / {3}	Hit	access #4 ne 0 ko set 0 mein wapas install kiya tha, aur tab se kuch bhi set 0 touch nahi kiya ⇒ 0 abhi bhi wahan hai

Ek hi table kyun (do nahi): sirf ek trap hai access #6 — yeh socha ja sakta hai ki 0 evict ho gaya, lekin step 4 dobara padho: wahan 0 ko wapas install kiya gaya set 0 mein, aur step 5 sirf set 1 touch karta hai, isliye 0 survive karta hai. Dono sets ko ek row mein track karna yeh visible banata hai, isliye kuch redo karne ki zarurat nahi.

Real misses = 5 (accesses 1,2,3,4,5), yaani $M_{real} = 5$ .

Step B — access #4 conflict hai ya capacity? Definitions se rule apply karo: 2-line fully-associative LRU ( $M_{fa}$ reference) ko same trace par #4 tak simulate karo, 0,1,2,0:

0→[0] (compulsory), 1→[0,1] (compulsory), 2→[1,2] (compulsory, 0 ko LRU ke roop mein evict karta hai), 0→miss (0 chala gaya).
Kyunki fully-associative cache bhi #4 par 0 par miss karta hai, mapping culprit nahi tha — size tha. Isliye access #4 ek capacity miss hai, conflict nahi.

Step C — teen formulas ke saath tally.

$M_{compulsory} = M_{inf} =$ distinct blocks first-touched $= {0, 1, 2, 3} = 4$ .
$M_{fa}$ full trace 0,1,2,0,3,0 par: 0c, 1c, 2c (0 evict), 0 capacity ([1,2] tha), 3c (1 evict → [0,3]), 0 hit (0 abhi wahan hai) ⇒ 5 misses, isliye $M_{fa} = 5$ .
$M_{capacity} = M_{fa} - M_{inf} = 5 - 4 = 1$ .
$M_{conflict} = M_{real} - M_{fa} = 5 - 5 = 0$ .
Check: $4 + 1 + 0 = 5 = M_{real}$ ✓.

Answer: 4 compulsory + 1 capacity + 0 conflict. Access #4 capacity miss hai.

Neeche ki timeline is trace ko step by step draw karti hai; step 4 par amber box follow karo — yeh capacity miss hai jo conflict jaisi lagti hai lekin hai nahi.

Problem 3.2 (L3)

Same trace 0, 1, 2, 0, 3, 0, lekin ab ek direct-mapped, 4-line cache ( $S = 4$ ). Teen C's recompute karo aur explain karo ki Problem 3.1 ke comparison mein kya badla.

Recall Solution 3.2

Index $= B mod 4$ : 0→0, 1→1, 2→2, 3→3. Har block ko apna khud ka set milta hai — koi do collide nahi karte.

#	Block	idx	Result	WHY
1	0	0	Compulsory	pehla touch, set 0 empty
2	1	1	Compulsory	pehla touch, set 1 empty
3	2	2	Compulsory	pehla touch, set 2 empty (0 ko disturb nahi karta)
4	0	0	Hit	0 abhi bhi set 0 mein hai; kuch bhi use evict nahi kiya
5	3	3	Compulsory	pehla touch, set 3 empty
6	0	0	Hit	0 kabhi disturb nahi hua

Real misses = 4, sab first-touches. Isliye $M_{real} = 4 = M_{inf}$ ⇒ $M_{compulsory} = 4$ , $M_{capacity} = M_{fa} - M_{inf} = 4 - 4 = 0$ , $M_{conflict} = M_{real} - M_{fa} = 4 - 4 = 0$ .

Kya badla: cache ko 2→4 lines se bada karne par woh eviction hati jo Problem 3.1 mein access #4 par capacity miss cause kar rahi thi. 1 capacity miss chali gayi. Bada cache capacity cure karta hai — Problem 1.2 ke rule se match karta hai.

Level 4 — Synthesis

Problem 4.1 (L4)

Ek single trace design karo jo direct-mapped, 2-line cache ( $S = 2$ ) mein teeno miss types produce kare, phir har access classify karo. (Ise build karo, sirf dhundho mat.)

Recall Solution 4.1

Design goals:

Compulsory chahiye → pehle touches include karo.
Conflict chahiye → do blocks ko same set mein force karo jabki sirf kuch distinct blocks live hain (taaki fully-assoc reference $M_{fa}$ unhe fit kare aur hit kare).
Capacity chahiye → live set ko genuinely 2 distinct blocks se zyada karo kisi moment mein (taaki even $M_{fa}$ miss kare).

Pehla attempt 0, 2, 0, 1, 3, 1 promising laga lekin $M_{fa}$ check karne par end mein re-touch fully-assoc mein abhi bhi hit kiya, conflict diya capacity ki jagah — isliye capacity requirement fail hui. Yeh failure fix sikhata hai: capacity miss force karne ke liye tumhe distinct-block count badhana hoga, sirf addresses ek set par aim karna nahi. Isliye use karo:

Chosen trace: 0, 2, 0, 1, 2, 1. Index $= B mod 2$ : 0→0, 2→0, 1→1 (isliye 0,2 set 0 share karte hain; 1 set 1 mein akela hai).

Real direct-mapped walk (WHY ke saath har label):

#	Block	idx	set0 / set1 before	Result (real)	WHY this label
1	0	0	{} / {}	Compulsory	0 ka pehla ever touch
2	2	0	{0} / {}	Compulsory	2 ka pehla ever touch; set 0 mein 0 tha ⇒ 0 evict, 2 install
3	0	0	{2} / {}	Conflict	0 pehle dekha gaya (cold nahi); abhi tak sirf {0,2} live hain ⇒ $M_{fa}$ hit karta hai (neeche check kiya) ⇒ mapping ne yeh miss cause ki
4	1	1	{0} / {}	Compulsory	1 ka pehla ever touch; set 1 empty tha
5	2	0	{0} / {1}	Capacity	2 pehle dekha gaya, lekin ab {0,1,2} sab live hain ⇒ even $M_{fa}$ miss karta hai (neeche check kiya) ⇒ size, mapping nahi
6	1	1	{2} / {1}	Hit	1 set 1 mein #4 par install hua tha aur tab se set 1 touch nahi hua ⇒ abhi bhi present

#3 verify karo ki conflict hai — $M_{fa}$ (2-line fully-assoc LRU) 0,2,0 tak simulate karo: 0→[0], 2→[0,2], 0→ present ⇒ hit. Fully-assoc hit karta hai lekin real miss hua ⇒ #3 conflict hai. ✓

#5 verify karo ki capacity hai — full trace 0,2,0,1,2,1 par $M_{fa}$ jaari rakho: 0→[0], 2→[0,2], 0→[2,0] (hit, 0 ab MRU), 1→[0,1] (2 ko LRU ke roop mein evict karo), 2→ miss (2 evict ho gaya!) ⇒ compulsory? Nahi — 2 pehle dekha gaya tha, aur yeh fully-assoc cache hai, isliye yeh size-limited fully-assoc cache ka genuine capacity-type miss hai. Kyunki $M_{fa}$ bhi yahaan miss karta hai, real cache mein access #5 capacity hai, conflict nahi. ✓

Formulas ke saath tally.

$M_{real}$ : #1,#2,#3,#4,#5 par misses = 5; #6 par hit.
$M_{inf} = M_{compulsory} =$ distinct blocks $= {0, 1, 2} = 3$ .
Upar full trace par $M_{fa}$ : 0,2,1,2 par misses = 4.
$M_{capacity} = M_{fa} - M_{inf} = 4 - 3 = 1$ (woh hai access #5).
$M_{conflict} = M_{real} - M_{fa} = 5 - 4 = 1$ (woh hai access #3).
Check: $3 + 1 + 1 = 5 = M_{real}$ ✓.

Answer: trace 0,2,0,1,2,1 se 3 compulsory + 1 conflict + 1 capacity + 1 hit milte hain — teeno C's present, exactly jaisa required tha.

Level 5 — Mastery

Problem 5.1 (L5)

Ek trace real cache par run hota hai. Tumhe simulation ke zariye diya gaya hai (is page ke top par define teen exact counts use karke): $M_{real} = 100$ , $M_{fa} = 70$ (same-size fully-associative, LRU), $M_{inf} = 45$ . (a) Compulsory, capacity, conflict counts compute karo. (b) Agar har miss ka 100-cycle penalty hai aur hits ka 0 extra cost hai, aur 1000 total accesses hain 1 cycle hit time ke saath, toh real cache ka Average Memory Access Time (AMAT) compute karo. (c) Perfect Prefetching saare compulsory misses eliminate karta hai; AMAT recompute karo.

Recall Solution 5.1

(a) Subtraction se decomposition — page ke top se same teen formulas, har idealized cache exactly ek cause hata raha hai: $M_{compulsory} = M_{inf} = 45$ $M_{capacity} = M_{fa} - M_{inf} = 70 - 45 = 25$ $M_{conflict} = M_{real} - M_{fa} = 100 - 70 = 30$ Check: $45 + 25 + 30 = 100 = M_{real}$ ✓

(b) AMAT. Formula (dekho Average Memory Access Time (AMAT)) hai $AMAT = HitTime + MissRate \times MissPenalty .$ Miss rate $= 100/1000 = 0.1$ . Isliye $AMAT = 1 + 0.1 \times 100 = 1 + 10 = 11 cycles.$

(c) Perfect prefetch ke saath 45 compulsory misses gayab ho jaate hain (capacity + conflict bachte hain kyunki prefetch room ya associativity nahi add karta): $M_{new} = 25 + 30 = 55, miss rate = 55/1000 = 0.055.$ $AMAT = 1 + 0.055 \times 100 = 1 + 5.5 = 6.5 cycles.$

Answer: (a) 45 / 25 / 30. (b) 11 cycles. (c) 6.5 cycles — ek 40.9% AMAT reduction, aur isne sirf compulsory component target kiya, exactly jaisa cure-map predict karta hai.

Problem 5.2 (L5)

Problem 5.1 ke trace ko jaari rakhte hue: tum ek upgrade apply kar sakte ho. Option X = full associativity (saare 30 conflict misses hata deta hai, hit time mein +1 cycle add karta hai). Option Y = cache size double karo (empirically 60% capacity misses hata deta hai, hit time unchanged). Kaun sa lower AMAT deta hai? Numbers dikhao.

Recall Solution 5.2

Option X (full associativity): conflicts → 0, isliye misses $= 45 + 25 + 0 = 70$ , miss rate $= 0.07$ , lekin hit time 2 ho jaata hai. $AMAT_{X} = 2 + 0.07 \times 100 = 2 + 7 = 9 cycles.$

Option Y (double size): $0.6 \times 25 = 15$ capacity misses hata deta hai, isliye capacity $= 10$ ; misses $= 45 + 10 + 30 = 85$ , miss rate $= 0.085$ , hit time 1 rehta hai. $AMAT_{Y} = 1 + 0.085 \times 100 = 1 + 8.5 = 9.5 cycles.$

Answer: Option X jeet jaata hai (9 < 9.5 cycles) — chahe hit time badhe, saare 30 conflict misses kill karna yahaan +1-cycle hit tax se zyada save karta hai. Lesson: ek upgrade ki value is baat par depend karti hai ki us target type ke kitne misses exist karte hain; conflicts is trace mein dominate karte the. Analogous tension ke liye block size ke saath dekho Cache Block Size Trade-offs.

Recall Final self-check (answers cover karo)

Conflict formula ::: $M_{real} - M_{fa}$ Capacity formula ::: $M_{fa} - M_{inf}$ Compulsory count equals ::: touched distinct blocks ki number (= $M_{inf}$ ) Ek miss jo same-size fully-assoc cache mein bhi miss kare woh hai ::: capacity (ya compulsory), kabhi conflict nahi Prefetching kis C ko target karta hai ::: compulsory AMAT formula ::: $HitTime + MissRate \times MissPenalty$

Related depth: Spatial and Temporal Locality explain karta hai ki re-references kyun cluster karte hain (capacity/conflict behavior feed karte hue), aur Cache Associativity & Set Mapping upar har conflict ke peeche $B mod S$ machinery detail karta hai.