--- title: Set-Associative Caches and Write Policies module: The Memory Hierarchy moduleNumber: 6 lessonNumber: 4 order: 604 summary: > Give each set several lines and a block has a choice of homes — fewer conflict misses, at the cost of comparing E tags in parallel and choosing a victim to evict. We re-run the direct-mapped ping-pong trace on a 2-way cache and watch the conflicts vanish, weigh LRU against random replacement, then turn to writes: write-through versus write-back with a dirty bit on a hit, write-allocate versus no-write-allocate on a miss, and a worked traffic count showing when each pairing wins. topics: [The Memory Hierarchy] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §6 The Memory Hierarchy" - book: Bistriceanu ref: "Computer Architecture Notes — §7–9 The Memory Hierarchy / The Cache / Main Memory" --- The [direct-mapped cache](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped) 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. $$ % caption: Line matching in a 2-way set-associative set. The index has already picked % caption: this set; the address tag is broadcast to both comparators, each checks one % caption: line's stored tag, and the OR of the matches is the hit signal. The matching % caption: line's block feeds the byte-select stage as before. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % two lines of the selected set, each drawn as v / tag / block sub-boxes \foreach \w/\y in {0/1.6, 1/0.4} { \node[draw, fill=acc!8, minimum width=6mm, minimum height=7mm, anchor=west, inner sep=0pt] (v\w) at (0,\y) {v}; \node[draw, fill=acc!8, minimum width=13mm, minimum height=7mm, anchor=west, inner sep=0pt] (t\w) at (0.6,\y) {tag$_\w$}; \node[draw, fill=acc!8, minimum width=23mm, minimum height=7mm, anchor=west, inner sep=0pt] (b\w) at (1.9,\y) {block$_\w$}; } \node[anchor=east, align=right] at (-0.25,1.0) {selected\\set}; % comparators, one per line, at the lines' heights \node[draw, circle, minimum size=7mm, inner sep=0pt] (c0) at (5.6,1.6) {$=$}; \node[draw, circle, minimum size=7mm, inner sep=0pt] (c1) at (5.6,0.4) {$=$}; \draw[->] (b0.east) -- (c0.west); \draw[->] (b1.east) -- (c1.west); % address tag rises along a clear channel and branches into both comparators \node[draw, minimum width=15mm, minimum height=7mm] (atag) at (4.7,-1.5) {addr tag}; \draw[acc] (atag.north) -- (4.7,1.32); \draw[->,acc] (4.7,0.12) -- (c1.south west); \draw[->,acc] (4.7,1.32) -- (c0.south west); % OR of the two matches = hit \node[draw, minimum width=9mm, minimum height=8mm] (or) at (7.4,1.0) {OR}; \draw[->] (c0.east) -- ++(0.45,0) |- ($(or.west)+(0,0.16)$); \draw[->] (c1.east) -- ++(0.45,0) |- ($(or.west)-(0,0.16)$); \draw[->] (or.east) -- ++(0.8,0) node[anchor=west,text=acc] {hit}; \end{tikzpicture} $$ 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](/computer-architecture/virtual-memory/the-tlb-and-multi-level-page-tables) builds — though most TLBs are set-associative). Most data caches sit in between, at 4-, 8-, or 16-way. > **Definition (Associativity).** The number $E$ of lines per set. **Direct-mapped** > is $E = 1$; **$E$-way set-associative** holds $E$ lines per set and compares $E$ tags > in parallel; **fully-associative** is the single-set extreme ($S = 1$, no index > bits) where a block may occupy any line. ## 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](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped), 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. $$ % caption: The alternating trace 0, 32, 0, 32, 0, 32 on the same 16 bytes of cache. % caption: Direct-mapped (top), the two blocks share one line and evict each other: % caption: six misses. Two-way (bottom), they occupy the two ways of one set: two cold % caption: misses, then hits. Filled boxes are misses, outlined boxes are hits. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.85,0) {direct-mapped}; \foreach \i/\addr in {0/0, 1/32, 2/0, 3/32, 4/0, 5/32} \node[draw, fill=acc!25, minimum width=10mm, minimum height=7mm] at (\i*1.35,0) {\addr}; \node[anchor=west,black] at (7.65,0) {6 misses}; \node[anchor=east] at (-0.85,-1.3) {2-way}; \foreach \i/\addr in {0/0, 1/32} \node[draw, fill=acc!25, minimum width=10mm, minimum height=7mm] at (\i*1.35,-1.3) {\addr}; \foreach \i/\addr in {2/0, 3/32, 4/0, 5/32} \node[draw=acc, very thick, minimum width=10mm, minimum height=7mm, text=acc] at (\i*1.35,-1.3) {\addr}; \node[anchor=west,black] at (7.65,-1.3) {2 misses, 4 hits}; \end{tikzpicture} $$ 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](/computer-architecture/memory-hierarchy/cache-performance-and-cache-friendly-code) 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. > **Definition (LRU replacement).** On a miss to a full set, evict the line that was > used least recently. It exploits temporal locality — the recently-touched lines are > the ones most likely to be touched again. True LRU needs per-line usage ordering, > which is cheap for small $E$ and is often approximated in hardware for large $E$. ### 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 | Set contents before | Hit / miss | Action | | --- | --- | --- | --- | --- | | 1 | $a$ | $\{\ \}$ | miss (cold) | install $a$; order $[a]$ | | 2 | $b$ | $\{a\}$ | miss (cold) | install $b$; order $[b, a]$ (b newest) | | 3 | $c$ | $\{b, a\}$ | miss | set full; evict LRU $= a$; order $[c, b]$ | | 4 | $a$ | $\{c, b\}$ | miss | evict LRU $= b$; order $[a, c]$ | | 5 | $c$ | $\{a, c\}$ | **hit** | $c$ resident; order $[c, a]$ | 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. $$ % caption: The LRU trace on one 2-way set for the stream a, b, c, a, c. Each column % caption: is the set after the access, most-recent line on top; a f\/illed cell is the % caption: line just touched, and the bottom (older) line is the eviction victim on the % caption: next miss. c survives step 4 because it was touched more recently than b. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=11mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\top/\bot/\hit in {0/a/{}/1, 1/b/a/1, 2/c/b/1, 3/a/c/1, 4/c/a/0} { \pgfmathsetmacro{\x}{\i*1.5} \node[anchor=south,black] at (\x+0.55,1.5) {\ifnum\i=4 hit\else miss\fi}; \ifnum\hit=1 \node[cell, fill=acc!25] at (\x,0.8) {$\top$}; \else \node[cell, fill=acc!8, draw=acc, very thick] at (\x,0.8) {$\top$}; \fi \node[cell] at (\x,0) {$\bot$}; } \node[anchor=east,black] at (-0.85,0.8) {newer}; \node[anchor=east,black] at (-0.85,0) {older}; \end{tikzpicture} $$ 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, \ldots$ 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. $$ % caption: Write-back with a dirty bit. A write hit updates the cached line and sets % caption: its dirty bit; memory is untouched. The block is written back to memory only % caption: when it is evicted and only if the dirty bit is set; a clean victim is simply % caption: discarded. \begin{tikzpicture}[font=\footnotesize,>=stealth, box/.style={draw, minimum width=30mm, minimum height=9mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box, fill=acc!8] (w) at (0,0) {write hit:\\update line,\\set dirty $=1$}; \node[box] (ev) at (4.6,0) {line evicted}; \node[draw, diamond, aspect=2, inner sep=1pt, align=center] (d) at (4.6,-2.4) {dirty?}; \node[box] (wb) at (8.6,-2.4) {write block\\back to memory}; \node[box] (drop) at (4.6,-4.6) {discard line\\(clean copy)}; \draw[->] (w) -- (ev); \draw[->] (ev) -- (d); \draw[->] (d.east) -- node[above]{yes} (wb.west); \draw[->] (d.south) -- node[right]{no} (drop.north); \end{tikzpicture} $$ > **Definition (Dirty bit).** A per-line flag set when the cached block is modified > and not yet reflected in memory. On eviction, a **dirty** line must be written back; > a **clean** line (dirty bit clear) can be discarded, since memory already holds an > identical copy. ## 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. | Hit policy | Miss policy | Memory traffic | Typical use | | --- | --- | --- | --- | | write-back | write-allocate | low (deferred, batched) | most data caches | | write-through | no-write-allocate | high (every write) | simple / 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. $$ % caption: Memory-bus traffic for the two workloads (bar length proportional to % caption: bytes). The hot counter rewards write-back 50-fold; the write-once stream % caption: mildly rewards write-through, since write-allocate fetches blocks that are % caption: never read. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % workload 1 \node[anchor=west,black] at (0,1.9) {hot counter, 100 writes:}; \node[anchor=east] at (2.9,1.2) {write-through}; \draw[fill=acc!25] (3.0,0.95) rectangle (11.0,1.45); \node[anchor=west] at (11.15,1.2) {800 B}; \node[anchor=east] at (2.9,0.35) {write-back}; \draw[fill=acc!8] (3.0,0.1) rectangle (3.16,0.6); \node[anchor=west] at (3.4,0.35) {16 B}; % workload 2 \node[anchor=west,black] at (0,-0.75) {write-once 64 B stream:}; \node[anchor=east] at (2.9,-1.45) {write-through}; \draw[fill=acc!25] (3.0,-1.7) rectangle (3.64,-1.2); \node[anchor=west] at (3.9,-1.45) {64 B}; \node[anchor=east] at (2.9,-2.3) {write-back}; \draw[fill=acc!8] (3.0,-2.55) rectangle (4.28,-2.05); \node[anchor=west] at (4.5,-2.3) {128 B (64 fetched + 64 written back)}; \end{tikzpicture} $$ ### 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$. | # | Access | Cache state after | Dirty? | Memory traffic | | --- | --- | --- | --- | --- | | 1 | read $b$ | $b$ resident, clean | 0 | fetch $b$ (16 B in) | | 2 | write $b$ | $b$ modified in cache | 1 | none — deferred | | 3 | write $b$ | $b$ modified again | 1 | none — absorbed | | 4 | evict $b$ | $b$ gone | — | write back $b$ (16 B out) | 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).[^waypredict] 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).[^skew] 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).[^hp4] 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. > **Takeaway.** An **$E$-way set-associative** cache holds $E$ lines per set and > compares all $E$ tags in parallel; re-running the direct-mapped ping-pong on a > 2-way cache turns six misses into two, because both contenders fit in one set. > A full set evicts by **LRU** — right when temporal locality holds, beaten by > random on cyclic scans just larger than the set. On a write **hit**, > **write-through** updates memory immediately while **write-back** defers it via > the **dirty bit** (800 vs 16 bytes on a hot counter). On a write **miss**, > **write-allocate** fetches the block first, **no-write-allocate** writes around > the cache — and write-back with write-allocate is the common pairing because > writes, too, have locality. We now have the full mechanism. The last lesson turns mechanism into a number — the [average memory access time](/computer-architecture/memory-hierarchy/cache-performance-and-cache-friendly-code) — and uses it to write code that uses the cache well. [^waypredict]: **B. Calder, D. Grunwald, J. Emer**, "Predictive sequential associative cache," _HPCA_ 1996 — way prediction reads a predicted way at direct-mapped latency and verifies the tag in parallel, paying the full probe only on a misprediction. [^skew]: **A. Seznec**, "A case for two-way skewed-associative caches," _ISCA_ 1993 — hashing the index differently per way so colliding pairs scatter, giving a 2-way cache the effective associativity of a larger conventional one. [^hp4]: **J. L. Hennessy, D. A. Patterson**, _Computer Architecture: A Quantitative Approach_, 6th ed., Morgan Kaufmann, 2019 — §2; write buffers let a store post and the processor proceed while the write drains to memory in the background.