Worst-case Execution Time - Finding WCET - Automated Approaches To Finding WCET - Static Analysis Techniques

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:

    The spider-mind acquires a faculty of memory, and, with it, a singular skill of analysis and synthesis, taking apart and putting together in different relations the meshes of its trap. Man had in the beginning no power of analysis or synthesis approaching that of the spider, or even of the honey-bee; but he had acute sensibility to the higher forces.
    Henry Brooks Adams (1838–1918)

    It is easy to lose confidence in our natural ability to raise children. The true techniques for raising children are simple: Be with them, play with them, talk to them. You are not squandering their time no matter what the latest child development books say about “purposeful play” and “cognitive learning skills.”
    Neil Kurshan (20th century)