Cache organization (direct-mapped) — Hinglish notes

5.4.2 · Hardware › Memory Hierarchy & Caches

Direct-Mapped Cache Kya Hai?

Ek direct-mapped cache sabse simple cache organization hai jahan main memory ka har block exactly ek cache line par map hota hai. Cache location memory address se determine hoti hai using:

$Cache Index = (Block Address) mod (Number of Cache Lines)$

First Principles Se Derivation

Kyun chahiye ye teen address components? Step-by-step build karte hain.

Step 1: Block Offset (Kyun?)

Problem: Memory byte-addressable hai, lekin ek baar mein ek byte fetch karna bus bandwidth waste karta hai.

Solution: Ek cache block fetch karo (multiple consecutive bytes). Agar block size = $2^{b}$ bytes hai, toh lowest $b$ bits block ke andar byte select karte hain.

Formula: $Block Offset = Address mod 2^{b}$

Kyun kaam karta hai: Offset bits har $2^{b}$ bytes par "wrap around" karte hain, naturally bytes 0, 1, 2, ..., $2^{b} - 1$ ko ek block ke andar index karte hain.

Step 2: Cache Index (Kyun?)

Problem: Hamare paas $2^{c}$ cache lines hain. Kisi diye gaye block ko kaun si line hold karni chahiye?

Solution: Block address (address jisme se offset bits hata di gayi hain) ko lines ki sankhya se modulo karo.

Derivation:

Block address = $⌊ \frac{Address}{2 ^{b}} ⌋$
Cache index = Block address $mod 2^{c}$
Binary mein, iska matlab hai address se bits $[b + c - 1 : b]$ extract karo

Formula: $Index = ⌊ \frac{Address}{2 ^{b}} ⌋ mod 2^{c}$

Modulo kyun? Hum chahte hain ki blocks 0, 1, 2, ... cache lines 0, 1, 2, ..., $2^{c} - 1$ se cycle karte rahen, phir wrap back karein line 0 par. Block $2^{c}$ line 0 par map hota hai, block $2^{c} + 1$ line 1 par, wagera.

Step 3: Tag (Kyun?)

Problem: Multiple memory blocks usi cache line par map hote hain (jaise blocks 0, $2^{c}$ , $2 \cdot 2^{c}$ , ... sab line 0 par map hote hain). Hum kaise jaanein ki abhi kaun sa block store hai?

Solution: Tag store karo (remaining high-order bits). Tag un blocks ko distinguish karta hai jo same index par collide karte hain.

Formula: $Tag = ⌊ \frac{Address}{2 ^{b + c}} ⌋$

Kyun kaam karta hai: Agar do addresses ka index same hai lekin tags alag hain, toh wo different blocks hain jo ek hi cache line ke liye compete kar rahe hain. Tag ek "full identifier" ki tarah kaam karta hai jab hum ek cache line par aa jaate hain.

Complete Access Algorithm

1. Extract index bits → cache line L dhundho
2. Valid bit check karo: agar V=0, toh MISS hai (cold miss)
3. Stored tag ko address se compare karo:
   - Match? → HIT, offset use karke data extract karo
   - No match? → MISS (conflict miss), evict karo aur naya block fetch karo

Worked Examples

Common Mistakes (Steel-Man Analysis)

Common mistake Mistake 2: "Tag bits se cache line dhundho"

Sahi kyun lagta hai: Tags blocks identify karte hain, toh pehle unhe lookup karo?

Steel-man: Associative arrays (hash tables) mein aap key se search karte ho. Naturally lagta hai tags bhi aise hi kaam karte hain. Fix: Index bits line determine karte hain (instant, no search). Tags check hote hain baad mein jab aap line par pahunch jaate ho. Isliye direct-mapped fast hai—ek comparison, search nahi.

Memory:

Wrong: Search all tags → find match → use that line
Right: Index → go to line → check its tag

Recall 12-Saal Ke Bacche Ko Samjhao

Socho tumhare paas ek chhoti bookshelf hai jisme 4 shelves hain, lekin ek badi library hai 100 books ki. Sab fit nahi ho sakti, toh ek rule banate ho: "Book number decide karta hai shelf."

Books 0, 4, 8, 12, ... shelf 0 par jaati hain
Books 1, 5, 9, 13, ... shelf 1 par jaati hain
Books 2, 6, 10, 14, ... shelf 2 par jaati hain
Books 3, 7, 11, 15, ... shelf 3 par jaati hain Shelf number index ki tarah hai (book number mod 4). Lekin jab aap shelf 2 par aate ho, toh wahan ek book dikhai deti hai—kya ye book 2 hai, 6 hai, 10 hai, ya 14? Aap book ki spine par label (tag) check karte ho. Agar wo match karta hai jo aap dhundh rahe ho, bahut accha! Agar nahi, toh books swap karo (purani nikalo, nayi laao).

Problem? Agar aap baar baar book 2 maangne lago, phir 10, phir book 2, phir book 10... dono shelf 2 ke liye ladte hain. Har baar jab ek chahiye, doosri wahan hoti hai, toh swap karna padta hai. Yahi hai conflict miss—space khatam nahi hua, balki tumhara simple rule (book number mod 4) unhe ek shelf share karwa deta hai.

Connections

Cache Performance Metrics - Hit rate, miss rate, AMAT directly-mapped caches ke conflict misses par heavily depend karte hain
Set-Associative Caches - Conflict problem solve karte hain multiple blocks per index allow karke (direct-mapped 1-way set-associative hai)
Memory Addressing - Address decomposition (tag/index/offset) spatial aur temporal locality exploitation ki foundation hai
Cache Replacement Policies - Direct-mapped mein koi choice nahi hoti (forced eviction), lekin ye associative caches mein LRU/FIFO se connect hota hai
Cache Write Policies - Write-through vs. write-back direct-mapped caches par apply hoti hain conflicts ke saath additional complexity ke saath

#flashcards/hardware

Direct-mapped cache mein memory address ke teen components kaun se hain? :: Tag (identify karta hai kaun sa memory block), Index (cache line select karta hai), Block Offset (block ke andar byte select karta hai)

Cache index ke liye modulo arithmetic kyun use karte hain?

Infinite memory addresses ko finite cache lines par map karne ke liye wrapping se: blocks 0, C, 2C, ... sab line 0 par map hote hain

Direct-mapped cache mein conflict miss kya hota hai?

Jab do alag memory blocks same cache line par map hote hain (same index, alag tags), repeated evictions cause karte hain chahe baaki lines empty hon

Direct-mapped cache mein cache index ka formula :: Index = (Address / 2^b) mod 2^c, jahan b = block offset bits, c = index bits

Cache access pe agar valid bit = 0 ho toh kya hota hai?

Cold miss (compulsory miss) - line kabhi fill nahi hui; memory se fetch karna padega

Har cache line mein tag kyun store karte hain?

Multiple memory blocks same index par map hote hain; tag distinguish karta hai ki abhi kaun sa block us line mein store hai

Agar cache mein 256 lines hain aur 16-byte blocks hain, toh kitne index bits?

8 bits (log₂(256) = 8) index ke liye, 4 bits (log₂(16) = 4) offset ke liye

Direct-mapped cache mein thrashing kya hai?

Same index lekin alag tags wale addresses par repeated access constant evictions aur reloads cause karta hai, 0% hit rate ke saath

Calculate karo tag bits: 32-bit address, 512 lines, 64-byte blocks :: Tag = 32 - log₂(512) - log₂(64) = 32 - 9 - 6 = 17 bits

Direct-mapped cache fully associative se faster kyun hai?

Sirf ek comparison chahiye (indexed line par tag check karo) vs. sab lines ke tags parallel ya sequentially compare karna