Set-Associative Caches and Write Policies

The direct-mapped cache gave every block exactly one home, and paid for it with conflict misses: two hot blocks that index to the same set evict each other endlessly while the rest of the cache sits idle. The fix is to relax the placement — let a set hold several lines, so a block has a choice of where to live within its set. This is set associativity, and it costs more comparison hardware and a decision about which line to evict. This lesson covers that relaxation and then turns to the question deferred so far: what happens when the processor writes.

E-way set-associative caches

A cache with $E$ lines per set is $E$-way set-associative. Everything about the address split is unchanged (the same $t$ tag bits, $s$ index bits, and $b$ offset bits), and set selection is identical: the index still picks one set. What changes is line matching. The selected set now holds $E$ lines, and the block could be in any of them, so the cache compares the address tag against all $E$ tags in the set at once, in parallel. A hit is any valid line in the set whose tag matches; the matching line's block then feeds byte selection exactly as in the direct-mapped case.

Associativity is a spectrum. Direct-mapped is $E=1$ (one home, no tag-compare choice, cheapest, most conflicts). At the other extreme, a fully-associative cache has a single set ($S=1$, so $s=0$ and there are no index bits) and all lines live in it; a block may go anywhere, conflict misses vanish, but every line in the cache must be tag-compared on every access, feasible only for small caches (such as some small TLBs — a structure module 7 builds — though most TLBs are set-associative). Most data caches sit in between, at 4-, 8-, or 16-way.

The ping-pong trace, re-run 2-way

The payoff is easiest to see on the exact workload that broke direct mapping. In the last lesson, addresses 0 and 32 shared set 0 of the 16-byte direct-mapped cache ($S=4$, $B=4$) and evicted each other on every alternation. Reorganize the same 16 bytes as a 2-way cache ($S=2$ sets, $E=2$, $B=4$, so the address now splits as $t=3$, $s=1$, $b=2$) and run the alternating trace $0,32,0,32,0,32$:

• Address 0 (000 0 00) indexes set 0, tag 0: cold miss, installed in way 0.
• Address 32 (100 0 00) also indexes set 0, tag 4, but the set has a second way. Cold miss, installed in way 1. Nothing is evicted.
• Every remaining access hits: both hot blocks sit in set 0 side by side.

Two cold misses, four hits. The direct-mapped cache missed all six times. Same capacity, same block size, same addresses: the only change is that a set can now hold both contenders. The thrashing dot product from the last lesson dissolves the same way: x and y blocks that collided in one line now share a set, no padding required.

Associativity is not free. Each way adds a comparator and widens the multiplexing in the hit path, so higher associativity tends to lengthen the hit time, one of the tensions the next lesson quantifies. In practice a little associativity buys a lot: going from direct-mapped to 2-way removes most conflict misses, 8-way behaves nearly like fully-associative, and beyond that the returns are thin.

A useful rule of thumb: doubling associativity from $E$ to $2E$ cuts the miss rate about as much as doubling the cache size from $C$ to $2C$ — but only up to around 8 ways, after which the miss-rate improvement shrinks while the hit-time cost keeps climbing. So the first way or two of associativity is a bargain (conflict misses fall steeply for little added delay), and the tenth is not (near-fully-associative behavior is already reached, and each extra comparator only slows the hit). That shape — steep early gains, a flat tail — is why the caches in real processors cluster at 2-, 4-, and 8-way rather than at the extremes.

Choosing a victim: replacement

With $E>1$, a miss raises a question direct mapping never had to ask: the set may already be full, so which of the $E$ lines do we evict to make room? The choice is the replacement policy. The ideal would evict the block whose next use is furthest in the future, but the future is unknown, so caches approximate it from the past. The standard approximation is least-recently-used (LRU): evict the line in the set that has gone the longest without a reference, betting (on temporal locality) that it is the least likely to be needed soon.

An LRU trace, worked

A short trace shows LRU in action. Take a 2-way set and follow one set's two lines through the access stream $a,b,c,a,c$ of distinct blocks that all map to it. The set tracks, for its two ways, which was touched more recently; the older one is the victim.

Access 5 is the payoff: $c$ was kept because it had been used at step 3, more recently than $b$, so LRU spent its one eviction on $b$ instead and $c$ survived to be reused. The bookkeeping is a single most-recent-to-least ordering per set, updated on every touch — trivial for $E=2$ (one bit: which way is older), growing as $E!$ orderings for larger sets, which is why real hardware approximates it (a tree of bits, or a not-most-recently-used scheme) once $E$ passes 4 or so.

The main rival is simpler still: random replacement, which evicts an arbitrary line and needs no bookkeeping at all. LRU usually wins, but not always, and the losing case is instructive. Suppose three hot blocks map to a 2-way set and the program cycles through them: $a,b,c,a,b,c,\dots$ LRU evicts the least-recently-used line, which under a cyclic scan is exactly the block that comes next: $c$ evicts $a$ just before $a$ is needed, $a$ evicts $b$ just before $b$ is needed, and every access misses, forever. Random replacement has no such resonance: each eviction spares a needed block half the time, so a good fraction of accesses hit. The general point: LRU is the right default because programs usually have temporal locality, but any deterministic policy has a worst-case access pattern that defeats it, and working sets slightly larger than the set are LRU's.

Writing: hit policies

Reads are simple: a copy in the cache is as good as the original. Writes are where the cache and memory can disagree, because a write changes the data, and now the cached copy and the memory copy may differ. The first question is what to do when the written block is in the cache (a write hit). Two policies:

• Write-through. Write the word to the cache and immediately propagate it to the next level down. Cache and memory always agree, so eviction is trivial, but every write generates memory traffic, even repeated writes to the same word.
• Write-back. Write only to the cached line and mark it dirty with a per-line dirty bit. Defer the memory update until the line is evicted; only then, if the dirty bit is set, is the block written back. This collapses many writes to a block into one memory write — far less traffic — at the cost of one extra bit per line and a write-back step on eviction.

Writing: miss policies

The second question is what to do when the written word is not in the cache (a write miss). Again two policies:

• Write-allocate. Treat the miss like a read miss: fetch the block into the cache first, then perform the write into the now-resident line. This pays off when the write is followed by more accesses to the same block (likely, given spatial locality).
• No-write-allocate. Skip the cache entirely: write the word straight to the next level and leave the cache unchanged. This avoids loading a block that may never be read.

The two pairs of choices are independent, but two combinations are by far the most common because they fit together cleanly. Write-back + write-allocate keeps as much traffic as possible inside the cache: writes stay local and a write miss pulls the block in so subsequent writes are also local — the usual choice for modern data caches. Write-through + no-write-allocate keeps memory always current and never loads a block on a write, a simpler pairing sometimes used at outer levels.

Counting the traffic

To compare the policies, count bytes on the memory bus. Two small workloads, one cache with $B=16$-byte blocks:

Workload 1: a hot counter. A loop updates one 8-byte counter in memory 100 times. Under write-through, every update goes to memory: $100\times 8=800$ bytes of write traffic. Under write-back, all 100 updates land in the cached line; memory sees a single 16-byte block write-back when the line is eventually evicted: 50x less traffic, because the dirty bit let the cache absorb the repetition.

Workload 2: a write-once stream. A loop fills a 64-byte buffer (four blocks) that will not be read again. Under write-through + no-write-allocate, the 16 four-byte writes go straight to memory: 64 bytes of traffic, and the cache is left undisturbed. Under write-back + write-allocate, each block is first fetched (64 bytes read) and later written back (64 bytes written): 128 bytes moved, twice the traffic, for data that had no reuse to exploit.

A write-back trace, step by step

To see the two write choices together, trace one short stream on a write-back, write-allocate cache — the common pairing — and track the dirty bit and the memory traffic it controls. Take a single line (block $b$, 16 bytes), initially not cached, and the access stream: read $b$, write $b$, write $b$, then a reference that evicts $b$.

Two writes to the block cost zero memory traffic between them; the dirty bit just stays set, and the single write-back at eviction pays for both at once. Had the same line been write-through, steps 2 and 3 would each have pushed to memory immediately — two writes instead of the one deferred write-back — and no dirty bit would be needed because memory is never allowed to fall behind. The trace shows the whole trade in miniature: write-back trades one bit of state and a write-back-on- eviction step for the right to absorb every repeat write in between.

Neither policy dominates; they suit different workloads. Write-back + allocate assumes that writes have locality — that a written block will be written or read again soon — the same assumption the whole hierarchy makes, which is why it wins in practice and is the default for on-chip data caches.

Hiding the costs of associativity and writes

CS:APP lays out the policies; the design literature is largely about paying for them without slowing the common case.

Way prediction buys associativity at direct-mapped speed. The cost of a 4-way set is the multiplexer that cannot forward data until the tag compares finish. Way prediction sidesteps it: a small predictor guesses which way will hit and reads that way immediately, checking the tag in parallel; a correct guess (the vast majority, since the same lines are reused) delivers data at direct-mapped latency, and only a misprediction pays the full associative probe (Calder, Grunwald & Emer studied way prediction and selective ways in the 1990s).¹ The Alpha 21264's instruction cache used exactly this — set-associative miss rates at close to direct-mapped hit times.

Skewed associativity attacks the conflict pattern itself. A standard set- associative cache uses the same index bits for every way, so two blocks that collide in way 0 also collide in way 1 — associativity helps only by adding room, not by breaking the collision. Skewed-associative caches hash the index differently per way, so two addresses that map together in one way are scattered in another, and a pair that would thrash a normal 2-way cache almost never collides in both (Seznec, A case for two-way skewed-associative caches, ISCA 1993).² The result is that a skewed 2-way cache behaves much like a normal 4-way one, buying associativity's effect without its comparators.

Write buffers hide write-through's traffic. Write-through's weakness is that every store waits on memory. A write buffer — a small FIFO between the cache and the next level — lets the store post its data and the processor continue immediately, while the buffer drains to memory in the background (Hennessy & Patterson, Computer Architecture: A Quantitative Approach, §2).³ This is why write-through remains viable at outer levels despite its raw traffic: the buffer decouples the store's latency from the processor's, converting a stall into a background transfer, as long as writes do not arrive faster than the buffer can drain.

We now have the full mechanism. The last lesson turns mechanism into a number — the average memory access time — and uses it to write code that uses the cache well.