Improving the precision of abstract interpretation based cache persistence analysis

Zhenkai Zhang, Xenofon Koutsoukos

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

5 Scopus citations

Abstract

When designing hard real-time embedded systems, it is required to estimate the worst-case execution time (WCET) of each task for schedulability analysis. Precise cache persistence analysis can significantly tighten the WCET estimation, especially when the program has many loops. Methods for persistence analysis should safely and precisely classify memory references as persistent. Existing safe approaches suffer from multiple sources of pessimism and may not provide precise results. In this paper, we first identify some sources of pessimism that two recent approaches based on younger set and may analysis may encounter. Then, we propose two methods to eliminate these sources of pessimism. The first method improves the update function of the may analysis-based approach; and the second method integrates the younger set-based and may analysis-based approaches together to further reduce pessimism. We also prove the two proposed methods are still safe. We evaluate the approaches on a set of benchmarks and observe the number of memory references classified as persistent is increased by the proposed methods. Moreover, we empirically compare the storage space and analysis time used by different methods.

Original languageEnglish
Title of host publicationLCTES 2015 - Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems
PublisherAssociation for Computing Machinery
Pages98-107
Number of pages10
ISBN (Electronic)9781450332576
DOIs
StatePublished - Jun 4 2015
Event16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems, LCTES 2015 - Portland, United States
Duration: Jun 18 2015Jun 19 2015

Publication series

NameProceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES)
Volume2015-June

Conference

Conference16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems, LCTES 2015
CountryUnited States
CityPortland
Period06/18/1506/19/15

Keywords

  • Cache analysis
  • Persistence analysis
  • WCET

Fingerprint Dive into the research topics of 'Improving the precision of abstract interpretation based cache persistence analysis'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Z., & Koutsoukos, X. (2015). Improving the precision of abstract interpretation based cache persistence analysis. In LCTES 2015 - Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (pp. 98-107). (Proceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES); Vol. 2015-June). Association for Computing Machinery. https://doi.org/10.1145/2670529.2754967