东北大学学报（自然科学版）

东北大学学报（自然科学版） ›› 2013, Vol. 34 ›› Issue (11): 1554-1557.DOI: 10.12068/j.issn.1005-3026.2013.11.009

• 信息与控制 • 上一篇    下一篇

MRUCache替换算法平均性能剖析

吕鸣松，郭浩，关楠   

  1. (东北大学 信息科学与工程学院，辽宁沈阳110819)
  • 发布日期:2013-07-09
  • 通讯作者: 吕鸣松
  • 作者简介:吕鸣松(1980-)，男，辽宁沈阳人，东北大学讲师，博士.
  • 基金资助:
    国家自然科学基金资助项目(61100023)；辽宁省博士启动基金资助项目(20111003)；中央高校基本科研业务费专项资金资助项目(N120404008).

Dissection of the AverageCase Performance of MRU Cache Replacement Policy〓

LYU Mingsong， GUO Hao， GUAN Nan   

  1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.
  • Published:2013-07-09
  • Contact: LYU Mingsong
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

535

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

关键词: MRU, Cache, 替换算法, 平均性能, 实时性能

Abstract: 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.

Key words: MRU(most recently used), Cache, replacement policy, averagecase performance, realtime performance

中图分类号: