Cache miss types (compulsory, capacity, conflict): Question bank

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

Shuru karne se pehle teen yardsticks ki yaad dahan:

Infinite cache → sirf compulsory misses bachti hain.
Fully-associative, finite → compulsory + capacity bachti hain.
Real (limited-associativity) → teeno miss types hoti hain.

True or false — justify karo

Jo data tumne pehle touch kiya tha, uska har miss ek conflict miss hai.

False — yeh capacity miss bhi ho sakta hai. Yeh conflict tab hi hoga jab usi size ka fully-associative cache hit karta; warna cache simply bahut chota tha.

Ek fully-associative cache abhi bhi capacity misses suffer kar sakta hai.

True — full associativity sirf mapping restriction (conflict) ko hataata hai. Agar working set lines ki sankhya se zyada ho, toh blocks phir bhi jagah na hone ki wajah se evict hote hain. Dekho Working Set & Program Behavior.

Ek fully-associative cache conflict misses suffer kar sakta hai.

False, by definition — conflict misses ek mapping rule se aati hain jo do blocks ko same slot mein force karta hai, aur full associativity aisa koi rule impose nahi karta.

Compulsory misses ko associativity badhane se eliminate kiya ja sakta hai.

False — compulsory miss kisi block ka pehla kabhi bhi touch hota hai; wahan kuch tha hi nahi rakhne ke liye, isliye slot arrangement irrelevant hai. Sirf Prefetching ya bade blocks (spatial locality ke zariye) inhe reduce karte hain.

Cache size double karne se conflict misses badh sakti hain.

True pathological cases mein, lekin standard result yeh hai: size double karne se index mapping shift ho sakti hai jisse kuch strides jo pehle collide karte the ab nahi karte (usually fewer conflicts). Conflict ka reliable fix associativity hi rehta hai, size nahi.

Ek direct-mapped cache mein usi size ke fully-associative cache se zyada conflict misses hoti hain.

True — direct-mapped har block ko exactly ek hi ghar deta hai, isliye same index wale koi bhi do blocks fight karte hain; zyada associativity har set ko zyada ghar deti hai aur yeh softens ho jaata hai.

Associativity badhana kabhi performance hurt nahi karta.

False — yeh conflict misses hataata hai lekin hit latency, energy badhata hai, aur clock speed lower kar sakta hai. 3 C's count time per hit ke baare mein kuch nahi kehta; dekho Average Memory Access Time (AMAT).

Compulsory misses ki sankhya un distinct blocks ki sankhya ke barabar hoti hai jo program touch karta hai.

True — har unique block ko memory se kam se kam ek baar fetch karna padta hai, aur woh pehla fetch kisi bhi cache mein, chahe infinite ho, unavoidable hai.

Bade cache blocks hamesha total misses reduce karte hain.

False — bade blocks compulsory misses cut karte hain (har fetch mein zyada neighbours) lekin resident distinct blocks ki sankhya kam ho jaati hai, jisse capacity aur conflict misses badhti hain. Yeh ek trade-off hai jiska ek optimum hota hai, per Cache Block Size Trade-offs.

Error dhundho

"Yeh access miss karti hai, aur yeh pehla touch nahi hai, isliye yeh zaroor conflict miss hai."

Yahan error capacity test ko skip kar deta hai. Tumhe same-size fully-associative cache simulate karna hoga: agar woh bhi miss kare, toh yeh capacity hai, conflict nahi.

"Hamara cache fully-associative hai, isliye agar ek repeated block miss kare toh yeh conflict miss honi chahiye."

Impossible — fully-associative caches mein zero conflict misses hoti hain. Wahan repeated-block miss ek capacity miss hai jo oversized working set ki wajah se hoti hai.

"Hum ne 2-way associative jaake saari conflict misses hata diin, toh total misses zero ho gayi."

Conflicts hatane se compulsory ya capacity misses touch nahi hoti. Cold blocks abhi bhi pehle touch par miss karte hain, aur oversized working set abhi bhi cache overflow karta hai.

"Compulsory = Misses in a fully-associative finite cache."

Galat yardstick. Compulsory = misses in an infinite cache. Fully-associative finite cache compulsory plus capacity misses chhod deta hai.

"Conflict count = real misses minus infinite-cache misses."

Woh difference capacity + conflict dono hai. Conflict akela =

M_{real} - M_{full-assoc}

; capacity =

M_{full-assoc} - M_{infinite}

"Kyunki LRU optimal hai, ek fully-associative LRU cache true minimum miss count deta hai."

LRU ek achha heuristic hai lekin optimal nahi; Belady's optimal policy behtar kar sakti hai. Phir bhi, LRU woh standard reference hai jo capacity misses define karne ke liye use hota hai, isliye classification usi ke relative defined hai.

Why questions

Hum miss types ko idealized caches se compare karke kyun define karte hain, intuition se kyun nahi?

Kyunki har ideal cache miss ka exactly ek cause remove karta hai, isliye unke miss counts subtract karne se har cause cleanly isolate ho jaata hai. Intuition subtle cases mein fail hoti hai (ek repeated block abhi bhi capacity ho sakta hai, conflict nahi).

Index formula

index = B mod S

mechanically conflict misses kyun produce karta hai?

Jo do blocks ke block-numbers sets ki sankhya

S

ke mod mein congruent hain, woh same set mein map hote hain, isliye woh ek dusre ko evict karte hain chahe baaqi cache khali hi kyun na ho.

Prefetching capacity misses kyun fix nahi kar sakta?

Prefetching sirf fetch ki latency hide karta hai usse early start karke; yeh zyada room nahi banata. Agar working set cache se zyada ho, toh prefetched blocks abhi bhi reuse se pehle evict ho jaate hain. Dekho Prefetching.

Associativity conflict fix karta hai lekin capacity kyun nahi?

Associativity har set ko zyada ghar deti hai, isliye colliding blocks coexist kar sakte hain — yeh conflict erase karta hai. Lekin yeh total lines nahi badhata, isliye oversized working set abhi bhi overflow karta hai: capacity untouched rehti hai.

3 C's decomposition ek designer ke liye useful kyun hai?

Yeh har miss cause ko ek distinct cure se map karta hai — size capacity ke liye, associativity conflict ke liye, prefetch/block-size compulsory ke liye — isliye tum transistors us cause par kharach karte ho jo tumhare program mein actually dominate karta hai.

Edge cases

Ek infinite cache ek program run karta hai. Kaunse miss types ho sakte hain?

Sirf compulsory — kuch bhi kabhi evict nahi hota, isliye koi capacity ya conflict misses possible nahi hain; har miss pehla touch hai.

Ek program sirf 2 distinct blocks touch karta hai jo ek direct-mapped cache mein same set mein map hote hain, aur inke beech hamesha alternate karta hai. Kaunse miss types hoti hain?

2 compulsory (pehle touches) phir endless conflict misses — 2-block working set ek fully-associative 2-line cache mein fit hota hai, isliye yeh pure conflict hai, 2-way associativity se curable.

Ek program ka working set exactly cache size ke barabar hai, fully-associative LRU cache par run ho raha hai, aur woh saare blocks ko order mein cycle karta hai. Kya hota hai?

Har re-reference miss karti hai (capacity) — LRU us block ko evict karta hai jo agle reuse hone wala hota hai, isliye ek working set jo barely fit nahi hota thrash karta hai. Ek single extra line, ya ek alag policy, ise bacha sakti hai.

Kya ek single access ek saath capacity aur conflict miss dono ho sakti hai?

Nahi — classification by construction mutually exclusive hai: infinite test karo (compulsory), phir same-size fully-associative (capacity), warna conflict. Har real miss exactly ek bin mein jaati hai.

Ek cache cold hai (abhi power on hui) aur program ka pehla access miss karta hai. Kaunsa type, hamesha?

Hamesha compulsory — koi bhi data abhi tak load nahi hua, isliye yeh capacity ya conflict nahi ho sakta chahe associativity ya size kuch bhi ho.

Agar do alag programs ke total miss counts identical hain, toh kya unke designs ko same fix chahiye?

Nahi — ek conflict-dominated ho sakta hai (associativity chahiye) aur doosra capacity-dominated (bada cache chahiye). Equal totals bilkul alag cures hide karte hain, aur yahi exactly woh reason hai kyun 3 C's breakdown matter karta hai.