Basic notions of timing analysis

The PREDATOR project is concerned with embedded systems that are characterised by efficiency requirements such as average-case performance, resource utilisation, and power consumption on the one hand, and worst-case constraints on the other.

Such systems occur in application domains such as automotive and avionics where the increase in the number of functions can no longer be coped with by adding one Electronic Control Unit or processor board per function. Instead, the trend in both application domains goes towards the integration of many functions on powerful hardware platforms. Multi-core and multi-processor system-on-chip (MPSoC) architectures provide the high performance requirements with high energy efficiency.

Offline guarantees for the satisfaction of critical constraints have to be derived by appropriate methods. The difficulty of deriving guarantees heavily depends on the predictability properties of the systems, in particular of the deployed processor architecture, the software design discipline, the operating system including the scheduling strategy, the communication mechanism, and the used middleware.

At the same time, system efficiency is typically measured in terms of average-case behaviour and under totally different criteria such as performance, utilisation of resources and power consumption.

Unfortunately, the gap between average-case and worst-case behaviour in computer system design is rapidly growing. The technical reasons for the limited timing predictability are well known, for example the variation and non-determinism of the system environment and the interference caused by the use of shared resources.

The figure above illustrates the basic notions of timing analysis. A program under analysis exhibits a certain variability of execution times influenced by input data and interference from the environment. The best-case execution time (BCET) and the worst-case execution time (WCET) are in general very difficult or even impossible to determine. Instead, reliable lower and upper bounds have to be determined by sound methods.