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?
3 Answers
My original answer was incorrect; see https://cs.stackexchange.com/a/105695/755 or https://cs.stackexchange.com/a/105719/755 for correct answers.
-
$\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$– BulatMar 18, 2019 at 8:31
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.
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.