Cache-related preemption delay analysis for multi-level inclusive caches

Zhenkai Zhang, Xenofon Koutsoukos

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

3 Scopus citations

Abstract

Cache-related preemption delay (CRPD) analysis is crucial when designing embedded control systems that employ preemptive scheduling. CRPD analysis for single-level caches has been studied extensively based on useful cache blocks (UCBs). As high-performance embedded processors are increasingly used, which are often equipped with multi-level caches, CRPD analysis for cache hierarchies also needs to be investigated. Recently, an approach has been proposed to estimate CRPD for multi-level non-inclusive caches. Since multi-level inclusive caches are also commonly used, especially in some multi-core processors, it becomes important to study how to analyze CRPD for inclusive cache hierarchies. However, as shown in this paper, new challenges appear due to the strict inclusion enforcement in the multi-level inclusive caches, which make the traditional UCB concept hard to use. In this paper, we propose a new concept of useful positive references (UPRs) to replace the UCB concept. Based on UPRs, we propose an approach to bound the additional cache misses due to a preemption in a two-level inclusive cache hierarchy. We present theoretical analysis to show the approach is safe, and we evaluate the proposed approach on a set of benchmarks to demonstrate its effectiveness. To the best of our knowledge, this is the first attempt to analyze CRPD for multi-level inclusive caches.

Original languageEnglish
Title of host publicationProceedings of the 13th International Conference on Embedded Software, EMSOFT 2016
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450344852
DOIs
StatePublished - Oct 1 2016
Event13th International Conference on Embedded Software, EMSOFT 2016 - Pittsburgh, United States
Duration: Oct 1 2016Oct 7 2016

Publication series

NameProceedings of the 13th International Conference on Embedded Software, EMSOFT 2016

Conference

Conference13th International Conference on Embedded Software, EMSOFT 2016
CountryUnited States
CityPittsburgh
Period10/1/1610/7/16

Keywords

  • CRPD Analysis
  • Cache Analysis
  • Timing Analysis

Fingerprint Dive into the research topics of 'Cache-related preemption delay analysis for multi-level inclusive caches'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Z., & Koutsoukos, X. (2016). Cache-related preemption delay analysis for multi-level inclusive caches. In Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016 [a16] (Proceedings of the 13th International Conference on Embedded Software, EMSOFT 2016). Association for Computing Machinery, Inc. https://doi.org/10.1145/2968478.2968481