Set-associative and fully associative caches

Overview

We saw that direct-mapped caches suffer from conflict misses when multiple addresses map to the same cache line. Set-associative caches solve this by allowing each memory block to go into multiple possible locations, while fully associative caches take this to the extreme by allowing a block to go anywhere. This is the fundamental tradeoff: flexibility vs. hardware complexity.

Why Do We Need Associativity?

Set-associative caches give you a small choice of spots. Fully associative caches let you park anywhere. More choice = fewer conflicts, but finding your car takes longer (more comparison hardware).

Set-Associative Caches

• N = 1: direct-mapped
• N = 2, 4, 8: common set-associative configurations
• N = total cache lines: fully associative

Address Decomposition

For a set-associative cache, the address splits into:

$\text{Address} = \langle \text{Tag} \mid \text{Set Index} \mid \text{Block Offset} \rangle$

$\text{Number of sets } S = \frac{C}{B \times N}$

$\text{Set index bits} = \log_2(S)$

Why this formula?

• Total cache lines = $C / B$
• Each set holds $N$ lines
• So number of sets = $(C/B) / N = C/(B \times N)$

The set index bits select which set to search. The tag bits distinguish between different blocks mapped to the same set. The block offset selects the byte within the block (same as direct-mapped).

Step 1: Calculate number of sets $S = \frac{64\text{KB}}{64\text{B} \times 4} = \frac{65536}{256} = 256 \text{ sets}$

Why 65536? $64\text{ KB} = 64 \times 1024 = 65536$ bytes.

Step 2: Calculate bit fields

• Block offset: $\log_2(64) = 6$ bits
• Set index: $\log_2(256) = 8$ bits
• Tag: $32 - 8 - 6 = 18$ bits

Why 8 bits for index? We need to distinguish between 256 sets, and $2^8 = 256$.

Step 3: Example address lookup Address: 0x001A4C0 (a 32-bit address, shown as 7 hex digits = 28 bits; the top 4 hex digits are 0).

Full 32-bit binary:

0000 0000 0001 1010 0100 1100 0000

(That is $0\text{x}001A4C0 = 0000\,0000\,0000\,0001\,1010\,0100\,1100\,0000_2$.)

Partition into Tag(18) | Index(8) | Offset(6), from MSB to LSB:

Tag    (18 bits): 00 0000 0000 0001 1010   = 0x01A
Index  (8 bits):  0100 1100                 = 0x4C = 76
Offset (6 bits):  00 0000                    = 0

Check: $18 + 8 + 6 = 32$ bits ✓, and the 8-bit index $01001100_2 = 64 + 8 + 4 = 76$.

The block maps to set 76. The cache controller checks all 4 tag fields in set 76 in parallel to find a match.

How Set-Associative Lookup Works

1. Extract set index from address → select the set
2. Compare tag against all N tags in the set simultaneously (parallel comparators)
3. If any tag matches and valid bit = 1 → HIT, use that line's data
4. If no match → MISS, fetch from memory, place in any line of that set (replacement policy decides which)

Fully Associative Caches

Address Decomposition

$\text{Address} = \langle \text{Tag} \mid \text{Block Offset} \rangle$

No index field! The tag must be large enough to identify the block uniquely.

$\text{Number of lines } = \frac{C}{B}$

$\text{Tag bits} = A - \log_2(B)$

$\text{Offset bits} = \log_2(B)$

Why no index? Since a block can go anywhere, we don't partition the cache into sets. We search everything.

Lines: $16384 / 64 = 256$ lines

Bit fields:

• Offset: $\log_2(64) = 6$ bits
• Tag: $32 - 6 = 26$ bits
• Index: 0 bits

On every access, the hardware compares the 26-bit tag against all 256 tags in parallel. This requires 256 comparators—expensive but eliminates conflict misses entirely.

Comparison: Direct-Mapped vs. Set-Associative vs. Fully Associative

| Property | Direct-Mapped | N-Way Set-Assoc | Fully Associative | |----------|---------------|-----------------| | Ways per set | 1 | N | C/B (all lines) | | Number of sets | C/B | C/(B×N) | 1 | | Comparators | 1 | N | C/B | | Hit time | Fastest | Medium | Slowest | | Miss rate | Highest (conflicts) | Medium | Lowest | | Hardware cost | Cheapest | Medium | Most expensive | | Use case | L1 caches (speed critical) | L2, L3 caches | TLBs, small caches |

Most real caches use 2-way, 4-way, or 8-way set-associative as a sweet spot.

Replacement Policies

When a miss occurs in a set-associative or fully associative cache, we must choose which line to evict. Direct-mapped caches have no choice (only one possible location), but associative caches need a replacement policy.

LRU performs best in practice but requires tracking access order (e.g., with counter bits or an "age matrix"). For 2-way, LRU needs 1 bit per set. For 4-way, it needs more complex logic.

A miss occurs. We evict Way 1 (least recently used). After filling Way 1 with new data, it becomes the most recently used: [Way 1, Way 2, Way 0, Way 3]

Why track order? LRU exploits temporal locality: if a block was used recently, it's likely to be used again soon. Evicting the "coldest" block minimizes future misses.

Derivation: Cache Configuration Math

Let's derive the relationship between cache parameters.

Given:

• Total cache size: $C$ bytes
• Block size: $B$ bytes
• Associativity: $N$ ways

Total cache lines: $L = \frac{C}{B}$

Why? Each line stores one block of $B$ bytes. If we have $C$ total bytes, we can fit $C/B$ blocks.

Number of sets: $S = \frac{L}{N} = \frac{C}{B \cdot N}$

Why? We have $L$ total lines, distributed evenly into $N$-way sets. Each set gets $N$ lines, so we need $L/N$ sets.

Set index bits: $i = \log_2(S) = \log_2\left(\frac{C}{B \cdot N}\right)$

Why? We need enough bits to uniquely identify one of $S$ sets. $\log_2(S)$ bits can represent $2^{\log_2(S)} = S$ values.

Tag bits: $t = A - i - b = A - \log_2(S) - \log_2(B)$

where $A$ is address width, $b = \log_2(B)$ is block offset bits.

Why? The address is partitioned into tag, index, and offset. What's not used for index and offset must be tag.

Common Mistakes

Why it feels right: "4-way" sounds like "4 times."

The fix: Associativity describes how many places a block can go, not total capacity. A 64 KB direct-mapped cache and a 64 KB 4-way set-associative cache have the same total storage. The 4-way version just has fewer sets (each with 4 lines), while direct-mapped has more sets (each with 1 line).

Why it feels right: "Any block can go anywhere" sounds unlimited.

The fix: Fully associative still has $C/B$ total lines. It just means no index bits—the block can occupy any of those lines. You still evict when full.

Why it feels right: Sequential thinking from software.

The fix: Hardware uses parallel comparators. All N tag comparisons happen simultaneously. Hit time grows slightly due to multiplexer delay, but it's not linear in N.

Worked Problem: Designing a 2-Way Set-Associative Cache

Problem: Design a 2-way set-associative cache with 32 KB capacity, 128-byte blocks, for a system with 32-bit addresses. Calculate:

1. Number of sets
2. Bit field sizes
3. Total tag storage bits

Solution:

Step 1: Number of sets $S = \frac{C}{B \cdot N} = \frac{32768}{128 \cdot 2} = \frac{32768}{256} = 128 \text{ sets}$

Why divide by 2? We have 2 ways, so lines are split into 2 groups per set.

Step 2: Bit fields

• Block offset: $\log_2(128) = 7$ bits
• Set index: $\log_2(128) = 7$ bits
• Tag: $32 - 7 - 7 = 18$ bits

Step 3: Total tag storage

• Each line needs: 18-bit tag + 1 valid bit + 1 dirty bit (if write-back) = 20 bits overhead
• Total lines: $32768 / 128 = 256$ lines
• Total overhead: $256 \times 20 = 5120$ bits = 640 bytes

Additional: Each set has 2 lines, so we need 1 LRU bit per set (to track which way is least recent). Total: 128 sets × 1 bit = 128 bits = 16 bytes.

Active Recall

In a direct-mapped notebook, each problem must go on a specific page number (like problem 10 always goes on page 10). If you have two problem 10s from different chapters, they fight for the same page—every time you write one, you erase the other. Super annoying!

In a set-associative notebook, you divide your notebook into sections. Problem 10 still maps to a specific section, but within that section, you have 2 or 4 empty slots. So two different problem 10s can both fit without erasing each other. Much better!

In a fully associative notebook, problem 10 can go on any page you want. No fights! But now finding where you wrote problem 10 takes longer—you have to scan every page. That's the tradeoff: more flexibility but slower to search.

Mnemonic

Connections

• Direct-mapped caches — the N=1 special case
• Cache replacement policies — LRU, FIFO, Random for choosing eviction victim
• Cache coherence — more complexity when multiple cores have associative caches
• Translation Lookaside Buffer (TLB) — often fully associative, small, fast
• Conflict misses vs capacity misses — associativity reduces conflict misses
• Cache performance metrics — hit time increases, miss rate decreases with associativity
• Write policies — write-back and write-through work the same across associativity types

#flashcards/hardware

What does "4-way set-associative" mean? :: A cache where each set contains 4 lines (ways), and a memory block maps to a specific set but can occupy any of the 4 lines within that set.

Concept Map

Hinglish (regional understanding)