Self-Correcting LRU Replacement Policies

摘要

L1 caches must be fast and have a good hit rate at the same time. To be fast,they must remain small.To have a good hit rate,they must be set-associative.With wider associativity the replacement algorithm becomes critical.The wide performance gap between OPT,the optimum off-line algorithm,and LRU suggests that LRU still makes too many mistakes.One way to improve L1 cache behavior is to manage actively the replacement policy to correct these mistakes on the fly.rn We introduce Self-correcting LRU(SCLRU)which is based on LRU augmented with a feedback loop to constantly monitor and correct replacement mistakes.It relies on several mechanisms to detect,predict,and correct bad replacement decisions.We identify three types of mistakes made by LRU and associate them with memory-access instructions.Our goal is to prevent a mistake to occur more than once.Based on evaluations using a set of seven SPEC95 benchmarks,we show that our approach achieves signif- icant and reliable miss rate improvements,sometimes close to that of OPT,for 2-way and 4-way L1 caches and can do this at a low implementation cost and without affecting the hit cycle time.