MRU Cache替换算法平均性能剖析

Dissection of the Average-Case Performance of MRU Cache Replacement Policy

研究了MRU替换算法的平均性能问题.研究结果发现,在一定条件下,MRU的平均性能优于LRU替换算法.针对具有线性访问序列循环体的程序,形式化证明了MRU平均性能优于LRU的成立条件.并采用实时系统时间分析测试集针对不同Cache配置进行实验,验证了MRU平均性能优于LRU这一结果的普遍性.结合本文结果与MRU实时性能的研究结果,可以认为MRU具有优异的平均性能和实时性能.

Cache is a processor feature that can greatly affect the performance of programs. The average-case performance of most recently used （MRU） Cache replacement policy was studied. Research results showed that MRU outperforms LRU in some circumstances. By analyzing loop structures with sequential memory accesses, the condition for this phenomenon is given and formally proved. Extensive experiments were conducted on real-time timing analysis benchmarks for different Cache configurations, which shows that MRU outperforms LRU in lots of execution scenarios. Combining this result and recent results on the real-time performance of MRU replacement policy, it can be concluded that MRU has very high performance in both average-case and real-time metrics.