Cache Write Policies

The problem with writes

A cache keeps copies of memory blocks. Reading a copy is harmless. But when the CPU writes, the copy in the cache changes, and the original in main memory doesn’t. There are now two versions of the same data. A write policy answers two questions:

1. On a write hit: when should memory get the new value?
2. On a write miss: should the block be brought into the cache at all?

Write hits: write-through vs write-back

	Write-through	Write-back (copy-back)
What a write updates	the cache and memory	the cache only
Memory is up to date?	always	not until the line is evicted
Extra bit per line	none	a dirty bit
Memory writes	one per write	one per dirty eviction
Evicting a line	just drop it	write it back first if dirty
Good at	simplicity, consistency	repeated writes to the same data

Write-back sets the line’s dirty bit when it is written. While the bit is 1, memory holds a stale value. In the model the memory box turns grey with a stale tag. When the line is later replaced, the cache first writes the block back, and only then loads the new block. Ten writes to a loop counter become one memory write.

Write-through keeps memory current at every step, which is simpler and makes sharing data with I/O devices or other processors easier. The cost is a memory write for every store. Real write-through caches put a small write buffer between the cache and memory, so the CPU doesn’t wait for each write to finish.

Write misses: allocate or not?

• Write-allocate (fetch on write): load the block into the cache, then do the write as a hit. Worth it if the program will touch the block again soon.
• No-write-allocate (write around): send the write straight to memory and leave the cache alone. Worth it for data that is written once and not read soon.

The two questions are independent, but the usual pairs are:

• write-back + write-allocate: later writes to the block will hit, and they cost nothing.
• write-through + no-write-allocate: every write goes to memory anyway, so loading the block gains nothing.

Worked example

The Mixed reads and writes preset is R1 W1=20 W1=21 W1=22 R5 W2=40 R2 W6=60 on a 4-line direct-mapped cache. Block b goes in line b mod 4.

Policy	Block loads (memory reads)	Memory writes
write-back + write-allocate	4	2, and block 6 is still dirty
write-back + no-write-allocate	3	3
write-through + write-allocate	4	5
write-through + no-write-allocate	3	5

Follow write-back + write-allocate:

1. R1 misses and loads block 1.
2. The three writes to block 1 hit. Each one changes only the cache, and block 1 becomes dirty.
3. R5 maps to the same line, so block 1 is written back once (value 22) before block 5 is loaded.
4. W2=40 misses, so block 2 is loaded and written (dirty). R2 then hits.
5. W6=60 evicts the dirty block 2 (a second write-back), then loads block 6.

Average access time

Exam problems often ask how long accesses take on average. The idea to remember:

• Reads behave the same under both policies: a hit costs the cache time, a miss also costs a block load.
• With write-through (and no write buffer), every write costs a memory write.
• With write-back, writes cost only cache time. The memory cost appears on misses that evict a dirty block, so problems give you the fraction of dirty blocks.

Where they are used

Most modern CPU caches are write-back with write-allocate, because it saves a lot of memory traffic. In a multicore chip, write-back means another core’s cache may hold a newer copy than memory. A cache coherence protocol such as MESI keeps the copies in agreement. Before a DMA transfer or power-off, dirty lines must be flushed to memory.

Code

def simulate(ops, write_back=True, allocate=True, lines=4):
    """Direct-mapped cache. ops: ('R', block) or ('W', block, value)."""
    mem = [12, 7, 30, 4, 19, 8, 25, 3]
    cache = [None] * lines              # each line: [block, value, dirty]
    reads = writes = 0
    for op in ops:
        b = op[1]
        line = b % lines
        hit = cache[line] is not None and cache[line][0] == b
        if not hit and (op[0] == 'R' or allocate):
            victim = cache[line]
            if victim and victim[2]:            # dirty: write it back first
                mem[victim[0]] = victim[1]
                writes += 1
            cache[line] = [b, mem[b], False]    # load the block
            reads += 1
        if op[0] == 'W':
            entry = cache[line]
            if entry and entry[0] == b:         # the block is (now) cached
                entry[1] = op[2]
                if write_back:
                    entry[2] = True             # memory is stale until eviction
                else:
                    mem[b] = op[2]              # write-through
                    writes += 1
            else:                               # no-write-allocate miss
                mem[b] = op[2]
                writes += 1
    return reads, writes

ops = [('R', 1), ('W', 1, 20), ('W', 1, 21), ('W', 1, 22), ('R', 5),
       ('W', 2, 40), ('R', 2), ('W', 6, 60)]
for wb in (True, False):
    for alloc in (True, False):
        print('write-back   ' if wb else 'write-through',
              'allocate   ' if alloc else 'no-allocate', simulate(ops, wb, alloc))
# write-back    allocate    (4, 2)
# write-back    no-allocate (3, 3)
# write-through allocate    (4, 5)
# write-through no-allocate (3, 5)

Common mistakes

• Thinking write-back loses data. Dirty data does reach memory: on eviction, or when the cache is flushed.
• Forgetting the write-back when counting. A miss that evicts a dirty block costs a block write and a block load.
• Mixing up the two questions. Write-through/write-back is about write hits. Write-allocate/no-write-allocate is about write misses. You choose one of each.
• Expecting reads to change. The write policy only matters for writes. Read hits and read misses behave the same.