Worked examples — Set-associative and fully associative caches

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

Yeh page ek drill hall hai. Parent note ne tumhe machinery di thi — ki ek address kaise tag, set index aur block offset mein split hota hai, aur direct-mapped, set-associative, aur fully associative caches mein kya fark hai. Yahan hum us machinery par har tarah ke questions throw karte hain taaki koi bhi exam scenario tumhe surprise na kare.

Shuru karne se pehle, ek promise: har symbol wahan explain hoga jahan woh pehli baar aata hai, aur neeche har number verify block mein machine-check kiya gaya hai.

---

Woh symbols jo hum baar baar use karenge

Yeh paanch letters yaad rakho — har example mein exactly inhi mein numbers daale jaate hain.

---

Scenario matrix

Cache-mapping problem ko ek aisi machine samjho jisme teen input dials hain:

• Associativity dial $N$ — ek block kitni jagahon par ja sakta hai: $N=1$ (direct-mapped), $N=$ koi beech ka number (set-associative), ya $N=$ har line (fully associative).
• Address dial — ek specific memory address, jo kahin bhi land kar sakta hai, including kisi boundary par (offset $=0$) ya block ki last byte par.
• Question type dial — "fields decode karo", "kaun sa set?", "hit hai ya miss?", "kitne bits?", ya ek real-world word problem.

Neeche ki table mein har case class list hai jo yeh topic throw kar sakta hai. Baad ke har example mein us cell ka tag lagega jise woh cover karta hai.

Cell	Case class	Kya stress kiya gaya hai
A	$N=1$ (direct-mapped) field decode	associativity ka degenerate low end
B	$N=$ middle (4-way) field decode	normal set-associative case
C	$N=$ sari lines (fully associative)	degenerate high end — koi index field nahi
D	Direct-mapped cache mein do addresses ka collision	conflict-miss ka janam
E	Wohi do addresses 2-way cache mein	associativity se conflict avoid karna
F	Offset = 0 (block boundary) vs offset = max (last byte)	degenerate / limiting offsets
G	Ek hit/miss trace replacement policy ke saath	time ke saath temporal behaviour
H	Word problem — bit budget mein associativity chunna	design decision
I	Exam twist — block size badlo, dekho har field kaisa move karta hai	ek dial ke badle sensitivity

---

Quick vocabulary refresh (taaki kuch bhi unexplained na rahe)

Recall

${\log }_2$ kyun, plain division kyun nahi? ${\log }_2(S)$ ka jawab hai "mujhe $S$ cheezein name karne ke liye kitne yes/no bits chahiye?" ::: Kyunki har bit count ko double karti hai: $k$ bits se $2^k$ cheezein name ho sakti hain, isliye $S$ cheezein name karne ke liye woh $k$ chahiye jisme $2^k=S$ ho, yaani $k={\log }_2(S)$.

Neeche ka field ruler yeh split scale mein dikhata hai (Example B ki widths use karke). Har baad wale example mein, mentally apna address is ruler par rakhna: orange slab right mein low bits leta hai (offset), teal slab beech mein agli bits leti hai (index), aur plum slab left mein baaki rakhta hai (tag). Caption ki yeh reminder note karo ki teen widths hamesha $A$ tak sum karti hain.

---

Example A — Direct-mapped decode (cell A)

Forecast: Pehle andaza lagao — $N=1$ ke saath, kitne sets hain? (Hint: utne hi jitni lines hain.)

1. Lines $L=C/B=32768/32=1024$ (yahan $C=32\text{ KB}=32768$ bytes, $B=32$ bytes). Yeh step kyun? Har line ek $B$-byte block rakhti hai; $C$ bytes mein $C/B$ blocks fit hote hain, toh yahi line count hai.
2. Sets $S=L/N=1024/1=1024$. Yeh step kyun? Direct-mapped matlab ek line per set, isliye sets $=$ lines. Yeh matrix ka degenerate low end hai.
3. Fields: offset $b={\log }_{2}32=5$; index $i={\log }_{2}1024=10$; tag $t=32-10-5=17$. Yeh step kyun? Fields ka sum address width ke barabar hona chahiye; jo offset ya index nahi hai woh tag hai.
4. Decode 0x0000ABCD $=00000000000000001010101111001101_2$.
   • Offset = low 5 bits $=01101_2=13$.
   • Index = agle 10 bits, yaani bits $[14:5]$ $=0101011110_2=350$.
   • Tag = baaki high 17 bits (bits $[31:15]$) $=1$. Yeh step kyun? Hum right se slice karte hain taaki har field apna numeric meaning rakhe: address ko $b$ se right shift karo phir index ke liye $i$ bits mask karo, tag ke liye $b+i$ se right shift karo.

Verify: $17+10+5=32$ ✓. Offset $13$ ek valid byte index hai ($0\le 13<32$) ✓. Line/set $=350$ range $[0,1023]$ mein hai ✓. (Numeric split Verify block mein checked hai.)

---

Example B — 4-way set-associative decode (cell B)

Forecast: Example A se zyada ways — kya tumhein zyada ya kam index bits lagti hain?

1. Lines $L=65536/64=1024$ (yahan $C=64\text{ KB}=65536$ bytes, $B=64$ bytes). Yeh step kyun? Wahi purana rule — capacity divided by block size batata hai kitne blocks fit hote hain.
2. Sets $S=L/N=1024/4=256$. Yeh step kyun? Chaar lines ek set share karti hain, isliye sets ki sankhya lines ki sankhya se ek-fourth hogi. Direct-mapped case se kam sets — index bits shrink hote hain, tag bits grow karti hain.
3. Fields: $b={\log }_{2}64=6$, $i={\log }_{2}256=8$, $t=32-8-6=18$. Yeh step kyun? Offset block ke $64$ bytes cover karta hai, index $256$ sets mein se ek name karta hai, tag bacha hua hai.
4. Decode 0x00DEAD00 $=00000000110111101010110100000000_2$.
   • Offset = low 6 bits $=000000_2=0$.
   • Index = agle 8 bits, bits $[13:6]$ $=10110100_2=180$.
   • Tag = high 18 bits (bits $[31:14]$) $=890$. Yeh step kyun? Wohi right-to-left slicing; sirf field widths badi hain.

Verify: $18+8+6=32$ ✓. Set $180\in [0,255]$ ✓. Offset $0$ matlab address block boundary par baith raha hai — ek cell F limiting case jo yahan bhi ho raha hai (neeche checked).

---

Example C — Fully associative decode (cell C)

Forecast: Jab block kahin bhi ja sakta hai, toh index field ka kya hota hai?

1. Lines $L=16384/64=256$ (yahan $C=16\text{ KB}=16384$ bytes, $B=64$ bytes). Yeh step kyun? Capacity-over-block rule phir se; yeh 256 lines total parking spots hain.
2. Sets $S=1$ (saari lines ek giant set mein). Yeh step kyun? Fully associative $=$ degenerate high end: koi partitioning nahi, isliye index bits $={\log }_{2}1=0$. Index field gayab ho jaata hai.
3. Fields: $b={\log }_{2}64=6$, $i=0$, $t=32-0-6=26$. Yeh step kyun? Offset ke upar sab kuch ab tag hai — tag ko memory ke saare blocks mein se block ko uniquely name karna hoga, kyunki search narrow karne ke liye koi set nahi hai.
4. Decode 0x00DEAD00: offset $=0$; tag $=$ address $\gg 6=228020$.

Verify: $26+0+6=32$ ✓. Usi address par Example B se compare karo: 4-way tag $890$ tha 8-bit index $=180$ ke saath. Yahan tag un 8 index bits ko nigal leta hai, isliye fully-associative tag $890\times 256+180=228020$ ke barabar hai — Verify mein checked. Yahi kahani hai "index bits tag mein migrate ho jaate hain."

---

Example D — Do colliding addresses, direct-mapped (cell D)

Forecast: Do alag addresses, same line — acha hai ya bura?

1. Config: $L=1024/16=64$ lines, $S=64$, $b={\log }_{2}16=4$, $i={\log }_{2}64=6$, $t=16-6-4=6$. Yeh step kyun? Kisi bhi address ko slice karne se pehle field widths chahiye; capacity/block 64 lines deta hai, direct-mapped 64 sets banata hai, toh index 6 bits ka hai.
2. 0x0120 ka index: bits $[9:4]$. 0x0120 $=0000000100100000_2$; low 4 bits offset hain, agle 6 bits $=010010_2=18$. Yeh step kyun? Hum 4 offset bits ke aage right shift karke agle 6 bits padhte hain — yahi set name karta hai.
3. 0x0520 ka index: bits $[9:4]$. 0x0520 $=0000010100100000_2$; agle 6 bits $=010010_2=18$ bhi. Yeh step kyun? Doosre address par same slice; dono $18$ dete hain → dono us set ki ek aur sirf ek line mein map hote hain.
4. Tags alag hain: 0x0120 tag = bits $[15:10]$ $=0$; 0x0520 tag $=1$. Yeh step kyun? Same set, alag tag = dono blocks ek hi line ke liye ladte hain.

Result: Inhe alternately access karne par har baar ek doosre ko evict karte hain → ek endless string of conflict misses, jabki 63 doosri lines khali baithi hain. Yahi parking-lot dard hai jiske baare mein parent note ne warning di thi.

Verify: dono indices $=18$ ✓, tags $0$ aur $1$ (distinct) ✓.

Neeche ki picture exactly yahi dikhati hai: 64 lines ka ek column, sirf line $18$ highlight hai, dono address arrows us ek orange slot par point kar rahe hain. Red caption seedha bolta hai kyun baaki 63 lines madad nahi kar sakti.

---

Example E — Wohi do addresses, ab 2-way mein (cell E)

Forecast: Humne har set mein choices double kar di. Kya ping-pong ruk jaayega?

1. Config: $L=64$, $S=L/N=64/2=32$ sets, $b=4$, $i={\log }_{2}32=5$, $t=16-5-4=7$. Yeh step kyun? Sets halve karne se index window shift ho jaati hai: index ab 5 bits ka hai (bits $[8:4]$), 6 ka nahi, aur jo bit free hui woh tag mein join ho gayi.
2. 0x0120 ka index: bits $[8:4]$. 0000\,0001\,0010\,0000_2 se, 4 offset bits drop karke 5 bits padhne par $10010_2=18$ milta hai. Yeh step kyun? Wohi slicing idea, lekin window ab 5 bits wide hai, toh field ke top par ek bit kam padhi.
3. 0x0520 ka index: bits $[8:4]$. 0000\,0101\,0010\,0000_2 se, 5-bit slice $10010_2=18$ hai. Yeh step kyun? Bit $9$ (jo dono addresses mein alag tha) ab tag ka hissa hai, index ka nahi — isliye dono ab bhi set $18$ share karte hain.
4. Lekin har set mein 2 lines hain. Dono blocks side by side fit ho jaate hain: ek way 0 mein, ek way 1 mein. Koi eviction nahi. Yeh step kyun? Associativity same set mein ek doosra parking spot deta hai, toh shared index ab fight force nahi karta.

Result: Ab alternating accesses pehle do loads ke baad dono hit ho jaate hain. Associativity ne conflict misses ki stream ko hits mein convert kar diya — exactly woh sweet-spot argument.

Verify: dono indices $=18$ ✓; do ways available hain toh dono simultaneously resident hain ✓.

---

Example F — Offset extremes: boundary vs last byte (cell F)

Forecast: $63$ ke fark wale do addresses — same block ya neighbours?

1. $b={\log }_{2}64=6$, toh offset $=$ low 6 bits. Yeh step kyun? Extremes test karne ke liye sirf offset width chahiye; chhe bits block ke 64 bytes count karti hain.
2. 0x1000: low 6 bits $=0$ → uske block ka pehla byte (degenerate zero-offset boundary case). Yeh step kyun? Offset $0$ sabse chhota possible offset hai — block ka starting byte.
3. 0x103F: low 6 bits $=63$ → usi block ka aakhri byte (maximum-offset limiting case). Yeh step kyun? Offset $63=B-1$ sabse bada offset hai, aur bit 5 ke upar ke bits 0x1000 se match karte hain, isliye tag+index identical hain → ek line.
4. Block base address $=$ 0x1000; block 0x1000–0x103F tak phailta hai. Yeh step kyun? Kisi bhi address ke low 6 bits mask kar do, ek hi base milta hai, jo ek shared block confirm karta hai.

Result: 0x1000 par ek single cache miss se saare 64 bytes load ho jaate hain, toh baad mein 0x103F ka access ek hit hota hai — yahi spatial locality concrete form mein hai, aur yeh dono offset limits ($0$ aur $B-1$) ek hi block ke andar dikhata hai.

Verify: offsets $0$ aur $63$ ✓; identical block base (address AND $\neg (B-1)$) ✓.

---

Example G — LRU ke saath Hit/miss trace (cell G)

Forecast: Paanch accesses, do homes, LRU evictions decide kar raha hai. Kitne hits?

Hum set ko [MRU ... LRU] (most-recently-used pehle) track karte hain.

1. A → set khali hai → MISS, A load karo. Set: [A]. Yeh step kyun? Cold start — abhi kuch bhi cache mein nahi hai, toh A ka pehla touch hit nahi ho sakta.
2. B → present nahi, spare way free hai → MISS, B load karo. Set: [B, A]. Yeh step kyun? B ek naya block hai aur set mein abhi ek free way hai, toh bina evict kiye load karte hain; B most-recent ban jaata hai.
3. A → present hai → HIT. A ko front par laao. Set: [A, B]. Yeh step kyun? A step 1 se abhi bhi resident hai; temporal locality kaam aaya, aur LRU order update hota hai toh A ab most-recent hai.
4. C → present nahi, set full → MISS. LRU B hai (peeche) → B evict karo, C load karo. Set: [C, A]. Yeh step kyun? Dono ways full hain, toh hume sabse thanda evict karna hoga; LRU B ko least-recently used mark karta hai.
5. B → present nahi (humne abhi evict kiya tha!) → MISS, LRU = A evict karo, B load karo. Set: [B, C]. Yeh step kyun? B ek access der se wapas aaya — step 4 mein throw out ho gaya tha, toh yeh fresh miss hai; A ab sabse thanda hai aur evict ho jaata hai.

Result: hits $=1$ (sirf step 3), misses $=4$. Final set [B, C].

Verify: hit count $=1$, miss count $=4$, final $=\{B,C\}$ (ek chhote LRU simulator se checked).

Figure in paanch snapshots ko left se right dikhata hai, HIT ko green aur MISS ko orange color karta hai, top box hamesha most-recently-used way hai — dekho B peeche girti hai aur evict ho jaati hai.

---

Example H — Word problem: bit budget mein associativity chunna (cell H)

Forecast: Zyada associativity → bade tags. Kahan tag 20 bits cross karta hai?

1. Lines $L=32768/64=512$. Offset $b=6$. Yeh step kyun? Index bits sets mein kaise split hote hain yeh jaanne ke liye line count chahiye; capacity/block 512 lines deta hai.
2. $N$ ke function ke roop mein tag: sets $S=512/N$, index $i={\log }_2(512/N)=9-{\log }_{2}N$, toh $t=32-i-b=32-(9-{\log }_{2}N)-6=17+{\log }_{2}N.$ Yeh step kyun? $N$ ke har doubling se sets half ho jaate hain, ek index bit remove hoti hai aur tag mein add ho jaati hai — toh tag exactly har doubling par $1$ bit badhta hai.
3. Evaluate karo:
   • $N=1$: $t=17$. ✓
   • $N=2$: $t=18$. ✓
   • $N=4$: $t=19$. ✓
   • $N=8$: $t=20$. ✓ (exactly budget par)
   • $N=16$: $t=21$. ✗ (budget se zyada) Yeh step kyun? Hum har associativity ko $t=17+{\log }_{2}N$ mein plug karke 20-bit ceiling se compare karte hain.
4. Answer: 8-way 20-bit tag budget ke andar highest associativity hai.

Verify: $t(8)=20\le 20$ ✓ aur $t(16)=21>20$ ✗ (dono checked).

---

Example I — Exam twist: block size badlo, har field dekho (cell I)

Forecast: Block double karna — kaunse fields grow karte hain, kaunse shrink?

1. Block 64 B: $b=6$; $L=65536/64=1024$; $S=1024/4=256$; $i=8$; $t=32-8-6=18$. Yeh step kyun? Baseline case: chhote block ke liye standard field computation.
2. Block 128 B: $b={\log }_{2}128=7$; $L=65536/128=512$; $S=512/4=128$; $i=7$; $t=32-7-7=18$. Yeh step kyun? $B$ double karne se ek offset bit add hoti hai (har block twice the bytes cover karta hai) aur line count half ho jaati hai, ek index bit remove hoti hai. Yeh do changes tag par equal aur opposite hain — toh tag $18$ par hi rehta hai.
3. Interpretation:
   • Offset: $6\to 7$ (bade blocks ko ek aur byte-selector bit chahiye).
   • Index: $8\to 7$ (kam, bade blocks → kam sets).
   • Tag: $18\to 18$ (unchanged — shifts cancel ho jaate hain).

Result: Cache size aur associativity fixed rakhne par, block size double karna ek index bit ko ek offset bit ke liye trade karta hai; tag invariant rehta hai. Examiners ko yeh neat fact test karna pasand hai.

Verify: dono tag values $18$ ke barabar ✓; offset $6\to 7$, index $8\to 7$ ✓.

Aakhri figure do field rulers stack karta hai taaki tum dekh sako index aur offset ke beech ki boundary ek bit left slide karti hai jabki tag edge frozen rehti hai — arrow us single migrating bit ko mark karta hai.

---

Wrap-up recall

Recall Jab size fixed rakhe associativity badhti hai, toh index aur tag bits ka kya hota hai?

Index bits $N$ ke har doubling par 1 se shrink hote hain; tag bits $N$ ke har doubling par 1 se grow hote hain; offset unchanged rehta hai. ::: Kyunki $S=L/N$ toh ${\log }_{2}S={\log }_{2}L-{\log }_{2}N$, aur index se jo bit jaati hai woh tag mein add ho jaati hai.

Recall Example G mein, B apni doosri appearance par miss kyun kiya?

Kyunki B ke dono accesses ke beech mein, block C ne eviction force kiya aur LRU ne B (sabse thanda) choose kiya. ::: B ek access der se wapas aaya — yeh ek textbook LRU thrash hai.

Related deeper dives: Cache performance metrics (in hit/miss traces ko AMAT mein convert karo), Write policies (ek store miss kya karta hai), Cache coherence (multiple caches racing), aur Translation Lookaside Buffer (TLB) jo khud ek small fully associative cache hai.