Lec 05-01-2025: Cache Mapping Strategies

There are three main strategies for deciding where in the cache a memory block can be stored. They differ in how much freedom blocks have in choosing their location, which in turn affects hardware cost, lookup speed, and miss rate.

Associative Mapping (aka Fully Associative)

The idea here is to give blocks complete freedom: any block from main memory can go into any cache line. Because a block can be “associated” with any line, this is also called Fully Associative mapping.

The flexibility of letting blocks go anywhere means there’s no quick formula to find where a given block ended up. Instead, when the CPU requests a block, the cache has to check all lines to see if any of them holds it. To improve the search time, each line gets its own hardware comparator to then be able to invoke a parallel search — fast, but the hardware cost grows with the number of lines, so this approach is only practical for small caches.

Since any block can occupy any line, each line needs to store the block’s number as a tag, so the cache knows which block is currently sitting there.

Cache line structure:

• Valid/Invalid bit
• Tag (block number)
• Data (could be multiple words)

Consider a situation where we get the following sequence of block accesses:

$$5, 2, 20, 30, 15$$

$\color{red}{\times}$ indicates a miss.

$\color{blue}{\checkmark}$ indicates a hit.

$$\begin{array}{ccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} \\ 5 & 2 & 20 & 30 & 15 \end{array} \;\longrightarrow\; \textbf{5 misses}$$

The diagram shows a cache that has been filled up with blocks 5, 2, 20, and 30 through successive cold misses. When block 15 is accessed next, it’s also a miss — and since every line is occupied, something has to be evicted to make room.

The standard replacement policy for fully associative caches is LRU (Least Recently Used): the block that hasn’t been accessed for the longest time gets replaced. The reasoning is that recently used data is more likely to be needed again soon, so you keep what’s fresh and discard what’s stale.

Example Problem

Find the number of misses with a fully associative mapping, consisting of 4 one-word blocks, given the following sequence of block addresses:

$$1, 2, 4, 6, 1, 2, 4, 2, 4, 3, 5$$

Solution:

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{6 misses}$$

Explanation

The first 4 accesses (1, 2, 4, 6) are cold misses that fill the cache. The next 5 accesses (1, 2, 4, 2, 4) all hit — those blocks are still in the cache. The last two (3, 5) both miss and each require an eviction, for 6 total misses.

Block	Result	Action
1	$\color{red}{\times}$ miss	Cache has a free line — Add block 1
2	$\color{red}{\times}$ miss	Cache has a free line — Add block 2
4	$\color{red}{\times}$ miss	Cache has a free line — Add block 4
6	$\color{red}{\times}$ miss	Cache has a free line — Add block 6
1	$\color{blue}{\checkmark}$ hit	—
2	$\color{blue}{\checkmark}$ hit	—
4	$\color{blue}{\checkmark}$ hit	—
2	$\color{blue}{\checkmark}$ hit	—
4	$\color{blue}{\checkmark}$ hit	—
3	$\color{red}{\times}$ miss	Cache is full, LRU is block 6 — Evict and replace with 3
5	$\color{red}{\times}$ miss	Cache is full, LRU is block 1 — Evict and replace with 5

LRU eviction walkthrough

Once the cache is full, each miss requires evicting the least recently used block. To find it, scan backwards through the sequence up to that point and collect unique blocks in the order you encounter them — the last unique block you collect is the LRU.

The first miss that requires an eviction: block 3

Block 3 arrives and the cache is full with $\{1, 2, 4, 6\}$. Scanning backwards through the access sequence so far:

$$\underbrace{1\ 2\ 4\ 6\ 1\ 2\ 4\ 2\ 4}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{unique order}: \ 4,\ 2,\ 1,\ 6$$

Reading right-to-left: 4 (used most recently), then 2, then 1, then 6 (LRU — the 4th unique, since the cache holds 4 blocks). Evict 6, insert 3.

The second miss that requires an eviction: block 5

Block 5 arrives and the cache now holds $\{1, 2, 4, 3\}$. Scanning backwards through the access sequence so far:

$$\underbrace{1\ 2\ 4\ 6\ 1\ 2\ 4\ 2\ 4\ 3}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{unique order}: \ 3,\ 4,\ 2,\ 1$$

Reading right-to-left: 3 (used most recently), then 4, then 2, then 1 (LRU). Evict 1, insert 5.

---

Direct Mapping

Rather than searching all lines, direct mapping assigns each memory block to exactly one cache line, determined by:

$$(\text{block } \#) \bmod (\text{\# of cache lines})$$

This makes lookups fast and cheap — no parallel search needed, since the cache goes directly to the one line a block can occupy. The downside is that many blocks share the same line (e.g., in a 4-line cache, blocks 0, 4, 8, 12, … all map to line 0). If two of those blocks are accessed frequently together, they’ll keep evicting each other even though other lines sit empty — a problem called thrashing.

Since multiple blocks map to the same line, each line stores a tag identifying which block is currently there. Without it, there’d be no way to tell whether the block currently in line 0 is block 0, block 4, or block 8.

Cache line structure:

• Tag (to tell apart blocks sharing the same line)
• Line Index
• Word offset (if multiple words per block)

Example Problem

Find the number of misses with Direct Mapping, consisting of 4 one-word blocks, given the following sequence of block addresses:

$$1, 2, 4, 6, 1, 2, 4, 2, 4, 3, 5$$

Solution:

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{7 misses}$$

Explanation

Each block maps to line $(\text{block\#}) \bmod 4$. When two blocks share a line, the incoming block simply overwrites whoever is there.

Block	Line	Result	Action
1	1	$\color{red}{\times}$ miss	Line is empty — Add block 1 to it
2	2	$\color{red}{\times}$ miss	Line is empty — Add block 2 to it
4	0	$\color{red}{\times}$ miss	Line is empty — Add block 4 to it
6	2	$\color{red}{\times}$ miss	Line is occupied by block 2 — Evict and replace
1	1	$\color{blue}{\checkmark}$ hit	—
2	2	$\color{red}{\times}$ miss	Line is occupied by block 6 — Evict and replace
4	0	$\color{blue}{\checkmark}$ hit	—
2	2	$\color{blue}{\checkmark}$ hit	—
4	0	$\color{blue}{\checkmark}$ hit	—
3	3	$\color{red}{\times}$ miss	Line is empty — Add block 3 to it
5	1	$\color{red}{\times}$ miss	Line is occupied by block 1 — Evict and replace

---

Set Associative Mapping

Set associative mapping is a middle ground between the above two strategies. The cache is divided into sets, each holding a fixed number of lines.

• Which set a block goes to is determined by direct mapping: $(\text{block\#}) \bmod (\text{\# of sets})$
• Which line within that set is chosen by fully associative placement — the block can go into any line in the set

This limits the parallel search to just the lines within one set (far fewer comparators than fully associative), while still giving enough flexibility within each set to reduce thrashing.

The number of lines per set is called the N-way count:

• 8 lines, 2 sets $\rightarrow$ 4 lines/set $\rightarrow$ 4-way associative
• 8 lines, 4 sets $\rightarrow$ 2 lines/set $\rightarrow$ 2-way associative

Example Problem

Find the number of misses with a 2-way set associative mapping, consisting of 4 one-word blocks, given the following sequence of block addresses:

$$1, 2, 4, 6, 1, 2, 4, 2, 4, 3, 5$$

Solution:

$$\text{\# of sets} = \frac{\text{\# of lines}}{\text{\# of lines per set}} = \frac{4}{2} = 2 \text{ sets}$$

Blocks are inserted into set $\#$:

$$(\text{block } \#) \bmod (\text{\# of sets})$$

With 2 sets, even-numbered blocks go to $S_0$ and odd-numbered blocks go to $S_1$. Each set holds 2 lines and uses LRU when full.

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{8 misses}$$

Explanation

Each block maps to a set via $(\text{block\#}) \bmod 2$: even blocks go to $S_0$, odd blocks to $S_1$. Each set holds 2 lines and uses LRU when full.

Block	Set	Result	Action
1	$S_1$	$\color{red}{\times}$ miss	Set has a free line — Add block 1
2	$S_0$	$\color{red}{\times}$ miss	Set has a free line — Add block 2
4	$S_0$	$\color{red}{\times}$ miss	Set has a free line — Add block 4
6	$S_0$	$\color{red}{\times}$ miss	Set is full, LRU is block 2 — Evict and replace with 6
1	$S_1$	$\color{blue}{\checkmark}$ hit	—
2	$S_0$	$\color{red}{\times}$ miss	Set is full, LRU is block 4 — Evict and replace with 2
4	$S_0$	$\color{red}{\times}$ miss	Set is full, LRU is block 6 — Evict and replace with 4
2	$S_0$	$\color{blue}{\checkmark}$ hit	—
4	$S_0$	$\color{blue}{\checkmark}$ hit	—
3	$S_1$	$\color{red}{\times}$ miss	Set has a free line — Add block 3
5	$S_1$	$\color{red}{\times}$ miss	Set is full, LRU is block 1 — Evict and replace with 5

LRU eviction walkthrough

The process is the same as fully associative, but before scanning backwards, filter the sequence to only blocks that belong to the same set as the incoming block.

The first miss that requires an eviction: block 6

Block 6 maps to $S_0$. Scanning backwards through the access sequence so far, filter to $S_0$ (even) blocks only, then read right-to-left for unique blocks.

$$\underbrace{\cancel{1}\ 2\ 4}_{\text{scan} \longleftarrow} \quad \xrightarrow{\text{filter to } S_0} \quad \underbrace{2 \quad 4}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{LRU} = 2$$

Reading right-to-left: 4 (used most recently), then 2 (LRU). Evict block 2, insert block 6.

Access 5 (block 1) is a hit -- no eviction needed

Block 1 is already in $S_1$, so this is a hit.

The second miss that requires an eviction: block 2

Block 2 maps to $S_0$. $S_0$ currently holds blocks 4 and 6. Scanning backwards through the access sequence so far, filter to $S_0$ blocks only.

$$\underbrace{\cancel{1}\ 2\ 4\ 6\ \cancel{1}}_{\text{scan} \longleftarrow} \quad \xrightarrow{\text{filter to } S_0} \quad \underbrace{2 \quad 4 \quad 6}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{LRU} = 4$$

Reading right-to-left: 6 (used most recently), then 4 (LRU — the 2nd unique, since the set holds 2 lines). Evict block 4, insert block 2.

The third miss that requires an eviction: block 4

Block 4 maps to $S_0$. $S_0$ currently holds blocks 6 and 2. Scanning backwards through the access sequence so far, filter to $S_0$ blocks only.

$$\underbrace{\cancel{1}\ 2\ 4\ 6\ \cancel{1}\ 2}_{\text{scan} \longleftarrow} \quad \xrightarrow{\text{filter to } S_0} \quad \underbrace{2 \quad 4 \quad 6 \quad 2}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{LRU} = 6$$

Reading right-to-left: 2 (used most recently), then 6 (LRU — not seen again after its first appearance). Evict block 6, insert block 4.

Accesses 8--10 (blocks 2, 4, 3) require no eviction

Blocks 2 and 4 are hits in $S_0$. Block 3 maps to $S_1$, which has a free line (only block 1 is there), so it’s a cold miss with no eviction needed.

The fourth miss that requires an eviction: block 5

Block 5 maps to $S_1$. $S_1$ currently holds blocks 1 and 3. Scanning backwards through the access sequence so far, filter to $S_1$ (odd) blocks only.

$$\underbrace{1\ \cancel{2}\ \cancel{4}\ \cancel{6}\ 1\ \cancel{2}\ \cancel{4}\ \cancel{2}\ \cancel{4}\ 3}_{\text{scan} \longleftarrow} \quad \xrightarrow{\text{filter to } S_1} \quad \underbrace{1 \quad 1 \quad 3}_{\text{scan} \longleftarrow} \quad \Rightarrow \quad \text{LRU} = 1$$

Reading right-to-left: 3 (used most recently), then 1 (LRU). Evict block 1, insert block 5.