Set-associative and fully associative caches: Exercises

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

Yeh page ek graded ladder hai. Har rung pichle se harder hai: L1 Recognition (kya tum piece ka naam bata sakte ho?) → L2 Application (kya tum formula mein numbers daal sakte ho?) → L3 Analysis (kya tum behaviour ke baare mein reason kar sakte ho?) → L4 Synthesis (kya tum poori cheez design kar sakte ho?) → L5 Mastery (kya tum compare kar ke ek choice defend kar sakte ho?).

Har problem ka poora answer ek collapsible [!recall]- block ke andar chhupaaya gaya hai — taaki tum pehle khud test kar sako, phir reveal karo. Koi bhi solution kholne se pehle paper par kaam karo.

Shuru karne se pehle, ek picture hai jis par har problem tiki hui hai. Use doosre tab mein khula rakhna.

Figure — Set-associative and fully associative caches

Picture ko left se right padhna: ek address (bits ki ek plain string — isse memory mein ek byte ka house number samjho) teen fields mein slice hoti hai. Sabse right wala slice, offset, ek block ke andar ek byte pick karta hai. Middle slice, index, yeh pick karta hai ki kis set mein dekha jaaye. Sabse left wala slice, tag, woh label hai jo cache store karti hai taaki baad mein confirm kar sake ki "haan, yeh sach mein tumhara block hai."

Hum yeh words constantly use karenge, toh inhe ek baar clearly define kar lete hain:

Level 1 — Recognition

Goal: piece ka naam lo, config padho, powers of two se zyada arithmetic nahi.

L1.1 Ek cache ko 8-way set-associative describe kiya gaya hai. Simple words mein, har set mein kitni lines hain, aur ek single memory block ko kitni jagahon par store kiya ja sakta hai?

L1.2 Set-associative ka kaunsa cache organisation special case $N = 1$ hai? Aur kaunsa woh special case hai jahan $N$ total lines ki sankhya ke barabar hota hai?

L1.3 Ek fully associative cache mein address split $⟨ Tag ∣ Offset ⟩$ hoti hai. Index field kyun nahi hota?

Recall Solution L1

L1.1 "8-way" ka matlab hai ki har set mein $N = 8$ lines hain. Ek block exactly ek set mein map hota hai (uske index bits se fixed), lekin us set ke andar woh 8 lines mein se kisi bhi mein baith sakta hai. Toh uske paas 8 possible homes hain.

L1.2

$N = 1$ → direct-mapped: ek set mein ek hi line, toh har block ka exactly ek hi ghar.
$N = L$ (saari lines ek set mein) → fully associative: koi bhi line valid ghar hai.

L1.3 Index field sirf isliye hota hai taaki kaun si set search karni hai choose ki ja sake. Fully associative cache mein sirf ek set hoti hai — choose karne ki zaroorat hi nahi — toh woh bits koi information nahi carry karenge. "Kaun sa block hai" ka poora kaam tag mein push ho jaata hai, aur har line ko parallel mein search kiya jaata hai.

Level 2 — Application

Goal: chaar equations mein numbers daalo.

L2.1 Ek 32 KB, 4-way set-associative cache 64-byte blocks aur 32-bit addresses use karti hai. Yeh nikalo: total lines $L$ , sets $S$ , aur bit split (offset / index / tag).

L2.2 Ek 16 KB fully associative cache, 32-byte blocks, 32-bit addresses. Lines, offset bits, index bits, tag bits nikalo.

L2.3 Address 0xDEADBE00 (32 bits) L2.1 ki cache mein hit karta hai. Uska offset, index (decimal set number mein), aur tag (hex mein) extract karo.

Recall Solution L2

L2.1 $C = 32 KB = 32 \times 1024 = 32768$ bytes. $L = \frac{C}{B} = \frac{32768}{64} = 512 lines$ $S = \frac{L}{N} = \frac{512}{4} = 128 sets$ Bits: $b = lo g_{2} 64 = 6$ , $i = lo g_{2} 128 = 7$ , $t = 32 - 6 - 7 = 19$ . Answer: 512 lines, 128 sets, split 19 tag / 7 index / 6 offset (sum $= 32$ ✓).

L2.2 $C = 16384$ , $B = 32$ . $L = \frac{16384}{32} = 512 lines$ $b = lo g_{2} 32 = 5$ , index $= 0$ (fully associative), $t = 32 - 5 = 27$ . Answer: 512 lines, 27 tag / 0 index / 5 offset.

L2.3 L2.1 ka split (19/7/6) use karo. Neeche ke 3 hex digits E00 ko binary mein likho (high bits sirf tag ko feed karte hain): $0xDEADBE00 = 19 tag 1101111010101101101 7 index 1111000 6 offset 000000$

Offset = last 6 bits = 000000 = $0$ .
Index = agले 7 bits = 1111000 = $64 + 32 + 16 + 8 = 120$ . → set 120.
Tag = top 19 bits. Numerically, tag $= ⌊ 0xDEADBE00 / 2^{13} ⌋ = 0x6F56D$ . Answer: offset $0$ , set 120, tag 0x6F56D.

Level 3 — Analysis

Goal: hits, misses aur eviction ke baare mein reason karo — sirf bit counts nahi.

L3.1 Ek 2-way set-associative cache jisme 1 set hai (toh yeh bahut chhota hai: 2 lines, effectively fully associative) LRU use karti hai. Block numbers ki access stream hai: $A, B, A, C, B, A$ Dono lines shuru mein empty hain. Har access ko HIT ya MISS mark karo aur final miss count do. (Dekho LRU.)

L3.2 Same 2-line cache, same stream $A, B, A, C, B, A$ , lekin ab FIFO replacement ke saath. Miss count?

L3.3 Ek direct-mapped cache ko kabhi replacement policy ki zaroorat kyun nahi padti, jabki 2-way cache ko padti hai?

Recall Solution L3

Notation: cache state likhi hai [most-recent, least-recent]; ✗ = miss, ✓ = hit.

L3.1 (LRU)

Access	Hit/Miss	Reason	State after (MRU→LRU)
A	✗	empty	[A]
B	✗	present nahi	[B, A]
A	✓	A present hai	[A, B]
C	✗	full → evict LRU = B	[C, A]
B	✗	B evict ho chuka tha	[B, C]
A	✗	A LRU tha, B load hone par evict hua	[A, B]

Misses = 5, hits = 1.

L3.2 (FIFO) — oldest by insertion ko evict karo, re-use ignore karo. State = [newest, oldest].

Access	Hit/Miss	State
A	✗	[A]
B	✗	[B, A]
A	✓	[B, A] (order unchanged — FIFO hit par refresh nahi karta)
C	✗ oldest A evict	[C, B]
B	✓	[C, B]
A	✗ oldest B evict	[A, C]

Misses = 4, hits = 2.

Interesting: yahan FIFO ne LRU ko beat kiya (4 vs 5). Yeh ek chhota hand-picked stream hai — real workloads mein LRU average par jeet ta hai, lekin koi bhi policy har trace par nahi jeetti.

L3.3 Ek direct-mapped cache har block ko exactly ek legal line deti hai ( $N = 1$ ). Miss hone par kuch choose karne ki zaroorat nahi: tum us ek line ko overwrite karte ho. Ek 2-way cache har set mein do legal lines deti hai, toh miss hone par tum decide karte ho ki dono mein se kaunsi throw out karni hai — yahi decision replacement policy hai.

Level 4 — Synthesis

Goal: ek spec se poori cache design karo aur har field defend karo.

L4.1 Ek cache design karo jo sab yeh conditions meet kare: total size 256 KB, 8-way set-associative, 128-byte blocks, 40-bit physical addresses. $L$ , $S$ , aur poora offset/index/tag split do. Sum verify karo.

L4.2 Tumhe bataya gaya hai ki ek set-associative cache mein 11 index bits, 6 offset bits, aur 512 KB total size hai. Iska associativity $N$ aur address width $A$ deduce karo agar tag 17 bits ka hai.

Recall Solution L4

L4.1 $C = 256 \times 1024 = 262144$ bytes, $B = 128$ , $N = 8$ , $A = 40$ . $L = \frac{262144}{128} = 2048 lines$ $S = \frac{2048}{8} = 256 sets$ $b = lo g_{2} 128 = 7$ , $i = lo g_{2} 256 = 8$ , $t = 40 - 8 - 7 = 25$ . Answer: 2048 lines, 256 sets, split 25 tag / 8 index / 7 offset (sum $= 40$ ✓).

L4.2 Ulta kaam karo.

Offset bits $b = 6 \Rightarrow B = 2^{6} = 64$ bytes.
Index bits $i = 11 \Rightarrow S = 2^{11} = 2048$ sets.
$C = 512 KB = 524288$ bytes, toh $L = C / B = 524288/64 = 8192$ lines.
$N = L / S = 8192/2048 = 4$ . → 4-way.
$A = t + i + b = 17 + 11 + 6 = 34$ bits. Answer: $N = 4$ (4-way), $A = 34$ bits.

Level 5 — Mastery

Goal: organisations compare karo, tradeoffs ke baare mein reason karo, design choice defend karo.

L5.1 Tumhe ek program cache karna hai jiska hot inner loop repeatedly exactly 3 arrays ko touch karta hai jinke base addresses sab direct-mapped cache mein same set index par map karte hain. Explain karo ki direct-mapped cache yahan kyun thrash karta hai, aur minimum associativity kya hogi jo yeh conflict misses hataa de. (Dekho Conflict misses vs capacity misses.)

L5.2 Ek fully associative cache aur ek direct-mapped cache ka same total size aur block size hai. Kaunsi (a) lower miss rate, (b) faster hit time, (c) zyada comparator hardware deti hai? Har ek ke liye, ek sentence mein reason do.

L5.3 Ek Translation Lookaside Buffer (TLB) almost hamesha fully associative hota hai jabki large caches rarely hoti hain. Do reasons do kyun yeh specifically ek TLB ke liye sense karta hai.

Recall Solution L5

L5.1 Teeno array bases ek hi index share karte hain, toh direct-mapped cache mein teeno ek single line ke liye ladte hain. Kisi doosre array ka har access pichle wale ko evict kar deta hai → har touch ek conflict miss hai, chahe cache mein hazaaron free lines kyun na hon. Set mein sirf 1 block ki jagah hai lekin 3 coexist karna chahte hain. Minimum associativity = 3-way (ya zyada): ek 3-way set teeno ko simultaneously rakh sakta hai, toh ek baar load hone ke baad woh resident rahte hain aur conflict misses khatam ho jaate hain. Practice mein tum 4-way tak round up karte ho (power of two, cleaner indexing).

L5.2

(a) Lower miss rate → fully associative. Ek block kisi bhi line mein ja sakta hai, toh kabhi conflict misses nahi hote; sirf true capacity misses bachte hain.
(b) Faster hit time → direct-mapped. Exactly ek candidate line, ek tag comparison, ways ke beech koi multiplexing nahi → sabse short critical path.
(c) Zyada comparators → fully associative. Yeh tag ko har line se compare karta hai ( $L = C / B$ comparators) parallel mein; direct-mapped ko sirf ek chahiye.

L5.3 (1) TLB chhota hota hai (tens of entries), toh "sab se compare karo" ka cost — har entry par ek comparator — affordable hai, unlike ek 512-line data cache. (2) Address translations ke scattered, unpredictable page numbers hote hain; wahan conflict misses bahut costly honge (ek miss slow page-walk trigger karta hai), toh full associativity se inhe completely eliminate karna hardware ke laayak hai.

Common mistake L5 trap: "L1 ko fully associative banao — best miss rate!"

Galat rasta: lower miss rate strictly achha hai, toh har jagah associativity maximize karo. Yeh sahi kyun lagta hai: comparison table literally kehti hai fully associative ka miss rate sabse kam hota hai. Fix: jo metric matter karta hai woh hai average access time $= hit time + miss rate \times miss penalty$ (dekho Cache performance metrics). Full associativity miss rate crush kar deta hai lekin hit time inflate kar deta hai (huge parallel tag compare + slow way-selection mux) aur power/area jalata hai. Ek L1 cache ke liye — jo har cycle access hoti hai, speed-critical — slower hit time har access ko hurt karta hai, toh 4-way/8-way sweet spot hai. Full associativity sirf chhote structures (TLBs) mein apna kaam karta hai, jahan hit-time penalty tiny hoti hai.

Recall Ek-line self-test

Cache config se sets nikalna ::: $S = C / (B N)$ ; phir index bits $i = lo g_{2} S$ , offset $b = lo g_{2} B$ , tag $t = A - i - b$ . Direct-mapped ko replacement policy kyun nahi chahiye? ::: Har block ke liye ek hi legal line — eviction par koi choice nahi. FIFO mein, kya hit hone par eviction order badalta hai? ::: Nahi — sirf insertion time matter karta hai; hits refresh nahi karte.