Interference channels and multicore processors Interference channels make WCET calculations a thorny issue

The challenge posed by multicore processors and Worst-Case Execution Times is one that has long been a stumbling block for developers of critical, hard real time applications.

Real-time control systems are closed-loop, allowing only a tight time window to gather data, process that data, and update the system. If the time window is missed then the stability of the system is degraded – and that can be catastrophic for critical applications.

Single-core processors cannot run multiple processes in parallel, and instead use rapid scheduling to make it appear as though they do. As proved by Liu and Layland as long ago as 1973, there is a very sound basis for taking such an approach. For a single core processor, multitasking real-time systems can be guaranteed to hit their deadlines as long as sufficient CPU headroom (capacity) is allowed for.

The challenge of Multicore processors and Worst-Case Execution Times (WCET)

Multicore Processors (MCPs) introduce an extra level of complication compared to SCPs in that they genuinely do run multiple processes in parallel. Unlike single processor applications, the task of finding a schedule of X tasks on Y processor cores such that all tasks meet their deadline has no efficient algorithm.

Exacerbating that problem, in multicore processors hardware interference can occur anywhere hardware is shared between processes. For example, often an entire hierarchical memory is shared so that interference is possible in many places. These interference channels cause the execution-time distribution to spread. Instead of a tight peak, the distribution of execution times becomes wide with a long tail.

Outside the realm of safety critical applications, these issues are of little consequence. But where functional safety is paramount, it is critical.

The role of static analysis

Although static analysis tools do exist for the purpose, even for a single core processor the calculation of a definitive value of WCET by mathematical analysis is not soluble in the general case. According to Reinhard Wilhelm et al., any such approach will therefore require approximations to be applied which have to be correct, but not necessarily complete. The result is that such tools will necessarily err “on the safe side” which is better than nothing but in an environment where precision is everything, it cannot be ideal – even without the additional vagaries introduced by MCPs.

However, there are long standing and proven mechanisms available to measure the properties of software code which are independent of their execution on any particular platform. For example, Halstead’s metrics reflect the implementation or expression of algorithms in different languages to evaluate the software module size, software complexity, and the data flow information – and these can be calculated precisely from the static analysis of the source code (below) using the TBvision component of the LDRA tool suite. Such an approach can identify which sections of code are the most demanding of processing time, but cannot provide absolute values for maximum time elapsed.

Halstead’s metrics are calculated precisely using static analysis

Using the static analysis to drive WCET dynamic analysis

There is no better way to ascertain how that information translates into time elapsed for a particular function or call tree than by measuring it in the environment in which it is intended to run. That can be measured dynamically by deploying the TBrun component of the LDRA tool suite.

For the most part, unit testing is similar irrespective of whether MCPs are in use, or not. However, timing analysis is especially important in MCP-based systems, because of the need to demonstrate that multicore interference has been adequately dealt with.

The LDRA tool suite is able to measure WCET dynamically, measuring the performance of each complete cycle algorithm in turn on a running system. It include the capability of loading one or more cores, forcing hardware interference to play a part.

The analysis approach leverages proven unit test technology repeatedly exercise and time the code under test, while stressing the target device simultaneously.

Generated graphs show the deterioration in execution times with processor cores under load

Multicore processors and Worst-Case Execution Times: Conclusions

The challenge posed by multicore processors and Worst-Case Execution Times is one that has long been a stumbling block for developers of critical, hard real time applications.

There is no doubt that an empirical approach to WCET analysis by dynamic means is the best – perhaps the only – way to demonstrate that interference channels have been adequately mitigated.

However, static analysis has a key role to play in ensuring that those measurements are truly representative or worst-case scenarios by allowing measurements to be focused upon the most demanding execution paths through the code.

More information on the LDRA tool suite’s capacity to support critical applications leveraging multicore processors is available here.