Why is the hit rate so bad until the cache has a certain size?

Question

For a certain cache, these are the measurements:

Test of different sizes of cache memory, from 16 to 1024 words, Block size = 2 words and assosiativity = 1. Access time: 20 cycles.

Size     16 words 32 words 64 words 128 words 256 words 512 words 1024 words

Hit rate   1%       1%         1%      1%        1%       17%      50%

Cycle count 44841 44521   43881   42601       40041      34841   19481

Why does hit rate look like it does? Why is the rate so bad until the size reaches a certain size?

Answer 1

The "certain size" is known as the "working set" of a piece of code, and the size of the working set varies considerably among different pieces of code.

The question is whether or not a particular item in the cache gets replaced by something else before it can be reused. You only get a decent hit rate if the cache is large enough to hold most of the working set without replacement occurring.

Answer 2

The rate is so bad until the cache reaches a certain size because it's direct mapped (associativity 1). The transition for this kind of cache, the poorest kind of cache, will be the worst. If the cache is 1024, it means that all addresses that differ only modulo 1024 map to the same block. Any time the program works with two or more memory locations that map to the same block, there is a constant stream of cache misses as those two memory locations fight to be in the cache. You can thrash a direct mapped cache simply by accessing just two memory locations in an alternating pattern!

Set associative and fully associative caches will have softer behavior because they take into account locality of reference, since they are able to choose from among "victim" blocks to be replaced when there is a cache miss.