![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
cpu caches
Jun. 9th, 2012 05:37 pmBest way to understand something is to explain it.
Yesterday I had to explain cache associativity to a colleague from another team. Nothing too complex, replacement policies, prefetchers, coherency was out of the scope. Just plain difference between directly mapped, fully associative and N-ways, illustrated by pictures I recall from the Hennessy & Patterson book.
Answering all basic questions took me a while. They guy is a kind of person I like to work with: unlike myself it takes him a while to get a new concept, but in return he is very good in making the last finishing touches on software and polishing it - the skill I struggle with.
Even in this simple exercise he finally managed to ask me a question I could not answer instantly:
"OK, when we move from N way cache to 2*N way cache, the set index part of address decreases by 1 bit, and tag field increases by that one bit. Why it improves hit rate? If access pattern is random, it is now twice less likely to hit the same index in the cache, but twice more likely that at any given index the tag is the same.". It took me about a minute to formulate an answer, and then another minute to come up with correct one :)
This was not purely theoretical discussion - we have a project where caches are directly mapped and 2-way. In caches with low associativity conflict misses become noticeable, and if we control physical memory allocation we can mitigate the effect.
Yesterday I had to explain cache associativity to a colleague from another team. Nothing too complex, replacement policies, prefetchers, coherency was out of the scope. Just plain difference between directly mapped, fully associative and N-ways, illustrated by pictures I recall from the Hennessy & Patterson book.
Answering all basic questions took me a while. They guy is a kind of person I like to work with: unlike myself it takes him a while to get a new concept, but in return he is very good in making the last finishing touches on software and polishing it - the skill I struggle with.
Even in this simple exercise he finally managed to ask me a question I could not answer instantly:
"OK, when we move from N way cache to 2*N way cache, the set index part of address decreases by 1 bit, and tag field increases by that one bit. Why it improves hit rate? If access pattern is random, it is now twice less likely to hit the same index in the cache, but twice more likely that at any given index the tag is the same.". It took me about a minute to formulate an answer, and then another minute to come up with correct one :)
This was not purely theoretical discussion - we have a project where caches are directly mapped and 2-way. In caches with low associativity conflict misses become noticeable, and if we control physical memory allocation we can mitigate the effect.
