Dissection of the average-case performance of MRU cache replacement policy

Ming Song Lyu, Hao Guo, Nan Guan

Research output: Journal article publicationJournal articleAcademic researchpeer-review


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.
Original languageEnglish
Pages (from-to)1554-1557
Number of pages4
JournalDongbei Daxue Xuebao/Journal of Northeastern University
Issue number11
Publication statusPublished - 26 Dec 2013
Externally publishedYes


  • Average-case performance
  • Cache
  • MRU(most recently used)
  • Real-time performance
  • Replacement policy

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this