{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:29Z","timestamp":1750220549995,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            The successful application of static program analysis strongly depends on flow facts of a program such as loop bounds, control-flow constraints, and operating modes. This problem heavily affects the design of real-time systems, since static program analyses are a prerequisite to determine the timing behavior of a program. For example, this becomes obvious in worst-case execution time (WCET) analysis, which is often infeasible without user-annotated flow facts. Moreover, many timing simulation approaches use statically derived timings of partial program paths to reduce simulation overhead. Annotating flow facts on binary or source level is either error-prone and tedious, or requires specialized compilers that can transform source-level annotations along with the program during optimization. To overcome these obstacles, so-called\n            <jats:italic>scenarios<\/jats:italic>\n            can be used. Scenarios are a design-time methodology that describe a set of possible system parameters, such as image resolutions, operating modes, or application-dependent flow facts. The information described by a scenario is unknown in general but known and constant for a specific system. In this article,\n            <jats:sup>1<\/jats:sup>\n            we present a methodology for scenario-aware program specialization to improve timing predictability. Moreover, we provide an implementation of this methodology for embedded software written in C\/C++. We show the effectiveness of our approach by evaluating its impact on WCET analysis using almost all of TACLeBench\u2013achieving an average reduction of WCET of 31%. In addition, we provide a thorough qualitative and evaluation-based comparison to closely related work, as well as two case studies.\n          <\/jats:p>","DOI":"10.1145\/3473333","type":"journal-article","created":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T16:12:01Z","timestamp":1630685521000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Scenario-Aware Program Specialization for Timing Predictability"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6522-6006","authenticated-orcid":false,"given":"Joscha","family":"Benz","sequence":"first","affiliation":[{"name":"University of T\u00fcbingen, Tbingen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-507X","authenticated-orcid":false,"given":"Oliver","family":"Bringmann","sequence":"additional","affiliation":[{"name":"University of T\u00fcbingen, Tbingen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Software ARM","year":"2019","unstructured":"ARM Software . 2019 . CMSIS-NN CIFAR10 Example . Retrieved November 10, 2019 from {https:\/\/github.com\/ARM-software\/ML-examples\/tree\/master\/cmsisnn-cifar10}. ARM Software. 2019. CMSIS-NN CIFAR10 Example. Retrieved November 10, 2019 from {https:\/\/github.com\/ARM-software\/ML-examples\/tree\/master\/cmsisnn-cifar10}."},{"doi-asserted-by":"crossref","unstructured":"G. Barany and A. Prantl. 2010. Source-level support for timing analysis. In Leveraging Applications of Formal Methods Verification and Validation. T. Margaria and B. Steffen (Eds.) Lecture Notes in Computer Science Vol. 6416 Springer Berlin 434\u2013448.  G. Barany and A. Prantl. 2010. Source-level support for timing analysis. In Leveraging Applications of Formal Methods Verification and Validation. T. Margaria and B. Steffen (Eds.) Lecture Notes in Computer Science Vol. 6416 Springer Berlin 434\u2013448.","key":"e_1_2_1_2_1","DOI":"10.1007\/978-3-642-16561-0_40"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 21st International Workshop on Software and Compilers for Embedded Systems.ACM","author":"Becker M.","year":"2077","unstructured":"M. Becker and S. Chakraborty . 2018. Optimizing worst-case execution times using mainstream compilers . In Proceedings of the 21st International Workshop on Software and Compilers for Embedded Systems.ACM , New York, NY. 10\u201313. DOI:https:\/\/doi.org\/10.1145\/3 2077 19.3207739 M. Becker and S. Chakraborty. 2018. Optimizing worst-case execution times using mainstream compilers. In Proceedings of the 21st International Workshop on Software and Compilers for Embedded Systems.ACM, New York, NY. 10\u201313. DOI:https:\/\/doi.org\/10.1145\/3207719.3207739"},{"volume-title":"Proceedings of the 22nd International Workshop on Software and Compilers for Embedded Systems. ACM","author":"Becker M.","unstructured":"M. Becker , M. Pazaj , and S. Chakraborty . 2019. WCET analysis meets virtual prototyping: Improving source-level timing annotations . In Proceedings of the 22nd International Workshop on Software and Compilers for Embedded Systems. ACM , New York, NY. 13\u201322. DOI:https:\/\/doi.org\/10.1145\/3323439.3323978 M. Becker, M. Pazaj, and S. Chakraborty. 2019. WCET analysis meets virtual prototyping: Improving source-level timing annotations. In Proceedings of the 22nd International Workshop on Software and Compilers for Embedded Systems. ACM, New York, NY. 13\u201322. DOI:https:\/\/doi.org\/10.1145\/3323439.3323978","key":"e_1_2_1_4_1"},{"volume-title":"Static WCET Analysis Based onAbstract Interpretation and Counting of Elements. Licentiate Theses No. 115","author":"Bygde S.","unstructured":"S. Bygde . 2010. Static WCET Analysis Based onAbstract Interpretation and Counting of Elements. Licentiate Theses No. 115 . Mrdalen University Press , Ver Sweden . S. Bygde. 2010. Static WCET Analysis Based onAbstract Interpretation and Counting of Elements. Licentiate Theses No. 115. Mrdalen University Press, Ver Sweden.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 1992 International Conference on Computer Languages.","author":"Hall K. D.","unstructured":"Cooper, K. D. , Hall , M. W. , and Kennedy , K . 1992. Procedure cloning . In Proceedings of the 1992 International Conference on Computer Languages. Cooper, K. D., Hall, M. W., and Kennedy, K.1992. Procedure cloning. In Proceedings of the 1992 International Conference on Computer Languages.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 16th International Workshop on Worst-Case Execution Time Analysis.","author":"Falk H.","unstructured":"H. Falk , S. Altmeyer , P. Hellinckx , B. Lisper , W. Puffitsch , C. Rochange , M. Schoeberl , R. B. Srensen , P. Wmann , and S. 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. H. Falk, S. Altmeyer, P. Hellinckx, B. Lisper, W. Puffitsch, C. Rochange, M. Schoeberl, R. B. Srensen, P. Wmann, and S. 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_2_1_7_1"},{"volume-title":"Proceedings of the 6th InternationalWorkshop on Worst-Case Execution Time Analysis. 121\u2013126","author":"Falk H.","unstructured":"H. Falk , P. Lokuciejewski , and H. Theiling . 2006. Design of a WCET-aware c compiler . In Proceedings of the 6th InternationalWorkshop on Worst-Case Execution Time Analysis. 121\u2013126 . H. Falk, P. Lokuciejewski, and H. Theiling. 2006. Design of a WCET-aware c compiler. In Proceedings of the 6th InternationalWorkshop on Worst-Case Execution Time Analysis. 121\u2013126.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1455229.1455232"},{"volume-title":"Proceedings of the 42nd Annual Design Automation Conference.101\u2013104","author":"Gheorghita S. V.","unstructured":"S. V. Gheorghita , S. Stuijk , T. Basten , and H. Corp oraal . 2005. Automatic scenario detection for improved WCET estimation . In Proceedings of the 42nd Annual Design Automation Conference.101\u2013104 . DOI:https:\/\/doi.org\/10.1145\/1065579.1065610 S. V. Gheorghita, S. Stuijk, T. Basten, and H. Corporaal. 2005. Automatic scenario detection for improved WCET estimation. In Proceedings of the 42nd Annual Design Automation Conference.101\u2013104. DOI:https:\/\/doi.org\/10.1145\/1065579.1065610","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","volume-title":"Retrieved","author":"H.","year":"2020","unstructured":"AbsInt Angewandte Informatik Gmb H. 2020 . The Industry Standard for Static Timing Analysis . Retrieved July 02, 2020 from https:\/\/www.absint.com\/ait\/. AbsInt Angewandte Informatik GmbH. 2020. The Industry Standard for Static Timing Analysis. Retrieved July 02, 2020 from https:\/\/www.absint.com\/ait\/."},{"key":"e_1_2_1_12_1","volume-title":"Retrieved","author":"H.","year":"2021","unstructured":"AbsInt Angewandte Informatik Gmb H. 2021 . aiT Worst-Case Exeuction Time Analyters: Workflow . Retrieved January 05, 2021 from https:\/\/www.absint.com\/ait\/features.htm. AbsInt Angewandte Informatik GmbH. 2021. aiT Worst-Case Exeuction Time Analyters: Workflow. Retrieved January 05, 2021 from https:\/\/www.absint.com\/ait\/features.htm."},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Gustafsson J.","year":"2013","unstructured":"J. Gustafsson . 2013 . WCET Project \/ Benchmarks . Retrieved January 05, 2021 from http:\/\/www.mrtc.mdh.se\/projects\/wcet\/benchmarks.html. J. Gustafsson. 2013. WCET Project \/ Benchmarks. Retrieved January 05, 2021 from http:\/\/www.mrtc.mdh.se\/projects\/wcet\/benchmarks.html."},{"key":"e_1_2_1_14_1","first-page":"136","volume-title":"In10th International Workshop on Worst-Case Execution Time Analysis. B. Lisper (Ed.), OpenAccess Series in Informatics","volume":"15","author":"Gustafsson J.","year":"2010","unstructured":"J. Gustafsson , A. Betts , A. Ermedahl , and B. Lisper . 2010. The Mrdalen WCET benchmarks: Past, present and future . In10th International Workshop on Worst-Case Execution Time Analysis. B. Lisper (Ed.), OpenAccess Series in Informatics , Vol. 15 , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , pp. 136 - 146 . DOI:https:\/\/doi.org\/10.4230\/OASICS.WCET. 2010 .136 J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper. 2010. The Mrdalen WCET benchmarks: Past, present and future. In10th International Workshop on Worst-Case Execution Time Analysis. B. Lisper (Ed.), OpenAccess Series in Informatics, Vol. 15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 136-146. DOI:https:\/\/doi.org\/10.4230\/OASICS.WCET.2010.136"},{"key":"e_1_2_1_15_1","volume-title":"Retrieved","author":"Guthaus M. R.","year":"2021","unstructured":"M. R. Guthaus , J. S. Ringenberg , T. M. Austin , T. Mudge , and R. B. Brown . 2002. MiBench Version 1 . Retrieved January 07, 2021 from http:\/\/vhosts.eecs.umich.edu\/mibench\/\/index.html. M. R. Guthaus, J. S. Ringenberg, T. M. Austin, T. Mudge, and R. B. Brown. 2002. MiBench Version 1. Retrieved January 07, 2021 from http:\/\/vhosts.eecs.umich.edu\/mibench\/\/index.html."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 4th Annual IEEE International Workshop on Workload Characterization. IEEE, 3\u201314","author":"Guthaus M. R.","year":"2001","unstructured":"M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , and R. B. Brown . 2001. MiBench: A free, commercially representative embedded benchmark suite . In Proceedings of the 4th Annual IEEE International Workshop on Workload Characterization. IEEE, 3\u201314 . DOI:https:\/\/doi.org\/10.1109\/WWC. 2001 .990739 M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. 2001. MiBench: A free, commercially representative embedded benchmark suite. In Proceedings of the 4th Annual IEEE International Workshop on Workload Characterization. IEEE, 3\u201314. DOI:https:\/\/doi.org\/10.1109\/WWC.2001.990739"},{"key":"e_1_2_1_17_1","volume-title":"Retrieved","author":"RWTH","year":"1996","unstructured":"RWTH Aachen ICE. 1996 . Institute for Communication Technologies and Embedded Systems: DSPStone . Retrieved January 07, 2021 from https:\/\/www.ice.rwth-aachen.de\/research\/tools-projects\/closed-projects\/dspstone\/. RWTH Aachen ICE. 1996. Institute for Communication Technologies and Embedded Systems: DSPStone. Retrieved January 07, 2021 from https:\/\/www.ice.rwth-aachen.de\/research\/tools-projects\/closed-projects\/dspstone\/."},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/2845083"},{"unstructured":"L. Lai N. Suda and V. Chandra. 2018. CMSIS-NN: Efficient neural network kernels for arm cortex-m CPUs. arXiv:1801.06601. Retrieved from https:\/\/arxiv.org\/abs\/1801.06601.  L. Lai N. Suda and V. Chandra. 2018. CMSIS-NN: Efficient neural network kernels for arm cortex-m CPUs. arXiv:1801.06601. Retrieved from https:\/\/arxiv.org\/abs\/1801.06601.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the 11th International Workshop on Software & Compilers for Embedded Systems.","author":"Lokuciejewski P.","unstructured":"P. Lokuciejewski , H. Falk , P. Marwedel , and H. Theiling . 2008. WCET-driven, code-size critical procedure cloning . In Proceedings of the 11th International Workshop on Software & Compilers for Embedded Systems. P. Lokuciejewski, H. Falk, P. Marwedel, and H. Theiling. 2008. WCET-driven, code-size critical procedure cloning. In Proceedings of the 11th International Workshop on Software & Compilers for Embedded Systems.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 3rd Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation.","author":"Lokuciejewski P.","unstructured":"P. Lokuciejewski , F. Gedikli , P. Marwedel , and K. Morik . 2009. Automatic WCET reduction by machine learning based heuristics for function inlining . In Proceedings of the 3rd Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation. P. Lokuciejewski, F. Gedikli, P. Marwedel, and K. Morik. 2009. Automatic WCET reduction by machine learning based heuristics for function inlining. In Proceedings of the 3rd Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/LRA.2018.2795643"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1007\/BF01088695"},{"unstructured":"D. Palossi A. Loquercio F. Conti E. Flamand D. Scaramuzza and L. Benini. 2019. A 64mW DNN-based Visual Navigation Enginde for Autonomous Nano-Drones. arXiv:1805.01831v1. Retrieved from https:\/\/arxiv.org\/abs\/1805.01831v1.  D. Palossi A. Loquercio F. Conti E. Flamand D. Scaramuzza and L. Benini. 2019. A 64mW DNN-based Visual Navigation Enginde for Autonomous Nano-Drones. arXiv:1805.01831v1. Retrieved from https:\/\/arxiv.org\/abs\/1805.01831v1.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/BF01088696"},{"doi-asserted-by":"crossref","unstructured":"P.\n      Puschner R.\n      Kirner B.\n      Huber and \n      D.\n      Prokesch\n  . \n  2012\n  . Compiling for time predictability. In Computer Safety Reliability and Security. F. Ortmeier and P. Daniel (Eds.) Lecture Notes in Computer Science Vol. \n  7613 Springer Berlin.  P. Puschner R. Kirner B. Huber and D. Prokesch. 2012. Compiling for time predictability. In Computer Safety Reliability and Security. F. Ortmeier and P. Daniel (Eds.) Lecture Notes in Computer Science Vol. 7613 Springer Berlin.","key":"e_1_2_1_27_1","DOI":"10.1007\/978-3-642-33675-1_35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/ACCESS.2020.2981411"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 7th IEEE\/ACM\/IFIP International Conference on Hardware\/Software Codesign and System Synthesis. 305","author":"Stattelmann S.","year":"2039","unstructured":"S. Stattelmann , O. Bringmann , and W. Rosenstiel . 2011. Dominator homomorphism based code matching for source-level simulation of embedded software . In Proceedings of the 7th IEEE\/ACM\/IFIP International Conference on Hardware\/Software Codesign and System Synthesis. 305 . DOI:https:\/\/doi.org\/10.1145\/ 2039 370.2039417 S. Stattelmann, O. Bringmann, and W. Rosenstiel. 2011. Dominator homomorphism based code matching for source-level simulation of embedded software. In Proceedings of the 7th IEEE\/ACM\/IFIP International Conference on Hardware\/Software Codesign and System Synthesis. 305. DOI:https:\/\/doi.org\/10.1145\/2039370.2039417"},{"volume-title":"Retrieved","year":"2020","unstructured":"The Clang Team. 2020 . LibTooling . Retrieved July 02, 2020 from https:\/\/clang.llvm.org\/docs\/LibTooling.html. The Clang Team. 2020. LibTooling. Retrieved July 02, 2020 from https:\/\/clang.llvm.org\/docs\/LibTooling.html.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the 4th ACM\/IEEE International Conference on Formal Methods and Models for Co-Design.","author":"Theelen B. D.","unstructured":"B. D. Theelen , M. C. W. Geilen , T. Basten , J. P. M. Voeten , S. V. Gheorghita , and S. Stuijk . 2006. A scenario-aware data flow model for combined long-run average and worst-case performance analysis . In Proceedings of the 4th ACM\/IEEE International Conference on Formal Methods and Models for Co-Design. B. D. Theelen, M. C. W. Geilen, T. Basten, J. P. M. Voeten, S. V. Gheorghita, and S. Stuijk. 2006. A scenario-aware data flow model for combined long-run average and worst-case performance analysis. In Proceedings of the 4th ACM\/IEEE International Conference on Formal Methods and Models for Co-Design.","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1109\/IPDPS.2007.370637"},{"volume-title":"Proceedings of the International Conference on Signal Processing Applications & Technology.","author":"Zivojnovic V.","unstructured":"V. Zivojnovic , J. Martinez , C. Schlr , and H. Meyr . 1994. DSPstone: A DSP-oriented benchmarking methodology . In Proceedings of the International Conference on Signal Processing Applications & Technology. V. Zivojnovic, J. Martinez, C. Schlr, and H. Meyr. 1994. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing Applications & Technology.","key":"e_1_2_1_33_1"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:15Z","timestamp":1750195695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3473333"],"URL":"https:\/\/doi.org\/10.1145\/3473333","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2021,9,3]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}