Prediction of the Worst Case Execution Time

In real-time systems the tasks are subject to deadlines. It is essential that the worst-case execution time (WCET) of each task is known in order to ensure that the system works correctly. The consequences of a missed deadline range from simply annoying to disastrous - just imagine a flight control software that does not react in time. It is the duty of the developer to guarantee that the tasks will always meet the deadlines specified.

Worst Case Execution Time PathComputing the worst-case execution time is a challenge:

  • Simply measuring the execution time of a task for a given input is typically not safe. It is mostly impossible to prove that the conditions leading to maximum execution time are taken into account.

  • Modern processor components like caches and pipelines complicate the task of determining the WCET considerably. For instance, the often safe yet almost never valid assumption of a cache hit never occurring results in a serious overestimate of the WCET. Overestimates of the WCET in turn may result in a failure of the overall schedulability analysis or an overscaled hardware design.

The WCET prediction technology implemented within the DAEDALUS project is based on statically analyzing a task's intrinsic cache and pipeline behavior. This allows us to compute correct and tight upper bounds for the worst-case execution time of the tasks in an application.

About Absint

AbsInt Angewandte Informatik GmbH provides advanced tools and services in the areas of compiler optimization, static program analysis, and worst-case execution time prediction.