Conferences and supporting programme
Obtaining Worst-Case Execution Time Bounds on Modern Microprocessors
In real-time systems the overall correctness depends on the correct timing behavior: each real-time tasks has to finish before its deadline. All current safety standards require reliable bounds of the worst-case execution time (WCET) of real-time tasks to be determined. With end-to-end timing measurements timing information is only determined for one concrete input. Due to caches and pipelines the timing behavior of an instruction depends on the program path executed before. Therefore, usually no full test coverage can be achieved and there is no safe test end criterion. Techniques based on code instrumentation modify the code which can significantly change the cache behavior (probe effect): the times measured for the instrumented software do not necessarily correspond to the timing behavior of the original software. One safe method for timing analysis is static analysis by Abstract Interpretation which provides guaranteed upper bounds for WCET of tasks. Static WCET analyzers are available for complex processors with caches and complex pipelines, and, in general, support single-core processors and multi-core processors. A prerequisite is that good models of the processor/System on-Chip (SoC) architecture can be determined. However, there are modern high performance SoCs which contain unpredictable and/or undocumented components that influence the timing behavior. Analytical results for such processors are unrealistically pessimistic. A hybrid WCET analysis combines static value and path analysis with measurements to capture the timing behavior of tasks. Compared to end-to-end measurements the advantage of hybrid approaches is that measurements of short code snippets can be taken which cover the complete program under analysis. Based on these measurements a worst-case path can be computed. The hybrid WCET analyzer TimeWeaver avoids the probe effect by leveraging the embedded trace unit (ETU) of modern processors, like Nexus 5001, which allows a fine-grained observation of a core’s program flow. TimeWeaver reads the executable binary, reconstructs the control-flow graph and computes ranges for the values of registers and memory cells by static analysis. This information is used to derive loop bounds and prune infeasible paths. Then the trace files are processed and the path of longest execution time is computed. The computed time bounds provide valuable feedback for assessing system safety and for optimizing worst-case performance. TimeWeaver also provides feedback for optimizing the trace coverage: paths for which infeasibility has been proven need no measurements; loops for which the analyzed worst-case iteration count has not been measured are reported. In this article we give an overview of timing predictability in general and provide criteria for selecting suitable WCET analysis methods. We will outline the methodology of hybrid WCET analysis and report on practical experience with the tool TimeWeaver.
--- Date: 28.02.2018 Time: 2:30 PM - 3:00 PM Location: Conference Counter NCC Ost