Beyond loop bounds: comparing annotation languages for worst-case execution time analysis

Raimund Kirner, Jens Knoop, Adrian Prantl, Markus Schordan, Albrecht Kadlec

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)
72 Downloads (Pure)

Abstract

Worst-case execution time (WCET) analysis is concerned with computing a precise-as-possible bound for the maximum time the execution of a program can take. This information is indispensable for developing safety-critical real-time systems, e. g., in the avionics and automotive fields. Starting with the initial works of Chen, Mok, Puschner, Shaw, and others in the mid and late 1980s, WCET analysis turned into a well-established and vibrant field of research and development in academia and industry. The increasing number and diversity of hardware and software platforms and the ongoing rapid technological advancement became drivers for the development of a wide array of distinct methods and tools for WCET analysis. The precision, generality, and efficiency of these methods and tools depend much on the expressiveness and usability of the annotation languages that are used to describe feasible and infeasible program paths. In this article we survey the annotation languages which we consider formative for the field. By investigating and comparing their individual strengths and limitations with respect to a set of pivotal criteria, we provide a coherent overview of the state of the art. Identifying open issues, we encourage further research. This way, our approach is orthogonal and complementary to a recent approach of Wilhelm et al. who provide a thorough survey of WCET analysis methods and tools that have been developed and used in academia and industry.

Original languageEnglish
Pages (from-to)411-437
Number of pages27
JournalSoftware and Systems Modeling
Volume10
Issue number3
DOIs
Publication statusPublished - Jul 2011

Keywords

  • Worst-case execution time (WCET) analysis
  • Annotation languages
  • Path-oriented , constraint-oriented, and hierarchy-oriented WCET annotation languages
  • WCET annotation language challenge
  • SOFTWARE

Fingerprint

Dive into the research topics of 'Beyond loop bounds: comparing annotation languages for worst-case execution time analysis'. Together they form a unique fingerprint.

Cite this