Importance of Worst-Case Execution Time
The importance of worst-case execution time (WCET) can be illustrated using a simple example relating to a system to control air bags in an automobile. If the airbag does not deploy within certain timing deadlines, its effectiveness in preventing injury to the driver may be negatively affected. Similar use cases exist in other safety-critical industries including aerospace, rail, nuclear etc.
For this reason, DO-178C guidance for aerospace and the ISO 26262 standard for automotive both require that evidence on the WCET of applications and their critical sub-routines are provided to support certification.
What are WCET tools?
WCET tools are a subset of software testing tools that analyze worst-case execution time (WCET) – and often other timing metrics – of an application. WCET tools are widely employed in the safety-critical industry to provide evidence to certification authorities that timing deadlines will be met.
WCET tools are based on either measurement, static analysis or a hybrid combination of the two.
Measurement-based WCET tools
These tools measure execution times of short sections of code ‘on-target’ (on the real hardware) . Measurements are derived from external hardware units such as oscilloscopes, or often via the processor clock.
Measurement-based analysis can yield the ‘worst observed’ execution time – often called ‘high-water mark time’ and provide evidence of the likelihood of this occurring. In practice, the inherent optimism of a measurement-based approach can be reduced by adding a safety margin, for example adding 20% to the longest observed execution time and treating this as a WCET estimation.
An example of a measurement-based WCET tool is Gliwa's Timing Suite T1.
Static analysis WCET tools
Static analysis WCET tools were developed as an alternative to measurement-based WCET tools. These tools rely on a precisely accurate model of the processor including pipelines, memory etc. and any other hardware feature that could affect the timing behavior of the software being analyzed.
A major advantage of static analysis WCET tools is that they do not need to run on-target, minimizing the cost and effort needed to use them.
The major disadvantage of these tools is that they identify the pathological – worst theoretically possible – WCET, which tends to be highly pessimistic. Another disadvantage is that highly complex architectures (such as multicore processors) cannot be accurately modeled, making the technique unsuitable for these architectures.
Examples of static analysis WCET tools are:
- Chronos, an open source static WCET analysis tool from the National University of Singapore.
- OTAWA, a framework of C++ classes dedicated to static analyses of programs in machine code and to the computation of WCET, from the Traces Research group on Architectures and Compilers for Embedded Systems at IRIT (Institut de Recherche en Informatique de Toulouse)
- Bound-T Execution Time Analyzer from Tidorum.
Hybrid WCET tools
Hybrid WCET tools aim to combine the best features of measurement-based and static analysis WCET tools whilst avoiding their pitfalls.
Hybrid WCET tools differ in that they:
- Use on-target testing to measure the execution time of short sub-paths between decision points in the code.
- Support offline analysis with information obtained during testing, such as numbers of loop iterations and execution frequencies (modal operation) to build up a model of the overall code structure and determine which combinations of sub-paths form complete and feasible paths through the code.
- Combine measurements and information from path analysis to compute worst-case execution times in a way that captures execution time variation on individual paths due to hardware effects.
Hybrid tools give a balanced approach to measuring WCET which is neither too optimistic nor pessimistic
Execution times are determined from real measurements, addressing the first problem with static-only WCET tools: no reliance on processor models.
Another advantage of hybrid WCET tools they can be used to obtain other accurate on-target timing metrics such as high and low water marks, execution frequencies, and execution time distributions
Examples of hybrid WCET tools are: