Photo by Brian Kostiuk on Unsplash
CPU Cache Associativity: Why Set-Associative Caches Win
Modern CPUs use set-associative caches almost universally, yet the design represents a careful compromise between two extremes. Understanding cache associativity explains why your processor organizes memory the way it does and why certain access patterns cause performance cliffs.
The Three Cache Organizations
A cache must decide where to store each memory address. Three strategies exist, each with distinct tradeoffs.
Direct-mapped caches are the simplest. Each memory address maps to exactly one cache line, determined by hashing bits from the address. Looking up data requires checking a single location, making this approach fast and power-efficient. The problem is rigidity: if two frequently-accessed addresses hash to the same cache line, they evict each other repeatedly in what’s called conflict misses or thrashing.
Fully-associative caches go to the opposite extreme. Any address can be stored in any cache line. This flexibility eliminates conflict misses entirely, but creates a lookup problem. To find data, the cache must check every line in parallel, requiring expensive comparison circuitry that doesn’t scale beyond small cache sizes. Fully-associative caches appear in TLBs (translation lookaside buffers), which are tiny, but not in the megabytes of L2 or L3 cache.
Set-associative caches split the difference. The cache is divided into sets, with each address mapping to one specific set but able to occupy any line within that set. An 8-way set-associative cache allows each address to live in any of 8 possible locations. This provides enough flexibility to avoid most conflict misses while keeping lookup circuits practical.
How Address Mapping Works
Cache addressing uses three components extracted from the memory address: tag, index, and offset.
The offset identifies the byte within a cache line (typically 64 bytes, requiring 6 bits). The index selects which set to look in. The tag is the remaining high-order bits, stored alongside cached data to verify a match.
In a 4-way set-associative cache with 512 sets and 64-byte lines, the index uses 9 bits to select one of 512 sets, then the cache checks 4 tag comparisons in parallel. If any of the 4 tags match, it’s a cache hit. This design scales to large caches because adding capacity means adding sets (requiring one more index bit), not increasing associativity.
Why 4-Way and 8-Way Dominate
Most L1 caches use 8-way associativity while L2 and L3 caches range from 8-way to 16-way. These numbers aren’t arbitrary.
Research and simulation show diminishing returns beyond 8-way associativity for most workloads. Going from direct-mapped to 2-way nearly halves conflict misses. Jumping to 4-way cuts them further. But 16-way versus 8-way shows minimal improvement for the added circuit complexity and power consumption.
The choice also depends on cache size. Small caches need higher associativity because they have fewer sets, increasing the chance of collisions. A 32KB 4-way L1 cache has only 128 sets, meaning many addresses collide in the same set. A 8MB 16-way L3 cache has thousands of sets, making conflicts less frequent even before the 16-way flexibility helps.
The Replacement Policy Challenge
When all ways in a set are full and new data arrives, the cache must evict something. The replacement policy determines what goes.
LRU (least recently used) is conceptually clean but expensive to implement precisely. An 8-way cache requires tracking access order among 8 lines per set. Most processors use approximations like pseudo-LRU or PLRU, which use a tree of bits to track rough recency with less overhead.
Random replacement sounds crude but performs surprisingly well, especially at higher associativities. With 8 ways, randomly picking a victim rarely chooses the worst option. Some Intel processors use a hybrid approach, avoiding the most recently used line but otherwise choosing randomly.
When Associativity Fails You
Set-associative caches still suffer from pathological access patterns. Strided memory access with a stride that’s a multiple of the cache size (or set count times line size) creates hotspots in specific sets.
Hash table implementations can trigger this. A power-of-two sized table accessed with a simple modulo operation concentrates activity in predictable sets. Adding a prime-number stride or using better hash functions helps. Structure padding and data layout matter too: arrays of structs with size that’s a power-of-two can create access patterns that alias to the same sets.
Cache-oblivious algorithms and data-oriented design both acknowledge this reality. Organizing data to maximize spatial and temporal locality within set constraints yields measurable performance gains, especially in tight loops processing large arrays.
The Hardware Perspective
Implementing set-associative caches requires parallel tag comparators, one per way. These comparators operate simultaneously, making the associativity check happen in a single clock cycle despite comparing multiple locations. The hit/miss signal feeds directly into the processor pipeline, so any added latency from complexity directly impacts performance.
Power consumption scales with associativity because more comparators mean more transistors switching every lookup. This matters more for L1 caches accessed every cycle than L3 caches accessed only on L2 misses. Battery-powered devices particularly feel this tradeoff, making 4-way L1 caches common in efficiency-oriented designs.
Set-associative caches prove that computer architecture rarely offers perfect solutions, only engineered compromises. The design persists because it solves the right problem: providing enough flexibility to handle real workloads without the cost of unlimited flexibility.