Whether on the factory floor, in a medical device, or in an aircraft, real-time critical embedded systems demand quick decision-making processes. They deploy closed-loop control, allowing only a tight time window to gather data, process that data, and update the system. The challenge for developers is that proving that execution times never exceed their allotted window is always a challenge, and even more difficult when using multicore processors.
The worst-case execution time (WCET) of a computational task is the maximum length of time that task could take to execute in a specific environment.
Hard real-time systems need to satisfy stringent timing constraints imposed by the nature of the functions they fulfil. Unfortunately, it is not possible in general to calculate definitive upper bounds on execution times for programs.
Suppose that a real-time system runs on a single-core processor and consists of several tasks, running concurrently. The diagram depicts several relevant properties of one of those real-time tasks.
The WCET is the longest execution time possible for a program, and the BCET (Best Case Execution Time) is the shortest. The pertinent calculations must consider all possible inputs, including specification violations.
Upper and lower bounds for a task running on a single-core processor can be approximated by computing bounds for different paths in the task, searching for the overall path with the longest and shortest execution times respectively.
The upper curve in the diagram depicts the set of all execution times, which will naturally vary. Developers must be aware of the Worst-Case Execution Time (WCET) to ensure that the timing window allocated to the task is adequate in all cases.
Timing analysis and time budgeting in safety-critical embedded systems involve evaluating and allocating precise time constraints to ensure tasks are completed within their required time frames. Because this is crucial for maintaining system reliability and performance, it is highlighted in most (if not all) pertinent standards as exemplified below.
DO-178C establishes a need for the analysis of WCET, highlighting it in §6.3 (Software Reviews and Analyses), §6.3.4 (Reviews and Analyses of Source Code), and §11.20 (Software Accomplishment Summary).
For many years, the use of multicore processors in civil aviation has been restricted to the use of a single core only due to concerns over some characteristics of multicore processors. CAST-32A was an advisory document written to be supplemental to DO-178C, and to “[provide] a rationale that explains why these topics are of concern and [propose] objectives to address the concern.”
CAST-32A and its successor documents, AMC 20-193 and AC 20-193, include detailed guidance on the criteria that are to be satisfied if multicore processors are to be deployed in DO-178C compliant applications.
IEC 61508 part 3 §7.9 is concerned with software verification. §7.9.2.14 discusses the verification of timing performance more specifically, requiring that the “verification of timing performance: predictability of behaviour in the time domain shall be verified.” It goes on to note that “timing behaviour may include… worst case execution time”.
For time-critical functions, ISO 26262 requires that timing constraints should be included within the software safety requirements. Both the worst-case execution time at the code level and the response time at the system level are to be considered, and there is reference to “appropriate scheduling properties”.
Temporal constraints also are a part of the software architectural design (Part 6 §7.4.5), especially the worst-case execution time.
EN 50128 §D.45 is concerned with response timing and memory constraints. It requires that “An analysis is performed which will identify the distribution demands under average and worst-case conditions”.
IEC 62304 §5.2.2 suggests the definition of functionality and capability requirements should include “timing requirements”.
As discussed above, the term “worst-case execution time” is generally used in connection with hard real-time systems to ensure that scheduling deadlines are met.
The term “worst-case running time” (or more formally, “worst-case time-complexity”) usually refers to the time taken to execute the most demanding path through a particular algorithm. An example might be the longest time it would take a sorting algorithm to sort a list of N items assuming worst-case initial ordering.
In short, the two concepts are related but not the same.
To understand why multicore processors present such a challenge, first consider how single-core processors handle the various tasks (or “processes”) scheduled by an operating system.
Single-core processors cannot run multiple processes in parallel. They use rapid scheduling to make it appear as though they do. A multitasking real-time system running on a single-core processor can hit guaranteed deadlines, as proved by Liu and Layland in 1973.
Multicore processors 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.
The operating systems used in laptops and mobile phones do a good job, but they cannot guarantee to meet task deadlines. Exacerbating that problem, hardware interference can occur anywhere hardware is shared between multicore processors cores.
On a single-core processor, resources such as memory are dedicated to that core. The introduction of additional cores results in those resources being shared between them. Time-related delays occur as users wait for access.
For example, the diagram shows that when a hierarchical memory is shared, 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, this issue is of little consequence. But where functional safety and timing are both paramount, it is critical.
In a critical application, it is often vitally important that the timing window allocated to each task is always big enough. To be sure of that, developers must be able to quantify the Worst-Case Execution Time (WCET). Worst-case execution time calculation traditionally involves calculations and/or measurements aimed at achieving that end.
Traditional methods include
Neither approach is capable of producing a definitive value, and so the inclusion of a “margin of error” is necessary.
Worst-case execution time prediction by static program analysis represents one possible approach to arriving at a more satisfactory answer. There are static analysis tools designed for that purpose, but these too can only arrive at an approximation. Even for an individual task the state space is too large to exhaustively explore all possible executions and thereby determine an exact value. At best, such tools can only lessen the necessary margin of error – and that’s when hardware is relatively simple.
The combination of multicore interference channels and the insoluble “X tasks on Y cores” conundrum demands a rethink of many established practices reliant upon the constraints implied by single-core devices.
One approach to ensuring adequate timing windows is to introduce restrictions to the architecture of the solution.
Civil aviation guidance in CAST-32A and A(M)C0193 defines Robust Time Partitioning on a multicore processor as the “result of mitigating the time interference between partitions hosted on different cores [such that] no software partition consumes more than its allocation of execution time on the core(s) on which it executes, irrespective of whether partitions are executing on none of the other active cores or on all of the other active cores.” Robust partitioning enables “separate determination of the WCET [worst case execution time] of an application without any other applications executing.”
As the documents highlight there are many highly effective robust partitioning mechanisms available. These mitigate for many of the most significant interference channels. However, there are two caveats.
Whether robust partitioning is in place or not, the onus remains on the developer to demonstrate that interference mitigation is effective which can only be achieved through measurement.
Even in the case of single core processors, the calculation of WCET based on first principles is not a trivial exercise. Several methods exist, including end-to-end measurements of execution times, and manual static analysis techniques such as counting and summing assembler instructions for each function, loop etc.
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 such that tools will necessarily err “on the safe side”. That is better than nothing, but in an environment where precision is everything it cannot be ideal – even without the additional vagaries introduced by multicore processors.
A better way to proceed is to use precise calculations where they are available, and to use them in combination with empirical measurements where they are not. The LDRA tool suite provides an integrated static and dynamic analysis environment to ease that process.
Static analysis does have a contribution to make to a more precise, reliable approach. 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. The TBvision component of the LDRA tool suite can calculate these metrics precisely.
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
The same static analysis also yields call diagrams associated with the code base, presenting a means of visualizing calls to the most demanding functions in the context of the code base as a whole.
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 will ultimately run. The TBwcet component of the LDRA tool suite measures that dynamically, as this artist’s impression of its graphical output shows.
TBwcet adopts a “wrapper” principle which affords the flexibility to perform execution time analysis from a complete thread or process, right down to class/function/procedure level. This ability to “drill in” to problem areas can be supplemented by system-wide analysis through TBexec.
The choice of stressor mechanism is left to the user. Open source solutions such as Stress‑ng provides specific stressors for Hardware Shared Resources (HSRs) such as
The flexibility of the test harness presents the opportunity for these stressors to be adapted to suit specific circumstances, or for new ones to be developed from first principles.
TBwcet is complemented by the TBexec component which captures whole-application timing and coverage metrics. Both TBwect and TBexec are based on proven technology, and are available for developers to use without committing to a consultancy package – although that support is available if needed.
These timing analysis tools provide a sound foundation for the interference research and iterative development processes that are a necessary part of Multicore Processor adoption in critical hard real-time applications.
The worst-case execution time (WCET) of a computational task is the maximum length of time that task could take to execute in a specific environment.
Hard real-time systems need to satisfy stringent timing constraints imposed by the nature of the functions they fulfil. Unfortunately, it is not possible in general to calculate definitive upper bounds on execution times for programs, particularly where multicore processors (MCPs) are deployed. Execution time analysis and the derivation of WCET therefore have an important part to play in the development of any such system.
However, it is also important to note that timing analysis is just one small part of a much bigger picture that is painted by compliance with standards including DO-178C, ISO 26262, and IEC 61508. The best choice of tool chain for your application will provide sound support throughout that whole development lifecycle.
Technical white paper: Developing compliant critical software systems with multicore processors
Technical briefing: Getting to grips with A(M)C 20-193
Technical white paper: Following the recommendations of A(M)C 20-193
Email: info@ldra.com
EMEA: +44 (0)151 649 9300
USA: +1 (855) 855 5372
INDIA: +91 80 4080 8707