An Overview of Worst-Case Execution Time Estimation for Embedded Programs

Abstract:

Most embedded systems are real-time systems, so real-time is an important performance metric for embedded systems. The worst-case execution time (WCET) estimation for embedded programs could satisfy the requirement of hard real-time evaluation, so it is widely used in embedded systems evaluation. Based on sufficient survey on the progress of WCET estimation around the world, it proposes a new classification of WCET estimation. After introducing the principle of WCET estimation, it mainly demonstrates various types of technologies to estimate WCET and classifies them into two main streams, namely, static and dynamic WCET estimations. Finally, it shows the development of WCET analysis tools.

• Periodical: Applied Mechanics and Materials (Volumes 651-653)
• Pages: 624-629
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.651-653.624
• Online since: September 2014
• Authors: Liang Liang Kong*, Lin Xiang Shi, Lin Chen
• Keywords: Embedded System, Measurement, Real-Time System, Simulation, Worst-Case Execution Time Estimation

References

[1] J. Engblom, A. Ermedahl, F. Stappert. A worst-case execution-time analysis tool prototype for embedded real-time systems. In: Proceedings of the first Workshop on Real-Time Tools, Uppsala University, Sweden, 2001: 1-12.

DOI: 10.1109/real.2000.896006

[2] L. Kong, J. Jiang, J. Xiao, and Y. Jiang. Simulation-based Non-linear Methods for the Estimation of Execution Cycles of ARM Programs. Journal of Computer Research and Development, 2012, 49(2): 392-401.

[3] R. Wilhelm, J. Engblom, A. Ermedahl, et al. The worst-case execution-time problem-overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 2008, 7(3): 1-49.

DOI: 10.1145/1347375.1347389

[4] C. Y. Park. Predicting program execution times by analyzing static and dynamic program paths. Real-Time Systems, 1993, 5 (1): 31-62.

DOI: 10.1007/bf01088696

[5] P. Puschner, A. Schedl. Computing maximum task execution times with linear programming techniques. In: Proceedings of IEEE International Conference on Embedded and Real-Time Computing Systmes and Applications, IEEE, Piscataway, NJ, 1995: 12-24.

[6] F. Stappert, P. Altenbernd. Complete worst-case execution time analysis of straight-line hard real-time programs. Journal of Systems Architecture: the EUROMICRO Journal - Special issue on real-time systems, 2000, 46 (4): 339-355.

DOI: 10.1016/s1383-7621(99)00010-7

[7] J. Gustafsson, A. Ermedahl, B. Lisper. Towards a flow analysis for embedded system C programs. In: Proceedings of the 10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, IEEE, Piscataway, NJ, 2005: 287-297.

DOI: 10.1109/words.2005.53

[8] J. Gustafsson. Analyzing execution-time of object-oriented programs using abstract interpretation: [dissertation]. Uppsala: Department of Computer Systems, Information Technology, Uppsala University, (2000).

[9] J. Gustafsson, A. Ermedahl, C. Sandberg, et al. Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution. In: Proceedings of the 27th IEEE International Workshop on Real-Time Systems Symposium, IEEE, Piscataway, NJ, 2006: 57-66.

DOI: 10.1109/rtss.2006.12

[10] L. Kong, J. Jiang. A worst-case execution time analysis approach based on independent paths for ARM programs. Wuhan University Journal of Natural Sciences, 2012, 17(5): 391-399.

DOI: 10.1007/s11859-012-0860-1

[11] S. Thesing. Safe and Precise WCET Determination by Abstract Interpretation of Pipeline Models. O'Connor, Australia: Pirrot Press, (2004).

[12] A. Colin, I. Puaut. A modular and retargetable framework for tree-based WCET analysis. In: Proceedings of the 13th Euromicro Conference on Real-Time Systems, IEEE Computer Society, Washington, DC, USA, 2001: 37 - 44.

DOI: 10.1109/emrts.2001.933995

[13] F. Stappert. Predicting pipelining and caching behavior of hard real-time programs. In: Proceedings of the 9th Euromicro Workshop on Real Time Systems, IEEE, Piscataway, NJ, 1997: 80-86.

DOI: 10.1109/emwrts.1997.613767

[14] S-S. Lim, Y. H. Bae, G. T. Jang, et al. An accurate worst case timing analysis technique for RISC processors. IEEE Trans on Software Engineering, 1995, 21(7): 593-604.

DOI: 10.1109/32.392980

[15] S. Malik, M. Martonosi, Y-T. S. Li. Static timing analysis of embedded software. In: Proceedings of the 34th Annual Conf on Design Automation, ACM, New York, 1997: 147-152.

DOI: 10.1145/266021.266052

[16] R. Ernst, W. Ye. Embedded program timing analysis based on path clustering and architecture classification. In: Proceedings of the 1997 IEEE/ACM Int Conf on Computer-Aided Design, IEEE, Piscataway, NJ, 1997: 598-604.

DOI: 10.1109/iccad.1997.643600

[17] Y-T S. L. S. Malik. Performance Analysis of Embedded Software Using Implicit Path Enumeration. In: Proceedings of the 32nd annual ACM/IEEE Design Automation Conference, ACM, New York, NY, 1995: 456-461.

DOI: 10.1145/217474.217570

[18] B. Guillem, C. Antoine, M. P. Stefan. WCET analysis of probabilistic hard real-time systems. In: Proceedings of the 23rd IEEE Real-Time Systems Symposium, IEEE Computer Society, Washington, DC, USA, 2002: 279 - 288.

DOI: 10.1109/real.2002.1181582

[19] S. Stefan, S. Bernhard, M. P. Stefan, et al. Static analysis support for measurement-based wcet analysis. In: Proceedings of the 12th IEEE International Conference on Embeded and Real-Time Computing Systmes and Applications, IEEE, Piscataway, NJ, 2006: 12-21.

[20] B. Guillem, C. Antoine, M. P. Stefan. pWCET: a Tool for Probabilistic Worst-Case Execution Time Analysis of Real-Time Systems. Tech Rep: YCS-2003-353, (2003).

[21] Guillem Bernat Alan Burns. An approach to symbolic worst-case execution time analysis. In: Proceedings of the 25th IFAC Workshop on Real-Time Programming, (2000).

DOI: 10.1016/s1474-6670(17)39931-7

[22] H. S. Negi, A. Roychoudhury, T. Mitra. Simplifying WCET analysis by code transformations. In: Proceedings of the 4th International Workshop on Worst-Case Execution Time Analysis, Sicily, Italy, (2004).

[23] J. Fredriksson, T. Nolte, A. Ermedahl, and M. Nolin. Clustering Worst-Case Execution Times for Software Components. In: Proceedings of 7th International Workshop on Worst-Case Execution Time Analysis, IEEE Computer Society Washington, DC, USA, 2007: 1-7.

DOI: 10.1109/emwrts.1998.685079

[24] J. Fredriksson, T. Nolte, M. Nolin, et al. Contract-based reusable worst-case execution time estimate. In: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, Washington, DC, USA, 2007: 39-46.

DOI: 10.1109/rtcsa.2007.32

[25] A. Ermedahl, J. Fredriksson, J. Gustafsson, et al. Deriving the worst-case execution time input values. In: Proceedings of the 21st Euromicro Conference on Real-Time Systems, IEEE Computer Society, Washington, DC, USA, 2009: 45-54.

DOI: 10.1109/ecrts.2009.32

[26] I. Wenzel, B. Rieder, R. Kirner, et al. Automatic timing model generation by CFG Partitioning and model checking. In: Proceedings of Conference on the Design, Automation, and Test in Europe, IEEE, Piscataway, NJ, 2005: 606-611.

DOI: 10.1109/date.2005.76

[27] I. Wenzel, R. Kirner, B. Rieder, P. Puschner. Measurement-based worst-case execution time analysis. In: Proceedings of the 3rd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, IEEE, Piscataway, NJ, 2005: 7-10.

DOI: 10.1109/seus.2005.12

[28] M. Zolda, S. Bunte, and R. Kirner. Towards adaptable control flow segmentation for measurement-based execution time analysis. In: Proceedings of the International Conference Real-Time and Network Systems, Paris, France, 2009: 77-85.

DOI: 10.1109/rtcsa.2011.73

[29] D. Jean-Francois and P. Isabelle. Safe measurement-based WCET estimation. In: Proceedings of 5th International Workshop on Worst-Case Execution Time Analysis, Balearic, Spain, (2005).

[30] M. P. Stefan. Worst-Case Execution Time Estimation for Advanced Processor Architectures: [dissertation]. Munchen: Munchen University. (2005).

[31] S. M. Petters, P. Zadarnowski, and G. Heiser. Measurments or static analysis or both?. In: Proceedings of 7th Workshop on Worst-Case Execution Time Analysis, Pisa, Italy, 2007: 54-58.

[32] F. Balarin, M. Chiodo, P. Giusto, et al. Hardware-software co-design of embedded systems: The POLIS Approach. Norwell, MA.: Kluwer Academic Publishers, (1997).

[33] W. Ye, R. Ernst. Fast timing analysis for hardware/software co-synthesis. In: Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, IEEE, Piscataway, NJ, 1993: 452-457.

DOI: 10.1109/iccd.1993.393335

[34] W. Hardt, R. Camposano. Trade-offs in HW/SW codesign. In: Proceedings of the 2nd Workshop on Hardware/Software Codesign, IEEE, Piscataway, NJ, 1993: 152-164.

DOI: 10.1049/ic:19950170

[35] F. Wolf, R. Ernst. Intervals in software execution cost analysis. In: Proceedings of the 13th Symposium on System Synthesis, IEEE, Piscataway, NJ, 2000: 130-135.

DOI: 10.1109/isss.2000.874039

[36] X. Li, Y. Liang, T. Mitra, et al. Chronos: a timing analyzer for embedded software. Science of Computer Programming, 2007, 69 (1-3): 56-67.

DOI: 10.1016/j.scico.2007.01.014

[37] X. Li, Y. Liang, T. Mitra, et al. Modeling control speculation for timing analysis. Real-Time Systems, 2005, 29 (1): 27 - 58.

DOI: 10.1023/b:time.0000048933.15922.f9

[38] X. Li, Y. Liang, A. Roychoudhury, et al. Modeling out-of-order processors for WCET analysis. Real-Time Systems, 2006, 34 (3): 195 - 227.

DOI: 10.1007/s11241-006-9205-5

[39] J. Gustafsson, B. Lisper, C. Sandberg, et al. A tool for automatic flow analysis of c-programs for WCET calculation. In: Proceedings of the 8th International Workshop on Object-Oriented Real-Time Dependable Systems, IEEE, Piscataway, NJ, 2003: 106-112.

DOI: 10.1109/words.2003.1218072

[40] F. Mueller. Timing analysis for instruction caches. The International Journal of Time-Critical Computing Systems, 2000, 18(2/3): 217–247.

[41] A. Colin, I. Puaut. Worst case execution time analysis for a processor with branch prediction. Real-Time Systems - Special issue on worst-case execution-time analysis, 2000, 18 (2/3): 249-274.

DOI: 10.1109/emrts.2001.934029

[42] A. Colin, I. Puaut. A modular & retargetable framework for tree-based WCET Analysis. In: Proceedings of the 13th Euromicro Conference on Real-Time Systems, IEEE Computer Society, Washington, D C, 2001: 37-44.

DOI: 10.1109/emrts.2001.933995

[43] M. Berkelaar. Lp Solve: A Mixed Integer Linear Program Solver. Tech Rep: Eindhoven University of Technology, (1999).

[44] H. Theiling, C. Ferdinand, R. Wilhelm. Fast and precise wcet prediction by separated cache and path analyses. Real-Time Systems, 2000, 18 (2/3): 157–179.

DOI: 10.1023/a:1008141130870

[45] J. Souyris, E. le Pavec, G. Himbert, et al. Computing the WCET of an avionics program by abstract interpretation. In: Proceedings of the 5th Workshop on Worst-Case Execution Time Analysis, Balearic, Spain, (2005).

[46] M. Langenbach, S. Thesing, R. Heckmann. Pipeline modelling for timing analysis. In: Proceedings of the 9th International Symposium on Static Analysis, Springer-Verlag, Lodon, UK, 2002: 294–309.

DOI: 10.1007/3-540-45789-5_22