Handling Write Backs in Multi-Level Cache Analysis for WCET Estimation


In this paper, we investigate how to soundly analyze multi-level caches that employ write-back policy at each level for worst-case execution time (WCET) estimation. To the best of our knowledge, there is only one existing approach for dealing with write backs in multi-level cache analysis. However, as shown in the paper, this existing approach is not sound. In order to soundly handle write backs, at a cache level, we need to consider whether a memory block is potentially dirty and when such a potentially dirty block may be evicted from the cache. To this end, we introduce a dirty attribute into persistence analysis for tracking dirty blocks, and over-approximate a write back window for each possible write back. Based on the overestimated write back occurring times, we propose an approach that can soundly deal with write backs in analysis of multi-level (unifed) caches for WCET estimation. Possible write back costs are also integrated into path analysis. We evaluate the proposed approach on a set of benchmarks to demonstrate its efectiveness.

Meeting Name

25th International Conference on Real-Time Networks and Systems, RTNS 2017 (2017: Oct. 4-6, Grenoble, France)


Computer Science

Keywords and Phrases

Multi-Level Cache Analysis; WCET Estimation; Write Back Handling

Document Type

Article - Conference proceedings

Document Version


File Type





© 2017 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 Jan 2017