Genetic Algorithms and Cache Replacement Policy

This paper proposes a novel methodology for cache replacement policy based on techniques of genetic algorithms. The key innovation is to allow the cache to be tuned to a given workload by using an appropriate combination of LRU, FIFO, or other information such as a history of hits and misses in a set or the number of hits to each line. By employing genetic algorithms the search for the appropriate combination can be performed effectively and efficiently. In order to allow tuning of individual benchmarks, we propose the use of programmable replacement policies. In this paper, we use an optimal replacement policy, known as OPT. OPT gives the theoretical limit of any replacement policy which does not prefetch. OPT has been found to provide a miss rate about 70% that of LRU for the same size and configuration of cache [20]. Our objective is to reduce the large LRU-OPT gap in miss rate and we use the LRU-OPT gain --- the fraction of the LRU-OPT gap we eliminate --- to measure our improvemen..