Abstract Cache Replacement Policy Revisited

Cache replacement policy is a major design parameter of any memory hierarchy. The efficiency of the replacement policy affects both the hit rate and the access latency of a cache system. The higher the associativity of the cache, the more vital the replacement policy becomes. Therefore, a lot of work has been proposed, both in industry and academia, to enhance the performance of the replacement policy. However, all the proposed schemes are local in nature. The memory system does not consist of a single cache, but a hierarchy of caches. If each cache in the hierarchy decides which block to replace in an independent manner, the performance of the whole memory hierarchy will suffer, especially if inclusion is to be maintained. For example, if the level 2 cache decides to evict an LRU block, one or more blocks at level 1, possibly not LRU, can be evicted, therefore affecting the hit rate of level 1 and the overall performance. So, is a global replacement algorithm needed? In this paper we study the feasibility of having a global replacement algorithm. The contribution of this paper is threefold. First, we show the shortcomings of the localized replacement policies. Second, we propose several global replacement policies that tackle the shortcomings of the localized version. Third, we show when the proposed techniques do not work, and the characteristics of an application that makes use of these techniques. This will lead to a new way of thinking about replacement policies in general.