Write-allocate vs no-allocate: Worked examples — Hinglish deep dive

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

Yeh page Write-allocate vs no-allocate ki practice ground hai. Parent note ne idea explain kiya; yahan hum har us situation ko grind karte hain jo ek write miss create kar sakta hai aur har baar memory traffic count karte hain.

Kuch bhi karne se pehle, in words ko pin down karte hain taaki koi symbol bina wajah use na ho.

Scenario matrix

Har write-miss situation jo yeh topic aap par throw kar sakta hai, in cells mein se ek mein aati hai. Jo examples follow karte hain woh sab us cell ke saath tagged hain jo wo cover karte hain, aur mil kar yeh sab ko hit karte hain.

#	Case class	Kya special hai	Policy jo shine kare	Example
A	Single isolated write, jald reuse hoga	temporal locality present	write-allocate + write-back	Ex 1
B	Single isolated write, kabhi reuse nahi	zero temporal locality	no-allocate + write-through	Ex 2
C	Ek block par writes ka cluster, phir read	spatial locality	write-allocate	Ex 3
D	Kai blocks mein streaming writes	data cache se bada	no-allocate / Streaming Stores	Ex 4
E	Degenerate: same address par do baar write	kya 2nd hit hai?	dono — hit logic test karta hai	Ex 5
F	Boundary: block edge par straddling write	offset line size ke paas	block granularity reveal karta hai	Ex 6
G	Eviction / dirty writeback	line already dirty, conflict	write-back cost accounting	Ex 7
H	Word-problem (real workload)	ek policy choose karo & justify karo	decision framework	Ex 8
I	Exam twist: forbidden combo	write-back + no-allocate	dikhata hai yeh illegal kyun hai	Ex 9

Jab tak alag na bataya jaaye, poore note mein yeh cache use hogi: 4 lines, 8 bytes/line, direct-mapped, shuruaat mein khaali.

Cell A — isolated write, jald reuse hoga

Worked example Example 1 · write-allocate + write-back

Statement. Address 0x28 par 0xFF write karo. Phir 0x29 read karo. Write-allocate + write-back ke under memory traffic count karo.

Forecast: abhi andaza lagao — memory tak total kitne trips? Reads? Writes?

Block locate karo. $index = ⌊ 0 x 28/8 ⌋ mod 4 = (5) mod 4 = 1$ . Offset $= 0 x 28 mod 8 = 0$ . Yeh step kyun? Hum hit ya miss kehne se pehle yeh jaanna zaroori hai ki kaun sa slot check karein.
Line 1 check karo. Khaali cache ⇒ valid bit 0 ⇒ write miss. Kyun? Miss hi policy branch trigger karta hai.
Allocate + fetch. Memory se poora 8-byte block 0x28–0x2F line 1 mein read karo. → 1 memory read. Poora block kyun? Cache sirf line-sized units mein data move karta hai; aap sirf ek byte hold nahi kar sakte.
Cache mein write karo offset 0 par: byte 0xFF ho jaati hai. Dirty bit = 1 set karo (memory abhi update nahi hui). Write-back kyun? Write-back memory write ko eviction tak defer karta hai — dekho Write-back vs Write-through.
0x29 read karo. Same block, already valid ⇒ hit, zero traffic. Hit kyun? Hamne step 3 mein neighbour 0x29 free mein fetch kiya tha — yahi spatial locality ka faayda hai.

Verify karo: memory reads = 1, writes = 0 (abhi tak kuch evict nahi hua). Total = 1. Baad wala read kuch cost nahi aaya — exactly woh faayda jo write-allocate promise karta hai.

Cell B — isolated write, kabhi reuse nahi hoga

Worked example Example 2 · no-allocate + write-through

Statement. 0x28 par 0xFF write karo, phir 0x28 read karo. No-allocate + write-through ke under traffic count karo.

Forecast: kya read hit hoga ya miss? Kitne trips?

Locate & check karo. Index 1, khaali ⇒ write miss (Ex 1 jaisa hi).
No-allocate: cache skip karo. Fetch mat karo, line allocate mat karo. Kyun? Hum maante hain temporal locality kam hai, toh yahan ek cache line waste hogi — yeh Cache Pollution se bachna hai.
Write-through: seedha memory mein jao. → 1 memory write. Line 1 invalid rahegi. Kyun? No-allocate data aur kahin nahi rakh sakta, toh yeh abhi memory mein jaana zaroori hai.
0x28 read karo. Line 1 abhi bhi invalid ⇒ miss → 1 memory read. Miss kyun? Humne jaanbujhkar block kabhi laya hi nahi.

Verify karo: reads = 1, writes = 1, total = 2. Yahan read miss hua — lekin is cell ka assumption hai ki hum normally dobara read nahi karte; jab karte hain, no-allocate haar jaata hai. Yahi sahi trade visualise ho rahi hai.

Cell C — ek block par cluster, phir read (spatial locality)

Worked example Example 3 · ek block mein chaar writes

Statement. 0x100, 0x104, 0x108, 0x10C par writes (sab ek block mein), phir 0x100 read karo. Dono policy pairs compare karo.

Forecast: kaun si policy 5 trips bhejegi aur kaun si 1?

Pehle confirm karo ki yeh sab ek block share karte hain. $⌊ 0 x 100/8 ⌋ = 0 x 20$ , $⌊ 0 x 10 C /8 ⌋ = ⌊ 268/8 ⌋ = 33 = 0 x 21$ .

Write-allocate + write-back:

0x100: miss → block 0x20 fetch karo (1 read), write karo, dirty.
0x104: same block → hit.
0x108: miss → block 0x21 fetch karo (1 read), write karo, dirty.
0x10C: same block 0x21 → hit.
0x100 read: block 0x20 valid → hit. Kyun? Har block ek baar fetch hota hai; neighbours free mein saath aa jaate hain. → reads = 2, writes = 0. Total = 2.

No-allocate + write-through: 1–4. har write cache bypass karta hai → 4 writes. 5. 0x100 read: kuch cached nahi → 1 read. → Total = 5.

Verify karo: write-allocate 2 vs no-allocate 5. Write-allocate jeet jaata hai kyunki yeh ek fetch ko kai kareeb writes par amortise karta hai — spatial locality kaam aa rahi hai.

Cell D — kai blocks mein streaming

Worked example Example 4 · ek frame-buffer sweep

Statement. 0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38 (8 distinct blocks) mein se har ek mein ek baar write karo, kabhi read mat karo. Cache sirf 4 lines hold karti hai. Policies compare karo.

Forecast: sirf 4 lines aur 8 blocks ke saath, kya write-allocate kuch bhi useful rakh paata hai?

Write-allocate + write-back:

Blocks 0x00,0x08,0x10,0x18 indices $0, 1, 2, 3$ par map hote hain: 4 fetches (4 reads), 4 dirty lines.
0x20 → index $⌊ 4 ⌋ mod 4 = 0$ : conflict — dirty line 0 evict hoti hai → 1 write-back, phir fetch ke liye 1 read. 0x28(idx1), 0x30(idx2), 0x38(idx3) ke liye bhi same: har ek 1 writeback + 1 read hai. Itna bura kyun? Hum koi data nahi rakhte (kabhi read nahi karte), phir bhi fetch aur evict karne ki cost pay karte hain — pure overhead. → reads $= 4 + 4 = 8$ , writes (evictions) $= 4$ . Total = 12.

No-allocate + write-through:

8 writes cache completely bypass karte hain → 8 writes, 0 reads. Total = 8.

Verify karo: no-allocate 8 vs write-allocate 12. Streaming mein zero reuse hota hai, toh allocate karna sirf fetch + eviction cost add karta hai. Exactly isliye Streaming Stores aur Write Combining Buffers exist karte hain.

Cell E — degenerate: same address par do baar write

Cell F — boundary: block edge par straddling write

Cell G — dirty line ki eviction

Worked example Example 7 · dirty writeback cost

Statement. Write-allocate + write-back ke under: 0x28 (index 1) write karo, phir 0x48 write karo. Total traffic kya hai?

Forecast: 0x48 ka index — aur kya purani dirty line cost karti hai?

0x28 write karo: index 1, miss → fetch karo (1 read), dirty line 1.
0x48 write karo: $⌊ 0 x 48/8 ⌋ = ⌊ 72/8 ⌋ = 9$ , index $9 mod 4 = 1$ . Same slot, occupied by ek dirty line. Conflict kyun? Alag block, same index — direct-mapped mein har index par sirf ek slot hota hai.
Line 1 evict karo: yeh dirty hai ⇒ write it back (1 write), phir 0x48 ke block ke liye fetch karo (1 read), write karo, dirty. Pehle write back kyun? Write-back ne pehle wala 0x28 change kabhi nahi gumaya; slot reuse hone se pehle yeh save hona zaroori hai, warna data corrupt hoga.

Verify karo: reads = 2, writes = 1. Total = 3. Write-through se compare karo, jo 0x28 write immediately pay karta aur kabhi dirty writeback ki zaroorat nahi hoti.

Cell H — real-world word problem

Worked example Example 8 · ek policy choose karo

Statement. Ek logging system sequentially ek file buffer mein 64-byte records append karta hai, disk par flush hote hain aur CPU kabhi re-read nahi karta. Records total 100 MB hain; cache 1 MB hai. Kaun si policy, aur relative traffic estimate karo?

Forecast: allocate karein ya nahi?

Access pattern: pure sequential writes, koi reads nahi ⇒ zero temporal, aur data (100 MB) ≫ cache (1 MB) ⇒ koi line survive nahi karti reuse hone ke liye. Kyun matter karta hai: yeh streaming signature hai (Cell D at scale).
Framework apply karo parent se: write-allocate tabhi use karo jab $P (reuse ∣ write)$ high ho. Yahan yeh ≈ 0 hai.
Decision: no-allocate (non-temporal stores). Har 64-byte record ke liye ek write.
- Write-allocate additionally har 64-byte block read karta (100 MB ka pointless fetch) aur baad mein evict karta.
- Toh write-allocate traffic ≈ no-allocate ka $2 \times$ (har useful write ke liye ek fetch + ek writeback).

Verify karo: no-allocate ≈ 100 MB written; write-allocate ≈ 100 MB read + 100 MB written = 200 MB. Ratio 2:1 no-allocate ke favour mein — "streaming ⇒ bypass cache" rule se match karta hai aur 1 MB cache ki Cache Pollution se bachata hai.

Cell I — exam twist: forbidden combination

Worked example Example 9 · write-back + no-allocate illegal kyun hai

Statement. Ek student write-back + no-allocate propose karta hai. Ek write miss trace karo aur contradiction dikhao.

Forecast: kahan toot ta hai?

A par write miss.
No-allocate kehta hai: A ko cache mein mat daalo.
Write-back kehta hai: memory tab hi touch karo jab ek dirty cached line evict ho. Yeh deadlock kyun hai: data cache mein nahi hai (step 2), toh write-back ke paas defer karne ke liye kuch nahi — phir bhi write-back abhi memory mein likhne se mana karta hai.
Iska single escape hai memory mein turant likhna — lekin yeh literally write-through behaviour hai.

Verify karo: combination write-through mein collapse ho jaata hai, toh yeh ek alag valid policy nahi hai. Isliye parent ki identity $Write-back \Leftrightarrow Write-allocate$ hold karti hai. Dekho Write-back vs Write-through.

Recap

Recall Pure streaming writes ke liye kaun sa cell jeet ta hai?

No-allocate — zero reuse ka matlab hai allocation sirf fetch + eviction cost add karta hai. (Cell D / Ex 4)

Recall Ex 3 mein write-allocate 1 nahi, 2 reads kyun cost hua?

0x100–0x10C do blocks (0x20 aur 0x21) par span karta tha, har ek ek baar fetch hua.

Prior allocation ke baad write-allocate hit ka traffic count

Zero — block already valid hai, toh ek repeated write sirf dirty bit flip karta hai.

Dirty line eviction par extra cost kyun aati hai

Ise memory mein write back karna hota hai apna slot reuse hone se pehle, jo ek memory write add karta hai.