–
January 28, 2016
Caches are managed through admission or replacement policies. These policies decide which object should be kept in the cache in an attempt to maximize the hit probability. In this talk, I will review the performance models that are used to study caches. I will focus on a case where the cache is decomposed into lists. An item enters the cache via the first list and jumps to the next list whenever a hit on it occurs. The classical policies FIFO, RANDOM, CLIMB and LRU are obtained as special cases. I will develop a model to study the steady-state and transient behavior of a cache governed by such policy. I will show how to compute the hit probabilities and provide some guidelines on how to select a replacement algorithm. I will also disprove an old conjecture that CLIMB is optimal among this family.
This is a joint work with Benny Van Houdt.
