Handling write backs in multi-level cache analysis for WCET estimation

Zhenkai Zhang, Zhishan Guo, Xenofon Koutsoukos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 25th International Conference on Real-Time Networks and Systems, RTNS 2017
PublisherAssociation for Computing Machinery
Pages208-217
Number of pages10
ISBN (Electronic)9781450352864
DOIs
StatePublished - Oct 4 2017
Event25th International Conference on Real-Time Networks and Systems, RTNS 2017 - Grenoble, France
Duration: Oct 4 2017Oct 6 2017

Publication series

NameACM International Conference Proceeding Series
VolumePart F131837

Conference

Conference25th International Conference on Real-Time Networks and Systems, RTNS 2017
CountryFrance
CityGrenoble
Period10/4/1710/6/17

Keywords

  • Multi-level cache analysis
  • WCET estimation
  • Write back handling

Fingerprint Dive into the research topics of 'Handling write backs in multi-level cache analysis for WCET estimation'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Z., Guo, Z., & Koutsoukos, X. (2017). Handling write backs in multi-level cache analysis for WCET estimation. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, RTNS 2017 (pp. 208-217). (ACM International Conference Proceeding Series; Vol. Part F131837). Association for Computing Machinery. https://doi.org/10.1145/3139258.3139269