Improving the precision of abstract interpretation based cache persistence analysis

Zhenkai Zhang, Xenofon Koutsoukos

Research output: Contribution to journalArticle

2 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. Ex- isting 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 pes- simism. 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
Article numbera10
Pages (from-to)93-102
Number of pages10
JournalACM SIGPLAN Notices
Volume50
Issue number5
DOIs
StatePublished - May 2015

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