Lesson 8 — Intermediate

Cache Memory & Mapping

Cache hi wo jaadu hai jiski wajah se slow RAM ke bawajood CPU fast lagta hai. Is lesson mein hum dekhenge locality kya hoti hai, teeno mapping techniques (direct, fully associative, set associative) kaise kaam karti hain, AMAT ka numerical kaise banta hai, aur write policies kyun matter karti hain.

⏱ 16 min• Intermediate• Memory Hierarchy

Cache kya hai

WHAT

Cache CPU ke paas wali chhoti, ultra-fast memory hai jisme recently ya frequently used data rakha jaata hai. CPU ko zyada tar accesses isi se mil jaate hain, isliye average speed RAM se kam aur register ke karib aati hai.

WHEN

Har memory access pe — cache hit hua toh nanoseconds mein data, miss hua toh RAM jaana padta hai. Ek block (line) aata hai cache mein, ek word nahi.

WHERE

CPU ke andar/edge pe — L1 (sabse chhota+fast, per core), L2 (thoda bada), L3 (cores share karte hain). Iske baad seedha RAM.

Cache ka pura logic locality of reference par chalta hai — programs aksar aas-paas aur wahi cheezein baar baar access karte hain. Is assumption ne hi cache ko possible banaya.

Locality of reference

Temporal locality: jo cheez abhi access hui, wo jaldi phir access hogi (loop ka wahi variable). Isliye use ko cache mein chhod do.
Spatial locality: jis address ke paas access hui, uske aas-paas wale bhi jaldi aayenge (array sequential). Isliye poora BLOCK load karte hain, ek word nahi.
Block/Line size: fixed (4B, 16B, 64B) — spatial locality isi se exploit hoti hai.
Hit: data cache mein mil gaya. Miss: nahi mila → memory se laana padega.
Hit ratio h = hits / total accesses — jitna zyada, utna behtar (0.95+ normal hai).

Yaad rakho: Cache mein unit of transfer BLOCK (line) hai, unit of addressing WORD. Block jitna bada, spatial locality achhi par miss ka penalty bhi bada — GATE mein isi trade-off par question aata hai.

Mapping techniques (direct, associative, set-associative)

1) DIRECT MAPPING : har block ki EK hi jagah fixed
   cache line = (Block number) mod (Total lines)
   Address → | Tag | Line/Index | Block Offset |

   Example : 32-bit address, block size 16 B, cache 64 lines
   offset = log2(16) = 4 bits
   index  = log2(64) = 6 bits
   tag    = 32 - 6 - 4 = 22 bits
   → Line = block# mod 64 (conflict possible — 2 blocks ek line chaahte)

2) FULLY ASSOCIATIVE : block KAHIN bhi aa sakta hai
   Address → | Tag | Block Offset |   (koi index nahi)
   + poore lines parallel compare → MEHNGA (hardware zyada)
   → chhoti memories (TLB, small cache) ke liye ideal

3) SET-ASSOCIATIVE (n-way) : best balance — COMMON
   cache SETS mein divide, block apne set mein kahin bhi
   set = (Block#) mod (Total sets)
   Address → | Tag | Set index | Block Offset |
   2-way = har set mein 2 lines, 4-way = 4 lines
   Direct = 1-way, Fully assoc = lines-way (special cases)

Ek line mein: Direct = fixed parking, Fully assoc = free parking, Set-associative = section-wise free parking. Real CPUs 4-way se 16-way set associative use karte hain — conflict aur hardware dono ka balance.

GATE trap: Tag/offset/index bits ka numerical sabse poochha jaata hai. Offset = log2(block size), index = log2(number of sets/lines direct mein), baaki tag. Direct mapping mein jyada conflicts — isi liye mapping ka choice performance decide karta hai.

Hit ratio, AMAT aur write policies

AMAT (Average Memory Access Time) :
  AMAT = Hit time + (Miss rate × Miss penalty)
       = Hit time + (1 - h) × Miss penalty

Example : hit = 1 ns, h = 0.98, miss penalty = 100 ns
  AMAT = 1 + 0.02 × 100 = 3 ns

Two-level (L1 + L2) :
  AMAT = T_L1 + missrate_L1 × (T_L2 + missrate_L2 × penalty)

Effective speedup : non-pipeline memory time vs AMAT

WRITE POLICIES :
  Write-through : har write CACHE + MEMORY dono mein
                  → consistent, bus traffic zyada
  Write-back    : sirf cache mein, dirty bit = block badla hua
                  → block evict hone pe memory mein (kam traffic)
  Write-allocate : miss aane pe block pehle cache mein laao, phir write
  No-write-allocate : write miss pe seedha memory (cache mein mat lao)

AMAT kam karo teen tariko se: hit time kam, miss rate kam (badi/associative cache), miss penalty kam (multilevel cache).
Write-back default hai zyada tar modern CPUs mein — bus bandwidth bachti hai.
L1 split: instruction (L1I) + data (L1D) — Von Neumann bottleneck ka ilaaj.

Numerical rule: Miss rate = 1 − hit ratio, aur AMAT mein hit time + miss portion hi aata hai. Agar do caches ke numbers dein toh L1 ke miss pe L2 ka time bhi jodna — ye step exams mein aksar bhool jaate hain.

Exercise

Question: Block size 8 bytes hai toh block offset bits kitne honge? Sirf number daalo.

Question: Hit time 1 ns, hit ratio 0.95, miss penalty 50 ns — AMAT kitna (ns, sirf number)?

Question: Write-through policy mein write kahan hoti hai — sirf cache mein ya cache + memory dono mein?

Common mistakes

Direct mapping mein formula ulta bolna: Line number = block number MOD total lines (mod nahi divide). Aur index bits log2(lines) hain — ye do exam mein ghoom ke aate hain.
AMAT mein hit time chhod dena: AMAT = hit time + miss rate × penalty. Sirf miss portion likhna common galti hai — hamesha hit time add karo.
Write-back aur write-through confuse karna: Write-through = har write turant memory mein (safe, slow). Write-back = block ke time (fast, dirty bit chahiye).

Desi example: Phone ke recent apps

Tumhara phone bhi cache jaisa chalta hai — jo app abhi khola tha wo turant khulta hai:

Recent apps = cache lines
App dobara kholna (temporal locality) = cache HIT
Naya app = MISS → load from storage (penalty)
Swipe se aas-paas ke apps (spatial) = block prefetch
App kill kar di = evict — dirty apps save hoti hain (write-back)

Exam mapping (GATE / TCS / UGC)

GATE: tag/index/offset bits ka numerical — COA ka sabse frequent question.
GATE: AMAT calculation (single ya multilevel cache).
UGC-NET: mapping techniques ke types aur comparison.
Trap: "Fully associative mapping needs index bits" — galat, usme index field hi nahi hota.

Lesson complete?

Cache mapping aur AMAT clear. Agla lesson — Virtual Memory — mein dekhenge chhoti RAM pe bade programs kaise chalte hain (paging, segmentation, TLB).