Precise Multi-level Inclusive Cache Analysis for WCET Estimation

Zhenkai Zhang, Xenofon Koutsoukos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations


Multi-level inclusive caches are often used in multi-core processors to simplify the design of cache coherence protocol. However, the use of such cache hierarchies poses great challenges to tight worst-case execution time (WCET) estimation due to the possible invalidation behavior. Traditionally, multi-level inclusive caches are analyzed in a level-by-level manner, and at each level three analyses (i.e. must, may, and persistence) are performed separately. At a particular level, conservative decisions need to be made when the behaviors of other levels are not available, which hurts analysis precision. In this paper, we propose an approach which analyzes a multi-level inclusive cache by integrating the three analyses for all levels together. The approach is based on the abstract interpretation of a concrete operational semantics defined for multi-level inclusive caches. We evaluate the proposed approach and also compare it with two state-of-the-art approaches. From the experimental results, we can observe the proposed approach can significantly improve the analysis precision under relatively small cache size configurations.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE 36th Real-Time Systems Symposium, RTSS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages11
ISBN (Electronic)9781467395076
StatePublished - Jan 14 2016
Event36th IEEE Real-Time Systems Symposium, RTSS 2015 - San Antonio, United States
Duration: Dec 1 2015Dec 4 2015

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference36th IEEE Real-Time Systems Symposium, RTSS 2015
Country/TerritoryUnited States
CitySan Antonio


Dive into the research topics of 'Precise Multi-level Inclusive Cache Analysis for WCET Estimation'. Together they form a unique fingerprint.

Cite this