Consider a 2-way set associative cache with 256 blocks and uses LRU replacement. Initially the cache is empty. Conflict misses are those misses which occur due to contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks $$(0, 128, 256, 128, 0, 128, 256, 128, 1, 129, 257, 129, 1, 129, 257, 129)$$ is repeated 10 times. The number of conflict misses experienced by the cache is _________.

### Cache Organization

• Total number of cache blocks = $256$

• Associativity = $2$-way set-associative

• Number of sets:

  $$\text{Sets} = \frac{256}{2} = 128 \quad (\text{indexed } 0 \text{ to } 127)$$

### Mapping of Blocks

• Set index for block $B = B \pmod{128}$

• Blocks $0, 128, 256$ map to $\text{Set } 0$.

• Blocks $1, 129, 257$ map to $\text{Set } 1$.

The given sequence consists of accesses to Set $0$ followed by identical relative accesses to Set $1$:

• Sequence for Set $0$: $(0, 128, 256, 128, 0, 128, 256, 128)$

• Sequence for Set $1$: $(1, 129, 257, 129, 1, 129, 257, 129)$

### Trace for Set $0$ (Capacity = 2 blocks, LRU replacement)

Iteration 1:

1. Access 0: Compulsory miss $\rightarrow$ Cache: $[0]$

2. Access 128: Compulsory miss $\rightarrow$ Cache: $[0, 128]$

3. Access 256: Compulsory miss (replaces $0$) $\rightarrow$ Cache: $[128, 256]$

4. Access 128: Hit $\rightarrow$ Cache: $[256, 128]$

5. Access 0: Conflict miss (replaces $256$) $\rightarrow$ Cache: $[128, 0]$

6. Access 128: Hit $\rightarrow$ Cache: $[0, 128]$

7. Access 256: Conflict miss (replaces $0$) $\rightarrow$ Cache: $[128, 256]$

8. Access 128: Hit $\rightarrow$ Cache: $[256, 128]$

• In Iteration 1 for Set 0: $3$ Compulsory misses, $2$ Conflict misses.

Iterations 2 through 10 (9 iterations): Starting cache state: $[256, 128]$ ($256$ is LRU, $128$ is MRU)

1. Access 0: Conflict miss (replaces $256$) $\rightarrow$ Cache: $[128, 0]$

2. Access 128: Hit $\rightarrow$ Cache: $[0, 128]$

3. Access 256: Conflict miss (replaces $0$) $\rightarrow$ Cache: $[128, 256]$

4. Access 128: Hit $\rightarrow$ Cache: $[256, 128]$

5. Access 0: Conflict miss (replaces $256$) $\rightarrow$ Cache: $[128, 0]$

6. Access 128: Hit $\rightarrow$ Cache: $[0, 128]$

7. Access 256: Conflict miss (replaces $0$) $\rightarrow$ Cache: $[128, 256]$

8. Access 128: Hit $\rightarrow$ Cache: $[256, 128]$

• Each subsequent iteration produces $4$ conflict misses in Set $0$.

• Total conflict misses for Set $0 = 2 + (9 \times 4) = 38$.

### Total Conflict Misses Since Set $1$ follows the exact same pattern: