N-Way Set Associative Cache

computer-architecture memory

Definition

N-Way Set Associative Cache

An $N$-way set-associative cache is a set-associative cache in which each cache set contains exactly $N$ blocks.

Each block of main memory maps to exactly one cache set, but can be placed in any of the $N$ blocks of that set. So increasing $N$ increases the number of possible locations for a memory block and can reduce conflict cache misses.

Example

Two-way set-associative cache

Consider the loop:

addi s0, zero, 5
addi s1, zero, 0
LOOP:
  beq  s0, zero, DONE
  lw   s2, 0x4(s1)
  lw   s4, 0x24(s1)
  addi s0, s0, -1
  j    LOOP
DONE:

In a direct-mapped cache, the words at addresses 0x4 and 0x24 may map to the same cache set, so they evict one another and produce repeated conflict cache misses.

In a $2$-way set-associative cache, both words still map to the same set, but they can be stored in different ways of that set at the same time.

So only the first access to each block misses. After both blocks have been loaded, the later accesses hit. Over $5$ loop iterations, this gives $2$ misses out of $10$ loads, so the miss rate is

$$\frac{2}{10}=20\%.$$

$2$-way set associative cache

$4$-way set associative cache