Why Static analysis doesn't work for Multicore WCET estimation

Christos Evripidou & Daniel Wright

2019-10-07

The true worst-case execution time (WCET) of an application executing on modern hardware cannot be feasibly calculated. This is typically because of performance optimization features present in modern hardware. In domains featuring critical applications, the term WCET is synonymous with a WCET estimate, which must be tight (not too pessimistic), but never optimistic.

The estimation of a tight 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 inherently more complex, they also suffer from interference due to contention for shared resources and other hardware idiosyncrasies. Constructing an accurate enough model of the hardware is not feasible due to the level of complexity and strict restrictions on disclosing closely guarded IP block design features. Static WCET estimation techniques generally cannot account for all possible sources of interference, and even if they could, they would be very complex and extremely computationally expensive to run.

What is static analysis?

Static analysis was developed as a method of worst-case execution time estimation. The key advantage of static analysis over measurement-based methods 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 on the target platform.

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 cross-core 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 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:

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.
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 extremely low in this context.

To understand the implications of these two problems when estimating MCP WCET, WCETs determined by static analysis 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.

A measurement-based approach is better

A measurement-based approach to WCET estimation for multicore systems can yield practical values.

Measurement-based timing analysis tools such as RapiTime can help support some of the challenges of multicore timing analysis. One of the major challenges is in handling and analysis of the huge amount of data that must be collected across a comprehensive multicore timing analysis test campaign. RapiTime solves this challenge by providing various options for how data is summarized and displayed, including allowing filtering of results on specific tests and performance metrics, and allowing baselines to be set against which to compare results.

A common approach to determining WCET by a measurement-based approach is to design and run timing tests that use interference generator applications to generate interference on the multicore system. Rapita have a library of such applications, called RapiDaemons, which generate configurable, constant, predictable, and reproducible loads on specific shared multicore resources. In a measurement-based approach, the execution time of software running on one core is tested while interference generators such as RapiDaemons are executed on none, one or more other cores, so the impact of multicore interference on the software execution time can be understood (e.g. Figure 1).

RapiDaemons generate multicore interference — Figure 1. RapiDaemons can be used to generate interference in multicore systems

To apply a measurement-based approach to multicore WCET estimation, detailed understanding of the multicore platform and the shared resources and interference channels on it is needed. Expert engineers are needed to understand the system, analyze performance requirements, develop test plans, and generate test scenarios that stress the system’s execution time by selecting appropriate interference generators to use and hardware event monitors to observe during tests. At Rapita, we apply a V-model based approach as shown in Figure 2.

Rapita V model approach to multicore timing analysis — Figure 2. Rapita V-model based approach to multicore timing analysis

The use of a measurement-based approach that utilizes interference generators such as RapiDaemons avoids the pitfalls of static analysis; as execution times are determined from real measurements, there are no errors due to incorrect models (and there are currently no models available that can accurately model multicore systems and their interference), and as tests are specifically designed to identify the high-water mark paths through the code, the results are not overly pessimistic.

A proven approach for multicore WCET estimation

Rapita’s MACH¹⁷⁸ solution and Multicore Timing Solution are the only commercial solutions for WCET estimation for multicore systems. A key part of these solutions is the supporting tool suite which includes RapiTime, a dynamic analysis tool identified by The FAA as “an example of a mature tool in this aspect [dynamic timing analysis]”.