Reinhard Wilhelm
Jakob Engblom
Andreas Ermedahl
Niklas Holsti
Tulika Mitra
Skip Abstract Section
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 tools1 and research prototypes.
- Anantaraman, A., Seth, K., Patil, K., Rotenberg, E., and Mueller, F. 2003. Virtual simple architecture (VISA): Exceeding the complexity limit in safe real-time systems. In International Symposium on Computer Architecture. 250--261. Google Scholar
Digital Library
- Anantaraman, A., Seth, K., Patil, K., Rotenberg, E., and Mueller, F. 2004. Enforcing safety of real-time schedules on contemporary processors using a virtual simple architecture (VISA). In Proceedings of the IEEE Real-Time Systems Symposium. 114--125. Google ScholarDigital Library
- Arnold, R., Mueller, F., Whalley, D., and Harmon, M. 1994. Bounding worst-case instruction cache performance. In Proceedings of the IEEE Real-Time Systems Symposium. Puerto Rico. 172--181.Google Scholar
- Atanassov, P., Haberl, S., and Puschner, P. 1999. Heuristic worst-case execution time analysis. In Proceedings of the 10th European Workshop on Dependable Computing. Austrian Computer Society (OCG). 109--114.Google Scholar
- Austin, T., Larson, E., and Ernst, D. 2002. SimpleScalar: An infrastructure for computer system modeling. IEEE Comput. 35, 2. Google ScholarDigital Library
- Berkelaar, M. 1997. lp solve: A mixed integer linear program solver. Tech. Rept. Eindhoven University of Technology.Google Scholar
- Bernat, G., Colin, A., and Petters, S. M. 2002. WCET analysis of probabilistic hard real--time systems. In Proceedings of the 23rd Real-Time Systems Symposium RTSS 2002. Austin, Texas. 279--288. Google ScholarDigital Library
- Bernat, G., Newby, M., and Burns, A. 2005. Probabilistic timing analysis: An approach using copulas. J. Embedded Comput. 1, 2, 179--194. Google ScholarDigital Library
- Byhlin, S., Ermedahl, A., Gustafsson, J., and Lisper, B. 2005. Applying static WCET analysis to automotive communication software. In Proceedings of the 17th Euromicro Conference of Real-Time Systems, (ECRTS'05). 249--258. Google ScholarDigital Library
- Carlsson, M., Engblom, J., Ermedahl, A., Lindblad, J., and Lisper, B. 2002. Worst-case execution time analysis of disable interrupt regions in a commercial real-time operating system. In Proceedings of the 2nd International Workshop on Real-Time Tools (RT-TOOLS'2002).Google Scholar
- Chvatal, V. 1983. Linear Programming, Freeman, San Francisco, CA.Google Scholar
- Clarke, E. M., Grumberg, O., and Peled, D. A. 1999. Model Checking. MIT Press, Cambridge, MA. Google ScholarDigital Library
- Colin, A. and Bernat, G. 2002. Scope-tree: A program representation for symbolic worst-case execution time analysis. In Proceedings of the 14th Euromicro Conference of Real-Time Systems, (ECRTS'02). 50--59. Google ScholarDigital Library
- Colin, A. and Puaut, I. 2000. Worst case execution time analysis for a processor with branch prediction. J. Real-Time Syst. 18, 2--3 (May), 249--274. Google ScholarDigital Library
- Colin, A. and Puaut, I. 2001a. A modular and retargetable framework for tree-based WCET analysis. In Proceedings of the 13th Euromicro Conference on Real-Time Systems. Delft, The Netherlands. 37--44. Google ScholarDigital Library
- Colin, A. and Puaut, I. 2001b. Worst-case execution time analysis of the RTEMS real-time operating system. In Proceedings of the 13th Euromicro Conference on Real-Time Systems. Delft, The Netherlands. 191--198. Google ScholarDigital Library
- Cousot, P. and Cousot, R. 1977. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM Symposium on Principles of Programming Languages. Los Angeles, CA. 238--252. Google ScholarDigital Library
- Desikan, R., Burger, D., and Keckler, S. 2001. Measuring experimental error in microprocessor simulation. In Proceedings of the 28th International Symposium on Computer Architecture (ISCA 2001). ACM Press, New York. Google ScholarDigital Library
- Engblom, J. 2002. Processor pipelines and static worst-case execution time analysis. Ph.D. thesis, Uppsala University, Dept. of Information Technology, Box 337, Uppsala, Sweden.Google Scholar
- Eriksson, O. 2005. Evaluation of static time analysis for CC systems. M.S. thesis, Mälardalen University, Västerås, Sweden.Google Scholar
- Ermedahl, A. 2003. A modular tool architecture for worst-case execution time analysis. Ph.D. thesis, Uppsala University, Dept. of Information Technology, Box 325, Uppsala, Sweden. ISBN 91-554-5671-5.Google Scholar
- Ermedahl, A., Stappert, F., and Engblom, J. 2005. Clustered worst-case execution-time calculation. IEEE Trans. Comput. 54, 9 (9). Google ScholarDigital Library
- Ferdinand, C. and Wilhelm, R. 1999. Fast and efficient cache behavior prediction for real-time systems. Real-Time Systems 17, 131--181. Google ScholarDigital Library
- Ferdinand, C., Martin, F., and Wilhelm, R. 1999. Cache behavior prediction by abstract interpretation. Sci. Comput. Programming 35, 163--189. Google ScholarDigital Library
- Ferdinand, C., Heckmann, R., Langenbach, M., Martin, F., Schmidt, M., Theiling, H., Thesing, S., and Wilhelm, R. 2001. Reliable and precise WCET determination for a real-life processor. In EMSOFT. LNCS, vol. 2211. 469--485. Google ScholarDigital Library
- Gansner, E. R. and North, S. C. 2000. An open graph visualization system and its applications to software engineering. Softw. Pract. Exp. 30, 11, 1203--1233. Google ScholarDigital Library
- Graham, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45, 1563--1581.Google ScholarCross Ref
- Gustafsson, J. 2000. Analyzing execution-time of object-oriented programs using abstract interpretation. Ph.D. thesis, Department of Computer Systems, Information Technology, Uppsala University.Google Scholar
- Gustafsson, J., Lisper, B., Sandberg, C., and Bermudo, N. 2003. A tool for automatic flow analysis of C-programs for WCET calculation. In 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS 2003), Guadalajara, Mexico.Google Scholar
- Gustafsson, J., Ermedahl, A., and Lisper, B. 2005. Towards a flow analysis for embedded system C programs. In Proceedings of the 10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS 2005). Sedona. Google ScholarDigital Library
- Healy, C. and Whalley, D. 1999. Tighter timing predictions by automatic detection and exploitation of value-dependent constraints. In Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS'99). 79--88. Google ScholarDigital Library
- Healy, C. and Whalley, D. 2002. Automatic detection and exploitation of branch constraints for timing analysis. IEEE Trans. Softw. Eng. 763--781. Google ScholarDigital Library
- Healy, C., Whalley, D., and Harmon, M. 1995. Integrating the timing analysis of pipelining and instruction caching. In Proceedings of the IEEE Real-Time Systems Symposium. Pisa, Italy. 288--297. Google ScholarDigital Library
- Healy, C., Sjödin, M., Rustagi, V., and Whalley, D. 1998. Bounding loop iterations for timing analysis. In Proceedings of the 4th IEEE Real-Time Technology and Applications Symposium (RTAS'98). Google ScholarDigital Library
- Healy, C., Arnold, R., Müller, F., Whalley, D., and Harmon, M. 1999. Bounding pipeline and instruction cache performance. IEEE Trans. Comput. 48, 1 (Jan). Google ScholarDigital Library
- Healy, C., Sjodin, M., Rustagi, V., Whalley, D., and van Engelen, R. 2000. Supporting timing analysis by automatic bounding of loop iterations. J. Real-Time Syst. 121--148. Google ScholarDigital Library
- Heckmann, R., Langenbach, M., Thesing, S., and Wilhelm, R. 2003. The influence of processor architecture on the design and the results of WCET tools. IEEE Proc. Real-Time Syst. 91, 7, 1038--1054.Google ScholarCross Ref
- Hofstee, P. 2005. Power efficient processor architecture and the cell processor. In 11th Symposium on High-Performance Computing Architecture (HPCA-11). Google ScholarDigital Library
- Holsti, N., Långbacka, T., and Saarinen, S. 2000a. Using a worst-case execution-time tool for real-time verification of the DEBIE software. In Proceedings of the DASIA 2000 Conference (Data Systems in Aerospace 2000, ESA SP-457).Google Scholar
- Holsti, N., Långbacka, T., and Saarinen, S. 2000b. Worst-case execution-time analysis for digital signal processors. In Proceedings of the EUSIPCO 2000 Conference (X European Signal Processing Conference).Google Scholar
- Jayaseelan, R., Mitra, T., and Li, X. 2006. Estimating the worst-case energy consumption of embedded software. In 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). Google ScholarDigital Library
- Kirner, R. 2002. The programming language wcetC. Tech. rept. Technische Universität Wien, Institut für Technische Informatik, Treitlstr. 1-3/182-1, 1040 Vienna, Austria.Google Scholar
- Kirner, R. 2003. Extending optimising compilation to support worst-case execution time analysis. Ph.D. thesis, Technische Universität Wien, Vienna, Austria.Google Scholar
- Kirner, R. and Puschner, P. 2003. Transformation of meta-information by abstract co-interpretation. In Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems. Vienna, Austria. 298--312.Google Scholar
- Kirner, R., Lang, R., Freiberger, G., and Puschner, P. 2002. Fully automatic worst-case execution time analysis for matlab/simulink models. In Proceedings of the 14th Euromicro International Conference on Real-Time Systems. 31--40. Google ScholarDigital Library
- Krewell, K. 2005. IBM speeds Xbox 360 to market. Microprocessor Report.Google Scholar
- Langenbach, M., Thesing, S., and Heckmann, R. 2002. Pipeline modelling for timing analysis. In Static Analysis Symposium SAS 2002, M. V. Hermenegildo and G. Puebla, Eds. Lecture Notes in Computer Science, vol. 2477. Springer-Verlag, New York. 294--309. Google ScholarDigital Library
- Li, X. 2005. Microarchitecture modeling for timing analysis of embedded software. Ph.D. thesis, School of Computing, National University of Singapore.Google Scholar
- Li, X., Mitra, T., and Roychoudhury, A. 2003. Accurate timing analysis by modeling caches, speculation and their interaction. In ACM Design Auto. Conf. (DAC). Google ScholarDigital Library
- Li, Y.-T. S. and Malik, S. 1995. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the 32:nd Design Automation Conference. 456--461. Google ScholarDigital Library
- Li, Y.-T. S., Malik, S., and Wolfe, A. 1995a. Efficient microarchitecture modeling and path analysis for real-time software. In Proceedings of the IEEE Real-Time Systems Symposium. 298--307. Google ScholarDigital Library
- Li, Y.-T. S., Malik, S., and Wolfe, A. 1995b. Performance estimation of embedded software with instruction cache modeling. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 380--387. Google ScholarDigital Library
- Li, Y.-T. S., Malik, S., and Wolfe, A. 1999. Performance estimation of embedded software with instruction cache modeling. ACM Trans. Design Auto. Electronic Syst. 4, 3. Google ScholarDigital Library
- Li, X., Roychoudhury, A., and Mitra, T. 2004. Modeling out-of-order processors for software timing analysis. In IEEE Real-Time Systems Symposium (RTSS). Google ScholarDigital Library
- Li, X., Mitra, T., and Roychoudhury, A. 2005. Modeling control speculation for timing analysis. J. Real-Time Syst. 29, 1. Google ScholarDigital Library
- 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., and Kim, C. S. 1995. An accurate worst case timing analysis for RISC processors. IEEE Trans. Softw. Eng. 21, 7, 593--604. Google ScholarDigital Library
- Lundqvist, T. 2002. A WCET analysis method for pipelined microprocessors with cache memories. Ph.D. thesis, Dept. of Computer Engineering, Chalmers University of Technology, Sweden.Google Scholar
- Lundqvist, T. and Stenström, P. 1999a. A method to improve the estimated worst-case performance of data caching. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA'99). 255--262. Google ScholarDigital Library
- Lundqvist, T. and Stenström, P. 1999b. An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Syst. 17, 2/3 (Nov.). Google ScholarDigital Library
- Lundqvist, T. and Stenström, P. 1999c. Timing anomalies in dynamically scheduled microprocessors. In Proceedings of the 20th IEEE Real-Time Systems Symposium (RTSS'99). 12--21. Google ScholarDigital Library
- Mitra, T., Roychoudhury, A., and Li, X. 2002. Timing analysis of embedded software for speculative processors. In ACM SIGDA International Symposium on System Synthesis (ISSS). Google ScholarDigital Library
- Mohan, S., Mueller, F., Whalley, D., and Healy, C. 2005. Timing analysis for sensor network nodes of the atmega processor family. Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium. 405--414. Google ScholarDigital Library
- Mueller, F. 2000. Timing analysis for instruction caches. J. Real-Time Syst. 18, 2 (May), 217--247. Google ScholarDigital Library
- Nielson, F., Nielson, H. R., and Hankin, C. 1999. Principles of Program Analysis. Springer-Verlag, Heidelberg. Google ScholarDigital Library
- Olukotun, K. and Hammond, L. 2005. The future of microprocessors. ACM Queue. Google ScholarDigital Library
- Puaut, I. and Decotigny, D. 2002. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS02), Austin, Texas. 114--123. Google ScholarDigital Library
- Pugh, W. 1991. The omega test: A fast and practical integer programming algorithm for dependence analysis. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing. ACM Press, New York. 4--13. Google ScholarDigital Library
- Puschner, P. 2005. Experiments with WCET-oriented programming and the single-path architecture. In Proceedings of the 10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems. 205--210. Google ScholarDigital Library
- Puschner, P. and Schedl, A. 1997. Computing maximum task execution times—A graph-based approach. J. Real-Time Syst. 13, 1 (Jul.), 67--91. Google ScholarDigital Library
- Puschner, P. and Nossal, R. 1998. Testing the results of static worst-case execution-time analysis. In Proceedings of the 19th IEEE Real-Time Systems Symposium. 134--143. Google ScholarDigital Library
- Puschner, P. P. and Schedl, A. V. 1995. Computing maximum task execution times with linear programming techniques. Tech. rept. Technische Universität Wien, Institut für Technische Informatik. Apr.Google Scholar
- Ramaprasad, H. and Mueller, F. 2005. Bounding worst-case data cache behavior by analytically deriving cache reference patterns. In Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium. 148--157. Google ScholarDigital Library
- Reineke, J., Thesing, S., Wachter, B., Wilhelm, R., Becker, B., Eisinger, J., and Polian, I. 2006. On the notion of timing anaomaly. forthcoming.Google Scholar
- Sandell, D., Ermedahl, A., Gustafsson, J., and Lisper, B. 2004. Static timing analysis of real-time operating system code. In Proceedings of the 1st International Symposium on Leveraging Applications of Formal Methods (ISOLA'04). Google ScholarDigital Library
- Sehlberg, D. 2005. Static WCET analysis of task-oriented code for construction vehicles. M.S. thesis, Mälardalen University, Västerås, Sweden.Google Scholar
- Seth, K., Anantaraman, A., Mueller, F., and Rotenberg, E. 2003. FAST: Frequency-aware static timing analysis. In Proceedings of the IEEE Real-Time Systems Symposium. 40--51. Google ScholarDigital Library
- Shaw, A. C. 1989. Reasoning about time in higher-level language software. IEEE Trans. Softw. Eng. 15, 7, 875--889. Google ScholarDigital Library
- Souyris, J., le Pavec, E., Himbert, G., Jégu, V., Borios, G., and Heckmann, R. 2005. Computing the WCET of an avionics program by abstract interpretation. In WCET 2005. 15--18.Google Scholar
- Stappert, F. and Altenbernd, P. 2000. Complete worst-case execution time analysis of straight-line hard real-time programs. J. Syst. Architecture 46, 4, 339--355. Google ScholarDigital Library
- Stappert, F., Ermedahl, A., and Engblom, J. 2001. Efficient longest executable path search for programs with complex flows and pipeline effects. In Proceedings of the 4th International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, (CASES'01). Google ScholarDigital Library
- Staschulat, J. and Ernst, R. 2004. Multiple process execution in cache related preemption delay analysis. In EMSOFT. Pisa, Italy. Google ScholarDigital Library
- Staschulat, J. and Ernst, R. 2006. Worst case timing analysis of input dependent data cache behavior. In ECRTS. Dresden, Germany. Google ScholarDigital Library
- Staschulat, J., Schliecker, S., and Ernst, R. 2005. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In ECRTS. Palma de Mallorca, Spain. Google ScholarDigital Library
- Theiling, H. 2002a. Control flow graphs for real-time systems analysis. Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany.Google Scholar
- Theiling, H. 2002b. ILP-based interprocedural path analysis. In Embedded Software (EMSOFT). Lecture Notes in Computer Science, vol. 2491. Springer, New York. 349--363. Google ScholarDigital Library
- Theiling, H., Ferdinand, C., and Wilhelm, R. 2000. Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst. 18, 2/3 (May), 157--179. Google ScholarDigital Library
- Thesing, S. 2004. Safe and precise WCET determination by abstract interpretation of pipeline models. Ph.D. thesis, Saarland University.Google Scholar
- 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 2003 International Conference on Dependable Systems and Networks (DSN 2003). IEEE Computer Society, Los Alamitos, CA. 625--632.Google Scholar
- Thiele, L. and Wilhelm, R. 2004. Design for timing predictability. Real-Time Syst. 28, 157--177. Google ScholarDigital Library
- Vivancos, E., Healy, C., Mueller, F., and Whalley, D. 2001. Parametric timing analysis. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems. 88--93. Google ScholarDigital Library
- Wenzel, I., Rieder, B., Kirner, R., and Puschner, P. 2005a. Automatic timing model generation by CFG partitioning and model checking. In Proceedings of the Design, Automation and Test in Europe (DATE'05). Munich, Germany. Google ScholarDigital Library
- Wenzel, I., Rieder, B., Kirner, R., and Puschner, P. 2005b. Measurement-based worst-case execution time analysis. In Proceedings of the 3rd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS'05). Seatlle, Washington. 7--10. Google ScholarDigital Library
- White, R., Mueller, F., Healy, C., and Whalley, D. 1999. Timing analysis for data caches and wrap-around fill caches. Real-Time Syst. 209--233. Google ScholarDigital Library
- Wilhelm, R. 2004. Why AI + ILP is good for WCET, but MC is not, nor ILP alone. In VMCAI 2004. LNCS, vol. 2937. Springer, New York. 309--322.Google ScholarCross Ref
- Wilhelm, R. 2005. Determining bounds on execution times. In Handbook on Embedded Systems, R. Zurawski, Ed. CRC Press, Boca Raton, FL. 14--1, 14--23.Google Scholar
- Wilhelm, R., Engblom, J., Thesing, S., and Whalley, D. 2003. Industrial requirements for WCET tools—Answers to the ARTIST questionnaire. In EUROMICRO Workshop on WCET (WCET 2003).Google Scholar
- Wolf, F. 2002. Behavioral Intervals in Embedded Software. Kluwer Academic Publ., Norwel, MA. Google ScholarDigital Library
- Wolf, F., Ernst, R., and Ye, W. 2001. Path clustering in software timing analysis. IEEE Trans. VLSI Syst. 9, 6, 773--782. Google ScholarDigital Library
- Wolf, F., Kruse, J., and Ernst, R. 2002a. Timing and power measurement in static software analysis. In Microelectronics Journal, Special Issue on Design, Modeling and Simulation in Microelectronics and MEMS, vol. 6(2). 91--100.Google Scholar
- Wolf, F., Staschulat, J., and Ernst, R. 2002b. Hybrid cache analysis in running time verification of embedded software. J. Design Autom. Embedded Syst. 7, 3, 271--295.Google ScholarDigital Library
- Ye, W. and Ernst, R. 1997. Embedded program timing analysis based on path clustering and architecture classificaton. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD '97), San Jose, CA. 598--604. Google ScholarDigital Library
- Zhang, Y. 2005. Evaluation of methods for dynamic time analysis for CC systems AB. M.S. thesis, Mälardalen University, Västerås, Sweden.Google Scholar
Index Terms
- The worst-case execution-time problem—overview of methods and survey of tools
Recommendations
The worst-case execution time tool challenge 2006
The first international worst-case execution time (WCET) Tool Challenge in 2006 used benchmark programs to evaluate academic and commercial WCET tools. It aimed to study the state-of-the-art in WCET analysis. The WCET Tool Challenge comprised two ...
The Worst Case Execution Time Tool Challenge 2006
ISOLA '06: Proceedings of the Second International Symposium on Leveraging Applications of Formal Methods, Verification and ValidationWorst Case Execution Time (WCET) analysis has a growing importance for real-time systems, to guarantee correct timing, and to be an aid in developing such systems. The WCET tools are currently making their way out to the market, and there are many ...
Loop-Based Instruction Prefetching to Reduce the Worst-Case Execution Time
Estimating and optimizing worst-case execution time (WCET) is critical for hard real-time systems to ensure that different tasks can meet their respective deadlines. Recent work has shown that simple prefetching techniques such as the Next-N-Line ...
Comments