Set Associativity and the Address Bits a Cache Decodes

Every cache is a lookup table indexed by part of the address, and every cache design question follows from which part. The address bits chosen for the index decide which addresses compete for the same storage; the bits kept as the tag decide what must be compared on every access; the bits left as the offset decide how much data one lookup returns. Set associativity is the knob that governs how much of the competition is resolved by hardware rather than by replacement policy.

Splitting a physical address

A cache line of 64 bytes consumes six low-order address bits that never participate in indexing, because they select a byte within the line. Above them sits the index field, log2(S) bits wide for S sets. The remaining high bits form the tag. For a 32 KiB, eight-way cache with 64-byte lines: 512 lines, 64 sets, 6 index bits, 6 offset bits, and the remaining 36 bits of a 48-bit physical address as the tag.

 physical address, 48 bits on x86-64
+-----------------------------------+----------+--------+
| tag (36)                          | index(6) | off(6) |
+-----------------------------------+----------+--------+

The tag array stores one entry per line, holding the tag plus state: a valid bit, a dirty bit, and coherence bits where the protocol needs them. For a 48-bit physical address, tag storage is 36 bits plus four or so bits of state, 5 bytes per 64-byte line — under 8 percent overhead, which is why tag arrays are usually built as a separate small SRAM beside the data array rather than interleaved with it.

Sets are addressed by the index, and all W ways of a set are read in parallel on every access. The W tags are compared against the tag field simultaneously, and a way is selected by the one that matches and is valid. This is why associativity costs latency in the compare-and-select stage but not in the array access: a direct-mapped cache reads one tag and one line; an eight-way cache reads eight tags and eight lines and multiplexes afterwards. The energy cost is proportional to W because all ways are activated, which is the reason high associativity appears in the last-level cache and not in the L1.

The two ends of one trade

A direct-mapped cache has W = 1. Each address maps to exactly one line, so the index bits determine the location completely and the replacement decision is trivial: the new line evicts the old one. The array is as fast as an SRAM can be, the tag check is a single comparator, and the capacity per unit area is the best available. The failure is structural rather than statistical. Two addresses separated by a multiple of the cache size compete for the same line, and no amount of spare capacity elsewhere helps. A loop that walks an array with a stride equal to the cache size — the classic case being a power-of-two row length in a matrix traversal — will miss on every access even though the array is a fraction of the cache.

A fully associative cache has one set and W equal to the line count. Any address may occupy any line, so no address pair conflicts by construction and the replacement policy has complete freedom. The cost is a W-way comparator and multiplexer in the critical path and a replacement policy that must search or maintain metadata over every line. Fully associative structures survive only where they are small: the TLB is usually fully associative or highly associative, because it has tens to a few hundred entries; a micro-op cache or a small victim cache is similar. A 32 KiB fully associative L1 would need a 512-way compare on every access, which no pipeline schedules.

Set associativity interpolates. With eight ways, a conflict requires nine addresses that map to the same set to be live simultaneously, which for most code never happens. The number of conflict misses falls roughly with the associativity for random address streams, but the useful return flattens: going from one way to two removes most of the pathological cases, two to four removes the next tier, and beyond eight the marginal hit-rate gain is small while the latency and energy cost keep rising. Real L1 data caches are typically eight- or twelve-way; L2 is eight- to sixteen-way; L3 is twelve- to sixteen-way with a much larger line count, so the set count grows rather than the associativity.

Why the index bits are chosen where they are

The index must be taken from bits that vary across the addresses a program touches. Taking it from the lowest bits above the offset — the natural choice — makes consecutive lines land in consecutive sets, which distributes a sequential stream evenly and is what a prefetcher wants. It also means the index is available before address translation completes, since the page offset bits are identical in the virtual and physical address. That property is exploited by virtually indexed caches, which begin the array access from the virtual address and compare the physical tag afterwards.

The cost of indexing on low bits is that the index is confined to the page offset when the cache is large. With 4 KiB pages there are only twelve offset bits, so a cache whose index needs more than twelve bits cannot be virtually indexed without aliasing problems. A physically indexed cache has no such restriction: the index can use any physical bits, which is why large L2 and L3 arrays are physically indexed and can use bits above the page boundary. The consequence is that the index then depends on physical page assignment, and two virtual pages whose physical frames differ in those bits land in different sets — usually helpful, occasionally the source of aliasing pathologies that page coloring addresses from the other direction.

Some designs hash the index bits before use, mixing high tag bits into the index so that addresses that differ only in the high bits do not systematically collide. The hash is a few XOR and shift operations, and its effect is to spread structured strides that would otherwise hit one set repeatedly. It does not create capacity, and it makes the index depend on bits that are unavailable before translation, so hashed indexing appears mainly in physically indexed last-level caches.

What a conflict miss actually is

The three-miss taxonomy is standard and worth stating precisely, because each category has a different remedy and only one of them is the replacement policy’s business:

• Compulsory. The line has never been in the cache. Unavoidable on first touch, removable only by prefetching it earlier.
• Capacity. The line was evicted because the cache could not hold everything the program was using. A fully associative cache of the same size would miss equally.
• Conflict. The line was evicted because another line mapped to the same set, while other sets held unused lines. A fully associative cache of the same size would have hit.

The distinction is not observable from a single access; it is defined by a counterfactual, which is why measuring it requires simulation with a second, fully associative cache of the same capacity. What can be said without simulation is the shape of the problem. Conflict misses scale with the number of distinct addresses that map to one set within a reuse window, and they are worst when the working set has a regular structure whose period aligns with the set count.

/* Column-major traversal of a row-major array: consecutive accesses are
   ROW_LEN apart, so with ROW_LEN * sizeof(int) a multiple of the cache size
   every access maps to the same set. */
for (size_t c = 0; c < ROW_LEN; c++)
    for (size_t r = 0; r < N; r++)
        sum += a[r * ROW_LEN + c];

Padding the row length so that it is not a multiple of the cache stride, or blocking the traversal so that a tile fits in the cache, removes the conflict without changing the algorithm. This is the point at which associativity and layout become the same question: associativity buys tolerance for bad layout, and layout removes the need for it.

Edge cases that survive the model

Two details break the clean picture. The first is that the tag comparison is against a physical address on most designs, so the cache cannot complete a lookup until translation does — unless the index and offset come from the virtual address and only the tag waits. The second is that a set does not always hold W usable lines: coherence state occupies space, and some protocols reserve a way or restrict which ways may hold shared lines. A cache described as sixteen-way may have fifteen ways of usable data in practice, and a policy that assumes otherwise will compute the wrong replacement victim.

Finally, associativity interacts with the replacement policy in a way that is easy to miss. A high-associativity cache with a poor policy can behave worse than a low-associativity one with a good policy, because the extra ways only help if the victim chosen is the line least likely to be reused. The approximate LRU schemes that real hardware uses are covered in replacement without exact LRU; their behaviour depends on the number of ways in a manner the miss-rate curves above do not show.