Static Analysis Techniques
A static WCET tool attempts to provide WCET estimations by examining the computer software without executing it directly on the hardware. Static analysis techniques have dominated research in the area since the late 1980s, although in an industrial setting end to end measurements approaches were standard practice.
Static analysis tools work at a high-level to determine the structure of a program's task, working either on a piece of source code or disassembled binary executable. They also work at a low-level, using timing information about the real hardware that the task will execute on, with all its specific features. By combining those two kinds of analysis, the tool attempts to give an upper bound on the time required to execute a given task on a given hardware platform.
At the low-level, static WCET analysis is complicated by the presence of architectural features that improve the average-case performance of the processor: instruction/data caches, branch prediction and instruction pipelines for example. It is possible, but increasingly difficult, to determine tight WCET bounds if these modern architectural features are taken into account in the timing model used by the analysis.
Certification authorities such as the European Aviation Safety Agency, therefore, rely on model validation suites.
Static analysis has resulted in good results for simpler hardware, however a possible limitation of static analysis is that the hardware (the CPU in particular) has reached a complexity which is extremely hard to model. In particular, the modelling process can introduce errors from several sources: errors in chip design, lack of documentation, errors in documentation, errors in model creation; all leading to cases where the model predicts a different behavior to that observed on real hardware. Typically, where it is not possible to accurately predict a behavior, a pessimistic result is used, which can lead to the WCET estimate being much larger than anything achieved at run-time.
Multi-core hardware is particularly difficult to obtain good static WCET estimations for.
There are a number of commercial and academic tools that implement various forms of static analysis.
Read more about this topic: Worst-case Execution Time, Finding WCET, Automated Approaches To Finding WCET
Famous quotes containing the words analysis and/or techniques:
“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)
“The techniques of opening conversation are universal. I knew long ago and rediscovered that the best way to attract attention, help, and conversation is to be lost. A man who seeing his mother starving to death on a path kicks her in the stomach to clear the way, will cheerfully devote several hours of his time giving wrong directions to a total stranger who claims to be lost.”
—John Steinbeck (1902–1968)