0
$\begingroup$

As far as I know a 2-way set-associative cache works better than a one-way one considerably but going to 4 and 8-way caches leads to a marginal improvement. My question is: does increasing K (going more than 8) lead to better miss rate although marginal?

$\endgroup$

3 Answers 3

0
$\begingroup$

My original answer was incorrect; see https://cs.stackexchange.com/a/105695/755 or https://cs.stackexchange.com/a/105719/755 for correct answers.

$\endgroup$
1
  • $\begingroup$ " it will never make the miss rate worse," - to my much surprise, @gnasher729 figured out that this is incorrect, and I (hopefully) simplified his explanation. See our answers. $\endgroup$
    – Bulat
    Mar 18, 2019 at 8:31
3
$\begingroup$

It's not guaranteed; it may depend on the data. Let's say an 8-way associative cache can hold 8 items at position 512k + j for each fixed j, and a 4-way associative cache can hold 4 items at position 1024k + j. My algorithm accesses locations 1024k + 512 + j for just four values k all over again. And locations 1024k + j for lots of values k, so there is basically no cache reuse.

In this case, 4-way associative caches has lots of hits and 8-way almost none. (There may be some mistake made somewhere, but you should figure out a pattern where 4-way ends up better).

For random access patterns, and for not carefully constructed patterns, higher associativity will be better. There is of course the problem that picking one out of 8 sets will take more time than picking one out of 2 or out of 4 sets.

$\endgroup$
2
$\begingroup$

I failed to understand @gnasher729 explanation, so this is my one demonstrating the same situation.

Let's consider just one line of 8-way cache, and compare it to two corresponding lines (A and B) of 4-way cache. Imagine the situation when we access 4 different addresses of line A, then 5 addresses of line B, repeating that in loop. So, hit:miss ratio for 4-way LRU cache will be 4:5. But in 8-way cache these 9 addresses will go to the same line, leading to 0% hit ratio.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.