Exercises — Write-allocate vs no-allocate

• (a) Write-allocate — "fetch on write" is its literal other name.
• (b) No-allocate — data goes around the cache.
• (c) No-allocate — bypass = around.
• (d) Write-allocate — loading the whole block before modifying is the defining move.

True. Write-back keeps the only up-to-date copy inside the cache (marked dirty) and writes to memory later, at eviction. To hold a dirty copy you must first have a line — which is exactly what write-allocate provides. Pairing write-back with no-allocate leaves nowhere to store the deferred write, forcing an immediate memory write (i.e. write-through behaviour). See Write-back vs Write-through.

1. Which line? $0x28=40$. $40\gg 3=5$. $5\%4=1$. → line 1.
2. Line 1 is invalid → write miss.
3. Write-allocate: fetch the 8-byte block 0x28–0x2F from memory. → 1 read.
4. Write the byte at 0x28 into the cached line.
5. Write-back: don't touch memory now; set dirty = 1. Memory traffic: 1 read. Final line 1: valid = yes, dirty = yes.

1. Line 1, invalid → write miss.
2. No-allocate: do not fetch, do not allocate.
3. Write-through: send the write straight to memory. → 1 write. Memory traffic: 1 write. Final line 1: still invalid (valid = no).

• 0x29 is in the same block as 0x28 (both in 0x28–0x2F).
• Write-allocate case: the block is already in line 1 → hit, 0 memory traffic. This is spatial locality paying off (see Temporal vs Spatial Locality).
• No-allocate case: the block was never brought in → miss, must fetch the block now (1 read).

First, 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$. Different block!
• 0x10C = 268, $268\gg 3=33$.

So 0x100,0x104 are in block 32; 0x108,0x10C are in block 33. The parent note's Example 3 casually said "all in same block" — with an 8-byte line that is false. We correct it below. (See the figure.)

Write-allocate + write-back:

• WRITE 0x100: miss → fetch block 32 (1 read), write, dirty.
• WRITE 0x104: hit (block 32 present) → 0.
• WRITE 0x108: miss → fetch block 33 (1 read), write, dirty.
• WRITE 0x10C: hit → 0.
• READ 0x100: hit → 0. Blocks 32 and 33 map to lines $32\%4=0$ and $33\%4=1$ — different lines, no eviction, no write-back yet. Total: 2 reads, 0 writes = 2 operations.

No-allocate + write-through:

• Every write is a miss and goes straight to memory: 4 writes.
• READ 0x100: never cached → miss, 1 read. Total: 1 read + 4 writes = 5 operations.

Write-allocate wins 2 vs 5, because it amortised each fetched block over the two writes that hit it and the final read.

With a 16-byte line, block number = address $\gg 4$.

• 0x100: $256\gg 4=16$.
• 0x104,0x108,0x10C: $260,264,268\gg 4=16$. All in block 16! So:
• WRITE 0x100: miss → 1 read, dirty.
• next three writes: all hits → 0.
• READ 0x100: hit → 0. Total: 1 read. Bigger lines captured more spatial locality here — one fetch covered all four. This is the direct link to Cache Line Size.

Choose no-allocate + write-through (equivalently, use non-temporal / Streaming Stores). Why: each pixel is written once and never re-read → zero temporal locality, so caching buys nothing. Pollution damage of write-allocate here: the buffer is $1920\times 1080=2,073,600$ pixels. Say 4 bytes/pixel = $8,294,400$ bytes. With 64-byte lines that is $8,294,400/64=129,600$ distinct blocks streamed through the cache. A typical L1 holds only a few hundred lines — so the entire cache is flushed and refilled with garbage the program will never touch again, evicting genuinely useful data. That is Cache Pollution. No-allocate sends the pixels around the cache untouched, and Write Combining Buffers coalesce them into full-line bursts. See Streaming Stores.

1. Write miss to A. We must eventually get the new value of A into memory.
2. No-allocate says: don't create a cache line for A. So the modified value has no home inside the cache.
3. Write-back says: defer the memory write until the (dirty) line is evicted. But step 2 gave us no line to hold and no dirty bit to set — there is nothing to defer from. With no place to store and no way to defer, the write must go to memory immediately. But "write to memory immediately on a hit-or-miss write" is the definition of write-through. So "write-back + no-allocate" silently becomes write-through — it cannot exist as its own policy. Hence write-back requires write-allocate.

Set up per-write-miss expected cost.

• No-allocate: every access to the (uncached) region costs a through-write. The initial miss costs $C_{\text{wt}}$, and if reuse happens it costs another $C_{\text{wt}}$. Expected cost $=C_{\text{wt}}+p{C}_{\text{wt}}$.
• Write-allocate: pay the fetch once ($C_{\text{fetch}}$) plus a cheap cache write ($C_{\text{write}}$) on the miss; if reuse happens it is a cheap cache access $\approx C_{\text{write}}$ instead of $C_{\text{wt}}$. Expected cost $=C_{\text{fetch}}+C_{\text{write}}+p{C}_{\text{write}}$.

Write-allocate cheaper when $C_{\text{fetch}}+C_{\text{write}}+p{C}_{\text{write}}<C_{\text{wt}}+p{C}_{\text{wt}}.$ Group the $p$ terms: $C_{\text{fetch}}+C_{\text{write}}-C_{\text{wt}}<p(C_{\text{wt}}-C_{\text{write}}).$ So $p^{\star }=\frac{C_{\text{fetch}}+C_{\text{write}}-C_{\text{wt}}}{C_{\text{wt}}-C_{\text{write}}}.$ Plug in $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: because a through-write is as expensive as a fetch here, write-allocate only needs about a 1% reuse chance to win. High-fetch / low-reuse is the only regime where no-allocate dominates. This matches the parent's decision-framework inequality $P(\text{reuse}\mid \text{write})>\frac{C_{\text{fetch}}+C_{\text{write}}}{C_{\text{wt}}}$ up to the small $C_{\text{write}}$ correction in the denominator.

$p^{\star }=\frac{0+1-100}{100-1}=\frac{-99}{99}=-1.$ A negative threshold means "write-allocate wins even for $p=0$" — since probabilities can't be negative, the condition $p>-1$ is always true. Reading: if fetching costs nothing, always allocate, because you gain a possibly-cheaper future access at no downside. The sign of $p^{\star }$ is a quick "is one policy unconditionally better?" test.

Write-allocate on a miss first fetches the whole block, then writes. No-allocate sends the write around the cache to memory. Write-back must pair with write-allocate because it needs a line to hold the dirty copy. The right policy for a write-once frame buffer is no-allocate to avoid cache pollution.