Cache miss types (compulsory, capacity, conflict)

5.4.9 · Hardware › Memory Hierarchy & Caches

Intuition Badi picture (YE categories kyun exist karti hain)

Har cache miss tumhe slow karta hai, lekin sabhi misses ka ek jaisa cause nahi hota — aur na hi ek jaisa cure. Engineers ne 3 C's model isliye banaya taaki ek sawaal ka jawab mil sake: "Agar ye miss hua, toh kya ek better cache design isse avoid kar sakti thi?"

Compulsory — ise koi bhi avoid nahi kar sakta tha (data ka pehli baar kabhi bhi touch).
Capacity — cache simply itna chota tha ki jo kuch tum use kar rahe the usse hold nahi kar saka.
Conflict — cache mein jagah thi, lekin mapping rule ne do blocks ko ek hi slot ke liye ladate hue chod diya.

Iska kamal ye hai ki ye classification tumhe batati hai ki kya change karo: bada cache capacity fix karta hai, zyada associativity conflict fix karta hai, prefetching compulsory fix karta hai.

Setup: cache kya hota hai aur "miss" kya hota hai?

KYA hum measure karna chahte hain: kisi program ke access sequence ke liye, kitne misses hote hain aur kyun.

3 C's — precise definitions

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

Classification ko first principles se derive karna

KAISE decide karte hain ki real miss ka type kya hai? Same access trace ko teen model caches par simulate karo.

Worked Example 1 — direct-mapped conflict

Cache: direct-mapped, 4 lines (block = 1 word simplicity ke liye, toh $S = 4$ ). Block numbers ka access sequence: 0, 4, 0, 4, 0, 4.

Index $= B mod 4$ : block 0 → set 0; block 4 → $4 mod 4 = 0$ → bhi set 0.

Access	State before	Result	Kyun
0	empty	Compulsory miss	0 ka pehla kabhi touch
4	{0}	Compulsory miss	4 ka pehla kabhi touch (0 evict hota hai)
0	{4}	Conflict miss	0 pehle dekha gaya ⇒ cold nahi; sirf 2 blocks use hue ⇒ fully-assoc mein fit hoga ⇒ conflict
4	{0}	Conflict miss	same reasoning
0	{4}	Conflict miss	thrashing jari rehta hai
4	{0}	Conflict miss	thrashing jari rehta hai

Result: 2 compulsory + 4 conflict + 0 capacity. Fix: sirf 2-way associativity se dono blocks set 0 mein saath rehte hain → baad ke sabhi accesses hit hote hain. Conflict misses cache ko bade kiye bina gayab ho jaate hain.

Worked Example 2 — capacity miss

Cache: fully-associative, 2 lines, LRU. Sequence: 0, 1, 2, 0, 1, 2.

Access	Cache (LRU→MRU)	Result	Kyun
0	[0]	Compulsory	pehla touch
1	[0,1]	Compulsory	pehla touch
2	[1,2]	Compulsory (0 evict hota hai)	2 ka pehla touch
0	[2,0]	Capacity	0 pehle dekha gaya, lekin fully-assoc ne phir bhi miss kiya ⇒ cache bahut chota hai (3 blocks, 2 slots)
1	[0,1]	Capacity	same
2	[1,2]	Capacity	same

Result: 3 compulsory + 3 capacity + 0 conflict. Conflict kyun nahi? Cache fully-associative hai, isliye koi mapping restriction nahi — associativity se kuch fix karne ki zarurat nahi. Iska sirf ek ilaj hai bada cache (≥3 lines) ya chota working set.

Worked Example 3 — teeno ek hi trace mein

Direct-mapped, 2 lines ( $S = 2$ , index $= B mod 2$ ). Sequence: 0, 1, 2, 0, 3, 0.

Access	Index	State	Result	Yeh step kyun?
0	0	—	Compulsory	pehla touch
1	1	{0,1}	Compulsory	pehla touch
2	0	{2,1}	Compulsory	pehla touch (0 evict hota hai, dono set 0 mein map hote hain)
0	0	{0,1}	Conflict	0 pehle dekha gaya; sirf blocks {0,1,2} use hue, kya 2-line fully-assoc mein fit hota? Nahi — 3 blocks > 2 lines... dhyan se dekho
3	1	{0,3}	Compulsory	pehla touch (1 evict hota hai)
0	0	{0,3}	Hit	0 abhi bhi set 0 mein hai

Access #4 ke liye hume fully-assoc size 2 test karna hoga: sequence 0,1,2,0… — ek 2-line fully-assoc LRU cache ke paas {1,2} hoga jab 0 re-request hoga ⇒ woh bhi miss karta hai. Toh access #4 actually ek capacity miss hai, conflict nahi! Yeh dikhata hai ki classification ke liye reference cache simulate karna hota hai, ankhon se andaza nahi lagana. (Yeh subtle case exactly isliye hai kyunki hum types ko comparison se define karte hain, intuition se nahi.)

Common mistakes (Steel-man + fix)

Active recall

Recall Pehle forecast karo phir verify karo (answers dhak lo!)

Infinite cache mein kaun sa miss type bachta hai? → Sirf Compulsory.
Kaun sa cure conflict fix karta hai lekin capacity NAHI? → Higher associativity.
Sequence 0,4,0,4 direct-mapped 4-line cache mein ( $4 mod 4 = 0$ ): kitne conflict misses? → 2 (2 compulsory ke baad).
Conflict count ka formula? → $M_{real} - M_{full-assoc}$ .
Kya fully-associative cache mein kabhi conflict misses hote hain? → Nahi, by definition.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Ek choti bookshelf (cache) aur ek badi library (memory) ki imagine karo.

Compulsory: pehli baar jab tumhe koi book chahiye, woh kabhi bhi tumhari shelf par nahi hogi — tumhe library tak walk karna hoga. Koi bhi isse avoid nahi kar sakta tha.
Capacity: tumhari shelf 3 books rakhti hai lekin tum 4 ke beech switch karte rehte ho. Kuch na kuch hamesha push off ho jaata hai. Sirf badi shelf help karegi.
Conflict: tumhare paas shelf par kaafi jagah hai, lekin ek bewakoof rule kehta hai ki "red book aur blue book ek hi single spot par jaani chahiye." Woh ek dusre ko kick karte rehte hain chahe baaki spots khali hon. Rule change karo (zyada spots allow karo) aur problem gayab ho jaati hai.

80/20 — essential takeaways

Idealized caches se comparison se classify karo (infinite → full-assoc → real).
Cause ⇒ cure: compulsory→prefetch/bigger blocks; capacity→bigger cache; conflict→more associativity.
Conflict $=$ real misses $-$ fully-associative misses; agar yeh 0 hai, toh associativity help nahi karega.

Connections

Cache Associativity & Set Mapping
LRU and Replacement Policies
Spatial and Temporal Locality
Cache Block Size Trade-offs
Average Memory Access Time (AMAT)
Working Set & Program Behavior
Prefetching

The 3 C's model classifies cache misses into which three types?

Compulsory (cold), Capacity, Conflict.

What is a compulsory miss?

Kisi block ka pehla-kabhi reference; yeh infinite cache mein bhi miss karta hai.

What is a capacity miss?

Ek miss jo same size ke fully-associative cache mein bhi hota — working set cache capacity se zyada hai.

What is a conflict miss?

Ek miss jo equal size ke fully-associative cache mein HIT karta lekin limited associativity ki wajah se eviction force hone se miss hua.

Which idealized cache leaves only compulsory misses?

Ek infinite cache.

How do you compute the number of conflict misses?

Misses(real cache) − Misses(fully-associative cache of same size).

How do you compute capacity misses?

Misses(fully-associative same size) − Misses(infinite cache).

Cure for conflict misses?

Associativity badhao (ya victim cache / better indexing).

Cure for capacity misses?

Total cache size badhao ya working set chota karo.

Cure for compulsory misses?

Prefetching ya bada block size (spatial locality).

In a direct-mapped cache with S sets, which set does block B map to?

index = B mod S.

Does a fully-associative cache ever suffer conflict misses?

Nahi — koi mapping restriction nahi hone se, conflict misses definition se zero hote hain.

Why can larger blocks hurt?

Kam blocks fit hote hain, capacity aur conflict misses badhte hain aur bandwidth waste hoti hai.

Sequence 0,4,0,4 on a direct-mapped 4-line cache (4 mod 4 = 0): miss breakdown?

2 compulsory phir 2 conflict (dono set 0 mein map hote hain aur thrash karte hain).

Why can't associativity fix a capacity miss?

Capacity misses full associativity ke saath bhi hote hain; problem total size ki hai, mapping ki nahi.