Set-associative and fully associative caches: Question bank

5.4.3 · D5 · Hardware › Memory Hierarchy & Caches › Set-associative and fully associative caches

Yeh parent note Set-associative and fully associative caches (index 5.4.3) ke liye ek question bank hai. Har item ek one-line reveal hai: prompt padho, apna answer zor se bolo, phir check karo. Answers mein reasoning di gayi hai, sirf verdict nahi — wahi reasoning poora point hai.

Prerequisite ideas jo tumhare paas pehle se honi chahiye: Direct-mapped caches, Conflict misses vs capacity misses, Cache replacement policies, Cache performance metrics.

Is page par use hue symbols (pehle padho)

Poora page char letters par tika hua hai. Chahe tumne inhe parent note mein dekha ho, inhe yahan pakka kar lo taaki koi reveal undefined symbol use na kare.

Woh ek relation jo inhe aapas mein jodata hai, aur jis par is page ka aadha hissa tika hai:

Address ko phir teen fields mein kaata jaata hai jinki bit-widths sirf $S$ aur $B$ par depend karti hain. Figure s01 woh picture hai jo tumhare dimag mein poore waqt rehni chahiye.

True ya false — justify karo

Ek "way" ek set mein ek line slot hai, aur ek "set" ek group of ways hai jo index bits se select hoti hai. Shuru karne se pehle in dono ko alag-alag samajh lo. Figure s02 ek 4-way cache draw karta hai taaki tum ek set ko row ki tarah aur ek way ko column ki tarah dekh sako.

Ek 4-way set-associative cache, same block size ke direct-mapped cache se 4× zyada data store karta hai.

False. Associativity (

N

) yeh batata hai ki block kahaan ja sakta hai, naa ki kitna fit hoga. Kyunki

C = S \times N \times B

hai, ek 64 KB 4-way cache aur ek 64 KB direct-mapped cache dono 64 KB hi hold karte hain — 4-way mein sirf 4× kam sets hoti hain, har ek mein 4 lines hoti hain.

Associativity badhane se miss rate hamesha kam hoti hai.

Zyaadatar sahi, lekin ek ceiling hai. Zyada ways conflict misses khatam kar dete hain, lekin jab conflicts khatam ho jaate hain tab sirf capacity aur compulsory misses bachte hain, jinhe associativity fix nahi kar sakti — dekho Conflict misses vs capacity misses. ~8 ways se aage improvement usually negligible ho jaati hai.

Associativity badhane se average memory access time hamesha kam hoti hai.

False. Zyada ways matlab zyada parallel comparators aur ek bada tag mux, jo hit time badhata hai. Agar hit time miss rate shrinkage se zyada tezi se badhti hai, toh AMAT (dekho Cache performance metrics) worse ho sakta hai.

Fully associative cache mein zero conflict misses hote hain.

True. Conflict miss woh eviction hota hai jo limited placement ki wajah se force hoti hai. Any-block-anywhere placement ke saath, ek block sirf tab evict hota hai jab poora cache full ho — yeh capacity miss hai, conflict miss nahi.

Fully associative cache mein zero misses hote hain.

False. Ispe abhi bhi compulsory misses (ek block ka pehli baar touch) aur capacity misses (working set total size se zyada) aate hain. Associativity sirf conflict category ko khatam karta hai.

Ek direct-mapped cache sirf ek 1-way set-associative cache hai.

True.

N = 1

ke saath har set mein ek line hoti hai, toh index ek hi slot pick karta hai aur koi choice nahi hoti — yahi precisely direct-mapped rule hai.

Fully associative cache ek

S = 1

set-associative cache hai.

True. Ek set jisme saare

C / B

lines hain matlab koi index bits nahi aur har line ek candidate hai — yahi fully associative ki definition hai.

Set index field address ka woh part hai jo tag mein store hota hai.

False. Index set select karta hai; yeh is baat se implied hai ki block kahaan baitha hai, isliye yeh kabhi store nahi hota. Sirf tag bits store hoti hain taaki ek set ke andar blocks ko distinguish kiya ja sake.

Fully associative cache mein tag, same-size set-associative cache se bada hota hai.

True. Koi index bits nahi hone ki wajah se, jo bits index bits hote woh saare tag mein absorb ho jaate hain, isliye tag ko memory ke uss (single) set mein map hone wale saare blocks ke beech block ko uniquely identify karna hota hai.

2-way cache mein LRU ko 1 bit per set se implement kiya ja sakta hai.

True. Sirf do ways hone par, ek bit record karta hai dono mein se kaunsa zyada recently use hua; hit par set karo, miss par dusre ko evict karo. Zyada associativity mein zyada state chahiye — figure s04 mein pseudo-LRU tree dekho.

Direct-mapped cache mein replacement policy matter karti hai.

False. Ek block ka exactly ek hi legal slot hota hai, isliye koi choice hi nahi hai — incumbent hamesha evict hota hai. Policies sirf tab matter karti hain jab

N \geq 2

ho. Dekho Cache replacement policies.

Associativity double karte hue sets ki sankhya half karne se total capacity fixed rehti hai.

True. Capacity hai

C = S \times N \times B

. Agar

N

double ho aur

S

half ho, toh product nahi badlega, isliye same total bytes rehte hain.

Galti dhundo

Neeche har statement mein ek galti hai. Use naam do aur theek karo.

"64 KB, 64 B blocks, 4-way → sets = C/(B) = 1024."

N se divide karna bhool gaye. Sets

= C / (B \cdot N) = 65536/ (64 \cdot 4) = 256

, 1024 nahi. Sirf

B

se divide karne par total lines (

C / B = 1024

) milti hain, sets ki sankhya nahi.

"Fully associative caches ko kaunsi line search karni hai yeh pick karne ke liye index bits chahiye."

Koi index nahi hota.

S = 1

ke saath hume

i = lo g_{2} 1 = 0

index bits milte hain; har line parallel mein search hoti hai, isliye address sirf Tag | Offset hai.

"Ek 2-way cache ko 2 comparators chahiye, isliye yeh direct-mapped se 2× hardware cost karta hai."

Comparators sirf poori cost nahi hai. Sirf comparators ke liye hi 2× se zyada hai, lekin total "twice" se simple nahi — isme replacement state, wider tag mux, aur way-select logic bhi hai. "2 comparators" ≈ sahi; "twice the total cost" ek oversimplification hai.

"256 sets ke saath tumhe log₂(256) = 16 index bits chahiye."

$lo g_{2} 256 = 8$ hai, 16 nahi. Kyunki

2^{8} = 256

. Likhne wale ne shayad ise byte count ke saath confuse kar liya.

"Block size

B

badhane se hamesha index bits ki sankhya kam hoti hai."

Sirf tab agar $C$ aur $N$ fixed rahein — yeh hai poori chain.

S = C / (B \cdot N)

se shuru karo, toh

i = lo g_{2} S = lo g_{2} (C / (B \cdot N)) = lo g_{2} C - lo g_{2} B - lo g_{2} N

B

double karne se

lo g_{2} B

mein 1 add hota hai, jo

i

se 1 subtract karta hai sirf tab jab $C$ aur $N$ constant rakhe jaayein. Agar capacity

B

ke saath badhti hai (ya

N

badlta hai), toh

i

zaruri nahi gire — figure s03 ise trace karta hai.

"Tag + index + offset address width se zyada ho sakta hai agar cache kaafi badi ho."

Impossible — fields $A$ bits ko partition karti hain. Construction se

t = A - i - b

hai, isliye

t + i + b = A

exactly hoga, chahe cache kitni bhi badi ho. Toy example:

A = 8

B = 4 \Rightarrow b = 2

S = 4 \Rightarrow i = 2

, isliye

t = 8 - 2 - 2 = 4

aur

4 + 2 + 2 = 8

. Cache badi karne par sirf bits tag se index mein jaate hain; sum kabhi 8 se nahi jaata.

"LRU hamesha baaki har policy ko beat karta hai, isliye real hardware hamesha true LRU use karta hai."

LRU usually jeetat hai, lekin high associativity ke liye true LRU expensive hai. True LRU

N

ways ke liye saare

N

lines ko order karna padta hai (

\approx N lo g_{2} N

bits per set); real 8-way+ caches figure s04 ka sasta pseudo-LRU tree use karte hain (sirf

N - 1

bits) ya random bhi, thodi si miss-rate loss ke badle bahut kam state ke liye.

"Hit ke liye tag match hona chahiye; valid bit matter nahi karta."

Dono zaroori hain. Ek stale/uninitialised line accident se matching tag hold kar sakti hai; valid bit = 1 confirm karta hai ki line mein actually real data hai. Hit = tag match AND valid.

Why questions

Set-associative caches sabhi N tags ko ek-ek karke nahi, parallel mein kyun compare karti hain?

Hit time ek cycle mein rakhne ke liye. Sequential comparison hit latency ko

N

se multiply kar deta, jo fast cache ka purpose defeat kar deta — parallel comparators area/power kharch karke speed khareedte hain. Figure s02 mein comparator fan-out dekho.

Fully associative cache badi sizes par poorly kyun scale karti hai?

Ise ek comparator per line chahiye (

C / B

of them) plus ek bada priority encoder. Badi cache ke liye yeh hundreds ya thousands of comparators hain — bahut zyada area aur power, isliye yeh sirf chhoti structures jaise Translation Lookaside Buffer (TLB) ke liye reserved hai.

Tag ki zaroorat hi kyun hai agar index already set select kar leta hai?

Index sirf tumhe ek set tak narrow karta hai; bahut saare alag memory blocks ek hi set mein map hote hain (woh index bits share karte hain lekin baaki mein alag hain). Tag un distinguishing high bits store karta hai taaki tum pata kar sako ki actually kaunsa block har way mein baitha hai.

LRU temporal locality ko exploit kyun karta hai?

Temporal locality kehta hai ki recently-used block jald hi reuse hone ki sambhavna hai. LRU least recently used line evict karta hai — woh jo aage zaroorat padne ki sabse kam sambhavna hai — future misses minimize karta hai.

L1 caches low associativity prefer karti hain jabki L3 high kyun prefer karti hai?

L1 speed ke critical path par hai, isliye hit time tiny rakhne ke liye associativity kam rakhti hai. L3 core se door hai jahan slow hit tolerable hai, isliye woh miss rate cut karne aur costly main-memory trips reduce karne ke liye associativity spend karti hai.

Direct-mapped cache ko replacement policy ki zaroorat nahi hai lekin fully associative ko hai, kyun?

Direct-mapped har block ko exactly ek ghar deta hai, isliye "kise evict karein" pehle se decided hai. Fully associative har block ko kai ghar deta hai, isliye miss par hardware ko ek victim choose karna padta hai — woh choice hi policy hai.

Do programs same total data size ke saath same cache par bahut alag miss rates kyun dekh sakte hain?

Miss rate sirf data size par nahi, access pattern par depend karti hai. Strided ya aliasing patterns kai blocks ko ek set par dher kar sakte hain (low-associativity caches mein conflict misses), jabki friendlier pattern unhe spread out karta hai. Associativity specifically bad patterns ke khilaf ek defense hai.

Edge cases

Jab N total cache lines ki sankhya ke barabar ho (

N = C / B

) tab kya hota hai?

Tumhe exactly

S = 1

set milta hai — ek fully associative cache. Yeh associativity ki upper limit hai; tum isse upar nahi ja sakte.

Jab

S = 1

ho tab set index field kya hai?

Zero bits.

lo g_{2} 1 = 0

, isliye koi index nahi — address purely Tag | Offset hai, jo fully associative ke consistent hai.

Agar block size

B

poore cache size

C

ke barabar ho (aur

N = 1

ho), toh kitne sets honge?

Ek set mein ek line:

S = C / (B \cdot N) = C / (C \cdot 1) = 1

. Poora cache ek single block hai — koi useful associativity ya indexing nahi, ek degenerate case.

2-way cache mein, ek set ke dono ways invalid (cold) hain. Ek naya block aata hai — kaunsa way fill hota hai aur kya policy matter karti hai?

Pehle koi bhi empty way fill hota hai; replacement policy sirf tab kick in karti hai jab dono ways valid hon. Cold set par, "ek invalid line fill karo" LRU/FIFO se pehle priority leta hai.

Do addresses ka tag identical aur index identical hai lekin offset alag hai. Same block hai ya alag?

Same block. Tag+index block identify karte hain; offset sirf iske andar ek byte pick karta hai. Isliye woh same cache line hit karte hain aur, hit par, dono ussi se serve hote hain.

Agar ek loop mein har access same set mein map hota hai aur set 2-way hai, lekin teen distinct blocks cycle hote hain, toh kaunsa miss pattern aata hai?

Thrashing — teen blocks mein se har ek repeatedly dono mein se kisi ek ko evict karta hai kyunki ek saath sirf 2 hi reh sakte hain. Yeh conflict misses hain; ek 3-way (ya zyada) set, ya full associativity, inhe khatam kar deta.

Sabse chhoti associativity kya hai jo K blocks ka ek working set hold kar sake jo saare ek set mein map ho bina kisi conflict miss ke?

N = K

. Tumhare paas us set mein kam se kam utne ways hone chahiye jitne simultaneously-live blocks uske liye compete kar rahe hain; kam hone par evictions force hoti hain.