FIFO cache analysis for WCET estimation: A quantitative approach

Nan Guan, Xinping Yang, Mingsong Lv, Wang Yi

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

19 Citations (Scopus)


Although most previous work in cache analysis for WCET estimation assumes the LRU replacement policy, in practise more processors use simpler non-LRU policies for lower cost, power consumption and thermal output. This paper focuses on the analysis of FIFO, one of the most widely used cache replacement policies. Previous analysis techniques for FIFO caches are based on the same framework as for LRU caches using qualitative always-hit/always-miss classifications. This approach, though works well for LRU caches, is not suitable to analyze FIFO and usually leads to poor WCET estimation quality. In this paper, we propose a quantitative approach for FIFO cache analysis. Roughly speaking, the proposed quantitative analysis derives an upper bound on the "miss ratio" of an instruction (set), which can better capture the FIFO cache behavior and support more accurate WCET estimations. Experiments with benchmarks show that our proposed quantitative FIFO analysis can drastically improve the WCET estimation accuracy over pervious techniques (the average overestimation ratio is reduced from around 70% to 10% under typical setting).
Original languageEnglish
Title of host publicationProceedings - Design, Automation and Test in Europe, DATE 2013
Number of pages6
Publication statusPublished - 21 Oct 2013
Externally publishedYes
Event16th Design, Automation and Test in Europe Conference and Exhibition, DATE 2013 - Grenoble, France
Duration: 18 Mar 201322 Mar 2013


Conference16th Design, Automation and Test in Europe Conference and Exhibition, DATE 2013

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'FIFO cache analysis for WCET estimation: A quantitative approach'. Together they form a unique fingerprint.

Cite this