GATE 2017 CS (CS1) – Question 61
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 76
Explanation
256 blocks in a 2-way cache gives $256/2=128$ sets, so block $b$ goes to set $b\bmod128$. Blocks $0,128,256$ all map to set 0. Blocks $1,129,257$ all map to set 1, and the pattern in set 1 is identical to set 0, so count one set and double.
**Set 0, one pass of the sequence** $0,128,256,128,0,128,256,128$ with LRU (2 ways):
| Access | Result | Cache (LRU first) |
|---|---|---|
| 0 | miss (compulsory) | 0 |
| 128 | miss (compulsory) | 0, 128 |
| 256 | miss (compulsory, evicts 0) | 128, 256 |
| 128 | hit | 256, 128 |
| 0 | miss (conflict, evicts 256) | 128, 0 |
| 128 | hit | 0, 128 |
| 256 | miss (conflict, evicts 0) | 128, 256 |
| 128 | hit | 256, 128 |
First pass: 3 compulsory + 2 conflict misses.
**Later passes** start with cache $\{256,128\}$ and each have 4 misses (0, 256, 0, 256), all conflict misses.
Conflict misses in set 0 over 10 passes: $2+9\times4=38$. Set 1 behaves the same: another 38.
$$\text{Total conflict misses}=38+38=\mathbf{76}.$$