RVS 3.18 Launched
Solid Sands partners with Rapita Systems
Danlaw Acquires Maspatechnologies - Expanding Rapita Systems to Spain
Rapita co-authored paper wins ERTS22 Best paper award
Why mitigating interference alone isn’t enough to verify timing performance for multicore DO-178C projects
There are how many sources of interference in a multicore system?
Supporting modern development methodologies for verification of safety-critical software
Flexible licensing software fit for modern working
DO-178C Guidance: Introduction to RTCA DO-178 certification
MATLAB® Simulink® MCDC coverage and WCET analysis
Code coverage for Ada, C and C++
AMC 20-193
Aerospace Tech Week Europe 2023
Aeromart Montreal 2023
Certification Together International Conference
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 WCET estimates of your application and its critical sub-routines as evidence to support your certification argument.
What is WCET?
First, some terminology. A task is a piece of code that is to be run within a single thread of execution. A task issues a sequence of jobs to the processor which are queued and executed.
The time spent by the job actively using processor resources is its execution time. The execution time of each job instance from the same task is likely to differ.
Execution times are of interest to real-time systems designers usually in the context of worst-case execution times. High level system requirements will specify maximum response times for a task, known as a deadline.
Worst-case execution time is the maximum length of time a task takes to execute on a specific hardware platform. WCET is a metric commonly used in reliable real-time systems which have a non-negotiable deadline for execution. Real-time systems need to be able to receive inputs, process them and then return results quickly enough to affect the environment at that time.
Methods of calculating WCET
1. Measurement analysis
Measurement analysis involves measuring execution times of short code segments on real hardware or on simulator for some set of inputs. Measurements are taken by using a processor clock or external hardware units such as the oscilloscope of a logic analyzer. Using this technique, a developer can analyze the worst observed execution time - known as high-water mark time – and the likelihood of the occurrence of the worst-case scenario.
Measurement based analysis can’t provably identify WCET as, in general, only a subset of the executions are exercised, which may not contain the worst-case scenario.
For a variety of reasons, the use of measurement-based analysis tends to be the more practical approach, and consequently the approach used for many systems past and present. Because of the vast number of possible paths through the code, that could be taken, there is still the concern that you could miss a long execution time. Therefore, in practice, the optimism of a measurement-based approach is reduced by adding a "safety margin", for example, adding 20% to the longest observed execution time.
2. Static analysis
Static analysis WCET estimation was developed as an alternative to measurement-based estimation. The main advantage of static analysis is that it is not necessary to take measurements from a real target, minimizing cost and effort.
Static analysis estimation requires a precisely accurate model of the timing characteristics of the processor, which includes the behavior of pipelines, caches, memory, buses, and any other feature of the hardware under examination that may affect execution time of machine instructions. This is done without executing the code.
However, static analysis suffers from two key weaknesses:
- It is pessimistic as it identifies the pathological – worst theoretically possible - WCET.
- Complex architectures, such as multicore processors, cannot be accurately modelled.
3. Hybrid method
Rapita use a third approach – hybrid WCET estimation, using a combination of three techniques:
- Recognizing that the best possible model of a processor is the processor itself, hybrid approaches use online 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.
- Measurement and path analysis information is combined to compute worst-case execution times in a way that captures execution time variation on individual paths due to hardware effects.
Using these techniques, hybrid analysis aims to provide a value between the overly pessimistic WCET of static analysis and the optimistic values of pure measurement.
Execution times are determined from real measurements, addressing the first problem with static-only WCET: we can avoid relying on an MCP model that may contain errors, meaning it can be applied to more complex system models.
Another advantage of hybrid analysis is that we can obtain other accurate on-target timing metrics such as high and low water marks, execution frequencies, and execution time distributions.
WCET in multicore and complex systems
As mentioned previously, static analysis falls short when complex architectures, such as multicore processors, are being modelled. Model-based WCET analysis is designed to identify pathological WCET and therefore produces extremely pessimistic estimates. As the FAA identifies in the Assurance of Multicore Processors in Airborne Systems document, “Abstractions used for the WCET evaluation, for instance processor models, may not be correct or be so inaccurate that the computed WCETs are too pessimistic”. For this reason, it is intractable to estimate WCET in multicore system using static analysis.
When performing WCET analysis on multicore systems, the hybrid approach is the only effective method for generating useful timing metrics. That said, the conventional hybrid approach to single-core analysis does not answer multicore WCET estimation on its own, as it does not account for interference due to contention for shared resources and other hardware idiosyncrasies. Static WCET estimation techniques cannot account for all possible sources of interference; and even if they could, they would be hugely complex and computationally expensive to run.
For more information on performing WCET estimation on multicore systems, visit our Multicore Timing Solution page.
Rapita's approach to WCET
Rapita’s unique hybrid timing analysis tool is called RapiTime and is identified by The FAA as “an example of a mature tool" for dynamic timing analysis. By using a novel hybrid technique to produce WCET estimations, RapiTime eliminates the problems often encountered when using pure static or measurement-based approaches:
- As RapiTime measures software timing on your processor itself, the WCET it calculates is not affected by model errors
- RapiTime lets you specify infeasible paths in your source code and considers different call and loop contexts that may affect WCET
- RapiTime allows you to estimate WCET using transitions between instrumentation points, thereby analyzing execution paths more accurately for more realistic WCET estimates.
You can find out more about Rapita’s methodology for evaluating WCET for DO-178 standards in our whitepaper. Alternatively, this webinar explains how Rapita tackles WCET for multicore applications.
View WCET analysis webinar
