Learn about “hidden” timing couplings in multicore systems that cause unexpected interference, significantly impacting Worst-Case Execution Time (WCET) even for independent tasks.

Many real-time embedded applications have critical tasks that must meet crucial timing requirements to guarantee safe and reliable system operation. Standards within various industries—including automotive, avionics, industrial, military, and healthcare, to name just a few—require developers to verify that these real-time requirements are met under all operating conditions. This is often achieved by accurately accessing the worst-case execution time (WCET) of critical system tasks and confirming it does not exceed a system’s real-time deadlines.

In multicore systems, execution time can vary when tasks on different cores try to access the same data, functions, and/or shared resources (such as memory, peripherals). For example, if one task needs to access data another task is currently modifying, the first task must wait until the modification is complete and the data is released. Such data coupling or dependencies create interference that increases the task’s execution time.

But what happens when tasks are independent from each other? Consider two tasks that don’t share any data or call any of the same functions. They also don’t use any of the same processor peripherals. Furthermore, they use different RTOSes and run on their own cores. One might expect interference between these two tasks to be minimal.

As will be shown below, interference even between independent tasks running on different cores can be significant, even to the point of substantially impacting a task’s WCET. This article will explore the “hidden” interference that arises from timing couplings within multicore architectures, the effect on WCET, and how to identify and mitigate the impact on execution time.

Hidden Timing Couplings

Timing coupling is a type of coupling where tasks on separate cores have concurrent execution. Timing coupling is important because it can link otherwise independent tasks (in other words, the tasks have no data or functional dependencies), creating interference that causes longer execution times than expected from a software architecture perspective. Even though tasks are executed on different cores, they are within the same processor and timing coupling interference can arise over the use of shared multicore resources like the L2 cache and the bus interconnect to RAM.

This is ‘hidden’ interference because it is based on the internal infrastructure of a multicore architecture. These shared resources are managed by the processor, and the developer has little to no direct control over how interference between cores is handled. Thus, timing coupling interference cannot be assessed using software design tools; it must be measured during run-time execution on the target processor.

Consider L1 and L2 cache. Often, each core has its own L1 cache, so this is not a shared resource. Keeping a task’s data usage within L1 cache limits means the task’s performance is not actively relying on the L2 cache, which is shared between cores. As a task’s data size expands, its reliance on the L2 cache increases. When two tasks rely heavily on the L2 cache, they begin to interfere with each other. Specifically, interference between the tasks will arise when tasks both use the L2 cache to access large data sets concurrently. Note that similar reasoning applies in systems without an L2 cache, where the L1 cache is directly connected to RAM.

LDRA recently collaborated with the United States Army DEVCOM Aviation & Missile Center Multi-Core Processing & Artificial Intelligence Laboratory to conduct a study of the impact of timing coupling interference.

The table in Figure 1 shows the mean execution time difference of a task (Blue App) when another task (Red App) is running concurrently on another core. The table captures the impact of the data size used by each task on overall timing.

Column 1 (No Red App) represents the performance of Blue App when nothing is running on the other core(s). This sets the baseline performance. The other columns show the impact on baseline performance based on the data size of Red App and its impact on shared L2 cache efficiency.

This table shows the impact on the mean execution time of a task (Blue App) by a concurrent task (Red App) running on another core. The two tasks are data and functionally independent from each other. The difference in mean execution time arises from timing coupling interference within the multicore architecture for shared resources like L2 cache and bus interconnect to RAM. (Click on image to enlarge)

For this study, when the data size for Blue App was 24 KB, the entire data set fit within the available 32 KB L1 cache. That’s why there is negligible impact on timing, regardless of Red App’s data size. Starting at 256 KB, the efficiency of the L2 cache can be seen.

However, at some point, the data size of a task becomes large enough to interfere with its own L2 cache efficiency. That’s why the highest impact of 40.86% occurs at Blue App 512 KB and Red App 2 MB. On its own, Blue App at 512 KB still benefits significantly from the L2 cache. However, it’s at a point where it doesn’t take much interference from Red App to reduce the benefit of the L2 cache.

Overlapping function duration for two otherwise independent tasks executing concurrently on different cores. Function names include a timestamp. The graph shows the duration of each overlap.

Part of the challenge of assessing timing coupling interference is that concurrent tasks can overlap for varying lengths of time, depending upon when each started execution. Figure 2 shows how two tasks can have varying overlap. Where, when, and for how long they overlap changes the interference they experience. Thus, assessing timing coupling interference is an iterative process.

It’s important to note that 40.86% is not the theoretical maximum impact. Timing coupling interference depends upon many factors, and each system will have a different interference footprint, so to speak. That’s one reason why using tools to inject interference isn’t effective. Generated interference doesn’t reflect the real-time interference of the system and so is at best a guess.

Timing Coupling Mitigation

As can be seen from Figure 3, the WCET can be significantly impacted by timing coupling interference. Accurately identifying this interference enables developers to take appropriate steps to mitigate the impact of multicore-based timing coupling on WCET.

Timing coupling interference can significantly impact worst-case execution time. (Click on image to enlarge)

The following checklist will help developers validate that the worst-case execution scenario does not exceed the real-time requirements of the system.

• Multicore Processor Configuration: First, identify all processor configuration settings used. Vary settings (for example, cache, core affinity) to see how they influence timing coupling interference. Then keep these settings consistent across WCET analysis and other verification processes.
• Resource Allocation: Identify all shared multicore resources (for example, cache, interconnect, memory). Verify that software resource demands for each task stay within designated bounds. Assess how resource contention could vary timing coupling interference across cores.
• Functional Execution: Verify all software tasks under full multicore processor load to assess the maximum influence of timing coupling. At the same time, verify that execution under full load results in the expected system behavior. Also, confirm that control paths are predictable and repeatable across runs.
• Coupling Verification: To be confident in an WCET assessment, developers need to verify that they have identified all data and control coupling between tasks and cores, then exercised all couplings during requirements-based testing. To complete the assessment, coupling behavior must be verified as expected using the final production / deliverable system configuration.

The most reliable method for reducing timing coupling interference and increasing deterministic behavior for safety critical code is to use a smaller data size where possible. When task data size fits entirely within the L1 cache, timing coupling interference is minimized, keeping timing changes between runs within regular expected execution variance.

When task data size is larger than the L1 cache, timing coupling interference can arise, in turn increasing variance and negatively impacting determinism. One option is to disable the L2 cache. While this will negatively impact performance, it will minimize variance in execution time for applications where determinism is essential. Other mitigation strategies are available – including cache partitioning, cache coloring (cache split for each core), priority allocation (cache is allocated based on a task’s criticality), and robust partitioning by the RTOS – but these are beyond the scope of this article.

Just One Part of a Comprehensive Approach

Assessing hidden timing couplings in multicore architectures is just one part of a comprehensive approach to evaluating WCET and assuring safe and reliable system run-time behavior. Both the LDRA tool suite and TASKING winIDEA Debugger in conjunction with a TASKING BlueBox debugger or virtual ECU simulator, for example, provide a wide range of static and dynamic analysis tools to identify and evaluate data, function, and timing coupling.

The LDRA tool suite instruments code so it can run natively on the target processor and provide detailed run-time data. The TASKING winIDEA Debugger uses trace points to enable developers to view real-time snapshots of the system. Together, these tools give developers a variety of views into system behavior and operation, enabling thorough analysis of worst-case execution time.

Accurately assessing timing coupling interference gives developers greater insight into worst-case execution time analysis. By understanding the impact of resource sharing between cores, developers can identify hidden sources of variance and mitigate them.

Given the large data sets associated with artificial intelligence (AI) and machine learning (ML) algorithms, the ability to accurately identify and assess timing coupling interference arising from multicore architecture resource contention will only become more important as systems continue to integrate more complex AI and ML technology.

Written By Ldra Alex Lim and  co-authored by TASKING’s Gerard Vink.

Read Published article Here Using Worst-Case Execution Time Analysis to Uncover Hidden Timing Couplings – Industry Articles  – All About Circuits