Why Static analysis doesn't work for Multicore WCET estimation

The estimation of sensible worst case execution time (WCET) for applications running on multicore processors is far more challenging than for those running on single core processors. Multicore processors are more complex in design, and less predictable in behavior than single core systems.

Not only are multicore processors more complex by-design, they also suffer from interference due to contention for shared resources and other hardware idiosyncrasies. Static WCET estimation techniques generally cannot account for all possible sources of interference; even if they could they would be hugely complex and computationally expensive to run.

What is static analysis?

Static analysis was developed as an alternative method of worst-case execution time estimation to measurement based estimation. The key advantage of static analysis is that no measurements from a real target are required, minimizing the cost of testing.

Static analysis techniques rely on having a precisely accurate model of the timing characteristics of the processor, including the behavior of pipelines, caches, memory, buses, and any other hardware features that affect the execution time of machine instructions.

Static analysis techniques analyze the program, and compute the worst-case path and worst-case execution time by reference to the model of the processor's timing behavior. This is done without executing the code.

Static analysis for multicore is too pessimistic

Static analysis techniques can identify an upper bound on the worst-case execution time by finding the worst-case path (with interference factored in). In the context of safety-critical systems, this pessimistic approach may at first seem the safest way to approach MCP WCET estimation for such unpredictable systems.

However, the pathological WCET that static analysis techniques can theoretically produce is so pessimistic it is not fit for purpose. 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”.

The excessive pessimism of static WCET estimation stems from two fundamental problems:

  1. It is intractable to simulate actual MCP behavior via system modelling. Some semiconductor manufacturers do not even understand some of the behaviors observed in the MCPs they produce, so creating a 100% accurate model that always behaves exactly like the real thing is extremely difficult.
  2. As MCPs feature so many different interoperable components running in parallel, it is theoretically possible for every-possible-interference-channel to affect the application running to the worst-possible-extent at one particular time. This would generate a massive WCET for that worst case scenario, despite the likelihood of this scenario being statistically insignificant in this context.

To understand the implications of these two problems when estimating MCP WCET, static analysis WCET for some MCPs have been observed to be more than 200 times higher than the equivalent dynamic WCET figure.

The implication of excessively pessimistic WCET estimation is that more of the MCP’s resources/computational power need to be set aside for handling vanishingly unlikely worst case scenarios which theoretically could happen, but careful scheduling could prevent.

Hybrid timing analysis is better

Hybrid approaches to worst-case execution time estimation aim to combine the best features of measurement and static analysis whilst avoiding their pitfalls.

Hybrid approaches use a combination of three techniques

  1. 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.
  2. 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.
  3. 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.

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.

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.

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.

With single-core hybrid analysis, as described so far, we can collect snippets of worst-case execution times from different parts of the application, and then stitch together the worst-case snippets to form a complete worst-case path that represents the WCET. With multicore, this isn’t possible as

  1. It would take a very long time to find all the ‘worst’ snippets, as there are so many multicore hardware factors which can change timing behavior.
  2. We would not be able to account for the effects of interference on timing behavior.

What the hybrid approach is lacking is an effective way to factor in the potential effects of interference on timing behavior. To fulfil this requirement, Rapita have created a library of 'RapiDaemons', small applications that generate constant, predictable, and reproducible load for specific shared resources, to generate real interference on-target.

RapiDaemons are configurable meaning we can analyze a system for observable levels of interference and then tweak RapiDaemons to deliver slightly higher levels of contention to simulate a realistic worst-case scenario.

When this data is combined with deep knowledge of the MCP system and used in conjunction with interference mitigation strategies it is possible to estimate a WCET figure that is both safe and not overly pessimistic.

A hybrid solution

Rapita’s Multicore Timing solution is the only commercial solution for hybrid WCET estimation. A key part of this solution is the supporting toolsuite which includes RapiTime, a dynamic analysis tool identified by The FAA as “an example of a mature tool in this aspect [dynamic timing analysis]”.

N Bowles

Receive our blog by email