{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:23:13Z","timestamp":1759990993334,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1s","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>To compute a worst-case execution time (WCET) estimate for a program, the architectural effects of the underlying hardware must be modeled. For modern processors this results in the need for a cache and pipeline analysis.<\/jats:p>\n          <jats:p>The timing-relevant result of the cache analysis is the categorization of the accesses to cached memory. Categorizations that are obtainable by the well-known must and may cache analysis [Ferdinand 1997] are always-hit, always-miss and not-classified. The cache persistence analysis tries to provide additional information for the not-classified case to limit the number of misses.<\/jats:p>\n          <jats:p>There exists a cache persistence analysis by Ferdinand and Wilhelm based on abstract interpretation computing these classifications. In this article, we present a correctness issue with this analysis. To fix this issue, we propose two new abstract interpretation based persistence analyses and show their safety. One is based on the known may analysis and a second one on the concept of conflict counting.<\/jats:p>\n          <jats:p>\n            For\n            <jats:italic>fully timing compositional architectures<\/jats:italic>\n            [Wilhelm et al. 2009] the persistence information is straightforward to use. We will apply the concepts of persistence analysis for the first time to state-of-the-art architectures that exhibit both timing anomalies and domino effects. Such architectures do not allow the analyzer to quantify the costs of a single cache hit or miss in isolation. To make the usage of the persistence information feasible, we integrate the presented novel persistence analyses together with a novel path analysis approach into the industrially used WCET analyzer aiT.\n          <\/jats:p>","DOI":"10.1145\/2435227.2435236","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Cache persistence analysis"],"prefix":"10.1145","volume":"12","author":[{"given":"Christoph","family":"Cullmann","sequence":"first","affiliation":[{"name":"AbsInt Angewandte Informatik GmbH, Saarbr\u00fccken, Germany"}]}],"member":"320","published-online":{"date-parts":[[2013,3,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.34"},{"volume-title":"Proceedings of the 3rd European Congress on Embedded Real-Time Software. 25--27","author":"Cass\u00e9 H.","key":"e_1_2_1_2_1","unstructured":"Cass\u00e9 , H. and Sainrat , P . 2005. OTAWA, a framework for experimenting WCET computations . In Proceedings of the 3rd European Congress on Embedded Real-Time Software. 25--27 . Cass\u00e9, H. and Sainrat, P. 2005. OTAWA, a framework for experimenting WCET computations. In Proceedings of the 3rd European Congress on Embedded Real-Time Software. 25--27."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967677.1967695"},{"volume-title":"Proceedings of Embedded Real Time Software and Systems.","author":"Cullmann C.","key":"e_1_2_1_5_1","unstructured":"Cullmann , C. , Ferdinand , C. , Gebhard , G. , Grund , D. , Maiza , C. , Reineke , J. , Triquet , B. , and Wilhelm , R . 2010. Predictability considerations in the design of multi-core embedded systems . In Proceedings of Embedded Real Time Software and Systems. Cullmann, C., Ferdinand, C., Gebhard, G., Grund, D., Maiza, C., Reineke, J., Triquet, B., and Wilhelm, R. 2010. Predictability considerations in the design of multi-core embedded systems. In Proceedings of Embedded Real Time Software and Systems."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45449-7_32"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1805793.1805797"},{"key":"e_1_2_1_10_1","first-page":"52","article-title":"Cache behavior prediction by abstract interpretation","volume":"1145","author":"Ferdinand C.","year":"1996","unstructured":"Ferdinand , C. , Martin , F. , Wilhelm , R. , and Alt , M. 1996 . Cache behavior prediction by abstract interpretation . In Science of Computer Programming , vol. 1145 , Spring er, 52 -- 66 . Ferdinand, C., Martin, F., Wilhelm, R., and Alt, M. 1996. Cache behavior prediction by abstract interpretation. In Science of Computer Programming, vol. 1145, Springer, 52--66.","journal-title":"Science of Computer Programming"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008186323068"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., Austrian Computer Society, 5--15","author":"Gebhard G.","year":"2010","unstructured":"Gebhard , G. 2010 . Timing anomalies reloaded . In Proceedings of the 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., Austrian Computer Society, 5--15 . Gebhard, G. 2010. Timing anomalies reloaded. In Proceedings of the 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., Austrian Computer Society, 5--15."},{"key":"e_1_2_1_13_1","volume-title":"Practice: Predictability and Performance in Embedded Systems","author":"Gebhard G.","year":"2011","unstructured":"Gebhard , G. , Cullmann , C. , and Heckmann , R . 2011 . Software structure and WCET predictability. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems , P. Lucas, L. Thiele, B. Triquet, T. Ungerer, and R. Wilhelm, Eds., OpenAccess Series in Informatics (OASIcs) Series, vol. 18 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 1--10. Gebhard, G., Cullmann, C., and Heckmann, R. 2011. Software structure and WCET predictability. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems, P. Lucas, L. Thiele, B. Triquet, T. Ungerer, and R. Wilhelm, Eds., OpenAccess Series in Informatics (OASIcs) Series, vol. 18. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 1--10."},{"key":"e_1_2_1_14_1","unstructured":"Gustafsson J. Betts A. Ermedahl A. and Lisper B. 2010. The M\u00e4lardalen WCET Benchmarks -- Past Present and Future. B. Lisper Ed. OCG Brussels Belgium 137--147.  Gustafsson J. Betts A. Ermedahl A. and Lisper B. 2010. The M\u00e4lardalen WCET Benchmarks -- Past Present and Future. B. Lisper Ed. OCG Brussels Belgium 137--147."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.743411"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/827267.828941"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.814618"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.27"},{"volume-title":"Proceedings of the 9th International Workshop on Worst-Case Execution Time (WCET) Analysis. N. Holsti, Ed., Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","author":"Lesage B.","key":"e_1_2_1_19_1","unstructured":"Lesage , B. , Hardy , D. , and Puaut , I . 2009. WCET analysis of multi-level set-associative data caches . In Proceedings of the 9th International Workshop on Worst-Case Execution Time (WCET) Analysis. N. Holsti, Ed., Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , Germany, Dagstuhl, Germany. Lesage, B., Hardy, D., and Puaut, I. 2009. WCET analysis of multi-level set-associative data caches. In Proceedings of the 9th International Workshop on Worst-Case Execution Time (WCET) Analysis. N. Holsti, Ed., Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/827271.829103"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.30"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647474.727592"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008145215849"},{"volume-title":"Proceedings of the ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems.","author":"Mueller F.","key":"e_1_2_1_26_1","unstructured":"Mueller , F. , Whalley , D. B. , and Harmon , M . 1994. Predicting instruction cache behavior . In Proceedings of the ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems. Mueller, F., Whalley, D. B., and Harmon, M. 1994. Predicting instruction cache behavior. In Proceedings of the ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9032-3"},{"volume-title":"Proceedings of the Workshop on Worst-Case Execution-Time Analysis (WCET).","author":"Reineke J.","key":"e_1_2_1_29_1","unstructured":"Reineke , J. , Wachter , B. , Thesing , S. , Wilhelm , R. , Polian , I. , Eisinger , J. , and Becker , B . 2006. A definition and classification of timing anomalies . In Proceedings of the Workshop on Worst-Case Execution-Time Analysis (WCET). Reineke, J., Wachter, B., Thesing, S., Wilhelm, R., Polian, I., Eisinger, J., and Becker, B. 2006. A definition and classification of timing anomalies. In Proceedings of the Workshop on Worst-Case Execution-Time Analysis (WCET)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/356887.356892"},{"volume-title":"Proceedings of the 5th International Workshop on Worst-Case Execution Time (WCET) Analysis. 21--24","author":"Souyris J.","key":"e_1_2_1_31_1","unstructured":"Souyris , J. , Le Pavec , E. , Himbert , G. , J\u00e9gu , V. , Borios , G. , and Heckmann , R . 2005. Computing the worst case execution time of an avionics program by abstract interpretation . In Proceedings of the 5th International Workshop on Worst-Case Execution Time (WCET) Analysis. 21--24 . Souyris, J., Le Pavec, E., Himbert, G., J\u00e9gu, V., Borios, G., and Heckmann, R. 2005. Computing the worst case execution time of an avionics program by abstract interpretation. In Proceedings of the 5th International Workshop on Worst-Case Execution Time (WCET) Analysis. 21--24."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008141130870"},{"volume-title":"Proceedings of the Dependable Systems and Networks (DSN).","author":"Thesing S.","key":"e_1_2_1_35_1","unstructured":"Thesing , S. , Souyris , J. , Heckmann , R. , Randimbivololona , F. , Langenbach , M. , Wilhelm , R. , and Ferdinand , C . 2003. An abstract-interpretation-based timing validation of hard real-time avionics software systems . In Proceedings of the Dependable Systems and Networks (DSN). Thesing, S., Souyris, J., Heckmann, R., Randimbivololona, F., Langenbach, M., Wilhelm, R., and Ferdinand, C. 2003. An abstract-interpretation-based timing validation of hard real-time avionics software systems. In Proceedings of the Dependable Systems and Networks (DSN)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013287"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Wilhelm R. Lucas P. Parshin O. Tan L. and \n      Wachter B\n  . \n  2010\n  . Improving the precision of WCET analysis by input constraints and model-derived flow constraints. In Advances in Real-Time Systems S. Chakraborty and J. Ebersp\u00e4cher Eds. Lecture Notes in Computer Science Springer-Verlag\n  .  Wilhelm R. Lucas P. Parshin O. Tan L. and Wachter B. 2010. Improving the precision of WCET analysis by input constraints and model-derived flow constraints. In Advances in Real-Time Systems S. Chakraborty and J. Ebersp\u00e4cher Eds. Lecture Notes in Computer Science Springer-Verlag.","DOI":"10.1007\/978-3-642-24349-3_6"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435227.2435236","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2435227.2435236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:40Z","timestamp":1750235740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435227.2435236"}},"subtitle":["Theory and practice"],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":30,"journal-issue":{"issue":"1s","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2435227.2435236"],"URL":"https:\/\/doi.org\/10.1145\/2435227.2435236","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}