Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Code Analysis for Temporal Predictability

  • Published:
Real-Time Systems Aims and scope Submit manuscript

Abstract

The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Allen, J., Kennedy, K., Porterfield, C., and Warren, J. 1983. Conversion of Control Dependence to Data Dependence. In Proc. 10th ACM Symposium on Principles of Programming Languages, pp. 177–189.

  • Cousot, P., and Cousot, R. 1977. Abstract interpretation: A unified model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM Symposium on Principles of Programming Languages, pp. 238–252.

  • Consel, C., Lawall, J. L., and Le Meur, A.-F. 2004. A tour of Tempo: A program specializer for the C language. Science of Computer Programming, 52(1–3):341–370.

    MathSciNet  Google Scholar 

  • Fauster, J., Kirner, R., and Puschner, P. 2003. Intelligent Editor for Writing WCET-Oriented Programs. In Proc. 3rd International Conference on Embedded Software (EMSOFT'03), pp. 190–205.

  • Gustafsson, J. 2000. Analyzing Execution-Time of Object-Ori-ented Programs Using Abstract Interpretation. PhD thesis, Department of Computer Systems, Information Technology, Uppsala University.

  • Jones, N. D., Gomard, C. K., and Sestoft, P. 1993. Partial Evaluation and Automatic Program Generation. Hertfordshire, UK: Prentice Hall.

  • Mahlke, S., Hank, R., McCormick, J., August, D., and Hwu, W. 1995. A Comparison of Full and Partial Predicated Execution Support for ILP Processors. In Proc. 22nd International Symposium on Computer Architecture, pp. 138–150.

  • Nielson, H. R. and Nielson, F. 1992. Semantics with Applications. John Wiley & Sons.

  • Nielson, F., Nielson, H. R., and Hankin, C. 1999. Principles of Program Analysis, Springer. ISBN: 3-540-65410-0.

  • Puschner, P. and Burns, A. 2002. Writing temporally predictable code. In Proc. 7th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, pp. 85–91.

  • Puschner, P. 2002. Transforming execution-time boundable code into temporally predictable code. In B. Kleinjohann, K.H. (Kane) Kim, L. Kleinjohann, and A. Rettberg, editors, Design and Analysis of Distributed Embedded Systems, Kluwer Academic Publishers, pp. 163–172.

  • Puschner, P. 2003. Algorithms for dependable hard real-time systems. In Proc. 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, pp. 26–31.

  • Sestoft, P. and Zamulin, A. V. 1988. Annotated bibliography on partial evaluation and mixed computation. New Generation Computing, pp. 309–354.

  • Tip, F. 1995. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121– 189.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Electronics, Mälardalen University, Västerås, Sweden

    Jan Gustafsson & Björn Lisper

  2. Institut für Technische Informatik, Technische Universität Wien, Austria

    Raimund Kirner & Peter Puschner

Authors
  1. Jan Gustafsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Björn Lisper
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raimund Kirner
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Peter Puschner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jan Gustafsson.

Additional information

This work has been supported by the ARTIST2 Network of Excellence on Embedded Systems Design of IST FP6.

Raimund Kirner is an assistant professor in computer science in the Real-Time Systems Group of the Vienna University of Technology. He received a Master's degree in computer science and a doctoral degree in technical sciences both from the Vienna University of Technology in Austria in the years 2000 and 2003, respectively. His research interests include worst-case execution time analysis, compiler support for worst-case execution time analysis, and the verification of real-time systems.

Peter Puschner is a professor in computer science at Vienna University of Technology. His main research focus is on worst-case execution time (WCET) analysis for real-time programs. Puschner has been working on WCET analysis for more than ten years and has strongly influenced the state of the art in this field. He has published numerous papers on WCET analysis and software/hardware architectures supporting temporal predictability. He was a guest editor for the special issue on WCET analysis of the Kluwer International Journal on Real-Time Systems and chaired the program committee of the IEEE International Symposium on Object-oriented Real-time distributed Computing in 2003 and the Euromicro Real-Time Systems Conference in 2004. In 2000/2001 Peter Puschner spent one year as a Marie-Curie research fellow at the University of York, England.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gustafsson, J., Lisper, B., Kirner, R. et al. Code Analysis for Temporal Predictability. Real-Time Syst 32, 253–277 (2006). https://doi.org/10.1007/s11241-005-4683-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-005-4683-4

Keywords

Search

Navigation