Set-Associative Caches

In a direct-mapped cache, the index bits of an address pick exactly one line, and exactly one tag comparison happens per access. The problem is structural: any two addresses whose index bits agree, regardless of their tag, are forced to fight over the same single line, no matter how large the cache is overall or how little of it is otherwise in use. A set-associative cache breaks this rigidity by organizing the cache as a collection of sets, each containing N ways (N physical line slots). The index bits now select a set rather than a single line, and the block may occupy any of the N ways within that set. The number N is the associativity; a cache with this structure is called N-way set-associative. Locating data now requires comparing the address's tag against all N tags stored in the selected set. Doing this sequentially would multiply latency by N, which is unacceptable — so set-associative caches compare all N tags in parallel, using N independent comparators that all fire during the same cycle, followed by a multiplexer that selects the matching way's data (or signals a miss if none match). This is the key micro-architectural feature that distinguishes "just add more tags" from a scalable design: associativity is bought with parallel hardware breadth, not serial time. The two boundary cases of this design spectrum are worth naming precisely, because set-associativity is the general case that contains both. A direct-mapped cache is exactly a 1-way set-associative cache: each set has one way, so there is nothing to choose among and no replacement decision to make. A fully associative cache is the opposite extreme: it has exactly one set containing all the cache's lines, so the index field vanishes entirely and every tag in the whole cache must be compared in parallel against every access. Set-associativity, for any N strictly between 1 and the total number of lines, is the practical middle ground — and this middle ground is where nearly all real cache hardware lives.

Address breakdown. As in a direct-mapped cache, a memory address is split into three fields — assuming byte-addressable memory, a block size of $2^b$ bytes, and $S$ sets total: ``` | ......... Tag ......... | Index (log2 S bits) | Offset (b bits) | ``` The crucial difference from the direct-mapped case is what the index selects: instead of indexing directly into one line, it indexes into one of S sets, each holding N ways. Because there are S sets instead of (S·N) individually-addressed lines, the index field is shorter than it would be in a direct-mapped cache of the same total capacity — it needs only $\log_2 S$ bits rather than $\log_2 (S \cdot N)$ bits. Those saved index bits effectively migrate into the tag, which is why the tag field of a set-associative cache is wider than in a same-capacity direct-mapped cache: more of the address must be checked explicitly, since the index alone no longer pins down a unique line.

Lookup procedure. On every access the cache performs the following steps, with steps 2 and 3 occurring in the same hardware cycle across all N ways simultaneously: ``` function ACCESS(address): tag = TAG_BITS(address) index = INDEX_BITS(address) # selects the set offset = OFFSET_BITS(address) set = cache.sets[index] # N ways: (valid, tag, data) each

# --- parallel comparison across all N ways --- hit_way = NONE for way in 0 .. N-1: # conceptually simultaneous if set[way].valid and set[way].tag == tag: hit_way = way break # at most one match, by design if hit_way != NONE: return HIT, set[hit_way].data[offset]

# --- miss handling --- victim_way = SELECT_VICTIM(set) # e.g. LRU, random, FIFO block = FETCH_FROM_MEMORY(address) if set[victim_way].valid and set[victim_way].dirty: WRITE_BACK(set[victim_way]) set[victim_way].valid = true set[victim_way].tag = tag set[victim_way].data = block UPDATE_REPLACEMENT_STATE(set, victim_way) return MISS, block[offset] ``` `SELECT_VICTIM` is intentionally left abstract here — choosing among N candidates within a set (least-recently-used, random, FIFO) is a rich topic addressed by Cache Replacement Policies. The direct-mapped case is the special case N = 1, where `SELECT_VICTIM` is forced and there is no real decision at all.

Hardware realization of the parallel compare. The "for way in 0..N-1" loop above is not really a loop in hardware — it is N physical comparators wired in parallel, each comparing the incoming tag against one way's stored tag, with the valid bit ANDed in. The N hit signals feed an OR gate (to produce the overall hit/miss signal) and an encoder/multiplexer (to select which way's data proceeds to the output). This parallelism is exactly what keeps a set-associative lookup roughly as fast as a direct-mapped one, at the cost of N times the comparator hardware and one N-to-1 multiplexer per set — a fixed constant-factor cost per access, independent of total cache size.

Access time. A lookup performs N tag comparisons, but they occur in parallel, so the latency contributed by comparison is $O(1)$ in N — a small, roughly constant number of gate delays for the comparator plus one N-to-1 multiplexer delay (which grows like $O(\log N)$ in the depth of the selection network, negligible for the small N values used in practice, typically 2–16). This is the entire reason parallelism is used rather than a sequential scan: a sequential scan across N ways would cost $O(N)$ time, which would make higher associativity directly punish every access, not just misses.

Hardware cost. The per-set hardware is $\Theta(N)$: N valid bits, N tag registers, N comparators, and an N-to-1 data multiplexer, replicated across all S sets. For a fixed total capacity $C = S \cdot N \cdot (\text{block size})$, increasing N while shrinking S keeps total storage constant, but comparator and multiplexer count still scale with $N$ per set — so total comparator hardware across the whole cache is $\Theta(S \cdot N) = \Theta(C / \text{block size})$, independent of how you split $C$ between $S$ and $N$. In other words, associativity does not change the asymptotic silicon cost of comparators (it's linear in the number of lines either way) — but it does concentrate that hardware differently (wider muxes per set instead of a lookup tree across sets), and it adds real constant-factor costs: extra wiring, extra energy per access (activating N tag SRAM ways instead of 1), and small increases in critical-path delay from the wider mux, all of which is why very high associativity is avoided at the fastest cache levels.

Why associativity reduces conflict misses — the argument. Fix an access pattern that repeatedly touches a working set of $k$ distinct blocks whose indices happen to collide (they all map to the same set). In a direct-mapped cache (N = 1), any two of these blocks accessed in alternation cause every single access to be a miss — the working set of size $k \geq 2$ cannot fit in 1 line. In an N-way set-associative cache with $N \geq k$, all $k$ colliding blocks can reside simultaneously in the same set (one per way), so after the initial compulsory misses, every subsequent access is a hit. This shows a clean, provable separation: there exist access patterns for which direct-mapped achieves 0% hit rate on the hot set while N-way (N ≥ k) achieves near-100% hit rate, using the identical total cache capacity in both cases if $S$ is shrunk to compensate. Associativity cannot help with capacity misses (the working set genuinely exceeds total cache size) or compulsory misses (first-touch of any block), but it directly targets conflict misses, and this is the only failure mode a direct-mapped cache exhibits that a fully associative cache of the same size never can.

Correctness invariant. A set-associative cache is correct (returns the same data a memory system without any cache would return) provided the following invariant holds at every point in time: for each valid line, the stored tag correctly identifies the unique memory block currently occupying that line, and at most one way in any set holds a given tag. The lookup and eviction procedure above preserves this: on a miss, the victim's old tag is fully evicted (invalidated or written back) before the new tag is installed, so the "at most one match per set" precondition used by the `break` in the pseudocode is maintained as an invariant across all operations. This is exactly why the loop is safe to short-circuit on the first match — correctness of the replacement/allocation logic guarantees no duplicate tags ever coexist in a set.

Tradeoffs, stated plainly. More ways: lower conflict-miss rate, more silicon, more energy per access (more ways activated), and often a slightly longer critical path (wider mux). Fewer ways: faster and cheaper, but more exposed to adversarial or unlucky index collisions. Real designs push associativity higher at levels further from the CPU (L2, L3), where extra latency is amortized over more work and hit-rate matters more, and keep L1 associativity modest (often 4- or 8-way) to preserve single-cycle access time.

Consider a small 4-way set-associative cache with 4 sets, block size 16 bytes (offset = 4 bits), and thus index = 2 bits. Total capacity = 4 sets × 4 ways × 16 bytes = 256 bytes. Compare against three access streams, all touching addresses whose index bits are identical (a worst case for direct-mapped, chosen deliberately — not a symmetric toy case): Addresses (in hex), all sharing index = `01` (binary), differing only in tag:

Trace the direct-mapped case carefully: because there is only 1 way per set, step 5's access to tag `0000` must evict whatever currently sits in that single line — which by then is tag `0011` from step 4 — and reload tag `0000`. Every subsequent repeat access is therefore a miss forever, a 100% miss rate on the steady-state loop, even though the cache as a whole has 256 bytes of capacity and the entire working set here is only 64 bytes (4 blocks × 16 bytes). This is conflict misses in their purest form: ample total capacity, wasted by rigid mapping. In the 4-way case, all four tags coexist as four different ways of the same set after step 4. Steps 5–8 are all hits: 0% miss rate in steady state for this exact working set, on identical total capacity. If a fifth colliding address (tag `0100`) were introduced, the 4-way cache would finally need to evict one of the four resident tags — this is precisely where Cache Replacement Policies (LRU, random, FIFO) decide which way loses, a decision that does not exist at all when N = 1.

The set-associative organization emerged from IBM's cache research in the 1960s, as engineers sought a middle ground between the rigidity of direct mapping and the prohibitive cost of full associativity in early cache memories built for the IBM System/360 Model 85 — widely regarded as the first commercial computer with a cache.

Set-associative caches are the default organization in essentially every general-purpose processor produced today. L1 instruction and data caches in modern CPUs are commonly 4-way or 8-way set-associative, balancing the tightest possible latency budget against a meaningful reduction in conflict misses for typical code and data access patterns. L2 and L3 caches, which tolerate a few extra cycles of latency in exchange for higher hit rates, often push associativity to 8-way, 12-way, or 16-way, since a shared L3 serves many cores and many independent working sets simultaneously — exactly the situation where index collisions across unrelated programs are common and costly. Beyond general-purpose CPUs, set-associative structures appear throughout the memory system: Translation Lookaside Buffers (TLBs) are frequently set-associative for the same reason caches are — page-table entries can collide on index bits just as data blocks can. Set-associative organization also underlies victim caches, GPU texture caches, and certain branch target buffers, anywhere a fixed-size lookup structure needs to tolerate collisions gracefully without paying full associative search costs. Compiler and systems engineers reason directly about set-associativity when they choose array padding, structure layouts, or loop tiling strategies to avoid pathological index collisions — a discipline sometimes called "cache-conscious" programming, and one that only makes sense once the mechanics of sets and ways, and the address breakdown that drives them, are understood.

Ask the tutor: How would the worked example change if the cache had only 2 ways instead of 4, given the same four colliding addresses?