edited by
38,359 views
91 votes
91 votes

Consider a $2$-way set associative cache with $256$ blocks and uses $\text{LRU}$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of access to memory blocks :

      $\big \{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129 \big \}$

is repeated $10$ times. The number of conflict misses experienced by the cache is _________ .

edited by

9 Answers

1 votes
1 votes

There are 256 lines, so a memory block will numbered x will sit inside the cache in x mod 256th block. (Numbered 0 - 127)

But here, we got a 2-way set associative cache on our hands, so we have a total of 128 sets, and a memory block will sit inside x mod 128th set. (Numbered 0 - 127)

First iteration: 4 conflict misses.

Subsequent 9 iterations: 8 conflict misses each.

Total conflict misses = 76 


This image shows the first iteration. When a block comes in for the first time, it's compulsory miss.

So, conflict misses = 4 (second appearances of 0, 256, 1 and 257)

 

For the remaining iterations, the first block of Set 0, and the first block of Set 1 would repeat identically. While 128 and 129 would be untouched. But this time, all misses are conflict misses, because it's not the first time the block is introduced in the cache.
So, conflict misses = 8 for nine iterations.

So, 4 + 9(8) = 76.


 

1 votes
1 votes

The following sequence of access to memory blocks: is repeated 10 times.

 

Answer:

Related questions