Write-allocate vs no-allocate: Visual walkthrough — Hinglish deep dive

5.4.7 · D2 · Hardware › Memory Hierarchy & Caches › Write-allocate vs no-allocate

Yeh parent topic ka visual companion hai. Isse dheerey padhna; har step mein ek picture hai jo argument ko carry karti hai.

Step 0 — Vocabulary, use se pehle drawn

Jab tak hum "write miss" ki baat kar sakein, humein teen plain pictures chahiye. Yahan kuch bhi assume nahi kiya gaya.

Definition Jo words hum use karenge, zero se

Memory — boxes ka ek lamba numbered street. Har box ka ek address hota hai (uska house number) aur woh ek byte hold karta hai (0–255). Hum ek aisa address $A$ bolenge — $A$ ko "jo bhi box processor ne abhi poke kiya" ka stand-in naam samjho.
Cache — ek choti, fast shelf jo kuch boxes ki copies rakhti hai taaki processor ko baar baar street ke doosre chor tak jaana na pade.
Cache line (block) — cache kabhi akela box copy nahi karta. Woh ek saath poora chunk of neighbours copy karta hai; is page pe ek line 8 boxes milke hoti hai. Woh chunk ek cache line hai. (Dekho Cache Line Size.)
Dirty bit — shelf line pe laga ek single flag jiska matlab hai "yeh shelf copy change ho chuki hai aur ab memory se newer hai." Jab memory aur shelf agree karte hain, line clean hai; jaise hi aap uspe write karte ho, woh dirty ho jaati hai jab tak flush na ho. (Zyada detail Dirty Bit mein.)
Hit — jo box chahiye woh pehle se shelf pe hai. Fast.
Miss — box shelf pe nahi hai. Aapko memory tak jaana padega.
Write — processor kisi box ki value change karna chahta hai.

Picture dekho: lamba grey street memory hai, choti yellow shelf cache hai, aur dashed bracket ek line = 8 neighbouring boxes dikhata hai jo ek unit ki tarah copy hoti hain. Akela blue arrow ek write hai jo ek aisi box pe land ho raha hai jo shelf pe nahi hai — yeh ek write miss hai, aur yeh ek hi situation hai jiske baare mein yeh poora page hai.

Recall Hum sirf write

misses ki kyun chinta karte hain? Kyunki write hit boring hai — box pehle se shelf pe hai, aap bas use change karo. ::: Interesting decision (neighbourhood fetch karo, ya nahi?) sirf tab aata hai jab box cache mein absent ho.

Step 1 — Fork: write miss humein kya decide karne par majboor karta hai

KYA. Ek write miss abhi hua. Ab hume do behaviors mein se ek choose karna hai.

KYUN. Cache choti hai. Shelf pe jo bhi byte daalo, koi doosra byte bahar nikalta hai. Toh "kya is likhey hue byte ko shelf spot milni chahiye?" yeh ek real cost question hai, free choice nahi.

PICTURE.

Blue write ek empty line pe hit karta hai. Fork se do chalk arrows nikalte hain:

Left road — write-allocate (fetch-on-write bhi kehte hain): poori 8-box block shelf pe kheecho, phir ek byte change karo.
Right road — no-allocate (write-around bhi kehte hain): byte ko shelf ke around bhej do, seedha memory mein. Shelf khali rehti hai.

Neeche sab kuch sirf dono roads ke consequences count karna hai.

Step 2 — Road A traced: write-allocate, box by box

KYA. Left road follow karo ek single write ke liye address 0x28 pe (value 0xFF), ek aisi cache pe jisme 8-byte lines hain.

KYUN. Hume dekhna hai ki poori block fetch karna — sirf ek byte nahi — kyun unavoidable hai.

PICTURE.

Numbered chalk arrows trace karo:

0x28 pe Miss — target line empty hai.
Poori block 0x28–0x2F (saare 8 neighbours) memory se upar Fetch karo. Yeh pink "read" arrow hai jo upar ja raha hai.
Shelf pe 0x28 wale byte mein 0xFF Write karo (blue).
Mark dirty — Step 0 mein define kiya gaya dirty bit set ho jaata hai, jo yeh flag karta hai ki yeh shelf copy memory se newer hai.

Abhi tak ka cost: exactly 1 memory read (8 bytes). Memory mein abhi zero writes — dirty byte shelf pe wait kar raha hai.

Step 3 — Road B traced: no-allocate, box by box

KYA. Wahi write 0x28 pe, ab right road pe, write-through ke saath paired.

KYUN. Dekhne ke liye ki shelf khali rehti hai aur byte use skip karta hai.

PICTURE.

0x28 pe Miss.
No-allocate — shelf ko bilkul mat chhuao.
Write-through — byte neeche pink arrow se seedha memory box 0x28 mein flow karta hai.
Cache line empty (invalid) rehti hai.

Abhi tak ka cost: 1 memory write. Koi read nahi, koi fetch nahi, koi shelf space use nahi.

Recall Side-by-side, ek single write mein dono ko kya cost aayi?

Write-allocate: 1 read (8 neighbours kheech laaye). ::: No-allocate: 1 write (sirf byte). Ek isolated write ke liye no-allocate sasta hai — allocate ka payoff sirf tab aata hai jab neighbours reuse hote hain, jo Step 5 mein hai.

Step 4 — Forced marriage: kyun write-back write-allocate maangta hai

KYA. Ab hum ek pairing rule prove karte hain, sirf state nahi karte. Write-back sirf write-allocate ke saath ho sakta hai.

KYUN. Write-back ka matlab hai: "Main shelf pe single fresh copy rakhta hoon aur use memory mein baad mein likhta hoon, jab line evict ho." Aao ise no-allocate ke saath combine karne ki koshish karte hain aur dekhte hain kaise tootta hai.

PICTURE.

Board pe contradiction follow karo:

Write-back ka promise: abhi memory mein mat likho — baad mein, shelf se likho.
No-allocate ka rule: byte shelf pe nahi hai.
Toh "baad mein shelf se likho" impossible hai — shelf pe koi copy hai hi nahi jo baad mein likhi jaaye. Iska ek hi escape hai: abhi memory mein likho.
Lekin "abhi memory mein likho" write-through behavior hi hai!

Step 5 — Sab kuch decide karne wali counting: ek block pe chaar writes

KYA. 0x100, 0x104, 0x108, 0x10C likho (sab ek hi 8-byte line ke andar — line 0x100–0x107... ruko, neeche arithmetic check karo), phir 0x100 padho. Har road pe memory trips count karo. Yeh payoff calculation hai.

KYUN. Ek isolated write ne no-allocate ko favour kiya (Step 3). Lekin real programs neighbours likhte hain — yeh spatial locality hai. Hume dekhna hai tally kaise flip hota hai.

PICTURE.

Do chalk columns padho (ab charon writes genuinely line 0x100–0x107 share karte hain):

Step	Write-allocate + write-back	No-allocate + write-through
write `0x100`	miss → 1 read (fetch line)	miss → 1 write
write `0x102`	hit (same line, shelf pe)	miss → 1 write
write `0x104`	hit	miss → 1 write
write `0x106`	hit	miss → 1 write
read `0x100`	hit	miss → 1 read
Total	1 memory trip	5 memory trips

Gap kyun hai. Left side pe, ek fetch ne poori line 0x100–0x107 shelf pe kheench li, toh writes 2–4 aur final read sab free hits hain kyunki woh usi line mein land karte hain. Right side pe, har byte ek fresh independent trip hai kyunki kuch bhi kabhi cache nahi hota. Spatial locality exactly wahi hai jo write-allocate monetize karta hai.

$allocate: ek baar fetch 1 vs no-allocate: har access ek trip 4 + 1$

Step 6 — Teesra quadrant: write-through + write-allocate

KYA. Humne write-allocate+write-back (Step 2/5) aur no-allocate+write-through (Step 3) trace kiya. Bacha hua valid combination hai write-through + write-allocate — miss pe line fetch karo, lekin phir bhi har write immediately memory mein push karo.

KYUN. Step 4 ne write-back+no-allocate ko contradiction ki tarah kill kar diya. Lekin write-through+write-allocate perfectly consistent hai, aur yeh design grid ka aakhri box fill karta hai, taaki reader kisi un-shown quadrant se kabhi na mile.

PICTURE.

Is road pe, wahi four-write-then-read sequence aisa behave karta hai: pehla write miss karta hai aur line fetch karta hai (1 read), toh baad ke saare writes read-hits hain — lekin kyunki yeh write-through hai, har write memory mein bhi spill karta hai (4 writes), aur final read ek hit hai.

	write-through + write-allocate
write `0x100`	miss → 1 read (fetch) + 1 write-through
write `0x102`	hit + 1 write-through
write `0x104`	hit + 1 write-through
write `0x106`	hit + 1 write-through
read `0x100`	hit
Total	1 read + 4 writes = 5 trips

Step 7 — Degenerate case: streaming writes, jahan tally wapas flip ho jaata hai

KYA. Ab ek huge array ek baar likho aur kabhi read mat karo — jaise ek video frame buffer.

KYUN. Yeh woh case hai jo naive "allocate always wins" ko todta hai. Jab reuse probability zero ho, toh Step 2 ka fetch kuch nahi khareedta aur actively harm karta hai.

PICTURE.

for (int i = 0; i < 1920*1080; i++)
    framebuffer[i] = pixel_value;   // ek baar likha, kabhi nahi padha

Write-allocate road pe, har nayi line ek useless fetch trigger karti hai (woh pixels padh raha hai jo hum poori tarah overwrite karne wale hain), aur worse, woh shelf se genuinely useful data evict kar deta hai — yeh cache pollution hai. Right road (no-allocate) dono se bachta hai.

Isliye CPUs non-temporal / streaming store instructions offer karte hain (jaise movnti), jo often write-combining buffers se drain hote hain taaki kaafi saare bytes phir bhi kuch wide memory writes ki tarah nikle.

Ek-picture summary

Final board poori derivation compress karta hai: fork (Step 1), ek write ke do costs (Steps 2–3), write-back ke saath forced marriage (Step 4), complete 2×2 grid (Steps 5–6), aur streaming degenerate case (Step 7).

Recall Feynman retelling — ek story ki tarah bolo

Memory ek lamba numbered boxes ka street hai; cache ek tiny fast shelf hai jo sirf ek baar mein poori line of 8 neighbouring boxes grab karti hai. Jab aap ek aisi box pe write karte ho jo shelf pe nahi hai, toh aapko ek fork milta hai. ::: Road one, write-allocate: poori 8-box line upar kheecho (ek read), apna byte shelf pe change karo, use dirty flag karo. Abhi ek read cost aata hai, lekin usi line ke andar baad mein jo bhi neighbour touch karo woh free hit hai — toh line 0x100–0x107 ke andar chaar bytes likhna plus ek wapas padhna sirf ek memory trip hai (jab write-back ke saath paired ho). ::: Road two, no-allocate: byte ko shelf se seedha memory mein dhakelo. Shelf khali rehti hai. Ek isolated write is tarah sasta hai, lekin chaar bytes likhna aur ek wapas padhna paanch alag trips hai. ::: Line boundary se savdhaan raho: 8-byte lines ke saath, 0x108 ek nayi line shuru karta hai, toh "kareeb" kaafi nahi — addresses ko hits hone ke liye ek hi 8-aligned window share karni chahiye. ::: Grid mein chaar corners hain. Write-back write-allocate pe force hai (no-allocate write ko immediately bahar leak kar deta aur secretly write-through ban jaata). Write-through dono taraf ja sakta hai: allocate ke saath woh future reads ke liye shelf copy rakhta hai jabki phir bhi har write memory mein spill karta hai; no-allocate ke saath woh shelf ko bilkul bypass kar deta hai. ::: Rule: agar aap jaldi neighbourhood reuse karoge, reel it in (allocate). Agar aap sirf data stream kar rahe ho ek baar aur kabhi wapas nahi dekhna, shelf skip karo (no-allocate) taaki use garbage se pollute na karo ya aise fetches ka price na chukao jo tum turant overwrite kar doge.

Reveal-line quick checks:

Write miss ka matlab hai target box

abhi cache shelf pe nahi hai (cache se absent hai).

Write-allocate ka unavoidable upfront cost hai

poori line fetch karne ke liye ek memory read.

Write-back ko write-allocate ke saath pair karna zaroori hai kyunki

use defer karne ke liye shelf copy chahiye, jo no-allocate banane se mana karta hai.

Ek 8-byte line mein chaar writes aur ek read ke liye, allocate+write-back cost karta hai

1 memory trip vs no-allocate ke liye 5.

8-byte lines ke saath, 0x108 aur 0x100

alag alag lines mein hain (boundary har 8 ke multiple pe).

Streaming stores no-allocate prefer karte hain taaki

cache pollution aur useless fetch bandwidth se bacha ja sake.