HIT RATE MAXIMIZATION BY LOGICAL CACHE PARTITIONING IN A MULTI-CORE ENVIRONMENT

Abstract

It is imperative for any level of cache memory in a multi-core architecture to have a well defined, dynamic replacement algorithm in place to ensure consistent superlative performance. The most prevalently used LRU replacement policy does not acquaint itself dynamically to the changes in the workload. As a result, it can lead to sub-optimal performance for certain applications whose workloads exhibit frequently fluctuating patterns. To overcome the limitation of this conventional LRU approach, our paper proposes a novel counter-based replacement technique which logically partitions the cache elements into four zones based on their ‘likeliness’ to be referenced by the processor in the near future. Categorizing the elements into different zones is achieved with the help of a 3-bit counter that is associated with every cache line. On a cache hit, the corresponding element is promoted from one zone to another zone. Replacement candidates are chosen from the zones in the ascending order of their ‘likeliness factor’ (i.e.,) the first search space for the victim would be the never likely to be referenced zone, followed by the subsequent zones till the most likely to be referenced zone is reached. Periodic zone demotion of elements also occurs to make sure that stale data does not pollute the cache. Experimental results obtained by using the PARSEC benchmarks have shown almost 7% improvement in the overall number of hits and 3% improvement in the average cache occupancy percentage when compared to LRU algorithm.