In real-time systems, timely task completion is of the essence. Each real-time task has to be completed within a specified time frame 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. In other words, it is essential that the worst-case execution time (WCET) of each task is known in advance.
However, computing the WCET 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, since the execution time of a single instruction may depend on the execution history. Conservative cache analysis methods usually result in a serious overestimate of the WCET. Overestimates of the WCET in turn result in an overscaled hardware design.
Switching off caches to simplify WCET prediction can lead to severe performance degradation (by as much as 97%, according to a study by EADS).
The increasing performance of microcontrollers enables more and more functionality to be implemented by a single embedded-control unit. The software is complex; the timing behaviour of the interacting components is rarely known. Typically, it is not practical or even possible to test the system with all potential inputs.
This is where AbsInt comes in. Over the recent years we have built up an unparalleled expertise in the area of WCET determination for real-time systems.
Our award-winning aiT WCET Analyzers statically analyze the cache and pipeline behavior of each software task based on the technique of abstract interpretation and formal cache and pipeline models. This enables correct and tight upper bounds to be computed for the worst-case execution time.
A graphical user interface supports the visualization of the worst-case program path and the interactive inspection of all pipeline and cache states at arbitrary program points.
Benefits to the user:
aiT-computed tight bounds reflect the actual performance of the system. Ensuring deadline adherence is no longer done at the expense of hardware resources.
aiT-computed bounds are valid for all inputs and each execution of a task under any circumstances. Extensive manual timing testing is now a thing of the past.
aiT directly analyzes binary executables. It is widely independent of the compiler and source code language used. This means no modification of the user’s tool chain or the program’s operational behavior and performance is required.
aiT was designed in the IST project DAEDALUS according to the requirements of Airbus France for validating the timing behavior of critical avionics software.
aiT is probably the best of its kind in the world.
DAEDALUS Project Final Review
In 2003, only half a year after its launch, aiT was awarded a European Information Society Technology Prize, the most distinguished award for “groundbreaking products that represent the best of European innovation in information society technologies”.
In 2006, aiT participated successfully in the first WCET Tool Challenge, organized by University of Mälardalen and sponsored by the ARTIST2 Network of Excellence on Embedded Systems Design.
The aim of the WCET Tool Challenge was to inspect and to compare different approaches in analyzing the worst-case execution time. All available tools and prototypes able to determine safe upper bounds for the WCET of tasks have participated.
aiT was the only tool that started for 3 different real processor architectures. It was the only tool that was able to produce results for all test programs. The results of analyses by aiT were in most cases exceptionally precise. Finding in the challenge was, amongst others, that aiT allows for user-friendly WCET analysis, advises against unrealistic annotations, and provides tight WCET values.
aiT was able to handle every kind of benchmark and every test program that was tested in the [WCET Tool] Challenge. aiT is able to support WCET analysis even for complex processors. […] aiT demonstrates its leading position through all its features, which contribute to its position as an industry-strength tool, satisfying the requirements from industry as posed by EADS Airbus and proven by the accomplishment in various projects.
WCET Tool Challenge 2006 Final Report
Most recently, aiT has been integrated into SCADE, the market-leading mission and safety-critical embedded software development environment from Esterel Technologies. SCADE is the first embedded-software development environment worldwide to feature worst-case execution time (WCET) analysis at the model level.