GATE 2017 CS – 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
There are 128 sets. Blocks 0, 128 and 256 all map to set 0, and blocks 1, 129 and 257 map to set 1, and both sets see the same pattern. In set 0, the first pass has 3 compulsory misses and 2 conflict misses. Every later pass has 4 conflict misses, since 256 and 0 keep pushing each other out while 128 stays. That is $2 + 9 \times 4 = 38$ conflict misses per set, so $2 \times 38 = 76$.