Worst-Case Execution Time Analysis for Mixed-Criticality Tasks on Multicore Automotive Controllers: A Review of Methods and Open Problems

1. Introduction

A hard real-time task is correct only if it finishes on time, and a schedulability test can say whether it will only if it is given an upper bound on the time the task needs. Since the rate-monotonic and earliest-deadline analyses of Liu and Layland (1973), that bound has been treated as an input, a single number per task called the worst-case execution time (WCET). Producing the number is a research field of its own. The survey by Wilhelm et al. (2008) remains the standard account of how it is done on a single processor core and of why the problem is hard even there.

Two developments have complicated the picture for vehicle electronics. The first is consolidation. Functions that once had a control unit each are being gathered onto fewer and more capable devices, so a single controller may host software rated at the highest automotive safety integrity level next to software with no safety rating at all. The second is the move to multicore microcontrollers and, in domain and zone controllers, to application-class systems-on-chip. On these devices the time a task takes depends on what the other cores are doing, because cores compete for caches, buses, flash and memory controllers.

The research response has come from two directions. Mixed-criticality scheduling theory, which began with Vestal (2007), asks how tasks of different importance can share a processor when their execution time bounds are known with different degrees of confidence. Multicore timing verification asks how a bound can be obtained at all in the presence of interference from other cores (Maiza et al., 2019). This review reads the two together with the automotive setting in mind, and asks what an engineer responsible for a multicore controller can take from them.

2. Scope and Approach

This is a narrative review of the published literature. It draws on the established surveys of timing analysis, mixed-criticality scheduling and multicore verification, on the primary papers those surveys treat as foundational, and on the functional safety standard for road vehicles. Papers were chosen for their influence on the field and their relevance to automotive controllers, not through a formal search protocol, and the review makes no claim to completeness. Avionics sources are included where the automotive literature is thin, since certification authorities in that sector addressed multicore interference early and in explicit terms.

3. Execution Time Bounds on a Single Core

Three families of method estimate the WCET of a task running alone. Figure 1 places them beside the interference control techniques discussed later, and Table 1 summarises how each fares once cores share hardware.

Figure 1: Families of methods used to bound task execution time on a multicore controller

3.1. Static analysis

Static analysis derives a bound from the executable without running it. The control flow graph is reconstructed from the binary, a value analysis determines loop bounds and the addresses of memory accesses, and a micro-architectural analysis bounds the time of each basic block given the possible states of the pipeline and caches. The mathematical basis is abstract interpretation (Cousot and Cousot, 1977), applied to caches in the must and may analyses of Ferdinand and Wilhelm (1999). The longest path is then found by implicit path enumeration, which encodes the flow constraints as an integer linear program (Li and Malik, 1995). The result is a safe bound, provided the hardware model is right.

That proviso carries much of the weight. A sound model needs detailed knowledge of the processor, and the analysis must cope with timing anomalies, situations in which a locally faster outcome such as a cache hit leads to a longer overall execution (Lundqvist and Stenstrom, 1999). Where anomalies are possible the analysis cannot simply follow the locally worst case and has to track many hardware states, which costs both time and precision.

3.2. Measurement-based and hybrid analysis

Industrial practice leans heavily on measurement: the task is run under test, the longest observed time is recorded as a high-water mark, and an engineering margin is added. The approach needs no hardware model and works on any processor. Its weakness is that the worst path and the worst hardware state may never be exercised, so the result is an estimate and not a bound, and the size of the margin is a matter of judgement. Hybrid methods measure short program segments on the target and combine those timings using the program structure obtained statically, which removes the need to drive the longest path end to end but leaves the dependence on having seen the worst hardware state (Wilhelm et al., 2008).

3.3. Probabilistic analysis

Probabilistic timing analysis replaces the single bound with a distribution, the probabilistic WCET, which gives for each execution time budget the probability that it is exceeded. The idea goes back at least to Bernat et al. (2002). Its measurement-based form fits an extreme value distribution to observed times and extrapolates to very small exceedance probabilities. The fit is valid only if the observations satisfy the statistical assumptions of the theory, and much of the research has concerned how to make hardware behave that way, for instance through randomised cache placement, and how to check representativeness. Two comprehensive surveys set out the methods and their unresolved questions (Cazorla et al., 2019; Davis and Cucu-Grosjean, 2019).

4. The Mixed-Criticality Model and Its Reception

Vestal observed that the more rigorously a WCET is established, the larger it tends to be. A figure acceptable for a low-criticality function may be a measured maximum, while a certification authority may insist on a far more conservative bound for a flight or braking function. His model therefore gives each task a set of execution time budgets, one per criticality level, and asks that each task be schedulable when every task of equal or higher criticality uses the budget defined at that level (Vestal, 2007). The system runs in a low-criticality mode so long as budgets hold. If a high-criticality task overruns its optimistic budget, the system switches mode and protects the critical tasks, in the original formulations by abandoning the less critical ones.

A large literature followed. Response time analysis was extended to the model, with the adaptive mixed-criticality scheme among the best known results (Baruah et al., 2011), and multiprocessor variants were built on the earlier theory of global and partitioned scheduling (Davis and Burns, 2011). The survey by Burns and Davis (2017) catalogues this work and is the natural entry point to it.

The model has also been criticised from the standpoint of safety engineering. Ernst and Di Natale (2016) argue that it conflates criticality, a property assigned through hazard analysis, with the confidence placed in a timing estimate, and that standards require sufficient independence between functions of different integrity, which a scheme that sheds low-criticality work on demand does not obviously provide. Esper et al. (2015) reach a similar view after comparing the model's assumptions with industrial standards. The automotive standard is a case in point. ISO 26262 lets elements with different safety integrity levels coexist only if freedom from interference is shown, and it lists timing and execution among the interference classes (ISO, 2018). A task without a safety rating may be important to the driver all the same, and abandoning it at a mode change is a design decision that needs its own justification.

5. Interference on Shared Hardware

On a multicore device the execution time of a task is no longer a property of the task and its core alone. Cores may share a last-level cache, so that one task evicts another's data. They share the interconnect and the memory controller, so that accesses queue. On microcontrollers they commonly share program flash and peripheral buses. Reports from avionics, where the question was examined early, describe slowdowns of several-fold for memory-intensive code when other cores are loaded (Nowotsch and Paulitsch, 2012). The certification position paper CAST-32A asks applicants to identify every interference channel and to show that each is mitigated or bounded (CAST, 2016), and the reasoning carries over directly to road vehicles.

A fully integrated static analysis would model all cores at once. The state space makes this impractical for realistic software, and the survey literature treats it as a research direction more than a usable technique (Maiza et al., 2019). The alternatives fall into two groups: control the interference so that single-core analysis remains valid, or account for it explicitly in the schedulability analysis.

5.1. Controlling interference

Shared caches can be partitioned. Page colouring in the operating system assigns each core, or each task, a disjoint set of cache sets, and the frameworks of Mancuso et al. (2013) and Kim et al. (2013) show how this can be done on commodity platforms without hardware changes. Memory bandwidth can be budgeted: MemGuard uses performance counters to limit the number of memory accesses a core may issue per regulation period and suspends the core when its budget is spent (Yun et al., 2013). The predictable execution model goes further by restructuring tasks into a memory phase, in which code and data are loaded into private cache, and an execution phase that touches no shared memory; a system-wide schedule then lets only one core be in its memory phase at a time (Pellizzoni et al., 2011). Each technique trades average performance for a contention bound that can be stated in advance.

5.2. Accounting for interference

Where isolation is incomplete, the residual interference must enter the analysis. The simplest method pads each WCET for the worst contention on every access, which is safe and often so pessimistic that the second core brings little benefit. The multicore response time analysis framework of Altmeyer et al. (2015) avoids this by keeping resource demand separate from execution time: each task is described by how many bus, cache and memory accesses it can make, each resource by how its arbiter serves competing requests, and the response time calculation combines the two over the interval of interest. The approach depends on being able to bound those access counts, which brings the problem back to static analysis or to carefully instrumented measurement.

6. The Automotive Setting

Classic automotive microcontrollers differ from the commodity platforms on which most interference research is done. They have short pipelines, small or no shared caches, execution from flash and local scratchpad memory, and often lockstep core pairs for fault detection. Static analysis is tractable on such cores, and interference arises mainly through shared flash, buses and peripherals. The operating system layer defined by AUTOSAR already provides partitioned fixed-priority scheduling, memory protection and timing protection in the form of execution budgets and inter-arrival monitoring, which is close to the monitoring a mixed-criticality scheme requires. A budget overrun is ordinarily treated as a fault to be contained, though, and not as a trigger for a planned change of mode.

High-performance domain controllers are another matter. They use application processors with deep cache hierarchies and out-of-order execution, usually under a hypervisor that hosts safety-rated and unrated guests. Here the commodity multicore problem appears in full, and the mechanisms reviewed above, cache partitioning and memory bandwidth regulation at the hypervisor level in particular, are the available tools. What the automotive literature lacks, compared with avionics, is an agreed statement of what timing evidence for such a platform should contain.

7. Measurement as Supporting Evidence

Whatever analysis is chosen, the assumptions behind it have to be tested on the real device. The technique that has become customary is to run the task under analysis against synthetic co-runners written to load one shared resource as heavily as possible, an approach developed for commodity multicore processors by Radojkovic et al. (2012). If the execution time observed under such stress stays within the bound claimed, the isolation mechanisms are doing their work; if it does not, an interference channel has been missed. Such tests cannot establish a bound on their own, because no stress program is guaranteed to produce the worst alignment of requests. Their value is as a check on the argument. Trace interfaces on automotive microcontrollers make the measurements unintrusive, and the same instrumentation serves the budget monitoring that the operating system performs in the field.

8. Open Problems

Several gaps recur across the sources. Hardware documentation is the first: sound analysis requires knowledge of arbitration policies, prefetchers and controller behaviour that vendors seldom publish, and measurement can reveal such behaviour but cannot prove its absence. The second is the standing of probabilistic bounds. A probabilistic WCET sits naturally beside the failure rate targets used for hardware, yet the conditions under which an extreme value fit can be trusted remain debated (Davis and Cucu-Grosjean, 2019). The third is the distance between theory and practice in mixed-criticality scheduling: models that degrade low-criticality service gracefully, instead of abandoning it, are closer to what standards allow, and their analysis is less mature (Burns and Davis, 2017). A fourth concerns composability. Integrators need timing budgets that hold for a software component whatever is placed on the other cores, and current methods mostly deliver bounds tied to one configuration.

9. Conclusion

The literature does not offer a single method that yields tight, certifiable execution time bounds for arbitrary software on arbitrary multicore hardware. It does support a workable strategy for automotive controllers: restrict the interference channels through partitioning and budgeting, analyse each core with the static or hybrid tools that are already mature, account explicitly for whatever sharing remains, and use measurement under stress to test the assumptions. The mixed-criticality model contributes the useful idea of budgets held at different levels of assurance, though its mode-change semantics must be reconciled with the freedom-from-interference requirement before it can be applied as published. Progress now depends as much on hardware transparency and on agreement about acceptable evidence as on new analysis techniques.

Conflict of interest

To be declared by the author(s) before publication.

Funding

To be declared by the author(s) before publication.