Cache lines, tags, index, offset

4.1.10 · Coding › Computer Architecture (Deep)

Cache ko address slice kyun karna padta hai?

Main memory (DRAM) bahut badi lekin slow hai (~100 ns). CPU ~0.3 ns/cycle par chalta hai. Agar har load DRAM ka wait karta, toh CPU 99% time idle rehta. Isliye hum CPU ke paas hot data ki tiny copy rakhte hain.

Lekin cache, memory se bahut choti hai, isliye bahut saare memory addresses ko same cache slot share karna padta hai. Hardware ko ek fast, wiring-only tarika chahiye (koi arithmetic nahi, koi search nahi) jo:

1. Decide kare ki koi given address kaunse slot mein map hoga → index.
2. Confirm kare ki us slot mein jo data baitha hai, woh actually wahi address hai jo hum chahte hain → tag.
3. Fetch kiye gaye block ke andar exact byte(s) select kare → offset.

Hardware mein bits ko slice karna free hai (sirf wires), isliye yeh scheme jeeitti hai.

Cache line / block kya hota hai?

Teen fields ko scratch se kaise derive karein

Maan lo ek byte-addressable memory hai $n$-bit addresses ke saath, ek cache jo $S$ sets (rows) rakhta hai, aur har line ka size $B$ bytes hai.

Step 1 — Offset bits. $B$ bytes ke ek block ke andar hum har byte ko naam dena chahte hain. Distinct bytes ki sankhya $=B$, isliye hum chahte hain $\text{offset bits}={\log }_{2}B.$ Yeh step kyun? $0$ se $B-1$ tak count karne ke liye exactly ${\log }_{2}B$ bits chahiye.

Step 2 — Index bits. Offset hatane ke baad, block number hai $\lfloor A/B\rfloor$. Hum har block number ko $S$ sets mein se kisi ek mein map karna chahte hain. Hardware block number ke low bits use karta hai (taaki consecutive blocks sets mein spread ho jaayein): $\text{index bits}={\log }_{2}S.$ Yeh step kyun? ${\log }_{2}S$ bits, $S$ rows ko address karte hain; low bits isliye use hote hain taaki adjacent blocks collide na karein.

Step 3 — Tag bits. Jo bhi address bits bachi hain, woh uniquely identify karti hain ki is set mein map hone wale kitne blocks mein se kaun sa currently stored hai: $\text{tag bits}=n-{\log }_{2}S-{\log }_{2}B.$ Yeh step kyun? Index/offset ke liye use na hue saare address bits ko identity verify karne ke liye store aur compare karna padta hai.

Associativity (jahan se $S$ aata hai)

Cache mein $L$ total lines hoti hain. Unhe ways mein group karo:

• Direct-mapped ($1$-way): har set mein $1$ line, isliye $S=L$.
• $w$-way set-associative: har set mein $w$ lines, isliye $S=L/w$.
• Fully associative: ek bada set, $S=1$ ⇒ 0 index bits, sab kuch tag hai.

Worked Example 1 — Direct-mapped

Cache: $L=256$ lines, $B=64$ B, direct-mapped, 32-bit addresses.

• Offset $={\log }_{2}64=6$ bits. Kyun? 64 bytes per line.
• Sets $S=L=256$ (direct-mapped) ⇒ index $={\log }_{2}256=8$ bits. Kyun? 1 line per set.
• Tag $=32-8-6=18$ bits. Kyun? bache hue bits.

Address 0xDEADBEEF = 1101 1110 1010 1101 1011 1110 1110 1111.

Low 14 bits (= 8 index + 6 offset) ko carefully peelо. Address ke aakhri 14 bits hain 11 1110 1110 1111:

• Offset = low 6 bits = 101111 = 0x2F (line mein byte 47). Kyun? lowest ${\log }_{2}B$ bits.
• Index = agle 8 bits = 11111011 = 0xFB = set 251. Kyun? agle ${\log }_{2}S$ bits. (Boundary dhyan se dekho: offset bottom 6 bits khata hai, isliye index bits 13..6 par hai, jo 11111011 padhta hai, na ki 10111011.)
• Tag = top 18 bits, set 251 mein stored value se compare kiya jaata hai.

Worked Example 2 — 4-way set-associative

Same numbers lekin 4-way: $L=256$, $w=4$, $B=64$, 32-bit.

• Offset $=6$ (unchanged — sirf $B$ par depend karta hai).
• Sets $S=L/w=256/4=64$ ⇒ index $={\log }_{2}64=6$ bits. Kyun? ab kam sets hain.
• Tag $=32-6-6=20$ bits. Kyun? index ne 2 bits khoe, tag ne 2 bits paaye.

Worked Example 3 — total bits stored

4-way cache ke liye: har line ek valid bit aur tag bhi store karti hai. Bits per line $=\text{data}(64\times 8)+\text{tag}(20)+\text{valid}(1)=512+21=533$ bits. Total = $256\times 533=136,448$ bits of SRAM. Kyun? overhead (tag+valid) actual silicon cost hai — badi lines overhead ko amortize karti hain lekin agar locality poor ho toh bandwidth waste hoti hai.

Common mistakes (Steel-manned)

Flashcards

Connections

• Cache associativity & replacement policies
• Spatial and temporal locality
• Memory hierarchy and latency numbers
• Virtual vs physical addressing (VIPT/PIPT)
• Cache coherence (MESI)
• TLB and page tables — same "address split karo, lookup karo, verify karo" pattern

Concept Map