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

This page is the practice ground for Write-allocate vs no-allocate. The parent explained the idea; here we grind through every kind of situation a write miss can put you in and count the memory traffic each time.

Before anything else, let us pin down the words so no symbol is used unearned.

The scenario matrix

Every write-miss situation this topic can throw at you falls into one of these cells. The examples that follow are each tagged with the cell they cover, and together they hit all of them.

#	Case class	What makes it special	Policy that shines	Example
A	Single isolated write, reused soon	temporal locality present	write-allocate + write-back	Ex 1
B	Single isolated write, never reused	zero temporal locality	no-allocate + write-through	Ex 2
C	Cluster of writes to one block, then read	spatial locality	write-allocate	Ex 3
D	Streaming writes across many blocks	data larger than cache	no-allocate / Streaming Stores	Ex 4
E	Degenerate: write the same address twice	is the 2nd a hit?	either — tests hit logic	Ex 5
F	Boundary: write straddling a block edge	offset near line size	reveals block granularity	Ex 6
G	Eviction / dirty writeback	line already dirty, conflict	write-back cost accounting	Ex 7
H	Word-problem (real workload)	pick a policy & justify	decision framework	Ex 8
I	Exam twist: forbidden combo	write-back + no-allocate	shows why it's illegal	Ex 9

Cache used throughout unless stated: 4 lines, 8 bytes/line, direct-mapped, initially empty.

Cell A — isolated write, reused soon

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

Statement. Write 0xFF to address 0x28. Then read 0x29. Count memory traffic under write-allocate + write-back.

Forecast: guess now — how many trips to memory total? Reads? Writes?

Locate the block. $index = ⌊ 0 x 28/8 ⌋ mod 4 = (5) mod 4 = 1$ . Offset $= 0 x 28 mod 8 = 0$ . Why this step? We must know which slot to check before we can say hit or miss.
Check line 1. Empty cache ⇒ valid bit 0 ⇒ write miss. Why? A miss is what triggers the policy branch.
Allocate + fetch. Read the whole 8-byte block 0x28–0x2F from memory into line 1. → 1 memory read. Why the whole block? The cache only moves data in line-sized units; you cannot hold just one byte.
Write into cache at offset 0: byte becomes 0xFF. Set dirty bit = 1 (memory not yet updated). Why write-back? Write-back defers the memory write until eviction — see Write-back vs Write-through.
Read 0x29. Same block, already valid ⇒ hit, zero traffic. Why a hit? We fetched the neighbour 0x29 for free in step 3 — that is spatial locality paying off.

Verify: memory reads = 1, writes = 0 (nothing evicted yet). Total = 1. The subsequent read cost nothing — exactly the payoff write-allocate promises.

Cell B — isolated write, never reused

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

Statement. Write 0xFF to 0x28, then read 0x28. Count traffic under no-allocate + write-through.

Forecast: will the read be a hit or a miss? How many trips?

Locate & check. Index 1, empty ⇒ write miss (same as Ex 1).
No-allocate: skip the cache. Do not fetch, do not allocate a line. Why? We assume low temporal locality, so a cache line here would be wasted — this is avoiding Cache Pollution.
Write-through: go straight to memory. → 1 memory write. Line 1 stays invalid. Why? No-allocate cannot keep the data anywhere else, so it must land in memory now.
Read 0x28. Line 1 still invalid ⇒ miss → 1 memory read. Why a miss? We deliberately never brought the block in.

Verify: reads = 1, writes = 1, total = 2. Here the read did miss — but this cell assumes we normally wouldn't read again; when we do, no-allocate loses. That is the correct trade being visualised.

Cell C — cluster to one block, then read (spatial locality)

Worked example Example 3 · four writes in one block

Statement. Writes to 0x100, 0x104, 0x108, 0x10C (all in one block), then read 0x100. Compare both policy pairs.

Forecast: which policy sends 5 trips and which sends 1?

First, confirm they share a block. $⌊ 0 x 100/8 ⌋ = 0 x 20$ , $⌊ 0 x 10 C /8 ⌋ = ⌊ 268/8 ⌋ = 33 = 0 x 21$ .

Write-allocate + write-back:

0x100: miss → fetch block 0x20 (1 read), write, dirty.
0x104: same block → hit.
0x108: miss → fetch block 0x21 (1 read), write, dirty.
0x10C: same block 0x21 → hit.
read 0x100: block 0x20 valid → hit. Why? Each block is fetched once; neighbours ride along free. → reads = 2, writes = 0. Total = 2.

No-allocate + write-through: 1–4. every write bypasses cache → 4 writes. 5. read 0x100: nothing cached → 1 read. → Total = 5.

Verify: write-allocate 2 vs no-allocate 5. Write-allocate wins because it amortises one fetch over many nearby writes — spatial locality at work.

Cell D — streaming across many blocks

Worked example Example 4 · a frame-buffer sweep

Statement. Write once to each of 8 addresses 0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38 (8 distinct blocks), never read them. Cache holds only 4 lines. Compare policies.

Forecast: with only 4 lines and 8 blocks, does write-allocate even keep anything useful?

Write-allocate + write-back:

Blocks 0x00,0x08,0x10,0x18 map to indices $0, 1, 2, 3$ : 4 fetches (4 reads), 4 dirty lines.
0x20 → index $⌊ 4 ⌋ mod 4 = 0$ : conflict — evicts dirty line 0 → 1 write-back, then 1 read to fetch. Same for 0x28(idx1), 0x30(idx2), 0x38(idx3): each is 1 writeback + 1 read. Why so bad? We keep no data (never read), yet pay to fetch and to evict — pure overhead. → reads $= 4 + 4 = 8$ , writes (evictions) $= 4$ . Total = 12.

No-allocate + write-through:

8 writes bypass cache entirely → 8 writes, 0 reads. Total = 8.

Verify: no-allocate 8 vs write-allocate 12. Streaming has zero reuse, so allocating only adds fetch + eviction cost. This is exactly why Streaming Stores and Write Combining Buffers exist.

Cell E — degenerate: write same address twice

Cell F — boundary: write straddling a block edge

Cell G — eviction of a dirty line

Worked example Example 7 · dirty writeback cost

Statement. Under write-allocate + write-back: write 0x28 (index 1), then write 0x48. What is the total traffic?

Forecast: 0x48's index — and does the old dirty line cost us?

Write 0x28: index 1, miss → fetch (1 read), dirty line 1.
Write 0x48: $⌊ 0 x 48/8 ⌋ = ⌊ 72/8 ⌋ = 9$ , index $9 mod 4 = 1$ . Same slot, occupied by a dirty line. Why conflict? Different block, same index — direct-mapped has only one slot per index.
Evict line 1: it is dirty ⇒ write it back (1 write), then fetch block for 0x48 (1 read), write, dirty. Why write back first? Write-back never lost the earlier 0x28 change; it must be saved before the slot is reused, or data corrupts.

Verify: reads = 2, writes = 1. Total = 3. Contrast with write-through, which would have paid the 0x28 write immediately and never needed a dirty writeback.

Cell H — real-world word problem

Worked example Example 8 · choose a policy

Statement. A logging system appends 64-byte records to a file buffer sequentially, flushed to disk and never re-read by the CPU. Records total 100 MB; cache is 1 MB. Which policy, and estimate the relative traffic?

Forecast: allocate or not?

Access pattern: pure sequential writes, no reads ⇒ zero temporal, and data (100 MB) ≫ cache (1 MB) ⇒ no line survives to be reused. Why it matters: this is the streaming signature (Cell D at scale).
Apply the framework from the parent: use write-allocate only if $P (reuse ∣ write)$ is high. Here it is ≈ 0.
Decision: no-allocate (non-temporal stores). One write per 64-byte record.
- Write-allocate would additionally read each 64-byte block (100 MB of pointless fetch) and later evict it.
- So write-allocate traffic ≈ $2 \times$ no-allocate (a fetch + a writeback per useful write).

Verify: no-allocate ≈ 100 MB written; write-allocate ≈ 100 MB read + 100 MB written = 200 MB. Ratio 2:1 in favour of no-allocate — matches the "streaming ⇒ bypass cache" rule and avoids Cache Pollution of the 1 MB cache.

Cell I — exam twist: the forbidden combination

Recap

Recall Which cell wins for pure streaming writes?

No-allocate — zero reuse means allocation only adds fetch + eviction cost. (Cell D / Ex 4)

Recall In Ex 3, why did write-allocate cost 2 reads, not 1?

0x100–0x10C spanned two blocks (0x20 and 0x21), each fetched once.

Traffic count for write-allocate hit, given prior allocation

Zero — the block is already valid, so a repeated write just flips the dirty bit.

Why does a dirty line cost extra on eviction

It must be written back to memory before its slot is reused, adding one memory write.