Exercises — Write-allocate vs no-allocate

• (a) Write-allocate — "fetch on write" iska literally doosra naam hai.
• (b) No-allocate — data cache ke around jaata hai.
• (c) No-allocate — bypass = around.
• (d) Write-allocate — modify karne se pehle poora block load karna iska defining move hai.

Sahi hai. Write-back cache ke andar up-to-date copy ko (dirty mark karke) rakhta hai aur memory mein baad mein, eviction par, write karta hai. Ek dirty copy rakhne ke liye tumhare paas pehle ek line honi chahiye — jo exactly wahi hai jo write-allocate provide karta hai. Write-back ko no-allocate ke saath pair karne par deferred write store karne ki koi jagah nahi bachti, jisse immediate memory write forced ho jaata hai (yaani write-through behaviour). Dekho Write-back vs Write-through.

1. Kaunsi line? $0x28=40$. $40\gg 3=5$. $5\%4=1$. → line 1.
2. Line 1 invalid hai → write miss.
3. Write-allocate: memory se 8-byte block 0x28–0x2F fetch karo. → 1 read.
4. Cached line mein 0x28 par byte write karo.
5. Write-back: abhi memory ko mat touch karo; dirty = 1 set karo. Memory traffic: 1 read. Final line 1: valid = yes, dirty = yes.

1. Line 1, invalid → write miss.
2. No-allocate: fetch mat karo, allocate mat karo.
3. Write-through: write seedha memory ko bhejo. → 1 write. Memory traffic: 1 write. Final line 1: abhi bhi invalid (valid = no).

• 0x29 wahi block mein hai jahan 0x28 hai (dono 0x28–0x2F mein).
• Write-allocate case: block pehle se line 1 mein hai → hit, 0 memory traffic. Yahi spatial locality ka fayda hai (dekho Temporal vs Spatial Locality).
• No-allocate case: block kabhi laaya hi nahi gaya → miss, ab block fetch karna padega (1 read).

Pehle, block check. Block number = address $\gg 3$.

• 0x100 = 256, $256\gg 3=32$.
• 0x104 = 260, $260\gg 3=32$.
• 0x108 = 264, $264\gg 3=33$. Alag block!
• 0x10C = 268, $268\gg 3=33$.

Toh 0x100,0x104 block 32 mein hain; 0x108,0x10C block 33 mein hain. Parent note ke Example 3 ne casually kaha tha "sab same block mein" — 8-byte line ke saath yeh galat hai. Hum ise neeche correct karte hain. (Figure dekho.)

Write-allocate + write-back:

• WRITE 0x100: miss → block 32 fetch karo (1 read), write karo, dirty.
• WRITE 0x104: hit (block 32 present) → 0.
• WRITE 0x108: miss → block 33 fetch karo (1 read), write karo, dirty.
• WRITE 0x10C: hit → 0.
• READ 0x100: hit → 0. Block 32 aur 33 lines $32\%4=0$ aur $33\%4=1$ par map hote hain — alag lines, koi eviction nahi, abhi tak koi write-back nahi. Total: 2 reads, 0 writes = 2 operations.

No-allocate + write-through:

• Har write ek miss hai aur seedha memory jaata hai: 4 writes.
• READ 0x100: kabhi cached nahi → miss, 1 read. Total: 1 read + 4 writes = 5 operations.

Write-allocate 2 vs 5 se jeetta hai, kyunki usne har fetched block ko un do writes pe amortise kiya jo usse hit hua aur final read par bhi.

16-byte line ke saath, block number = address $\gg 4$.

• 0x100: $256\gg 4=16$.
• 0x104,0x108,0x10C: $260,264,268\gg 4=16$. Sab block 16 mein! Toh:
• WRITE 0x100: miss → 1 read, dirty.
• Agle teen writes: sab hits → 0.
• READ 0x100: hit → 0. Total: 1 read. Bade lines ne yahan zyada spatial locality capture ki — ek fetch ne chaaron ko cover kar liya. Yeh Cache Line Size se direct link hai.

No-allocate + write-through choose karo (equivalently, non-temporal / Streaming Stores use karo). Kyun: har pixel ek baar likha jaata hai aur kabhi re-read nahi hota → zero temporal locality, toh caching kuch nahi kharidta. Yahan write-allocate ka pollution damage: buffer $1920\times 1080=2,073,600$ pixels hai. Maano 4 bytes/pixel = $8,294,400$ bytes. 64-byte lines ke saath yeh $8,294,400/64=129,600$ distinct blocks hain jo cache se stream hote hain. Ek typical L1 sirf kuch sau lines hi hold karta hai — toh poora cache flush hokar un garbage se refill ho jaata hai jise program kabhi dobara touch nahi karega, genuinely useful data ko evict karta hua. Yahi Cache Pollution hai. No-allocate pixels ko cache se untouched around bhejta hai, aur Write Combining Buffers unhe full-line bursts mein coalesce karta hai. Dekho Streaming Stores.

1. A ko write miss. Humein eventually A ki nai value memory mein pohonchaani hai.
2. No-allocate kehta hai: A ke liye cache line mat banao. Toh modified value ka cache ke andar koi ghar nahi hai.
3. Write-back kehta hai: memory write ko tab tak defer karo jab tak (dirty) line evict na ho jaaye. Lekin step 2 ne humein koi line hold karne ko nahi diya aur koi dirty bit set karne ko nahi diya — defer karne ke liye kuch hai hi nahi jahan se. Store karne ki jagah nahi aur defer karne ka tarika nahi, toh write ko memory mein turant jaana hi padega. Lekin "hit-or-miss write par memory mein turant likhna" write-through ki definition hai. Toh "write-back + no-allocate" silently write-through ban jaata hai — yeh apni alag policy ke roop mein exist hi nahi kar sakta. Isliye write-back ko write-allocate ki zaroorat hai.

Per-write-miss expected cost setup karo.

• No-allocate: region ke har access par (uncached) through-write ka cost lagta hai. Initial miss ka cost $C_{\text{wt}}$ hai, aur agar reuse hoti hai toh ek aur $C_{\text{wt}}$. Expected cost $=C_{\text{wt}}+p{C}_{\text{wt}}$.
• Write-allocate: miss par ek baar fetch pay karo ($C_{\text{fetch}}$) plus ek sasta cache write ($C_{\text{write}}$); agar reuse hoti hai toh woh $C_{\text{wt}}$ ki jagah ek sasta cache access $\approx C_{\text{write}}$ hai. Expected cost $=C_{\text{fetch}}+C_{\text{write}}+p{C}_{\text{write}}$.

Write-allocate tab cheaper hai jab $C_{\text{fetch}}+C_{\text{write}}+p{C}_{\text{write}}<C_{\text{wt}}+p{C}_{\text{wt}}.$ $p$ terms group karo: $C_{\text{fetch}}+C_{\text{write}}-C_{\text{wt}}<p(C_{\text{wt}}-C_{\text{write}}).$ Toh $p^{\star }=\frac{C_{\text{fetch}}+C_{\text{write}}-C_{\text{wt}}}{C_{\text{wt}}-C_{\text{write}}}.$ Plug in karo $C_{\text{fetch}}=100,C_{\text{write}}=1,C_{\text{wt}}=100$: $p^{\star }=\frac{100+1-100}{100-1}=\frac{1}{99}\approx \mathrm{0.0101.}$ Interpretation: kyunki yahan ek through-write ek fetch jitna hi expensive hai, write-allocate ko jeetne ke liye sirf lagbhag 1% reuse chance chahiye. High-fetch / low-reuse wahi ek regime hai jahan no-allocate dominate karta hai. Yeh parent ke decision-framework inequality $P(\text{reuse}\mid \text{write})>\frac{C_{\text{fetch}}+C_{\text{write}}}{C_{\text{wt}}}$ se match karta hai, denominator mein chhoti $C_{\text{write}}$ correction tak.

$p^{\star }=\frac{0+1-100}{100-1}=\frac{-99}{99}=-1.$ Ek negative threshold ka matlab hai "write-allocate $p=0$ ke liye bhi jeetta hai" — kyunki probabilities negative nahi ho sakti, condition $p>-1$ hamesha true hai. Reading: agar fetching free hai, hamesha allocate karo, kyunki tum bina kisi downside ke ek possibly-cheaper future access gain karte ho. $p^{\star }$ ka sign ek quick "kya ek policy unconditionally better hai?" test hai.

Write-allocate ek miss par pehle fetches the whole block, phir write karta hai. No-allocate write ko around the cache to memory bhejta hai. Write-back ko write-allocate ke saath pair karna padta hai kyunki isse dirty copy rakhne ke liye ek line chahiye. Ek write-once frame buffer ke liye sahi policy no-allocate hai taaki cache pollution se bacha ja sake.