Precise Multi-level Inclusive Cache Analysis for WCET Estimation

Zhenkai Zhang, Xenofon Koutsoukos

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

Abstract

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.
Pages350-360
Number of pages11
ISBN (Electronic)9781467395076
DOIs
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
Volume2016-January
ISSN (Print)1052-8725

Conference

Conference36th IEEE Real-Time Systems Symposium, RTSS 2015
CountryUnited States
CitySan Antonio
Period12/1/1512/4/15

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

  • Cite this

    Zhang, Z., & Koutsoukos, X. (2016). Precise Multi-level Inclusive Cache Analysis for WCET Estimation. In Proceedings - 2015 IEEE 36th Real-Time Systems Symposium, RTSS 2015 (pp. 350-360). [7383591] (Proceedings - Real-Time Systems Symposium; Vol. 2016-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/RTSS.2015.40