{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:58Z","timestamp":1750308418192,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T00:00:00Z","timestamp":1653696000000},"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":[[2022,5,31]]},"abstract":"<jats:p>\n            Due to the dynamic behaviour of acceleration mechanisms such as caches and branch predictors, static Worst-case Execution Time (WCET) analysis methods tend to scale poorly to modern hardware architectures. As a result, a trade-off must be found between the duration and the precision of the analysis, leading to an overestimation of the WCET bounds. In turn, this reduces the schedulability and resource usage of the system. In this article, we present a new data structure to speed up the analysis: the\n            <jats:italic>eXecution Decision Diagram<\/jats:italic>\n            (XDD), which is an ad hoc extension of\n            <jats:italic>Binary Decision Diagrams<\/jats:italic>\n            tailored for WCET analysis problems. We show how XDDs can be used to represent efficiently execution states in a modern hardware platform. Moreover, we propose a new process to build the\n            <jats:italic>Integer Linear Programming<\/jats:italic>\n            system of the\n            <jats:italic>Implicit Path Enumeration Technique<\/jats:italic>\n            using XDD. We use benchmark applications to demonstrate how the use of an XDD substantially increases the scalability of WCET analysis and the precision of the obtained WCET.\n          <\/jats:p>","DOI":"10.1145\/3476879","type":"journal-article","created":{"date-parts":[[2022,1,26]],"date-time":"2022-01-26T18:20:38Z","timestamp":1643221238000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Framework for Calculating WCET Based on Execution Decision Diagrams"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1143-0762","authenticated-orcid":false,"given":"Zhenyu","family":"Bai","sequence":"first","affiliation":[{"name":"CNRS-IRIT-University of Toulouse, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9298-5235","authenticated-orcid":false,"given":"Hugues","family":"Cass\u00e9","sequence":"additional","affiliation":[{"name":"CNRS-IRIT-University of Toulouse, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3318-948X","authenticated-orcid":false,"given":"Marianne","family":"De Michiel","sequence":"additional","affiliation":[{"name":"CNRS-IRIT-University of Toulouse, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1411-1030","authenticated-orcid":false,"given":"Thomas","family":"Carle","sequence":"additional","affiliation":[{"name":"CNRS-IRIT-University of Toulouse, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7257-7114","authenticated-orcid":false,"given":"Christine","family":"Rochange","sequence":"additional","affiliation":[{"name":"CNRS-IRIT-University of Toulouse, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,5,28]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Henrik Reif Andersen. 1997. An introduction to binary decision diagrams. Lecture Notes IT University of Copenhagen. Retrieved from https:\/\/www.cmi.ac.in\/madhavan\/courses\/verification-2011\/andersen-bdd.pdf."},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Zhenyu Bai Hugues Cass\u00e9 Marianne De Michiel Thomas Carle and Chistine Rochange. 2020. Improving the performance of WCET analysis in the presence of variable latencies. InProceedings of the 21st ACM SIGPLAN\/SIGBED Conference on Languages Compilers and Tools for Embedded Systems (LCTES\u201920). 119\u2013130.","DOI":"10.1145\/3372799.3394371"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16256-5_6"},{"key":"e_1_3_2_5_2","unstructured":"Jean-Luc B\u00e9chennec and Franck Cassez. 2011. Computation of WCET using program slicing and real-time model-checking. Retrieved from https:\/\/arXiv:1105.1633."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90017-A"},{"key":"e_1_3_2_7_2","first-page":"37","article-title":"Timed automata for modelling caches and pipelines","author":"Cassez Franck","year":"2015","unstructured":"Franck Cassez and Pablo Gonz\u00e1lez de Aledo Marug\u00e1n. 2015. Timed automata for modelling caches and pipelines. In Proceedings of the Workshop on Models for Formal Analysis of Real Systems (MARS\u201915). 37\u201345.","journal-title":"Proceedings of the Workshop on Models for Formal Analysis of Real Systems (MARS\u201915)"},{"key":"e_1_3_2_8_2","volume-title":"Processor Pipelines and and Static Worst-Case Execution Time Analysis","author":"Engblom Jakob","year":"2002","unstructured":"Jakob Engblom. 2002. Processor Pipelines and and Static Worst-Case Execution Time Analysis. Ph.D. Dissertation. University of Uppsala."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.1999.811197"},{"key":"e_1_3_2_10_2","volume-title":"Proceedings of the 16th International Workshop on Worst-case Execution Time Analysis","author":"Falk Heiko","year":"2016","unstructured":"Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Bj\u00f6rn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sorensen, Peter W\u00e4gemann, and Simon Wegener. 2016. TACLeBench: A benchmark collection to support worst-case execution time research. In Proceedings of the 16th International Workshop on Worst-case Execution Time Analysis."},{"key":"e_1_3_2_11_2","volume-title":"A Fast and Efficient Cache Persistence Analysis","author":"Ferdinand Christian","year":"2005","unstructured":"Christian Ferdinand. 2005. A Fast and Efficient Cache Persistence Analysis. Technical Report. Saarl\u00e4ndische Universit\u00ebts-und Landesbibliothek\/Naturwissenschaftlich-Technische Fakult\u00ebt I."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.743411"},{"key":"e_1_3_2_13_2","first-page":"1","volume-title":"Proceedings of the 10th European Signal Processing Conference","author":"Holsti Niklas","year":"2000","unstructured":"Niklas Holsti, Thomas L\u00e5ngbacka, and Sami Saarinen. 2000. Worst-case execution time analysis for digital signal processors. In Proceedings of the 10th European Signal Processing Conference. 1\u20134."},{"key":"e_1_3_2_14_2","article-title":"Status of the Bound-T WCET tool","author":"Holsti Niklas","year":"2002","unstructured":"Niklas Holsti and Sami Saarinen. 2002. Status of the Bound-T WCET tool. Space Systems Finland Ltd.","journal-title":"Space Systems Finland Ltd"},{"key":"e_1_3_2_15_2","first-page":"657","volume-title":"Proceedings of the International Multiconference on Computer Science and Information Technology","author":"Kassem Rola","year":"2008","unstructured":"Rola Kassem, Mika\u00ebl Briday, Jean-Luc B\u00e9chennec, Yvon Trinquet, and Guillaume Savaton. 2008. Simulator generation using an automaton-based pipeline model for timing analysis. In Proceedings of the International Multiconference on Computer Science and Information Technology. IEEE, 657\u2013664."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34032-1_17"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45789-5_22"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-006-9205-5"},{"key":"e_1_3_2_19_2","first-page":"88","volume-title":"ACM SIGPLAN Notices","author":"Li Yau-Tsun Steven","year":"1995","unstructured":"Yau-Tsun Steven Li and Sharad Malik. 1995. Performance analysis of embedded software using implicit path enumeration. In ACM SIGPLAN Notices, Vol. 30.11. 88\u201398."},{"key":"e_1_3_2_20_2","first-page":"88","volume-title":"Proceedings of the Workshop on Languages, Compilers, and Tools for Real-Time Systems","author":"Li Yau.-Tsun S.","year":"1995","unstructured":"Yau.-Tsun S. Li and Sharad Malik. 1995. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the Workshop on Languages, Compilers, and Tools for Real-Time Systems. 88\u201398."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1999.818824"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123225"},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the 6th International Workshop on Worst-case Execution Time Analysis (WCET\u201906)","author":"Reineke Jan","year":"2006","unstructured":"Jan Reineke, Bj\u00f6rn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. 2006. A definition and classification of timing anomalies. In Proceedings of the 6th International Workshop on Worst-case Execution Time Analysis (WCET\u201906)."},{"key":"e_1_3_2_24_2","first-page":"222","article-title":"A context-parameterized model for static analysis of execution times","author":"Rochange Christine","year":"2009","unstructured":"Christine Rochange and Pascal Sainrat. 2009. A context-parameterized model for static analysis of execution times. Trans. High-Perform. Embed. Architect. Compil. II (2009), 222\u2013241.","journal-title":"Trans. High-Perform. Embed. Architect. Compil. II"},{"key":"e_1_3_2_25_2","volume-title":"ILP-based path analysis on abstract pipeline state graphs","author":"Stein Ingmar Jendrik","year":"2010","unstructured":"Ingmar Jendrik Stein. 2010. ILP-based path analysis on abstract pipeline state graphs. Ph.D. Dissertation. Saarland University."},{"key":"e_1_3_2_26_2","volume-title":"Safe and precise WCET determination by abstract interpretation of pipeline models","author":"Thesing Stephan","year":"2004","unstructured":"Stephan Thesing. 2004. Safe and precise WCET determination by abstract interpretation of pipeline models. Ph.D. Dissertation. Saarland University."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the Workshop on Worst-case Execution Time (WCET\u201907)","author":"Wilhelm Stephan","year":"2007","unstructured":"Stephan Wilhelm. 2007. Efficient analysis of pipeline models for WCET computation. In Proceedings of the Workshop on Worst-case Execution Time (WCET\u201907)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476879","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:20Z","timestamp":1750268960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,28]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,5,31]]}},"alternative-id":["10.1145\/3476879"],"URL":"https:\/\/doi.org\/10.1145\/3476879","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2022,5,28]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}