The worst-case execution-time problem—overview of methods and survey of tools
The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools 1 and research prototypes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Clarke, E. M., Grümberg, O., & Long, D. (1996) · Cited by 6,813
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279 · cited 5×
“Static program analysis is a generic method to determine properties of the dynamic behavior of a given task without actually executing the task [Cousot and Cousot 1977; Nielson et al. 1999].”
MethodInfluentialClarke, E. M., & Schlingloff, B. (1999) · Cited by 4,226
Principles of Program Analysis
Nielson, F., Nielson, H. R., & Hankin, C. (1999) · Springer eBooks · doi:10.1007/978-3-662-03811-6 · Cited by 1,836
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647
An open graph visualization system and its applications to software engineering
Gansner, E. R., & North, S. C. (2000) · Software: Practice and Experience · doi:10.1002/1097-024x(200009)30:11<1203::aid-spe338>3.0.co;2-n · Cited by 1,273
The Omega test: a fast and practical integer programming algorithm for dependence analysis
Pugh, W. (1991) · Proceedings of the 1991 ACM/IEEE conference on Supercomputing - Supercomputing '91 · doi:10.1145/125826.125848 · Cited by 750
Reasoning about time in higher-level language software
Shaw, A. C. (1989) · IEEE Transactions on Software Engineering · doi:10.1109/32.29487 · Cited by 369
Power Efficient Processor Architecture and The Cell Processor
Hofstee, H. P. (2005) · 11th International Symposium on High-Performance Computer Architecture · doi:10.1109/hpca.2005.26 · Cited by 346
Reliable and Precise WCET Determination for a Real-Life Processor
Ferdinand, C., Heckmann, R., Langenbach, M., Martin, F., Schmidt, M., Theiling, H., Thesing, S., & Wilhelm, R. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45449-7_32 · Cited by 278
Self-citationFast and Precise WCET Prediction by Separated Cache and Path Analyses
Theiling, H., Ferdinand, C., & Wilhelm, R. (2000) · Real-Time Systems · doi:10.1023/a:1008141130870 · Cited by 264
Self-citationThe influence of processor architecture on the design and the results of WCET tools
Heckmann, R., Langebach, M., Thesing, S., & Wilhelm, R. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814618 · Cited by 255
Self-citationAn accurate worst case timing analysis for RISC processors
Lim, S.-S., Bae, Y. H., Jang, G. T., Rhee, B.-D., Min, S. L., Park, C. Y., Shin, H., Park, K., Moon, S.-M., & Kim, C. S. (1995) · IEEE Transactions on Software Engineering · doi:10.1109/32.392980 · Cited by 254
Efficient and Precise Cache Behavior Prediction for Real-Time Systems
Ferdinand, C., & Wilhelm, R. (1999) · Real-Time Systems · doi:10.1023/a:1008186323068 · Cited by 233
Self-citationTiming Analysis for Instruction Caches
Mueller, F. (2000) · Real-Time Systems · doi:10.1023/a:1008145215849 · Cited by 183
Self-citationLow-complexity algorithms for static cache locking in multitasking hard real-time systems
Puaut, I., & Decotigny, D. (2003) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.2002.1181567 · Cited by 151
Self-citationProcessor Pipelines and Static Worst-Case Execution Time Analysis
Engblom, J. (2002) · Cited by 130
Self-citationComplete worst-case execution time analysis of straight-line hard real-time programs
Stappert, F., & Altenbernd, P. (2000) · Journal of Systems Architecture · doi:10.1016/s1383-7621(99)00010-7 · Cited by 121
An abstract interpretation-based timing validation of hard real-time avionics software
Thesing, S., Souyris, J., Heckmann, R., Randimbivololona, F., Langenbach, M., Wilhelm, R., & Ferdinand, C. (2004) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2003.1209972 · Cited by 94
Self-citationFAST: frequency-aware static timing analysis
Seth, K., Anantaraman, A. V., Mueller, F., & Rotenberg, E. (2004) · International Symposium on System-on-Chip · doi:10.1109/real.2003.1253252 · Cited by 73
Self-citationApplying Static WCET Analysis to Automotive Communication Software
Byhlin, S., Ermedahl, A., Gustafsson, J., & Lisper, B. (2006) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2005.7 · Cited by 73
Self-citationVirtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems
Anantaraman, A. V., Seth, K., Patil, K., Rotenberg, E., & Mueller, F. (2003) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/859618.859659 · Cited by 67
Self-citationPipeline Modeling for Timing Analysis
Langenbach, M., Thesing, S., & Heckmann, R. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45789-5_22 · Cited by 63
Self-citationTiming Analysis for Data and Wrap-Around Fill Caches
White, R. T., Mueller, F., Healy, C., Whalley, D. B., & Harmon, M. G. (1999) · Real-Time Systems · doi:10.1023/a:1008190423977 · Cited by 56
Self-citationILP-Based Interprocedural Path Analysis
Theiling, H. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45828-x_26 · Cited by 45
Static Timing Analysis of Real-Time Operating System Code
Sandell, D., Ermedahl, A., Gustafsson, J., & Lisper, B. (2006) · Lecture notes in computer science · doi:10.1007/11925040_10 · Cited by 43
Self-citationFaster WCET flow analysis by program slicing
Sandberg, C., Ermedahl, A., Gustafsson, J., & Lisper, B. (2006) · ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES) · doi:10.1145/1134650.1134666 · Cited by 38
Self-citation
Cited by
A survey of hard real-time scheduling for multiprocessor systems
Davis, R. I., & Burns, A. (2011) · ACM Computing Surveys · doi:10.1145/1978802.1978814 · Cited by 907
The Past, Present and Future of Cyber-Physical Systems: A Focus on Models
Lee, E. (2015) · Sensors · doi:10.3390/s150304837 · Cited by 682
Comprehensive formal verification of an OS microkernel
Klein, G., Andronick, J., Elphinstone, K., Murray, T., Sewell, T., Kolanski, R., & Heiser, G. (2014) · ACM Transactions on Computer Systems · doi:10.1145/2560537 · Cited by 348
Performance evaluation of component-based software systems: A survey
Koziolek, H. (2010) · Performance Evaluation · doi:10.1016/j.peva.2009.07.007 · Cited by 329
Lee, E. A. (2010) · Proceedings of the 47th Design Automation Conference · doi:10.1145/1837274.1837462 · Cited by 315
Metadata
- Authors
- Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mitra, T., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., & Stenström, P.
- Venue
- ACM Transactions on Embedded Computing Systems
- Published
- 2008-04
- Volume
- 7
- Issue
- 3
- Pages
- 1-53
- ISSN
- 1539-9087 (ISSN-L)
- 1558-3465
- OpenAlex
- W2076285066
- Cited by
- 1,871
- References
- 28
- FWCI
- 248.41
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.