Replacement and Write Policies

Every cache has to make two kinds of decision that the address alone cannot settle. When a set is full, which line should be thrown out? And when the processor writes data, should memory be updated at once or later? These are the replacement policy and the write policy. They look like details, but they change the miss rate, how much traffic reaches memory, and how complex the cache is. This article explains the common policies, works through examples step by step, and compares them on real traces.

12 min read | Intermediate

What You'll Learn

• Compare LRU, pseudo-LRU, random and FIFO replacement
• Trace LRU through a sequence of accesses
• Explain write-through and write-back, and what a dirty bit does
• Explain write-allocate and the role of a write buffer

Which Line to Evict

In a set-associative cache, a new block can go in any way of its set. If one is empty, that is easy. If all are full, one line, the victim, must be evicted. A direct-mapped cache has no choice, so this question applies only to associative caches.

The ideal policy would evict the line that will not be used for the longest time. That needs knowledge of the future, so it is impossible in hardware. It is known as Belady's optimal policy and it is useful in studies, as a limit that nothing can beat. Real policies try to guess the future from the past.

Least Recently Used

LRU evicts the line that has gone unused the longest. It relies on temporal locality: what was used recently will probably be used again. Here is a 2-way set that receives blocks A, B, A, C, B. The most recently used line is listed first:

For 2 ways, LRU takes one bit per set. For more ways, exact LRU needs more state, because the order of all the ways must be kept: the number of possible orders grows very quickly with the ways, and on every hit the state must be updated.

Pseudo-LRU

So real caches with many ways use an approximation. Tree pseudo-LRU arranges the ways as the leaves of a small binary tree, with one bit at each branch pointing toward the side used less recently. An 8-way set needs just 7 bits, and it picks a line that is not necessarily the oldest, but never one of the recently used ones. It is close to LRU in practice, for a fraction of the logic.

Random and FIFO

Random replacement picks any line, usually using a simple counter. FIFO, first in first out, evicts the line that has been in the cache longest, however recently it was used. Both need almost no logic and no update on a hit, which matters when reads must be fast and cheap.

How Much Does It Matter?

Less than you might think. A model of a 1 KB, 4-way data cache compared LRU with random replacement on six small programs:

The difference is small, and random even wins sometimes. On the matrix program, LRU has a clear lead. That one is worth looking at, but none of these changes comes close to the effect of a size or associativity change. Results on large programs agree: LRU is usually a little better, and the gain shrinks as the cache grows. Many first-level caches use pseudo-LRU, and some use random, because in a big cache it hardly matters.

When LRU Goes Wrong

LRU has a well-known failure. Suppose a loop cycles through just one more block than fits. With a 4-way set and five blocks A, B, C, D, E in a repeating sequence, each access evicts exactly the block needed next, and everything misses. Random replacement would keep some blocks by luck and get some hits. The array-sum result above shows a mild case of this: the data is larger than the cache and is scanned in order. Modern large caches therefore use smarter policies, which try to spot such scans and avoid letting them push out useful data.

Writing: Two Copies of the Truth

Reads never change anything, so a cache line and memory always agree. A store changes the data, so the question is which copies get updated. There are two standard answers.

Write-Through

In a write-through cache, every store goes to the cache and to the next level. The two always match, which is simple, and if a line is evicted there is nothing to save. The cost is that every store creates memory traffic. A processor storing one word per cycle would flood a memory that can take one write every ten cycles.

The usual remedy is a write buffer, a small queue between the cache and memory. A store is placed in the buffer, and the processor moves on at once while the buffer drains in the background. The processor stalls only if the buffer is full. A load must also check the buffer, since the newest copy of its data may be sitting there.

Write-Back

In a write-back cache, a store updates only the cache. The line is marked with a dirty bit, meaning it differs from memory. Memory is updated only when a dirty line is evicted, when the whole line is written back at once. Several stores to the same line cost only one memory write, so traffic falls sharply. The price is complexity: a miss may now have to write out a victim line before the new one can come in, and the latest data may exist only in the cache. Other agents in the system, such as DMA engines or other cores, must be able to see it, which is the subject of Cache Coherence Protocols.

Comparing the Traffic

A model of a 1 KB, 2-way data cache with 16-byte lines counted the bytes written to memory by each policy:

The bubble sort is the best case. It keeps rewriting the same small array, which fits in the cache, so during this run nothing needs to reach memory at all. The dirty lines would be written back only when they are evicted later. The memory copy is a draw, since each line is written once in full. The linked list is the surprise: write-back was worse. Its lines were evicted before they had absorbed many stores, and each eviction wrote all 16 bytes, even if only 4 had changed. So write-back usually wins, by a large margin, but not always.

Write buffers often do more than queue stores. A merging write buffer combines several stores to the same line into one memory write, which removes part of write-through's disadvantage. Write-back caches also use a small buffer for victims, so that the evicted dirty line can leave quietly while the new line is fetched first. The processor is waiting for that new line, so it should not wait for the old one to be written too.

Write Misses

What if a store misses? Two choices again. Write-allocate fetches the line into the cache and then updates it, betting that more accesses to the same line are coming. No-write-allocate sends the store straight to the next level, leaving the cache alone. Write-back caches usually use write-allocate, and write-through caches often use no-write-allocate, since storing the line in the cache does not save any writes.

Note what write-allocate does to a memory copy. Each destination line is fetched from memory just to be fully overwritten, which wastes a read. Some processors spot this pattern and skip the fetch, and some instruction sets offer a way to declare that a line will be fully overwritten. RISC-V's Zicboz extension can zero a whole cache line without reading it, for example.

The choice also affects reliability. A write-through cache can protect its data with simple parity, since a clean copy always exists in memory, while a write-back cache needs stronger error correction, because a dirty line may be the only copy.

The Rest of the Line's State

So far, a line has a valid bit, a tag, a dirty bit and replacement state. Some lines can also be locked, so that real-time code keeps a known block in the cache. Caches also have to be managed by software on occasion. Before a DMA engine reads a buffer, a driver may need to clean the cache, writing dirty lines out. Before reading a buffer that DMA has written, it may need to invalidate the old copies. RISC-V offers cache-management extensions for that, and Polling, Interrupts and DMA explains why DMA needs them.

Common Mistakes