WCET analysis with MRU caches: Challenging LRU for predictability

Nan Guan, Mingsong Lv, Wang Yi, Ge Yu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

11 Citations (Scopus)

Abstract

Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, but still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics, originally designed for LRU, do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide the k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits all the advantages in efficiency, precision and composability of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with benchmarks show that the estimated WCET by our proposed MRU analysis is rather close to (5% ∼ 20% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for the cache replacement policy in real-time systems.
Original languageEnglish
Title of host publicationProceedings - 18th IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2012
Pages55-64
Number of pages10
DOIs
Publication statusPublished - 14 Jun 2012
Externally publishedYes
Event18th IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2012 - Beijing, China
Duration: 17 Apr 201219 Apr 2012

Conference

Conference18th IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2012
CountryChina
CityBeijing
Period17/04/1219/04/12

Keywords

  • abstract interpretation
  • cache analysis
  • MRU replacement
  • real-time system
  • WCET analysis

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this