Abstract
A number of methods have been presented to calculate the worst case execution time (WCET) of real-time programs. However, to properly handle semantic dependencies, which in most cases is needed to reduce overestimation, all these methods require extra semantic information to be given by the programmer (manual annotations for paths, loops and recursion depth). To manually derive these annotations is often difficult and the process is error-prone. In this paper we present a new method to automatically derive safe and tight annotations for paths and loops. We illustrate our method by giving some examples and by presenting a prototype tool, implementing the method for a subset of C.
This work is performed within the ART-project within the Advanced Software Technology (ASTEC) competence centre, and is supported by the Swedish board for technical development (NUTEK), IAR Systems AB, Mecel AB and Uppsala University.
Chapter PDF
References
P. Altenbernd. On the false path problem in hard real-time programs. In Proceedings of the Eight Euromicro Workshop on Real-Time Systems, pages 102–107, June 1996.
J. Armstrong, R. Virding, C. Wikström, and M. Williams. jgn@mdh. se Concurrent programming in Erlang. Prentice Hall, 2 edition, 1996. ISBN 0-13-508301-X.
F. Bourdoncle. Abstract debugging of high-order imperative languages. In Proceedings of SIGPLAN'93 Conference on Programming Language design and Implementation, pages 46–55, 1993.
R. Chapman, A. Burns, and A. Wellings. Integrated program proof and worst-case timing analysis of SPARK Ada. In ACM Sigplan Workshop on Language, Compiler and Tool Support for Real-Time Systems, June 1994.
P. Cousot and R. Cousot. Abstract interpretation: A unified model for static analysis of programs by construction or approximation of fixpoints. In 4th ACM Symp. on Principles of Programming Languages, pages 238–252, 1977.
P. Cousot and R. Cousot. Comparing the Galois connection and widening/narrowing approaches to abstract interpretation. In Programming Language Implementation and Logic Programming, Proceedings of the Fourth International Symposium, PLILP'92, volume Lecture Notes in Computer Science 631, pages 269–295, Aug 1992.
A. Ermedahl and J. Gustavsson. Real-time industry inquiry of execution time analysis tools. Technical report, Department of Computer Systems, Uppsala University, Sweden, 1997. To be published.
M. Harmon, T. Baker, and D. Whalley. A retargetable tecnique for predicting execution time of code segments. The Journal of Real-Time Systems, 7, 1994.
Y.-T. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. In ACM Workshop on Lang., Comp. and Tools for RTS, May 1995.
Y.-T. Li, S. Malik, and A. Wolfe. Cache modeling for real-time software: Beyond direct mapped instruction caches. In 17th IEEE Real-Time Systems Symposium, RTSS'96, pages 254–263, 1996.
S. Lim, Y. Bae, G. Jang, B.-D. Rhee, S. Min, C. Park, H. Shin, K.Park, S.-M. Moon, and C. Kim. An accurate worst case timing analysis for rise processors. IEEE Trans. on Software Engineering, 21(7):593–604, July 1995.
H. R. Nielson and F. Nielson. Semantics with Applications. John Wiley & Sons, 1992.
G. Ottosson and M. Sjödin. Worst-case execution time analysis for modern hardware architectures. In Proc. SIGPLAN 1997 Workshop on Languages, Compilers and Tools for Real-Time Systems, June 1997. To appear.
C. Park. Predicting program execution times by analyzing static and dynamic program paths. The Journal of Real-Time System, 5:31–62, 1993.
C. Park and A. Shaw. Experiments with a program timing tool based on a source-level timing schema. Proceeding of 11th IEEE Real-Time Systems Symposium, pages 72–81, Dee 1990.
P. Puschner and C. Koza. Calculating the maximum execution time of real-time programs. The Journal of Real-Time Systems, 1(2):159–176, Sep 1989.
P. Puschner and A. Schedl. Computing maximum task execution times with linear programming techniques. Technical report, Report, Techn. Univ., Inst. für Technische Informatik, Vienna, April 1995.
E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
A. Vrchoticky. The Basis for Static Execution Time Prediction. PhD thesis, Institut für Technische Informatik, Technische Universität Wien, Austria, April 1994. *** DIRECT SUPPORT *** A0008C42 00045
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ermedahl, A., Gustafsson, J. (1997). Deriving annotations for tight calculation of execution time. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002886
Download citation
DOI: https://doi.org/10.1007/BFb0002886
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive