A Surprising Result

Apart from helping us catch bugs that would otherwise be very hard to figure out, some of our testing results surprised us. One particularly non-intuitive one is the following. Previously, we used to think that increasing associativity always decreases the number of cache misses. But, it is not true. Increasing associativity can actually increase the cache misses, albeit for some pathological cases. When we first encountered this result (quite rare depending on the sample size of addresses and the cache size), we put it in the category of some serious programming bug. After painstakingly perusing the code, and validating it by manually doing a test run on the input sample to ensure that it is not an implementation bug, we found the answer to our surprises. Since then, after analysing it more thoroughly, we came up with a small example that epitomizes this characteristics. Consider a cache of size = 2 elements, with only one element per block, and consider both a direct-mapped and fully-associative (in this case, 2-way set associative) cache with cache replacement policy as LRU (though this problem occurs with all common cache replacement schemes that we look at). In the direct-mapped case, all the even addresses would be mapped to frame 0, and all the odd addresses would be mapped to frame 1. Next, let the address stream be

        1 0 2 1

The direct mapped case suffers only 3 cold misses in this case but the fully associative case suffers 4 misses. We presently don't know for sure under which category of cache misses, this phenomenon of constructive interference comes, whereby the cache misses actually decrease by decreasing the associativity. Most probably, it should be put under capacity miss because the fully-associative cache had to replace the block because of a lack of sufficient capacity. It is not that the difference in the number of cache misses goes away, if the same set of accesses are made repeatedly. In fact, for every repeated access, in the direct mapped case, only two of the four accesses would result in a cache miss as opposed to three of the four accesses resulting in a cache miss in the fully associative case.

This demonstrates that it could well be that a program could start suffering from more cache misses, once we increase the associativity. In such cases, increasing associativity is unanimously bad. It not only increase the hit time (because of the increase in complexity of decision regarding which block to evict), but also adversely affects the cache miss rate.