The GATE Grind

GATE 2017 CS (CS1) – Question 61

Computer Organization and Architecture · Memory Interfacing and Hierarchy · 2 marks · Numerical answer

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):

AccessResultCache (LRU first)
0miss (compulsory)0
128miss (compulsory)0, 128
256miss (compulsory, evicts 0)128, 256
128hit256, 128
0miss (conflict, evicts 256)128, 0
128hit0, 128
256miss (conflict, evicts 0)128, 256
128hit256, 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}.$$

More Memory Interfacing and Hierarchy questions

All Memory Interfacing and Hierarchy questions →