Write policies — write-through, write-back, write-allocate: Exercises

Before we start, one shared notation table — every symbol used below is defined here, in plain words, so nothing appears un-earned.

L1 — Recognition

Goal: name the policy from its behaviour. No maths, just definitions.

Exercise 1.1. A cache updates both the line and main memory on every write hit. Name this write-hit policy. Does it need a dirty bit?

Recall Solution 1.1

Updating both copies immediately = write-through. Memory is never behind the cache, so there is nothing "stale" to track ⇒ no dirty bit needed. The dirty bit only exists to answer "is memory out of date?" — under write-through the answer is always "no".

Exercise 1.2. On a write miss, a cache writes the value straight to memory and does not load the block into cache. Name this policy.

Recall Solution 1.2

Writing around the cache on a miss = no-write-allocate (also called write-around). The bet: this write is a one-off you won't read back soon, so caching it would waste a slot.

Exercise 1.3. A cache line has dirty=1 and is about to be evicted. What must happen before the new block loads?

Recall Solution 1.3

dirty=1 means the cache copy was modified and memory is stale, so we must write the whole block back to memory first, then load the new block. If it were dirty=0, we would just overwrite — no memory write.

L2 — Application

Goal: apply one rule to a concrete situation.

Exercise 2.1. Write-through + no-write-allocate. A write misses. List exactly what the hardware does.

Recall Solution 2.1

Block is not in cache (miss).
No-write-allocate ⇒ do not fetch the block.
Write the value directly to memory.
Cache is left unchanged. One memory write; nothing enters the cache.

Exercise 2.2. Write-back + write-allocate. A write misses on a line whose current occupant is dirty. Count the memory accesses.

Recall Solution 2.2

Evict the dirty victim ⇒ write-back the old block: 1 memory write.
Write-allocate ⇒ fetch the new block: 1 memory read.
Perform the write into the freshly-loaded line, set dirty=1 (no memory access — it's now a hit). Total = 2 memory accesses (one write, one read). Note: the write itself touched memory zero times directly.

Exercise 2.3. Using the cost formula $T_{w b} = t_{c} + m t_{m} (1 + d)$ with $t_{c} = 2$ , $t_{m} = 100$ , $m = 0.10$ , $d = 0.5$ , compute the average write cost for write-back.

Recall Solution 2.3

Plug in step by step: $T_{w b} = 2 + 0.10 \times 100 \times (1 + 0.5) = 2 + 0.10 \times 100 \times 1.5 = 2 + 15 = 17 cycles .$ Why the $(1 + d)$ ? A miss always costs one fetch ( $t_{m}$ ); half the time it also forces a dirty write-back ( $d t_{m}$ ).

L3 — Analysis

Goal: trace sequences and compare policies quantitatively.

Exercise 3.1. Cache empty, one line, x and y map to the same line. Policy: write-back + write-allocate. Stream: W x; W x; R x; W y; R x. Count total memory writes and memory reads.

Recall Solution 3.1

Step	Event	Memory action
`W x`	miss → allocate	read x's block; write into cache, `dirty=1`
`W x`	hit	none
`R x`	hit	none
`W y`	miss, evicts dirty x	write x back; read y's block; `dirty=1`
`R x`	miss, evicts dirty y	write y back; read x's block

Memory reads = 3 (x, y, x again), memory writes = 2 (x back, y back).

Exercise 3.2. Same stream, same mapping, but write-through + no-write-allocate. Count memory writes and reads. (Reads always allocate.)

Recall Solution 3.2

Step	Event	Memory action
`W x`	write-miss, no-allocate	write memory; cache unchanged
`W x`	still miss	write memory
`R x`	read-miss → allocate	read x's block into cache
`W y`	write-miss, no-allocate	write memory (y); cache still holds x
`R x`	hit (x still cached!)	none

Memory writes = 3, memory reads = 1. Contrast with 3.1: write-through does more memory writes (3 vs 2) but here fewer reads (1 vs 3), because no-write-allocate never evicted the resident x. Policy trade-offs are workload-dependent — there is no universal winner.

Exercise 3.3. With $t_{c} = 1$ , $t_{m} = 50$ : write-through no-allocate costs $t_{c} + t_{m}$ per write; write-back costs $t_{c} + m t_{m} (1 + d)$ . For $h = 0.90$ ( $m = 0.10$ ), $d = 0.4$ , find the speedup (write-through cost ÷ write-back cost), rounded to 2 decimals.

Recall Solution 3.3

Write-through: $T_{w t} = 1 + 50 = 51$ . Write-back: $T_{w b} = 1 + 0.10 \times 50 \times (1 + 0.4) = 1 + 0.10 \times 50 \times 1.4 = 1 + 7 = 8$ . Speedup $= 51/8 = 6.375 \approx 6.38 \times$ . Why: the slow $t_{m}$ multiplies by $m = 0.10$ in write-back but by $1$ in write-through.

Figure — Write policies — write-through, write-back, write-allocate

L4 — Synthesis

Goal: choose and justify a design; combine both axes.

Exercise 4.1. You are initialising a 1 MB array with memset (write every byte once, never read back). Cache line = 64 B, $t_{m} = 100$ cycles per block. Compare wasted fetch traffic between write-allocate and no-write-allocate. How many block fetches does each policy trigger?

Recall Solution 4.1

Number of blocks $= \frac{1 MB}{64 B} = \frac{1 , 048 , 576}{64} = 16, 384$ blocks.

Write-allocate: every write-miss fetches the whole 64 B block just to overwrite it — 16,384 useless fetches = $16, 384 \times 100 = 1, 638, 400$ wasted cycles.
No-write-allocate: writes go straight to memory, 0 fetches. Verdict: for pure streaming writes, no-write-allocate wins decisively. This is why real CPUs offer non-temporal / streaming store instructions that bypass allocation. See Write Buffers and Store Buffers.

Exercise 4.2. Design question: You need a cache for a multiprocessor where other cores and DMA devices must always see current memory. Which write-hit policy simplifies coherence, and what is the cost you accept?

Recall Solution 4.2

Choose write-through: memory is always current, so external observers (other cores, DMA) never read stale DRAM. The accepted cost is higher memory write traffic (every write hits DRAM). A write buffer hides much of the latency so the CPU rarely stalls. Under MESI the "always-current-memory" property removes the need to hunt for a dirty owner on every external read. Trade: simplicity + coherence bought with bandwidth.

Exercise 4.3. Combine axes for a hot inner loop that repeatedly reads and writes a small working set that fits in cache. Which pairing minimises memory traffic, and estimate memory writes for $N = 1000$ writes to the same resident block (never evicted).

Recall Solution 4.3

Pairing: write-back + write-allocate.

First write: 1 miss → 1 fetch (read), dirty=1.
Remaining 999 writes: all hits, 0 memory writes.
Block never evicted ⇒ 0 write-backs during the loop. Memory writes during the loop = 0 (the single dirty write-back happens only if/when it's finally evicted). Write-through would have done 1000 memory writes. Write-back collapses them all.

L5 — Mastery

Goal: edge cases, degenerate inputs, and the full sign/limit sweep of the cost model.

Exercise 5.1 (limits). In $T_{w b} = t_{c} + m t_{m} (1 + d)$ , evaluate the two extreme corners: (a) perfect locality $m = 0$ ; (b) worst case $m = 1, d = 1$ . Interpret each.

Recall Solution 5.1

(a) $m = 0$ : $T_{w b} = t_{c} + 0 = t_{c}$ . Every write is a hit — the cache does all the work, memory is never touched. This is the ideal write-back scenario. (b) $m = 1, d = 1$ : $T_{w b} = t_{c} + 1 \times t_{m} \times (1 + 1) = t_{c} + 2 t_{m}$ . Every write misses and every victim is dirty — each write costs one write-back plus one fetch. This is the pathological thrashing case; here write-back is at its worst. Compare write-through's flat $t_{c} + t_{m}$ : it sits between these two extremes and never depends on $d$ or locality — its cost is constant, which is exactly its predictability advantage.

Exercise 5.2 (crossover). Find the miss rate $m^{⋆}$ at which write-back ( $t_{c} + m t_{m} (1 + d)$ ) costs the same as write-through ( $t_{c} + t_{m}$ ). Use $t_{m}$ general, $d = 0.5$ . Then plug $t_{m} = 50$ … (it cancels — show why).

Recall Solution 5.2

Set equal and cancel the common $t_{c}$ : $m^{⋆} t_{m} (1 + d) = t_{m} \Rightarrow m^{⋆} = \frac{1}{1 + d} .$ The $t_{m}$ cancels — the crossover miss rate depends only on the dirty fraction, not on how slow memory is! With $d = 0.5$ : $m^{⋆} = \frac{1}{1.5} = 0.6 \overline{6} \approx 0.667$ . Meaning: as long as fewer than ~66.7% of writes miss, write-back beats write-through here. Real caches sit far below that (single-digit %), so write-back wins comfortably.

Exercise 5.3 (degenerate hardware). A student proposes write-through + write-allocate. On a write miss it (i) fetches the block and (ii) writes memory anyway. For the stream W x; W x; W x (all to a cold block, block stays resident), count memory reads and writes and explain why this pairing is wasteful.

Recall Solution 5.3

Step	Event	Memory action
`W x`	write-miss	read block (allocate) + write memory (through)
`W x`	hit	write memory (through)
`W x`	hit	write memory (through)

Memory reads = 1, memory writes = 3. It pays the fetch cost of write-allocate (1 read) and the per-write memory cost of write-through (3 writes) — the worst of both axes, with none of the write-back savings. This is why the natural pairs are WB+allocate and WT+no-allocate; the mixed corner combines costs without combining benefits.

Recall Self-test recap (cover and recall)

Write-through needs a dirty bit? ::: No — memory is always current. Write-allocate/no-allocate apply on which event? ::: A write miss. Crossover miss rate write-back vs write-through (dirty fraction $d$ )? ::: $m^{⋆} = \frac{1}{1 + d}$ . Best pairing for a hot read/write loop? ::: Write-back + write-allocate. Best pairing for memset streaming writes? ::: No-write-allocate (avoids useless fetches).