{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:15:29Z","timestamp":1773407729176,"version":"3.50.1"},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Syst Model"],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1007\/s10270-010-0161-0","type":"journal-article","created":{"date-parts":[[2010,4,8]],"date-time":"2010-04-08T02:21:55Z","timestamp":1270693315000},"page":"411-437","source":"Crossref","is-referenced-by-count":12,"title":["Beyond loop bounds: comparing annotation languages for worst-case execution time analysis"],"prefix":"10.1007","volume":"10","author":[{"given":"Raimund","family":"Kirner","sequence":"first","affiliation":[]},{"given":"Jens","family":"Knoop","sequence":"additional","affiliation":[]},{"given":"Adrian","family":"Prantl","sequence":"additional","affiliation":[]},{"given":"Markus","family":"Schordan","sequence":"additional","affiliation":[]},{"given":"Albrecht","family":"Kadlec","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,9]]},"reference":[{"key":"161_CR1","unstructured":"AbsInt. aiT. Web page. http:\/\/www.absint.com\/aiT . Accessed online in February (2010)"},{"key":"161_CR2","volume-title":"Compilers, Principles, Techniques, and Tools","author":"A.V. Aho","year":"2007","unstructured":"Aho A.V., Lam M.S., Sethi R., Ullman J.D.: Compilers, Principles, Techniques, and Tools. Addison-Wesley, New York (2007) ISBN 0-321-48681-1"},{"key":"161_CR3","unstructured":"Ballabriga, C., Cass\u00e9, H., Nemer, F., Rochange, C., Sainrat, P.: OTAWA. Online Program Documentation. University of Toulouse, France. http:\/\/www.otawa.fr\/ (2008)"},{"key":"161_CR4","doi-asserted-by":"crossref","unstructured":"Bernat, G., Colin, A., Petters, S.M.: WCET analysis of probabilistic hard real-time systems. In: Proceedings of the 23rd Real-Time Systems Symposium, December, pp. 279\u2013288, Austin, TX, USA (2002)","DOI":"10.1109\/REAL.2002.1181582"},{"issue":"6","key":"161_CR5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/267896.267921","volume":"22","author":"R. Bod\u00edk","year":"1997","unstructured":"Bod\u00edk R., Gupta R., Soffa M.L.: Refining data flow information using infeasible paths. SIGSOFT Softw. Eng. Notes 22(6), 361\u2013377 (1997)","journal-title":"SIGSOFT Softw. Eng. Notes"},{"issue":"3","key":"161_CR6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0096-0551(94)90004-3","volume":"20","author":"J. Blieberger","year":"1994","unstructured":"Blieberger J.: Discrete loops and worst case performance. Comp. Lang. 20(3), 193\u2013212 (1994)","journal-title":"Comp. Lang."},{"key":"161_CR7","doi-asserted-by":"crossref","unstructured":"Chapman, R., Burns, A., Wellings, A.: Integrated program proof and worst-case timing analysis of SPARK Ada. In: Proceedings of the ACM Workshop on Language, Compiler and Tool Support for Real-time Systems, pp. K1\u2013K11, June (1994)","DOI":"10.1145\/192867.192873"},{"issue":"2","key":"161_CR8","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF00365316","volume":"11","author":"R. Chapman","year":"1996","unstructured":"Chapman R., Burns A., Wellings A.: Combining static worst-case timing analysis and program proof. Real-Time Syst. 11(2), 145\u2013171 (1996)","journal-title":"Real-Time Syst."},{"key":"161_CR9","unstructured":"Chen, M.: A Timing Analysis Language\u2014(TAL). Department of Computer Science, University of Texas, Austin, TX, USA (1987). Programmer\u2019s Manual"},{"key":"161_CR10","unstructured":"Colin, A., Puaut, I.: A modular and retargetable framework for tree-based WCET analysis. In: Proceedings of the 13th Euromicro Conference on Real-Time Systems, pp. 37\u201344, Delft, Netherland, June (2001). Technical University of Delft"},{"key":"161_CR11","unstructured":"Cass\u00e9, H., Sainrat, P.: OTAWA, a framework for experimenting WCET computations. In: European Congress on Embedded Real-Time Software (ERTS), Toulouse, 25\/01\/06-27\/01\/06, page (electronic medium), http:\/\/www.see.asso.fr , January, See p. 8 (2006)"},{"key":"161_CR12","unstructured":"Engblom, J., Ermedahl, A.: Modeling complex flows for worst-case execution time analysis. In: Proceedings of the 21st IEEE Real-Time Systems Symposium (RTSS), December, Orlando, FL, USA (2000)"},{"key":"161_CR13","unstructured":"Ermedahl, A., Engblom, J., Stappert, F.: A unified flow information language for WCET analysis. In: Proceedings of the 2nd International Workshop on Worst Case Execution Time Analysis. Technical University of Vienna, Austria, June (2002)"},{"issue":"9","key":"161_CR14","doi-asserted-by":"crossref","first-page":"1104","DOI":"10.1109\/TC.2005.139","volume":"54","author":"A. Ermedahl","year":"2005","unstructured":"Ermedahl A., Stappert F., Engblom J.: Clustered worst-case execution time calculation. IEEE Trans. Comp. 54(9), 1104\u20131122 (2005)","journal-title":"IEEE Trans. Comp."},{"key":"161_CR15","unstructured":"Ferdinand, C., Heckmann, R., Theiling, H.: Convenient user annotations for a WCET tool. In: Proceedings of the 3rd International Workshop on Worst-Case Execution Time Analysis, pp. 17\u201320, Porto, Portugal, July (2003)"},{"key":"161_CR16","doi-asserted-by":"crossref","unstructured":"Floyd, R.: Assigning meaning to programs. In: Proceedings of the AMS Symposia in Applied Mathematics, pp. 19\u201332 (1967)","DOI":"10.1090\/psapm\/019\/0235771"},{"key":"161_CR17","unstructured":"Gustafsson, J.: The WCET tool challenge 2006. In: Preliminary Proceedings of the 2nd Int. IEEE Symposium on Leveraging Applications of Formal Methods, Verification and Validation, pp. 248\u2013249, Paphos, Cyprus, November (2006)"},{"key":"161_CR18","doi-asserted-by":"crossref","unstructured":"Healy, C.A., Arnold, R.D., Mueller, F., Whalley, D., Harmon, M.G.: Bounding pipeline and instruction cache performance. IEEE Trans. Comp. 48(1) (1999)","DOI":"10.1109\/12.743411"},{"key":"161_CR19","volume-title":"Flow Analysis of Computer Programs","author":"M.S. Hecht","year":"1977","unstructured":"Hecht M.S.: Flow Analysis of Computer Programs. Elsevier, North-Holland (1977)"},{"key":"161_CR20","unstructured":"Heptane (Hades embedded processor timing analyzer). Tool web page: http:\/\/www.irisa.fr\/aces\/work\/heptane-demo\/heptane.html . Accessed online in February (2010)"},{"key":"161_CR21","unstructured":"Heckmann, R., Ferdinand, C.: Combining automatic analysis and user annotations for successful worst-case execution time prediction. In: Embedded World 2005 Conference, February, N\u00fcrnberg, Germany (2005)"},{"key":"161_CR22","unstructured":"Holsti, N., Gustafsson, J., Bernat, G., Ballabriga, C., Bonenfant, A., Bourgade, R., Cass\u00e9, H., Cordes, D., Kadlec, A., Kirner, R., Knoop, J., Lokuciejewski, P., Merriam, N., de Michiel, M., Prantl, A., Rieder, B., Rochange, C., Sainrat, P., Schordan, M.: WCET 2008\u2014Report from the Tool Challenge 2008. In: Proceedings of the 8th International Workshop on Worst-Case Execution Time Analysis, July, pp. 149\u2013171, Prague, Czech Republic (2008)"},{"key":"161_CR23","unstructured":"Harbour, M.G., Garcia, J.J.G., Gutierrez, J.C.P., Moyano, J.M.D.: MAST: Modeling and analysis suite for real time applications. In: Proceedings of the 13th Euromicro Conference on Real-Time Systems, pp. 125 \u2013134, Delft, The Netherlands. Euromicro (2001)"},{"key":"161_CR24","unstructured":"Holsti, N., L\u00e5ngbacka, T., Saarinen, S.: Worst-case execution time analysis for digital signal processors. In: European Signal Processing Conference 2000 (EUSIPCO 2000) (2000)"},{"key":"161_CR25","unstructured":"Holsti, N., L\u00e5ngbacka, T., Saarinen, S.: Bound-T timing analysis tool User Manual. Tidorum Ltd (2005)]"},{"issue":"10","key":"161_CR26","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1145\/363235.363259","volume":"12","author":"C.A.R. Hoare","year":"1969","unstructured":"Hoare C.A.R.: An axiomatic basis for computer programming. Communications of the ACM 12(10), 576\u2013580 (1969)","journal-title":"Communications of the ACM"},{"key":"161_CR27","unstructured":"Holsti N.: Bound-T assertion language: Planned extensions. Technical report. Tidorum Ltd, (2005)"},{"key":"161_CR28","unstructured":"IBM: IBM ILOG CPLEX\u2014High-performance mathematical programming engine. Web page. http:\/\/www.ibm.com\/software\/integration\/optimization\/cplex\/ . Accessed in Feb. (2010)"},{"key":"161_CR29","unstructured":"Kirner, R.: User\u2019s Manual\u2014WCET-Analysis Framework based on wcetC. Vienna University of Technology, July, Vienna, Austria, 0.0.3 edition, 2001. available at http:\/\/www.vmars.tuwien.ac.at\/~raimund\/calc_wcet\/"},{"key":"161_CR30","unstructured":"Kirner, R.: The programming language wcetC. Technical report, Technische Universit\u00e4t Wien, Institut f\u00fcr Technische Informatik, Treitlstr. 1-3\/182-1, 1040 Vienna, Austria (2002)"},{"key":"161_CR31","unstructured":"Kirner, R.: Compiler Support for Timing Analysis of Optimized Code: Precise Timing Analysis of Machine Code with Convenient Annotation of Source Code. VDM Verlag, Germany, July 2008. ISBN: 978-3-8364-6883-1"},{"key":"161_CR32","unstructured":"Kirner, R., Knoop, J., Prantl, A., Schordan, M., Wenzel, I.: WCET analysis: the annotation language challenge. In: Proceedings of the 7th International Workshop on Worst-Case Execution Time Analysis, pp. 83\u201399, Pisa, Italy, July (2007)"},{"key":"161_CR33","unstructured":"Kirner, R., Kadlec, A., Puschner, P., Prantl, A., Schordan, M., Knoop, J.: Towards a common WCET annotation language: essential ingredients. In: Proceedings of the 8th International Workshop on Worst-Case Execution Time Analysis, pp. 53\u201365, Prague, Czech Republic, July (2008)"},{"key":"161_CR34","doi-asserted-by":"crossref","unstructured":"Kirner, R., Kadlec, A., Puschner, P.: Precise worst-case execution time analysis for processors with timing anomalies. In: Proceedings of the 21st Euromicro Conference on Real-Time Systems, pp. 119\u2013128, Dublin, Ireland, July 2009. IEEE, New York","DOI":"10.1109\/ECRTS.2009.8"},{"key":"161_CR35","doi-asserted-by":"crossref","unstructured":"Kirner, R., Lang, R., Freiberger, G., Puschner, P.: Fully automatic worst-case execution time analysis for Matlab\/Simulink models. In: Proceedings of the 14th Euromicro Conference on Real-Time Systems, pp. 31\u201340, Vienna, Austria, June 2002. Vienna University of Technology. IEEE, New York","DOI":"10.1109\/EMRTS.2002.1019183"},{"key":"161_CR36","unstructured":"Kirner, R., Puschner, P.: Classification of code annotations and discussion of compiler-support for worst-case execution time analysis. In: Proceedings of the 5th International Workshop on Worst-Case Execution Time Analysis, Palma, Spain, July (2005)"},{"issue":"9","key":"161_CR37","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1109\/TSE.1986.6313049","volume":"12","author":"E. Klingerman","year":"1986","unstructured":"Klingerman E., Stoyenko Alexander D.: Real-time euclid: a language for reliable real-time systems. IEEE Trans. Softw. Eng. 12(9), 941\u2013989 (1986)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"161_CR38","doi-asserted-by":"crossref","unstructured":"Lokuciejewski, P., Falk, H., Marwedel, P., Theiling, H.: Wcet-driven, code-size critical procedure cloning. In: Falk, H. (ed.) SCOPES, ACM International Conference Proceeding Series, vol. 296, pp. 21\u201330 (2008)","DOI":"10.1145\/1361096.1361100"},{"key":"161_CR39","unstructured":"Lisper, B.: Ideas for annotation language(s). Technical Report Oct. 25, Department of Computer Science and Engineering, University of M\u00e4lardalen (2005)"},{"key":"161_CR40","unstructured":"Li, X., Liang, Y., Mitra, T., Roychoudhury, A.: Chronos user manual. Web page. http:\/\/www.comp.nus.edu.sg\/~rpembed\/chronos\/chronos_manual.pdf . Accessed online in February (2010)"},{"key":"161_CR41","unstructured":"Li, X., Liang, Y., Mitra, T., Roychoudury, A.: Chronos: A timing analyzer for embedded software. Science of Computer Programming, 69(1\u20133):56\u201367, (2007). http:\/\/www.comp.nus.edu.sg\/~rpembed\/chronos"},{"key":"161_CR42","doi-asserted-by":"crossref","unstructured":"Li, Y.-T.S., Malik, S.: Performance analysis of embedded software using implicit path enumeration. In: Proceedings of the 32nd ACM\/IEEE Design Automation Conference, June, pp. 456\u2013461 (1995)","DOI":"10.1145\/217474.217570"},{"key":"161_CR43","unstructured":"lpsolve. Tool web page: http:\/\/lpsolve.sourceforge.net\/ . Accessed online in February (2010)"},{"key":"161_CR44","doi-asserted-by":"crossref","unstructured":"Lundqvist, T., Stenstr\u00f6m, P.: Timing analysis in dynamically scheduled microprocessors. In: Proceedings of the 20th IEEE Real-Time Systems Symposium (RTSS), December, pp. 12\u201321 (1999)","DOI":"10.1109\/REAL.1999.818824"},{"key":"161_CR45","unstructured":"Mok, A.K., Amerasinghe, P., Chen, M., Tantisirivat, K.: Evaluating tight execution time bounds of programs by annotations. In: Proceedings of the 6th IEEE Workshop on Real-Time Operating Systems And Software, May, pp. 74\u201380, Pittsburgh, PA, USA (1989)"},{"key":"161_CR46","unstructured":"Maxima Manual, 5.18 edn. Available online at http:\/\/maxima.sourceforge.net\/docs\/manual\/en\/maxima.pdf"},{"key":"161_CR47","unstructured":"Muchnick, S.S.: Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco (1997). ISBN 1-55860-320-4"},{"key":"161_CR48","doi-asserted-by":"crossref","unstructured":"MacNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IRE Trans. Electron. Comp. 9(39\u201347), (1960)","DOI":"10.1109\/TEC.1960.5221603"},{"key":"161_CR49","unstructured":"OMG. UML Profile for Modeling and Analysis of Real-time and Embedded Systems (MARTE). Object Management Group, June (2008)"},{"key":"161_CR50","unstructured":"Park, C.Y.: Predicting Deterministic Execution Times of Real-Time Programs. Ph.D. Thesis, University of Washington, Seattle, USA, 1992. TR 92-08-02"},{"issue":"1","key":"161_CR51","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF01088696","volume":"5","author":"C.Y. Park","year":"1993","unstructured":"Park C.Y.: Predicting program execution times by analyzing static and dynamic program paths. Real-Time Syst. 5(1), 31\u201362 (1993)","journal-title":"Real-Time Syst."},{"key":"161_CR52","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF00571421","volume":"1","author":"P. Puschner","year":"1989","unstructured":"Puschner P., Koza C.: Calculating the maximum execution time of real-time programs. J. Real-Time Syst. 1, 159\u2013176 (1989)","journal-title":"J. Real-Time Syst."},{"key":"161_CR53","unstructured":"Prantl, A., Knoop, J., Kirner, R., Kadlec, A., Schordan, M.: From trusted annotations to verified knowledge. In Proceedings of the 9th International Workshop on Worst-Case Execution Time Analysis, Dublin, Ireland, June (2009)"},{"issue":"5","key":"161_CR54","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/2.76286","volume":"24","author":"C.Y. Park","year":"1991","unstructured":"Park C.Y., Shaw A.C.: Experiments with a program timing tool based on a source-level timing schema. Computer 24(5), 48\u201357 (1991)","journal-title":"Computer"},{"key":"161_CR55","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1007905003094","volume":"13","author":"P. Puschner","year":"1997","unstructured":"Puschner P., Schedl A.V.: Computing maximum task execution times\u2014a graph-based approach. J. Real-Time Syst. 13, 67\u201391 (1997)","journal-title":"J. Real-Time Syst."},{"key":"161_CR56","unstructured":"Prantl, A., Schordan, M., Knoop, J.: TuBound\u2014a conceptually new tool for worst-case execution time analysis. In: 8th International Workshop on Worst-Case Execution Time Analysis (WCET 2008), pp. 141\u2013148, Prague, Czech Republic, 2008. ISBN: 978-3-85403-237-3"},{"key":"161_CR57","unstructured":"RAPITA Systems Ltd. Worst-case execution time analysis. White Paper (Automotive), Rev. 1.32, 21st Sep. (2006)"},{"issue":"4","key":"161_CR58","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S1383-7621(99)00010-7","volume":"46","author":"F. Stappert","year":"2000","unstructured":"Stappert F., Altenbernd P.: Complete worst-case execution time analysis of straight-line hard real-time programs. J. Syst. Archit. 46(4), 339\u2013355 (2000)","journal-title":"J. Syst. Archit."},{"issue":"7","key":"161_CR59","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1109\/32.29487","volume":"15","author":"A.C. Shaw","year":"1989","unstructured":"Shaw A.C.: Reasoning about time in higher level language software. IEEE Trans. Softw. Eng. 15(7), 875\u2013889 (1989)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"161_CR60","unstructured":"Sharir, M., Pnueli, A.: Two approaches to interprocedural data flow analysis. In: Muchnick, S.S., Jones, N.D. (eds.) Program Flow Analysis: Theory and Applications, chapter 7, pp. 189\u2013233. Prentice Hall, Englewood Cliffs (1981)"},{"issue":"3","key":"161_CR61","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1145\/322261.322273","volume":"28","author":"R.E. Tarjan","year":"1981","unstructured":"Tarjan R.E.: Fast algorithms for solving path problems. J. ACM 28(3), 594\u2013614 (1981)","journal-title":"J. ACM"},{"key":"161_CR62","unstructured":"Tan, L., Echtle, K.: The WCET tool challenge 2006: external evaluation\u2014draft report. In: Handout at the 2nd Int. IEEE Symposium on Leveraging Applications of Formal Methods, Verification and Validation, Paphos, Cyprus, November 2006, 13\u00a0pp."},{"key":"161_CR63","unstructured":"Vrchoticky, A.: Modula\/R\u2014Language Definition. Technical Report 02\/1992, Technische Universit\u00e4t Wien, Institut f\u00fcr Technische Informatik, Treitlstr. 1-3\/182-1, 1040, March. Vienna, Austria (1992)"},{"key":"161_CR64","unstructured":"Vrchoticky, A.: Compilation support for fine-grained execution time analysis. In: Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems, June. Orlando FL (1994)"},{"key":"161_CR65","unstructured":"WCET annotation language challenge. Web page: http:\/\/costa.tuwien.ac.at\/languages.html . Accessed online in Feb. (2010)"},{"key":"161_CR66","doi-asserted-by":"crossref","unstructured":"Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckman, R., Mitra, T., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., Stenstrom, P.: The worst-case execution time problem\u2014overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. (TECS) 7(3), (2008)","DOI":"10.1145\/1347375.1347389"},{"key":"161_CR67","doi-asserted-by":"crossref","unstructured":"Wenzel, I., Kirner, R., Rieder, B., Puschner, P.: Measurement-based timing analysis. In: Proceedings of the 3rd Int\u2019l Symposium on Leveraging Applications of Formal Methods, Verification and Validation, Porto Sani, Greece (2008)","DOI":"10.1007\/978-3-540-88479-8_30"},{"key":"161_CR68","unstructured":"Wright, F.: Computing with Maple. Crc Mathematics Series. Chapman & Hall, London (2001)"},{"key":"161_CR69","doi-asserted-by":"crossref","unstructured":"Wenzel, I., Rieder, B., Kirner, R., Puschner, P.: Automatic timing model generation by CFG partitioning and model checking. In: Proceedings of the Conference on Design, Automation and Test in Europe (DATE\u201905), March, pp. 606\u2013611. Munich, Germany. IEEE New York (2005)","DOI":"10.1109\/DATE.2005.76"}],"container-title":["Software & Systems Modeling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s10270-010-0161-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T22:04:26Z","timestamp":1740002666000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10270-010-0161-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,9]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["161"],"URL":"https:\/\/doi.org\/10.1007\/s10270-010-0161-0","relation":{},"ISSN":["1619-1366","1619-1374"],"issn-type":[{"value":"1619-1366","type":"print"},{"value":"1619-1374","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,9]]}}}