Top-down and bottom-up multi-level cache analysis for WCET estimation

Zhenkai Zhang, Xenofon Koutsoukos

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

3 Scopus citations

Abstract

In many multi-core architectures, inclusive shared caches are used to reduce cache coherence complexity. However, the enforcement of the inclusion property can cause invalidation of memory blocks at higher cache levels. In order to ensure safety, analysis of cache hierarchies with inclusive caches for worst-case execution time (WCET) estimation is typically based on conservative decisions. Thus, the estimation may not be tight. In order to tighten the estimation, this paper proposes an approach that can more precisely analyze the behavior of a cache hierarchy maintaining the inclusion property. We illustrate the approach in the context of multi-level instruction caches. The approach first analyzes all the inclusive caches in the hierarchy in a bottom-up direction, and then analyzes the remaining non-inclusive caches in a top-down direction. In order to capture the inclusion victims and their effects, we also propose a concept of aging barrier and integrate it with the traditional must and persistence analyses to safely slow down their aging process so as to derive more precise analyses. We evaluate the proposed approach on a set of benchmarks and the evaluation reveals that the estimations are tightened.

Original languageEnglish
Title of host publicationProceedings - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages24-35
Number of pages12
ISBN (Electronic)9781479986033
DOIs
StatePublished - May 14 2015
Event21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015 - Seattle, United States
Duration: Apr 13 2015Apr 16 2015

Publication series

NameProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Volume2015-May
ISSN (Print)1545-3421

Conference

Conference21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
CountryUnited States
CitySeattle
Period04/13/1504/16/15

Fingerprint Dive into the research topics of 'Top-down and bottom-up multi-level cache analysis for WCET estimation'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Z., & Koutsoukos, X. (2015). Top-down and bottom-up multi-level cache analysis for WCET estimation. In Proceedings - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015 (pp. 24-35). [7108413] (Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS; Vol. 2015-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/RTAS.2015.7108413