WCET Methods


Verifying the timing correctness of real-time software isn't about the 99.9% of times when the software runs fast enough. Rather, to ensure reliable operation, it is necessary to focus on the worst-case or near worst-case behaviour when time constraints may be broken.

There are three main approaches to obtaining information about the worst-case execution time behaviour of real-time systems. These pages provide a brief description of each method, along with a summary of their advantages and disadvantages.

Measurement

Measurement is the most common method of worst-case execution time estimation in commercial use today. Measurement techniques insert profiling code into the software, recording the end-to-end execution time of sub-systems, functions, or individual blocks of code.

MORE

Static Analysis

Static analysis was developed as an alternative method of worst-case execution time estimation to measurement.

Static analysis techniques rely on having a precisely accurate model of the timing behaviour of the microprocessor, including the effects of pipelines, caches, memory, buses, and any other hardware features that affect the execution time of machine instructions. Static analysis techniques analyse the object code for the program, and compute the worst-case path and worst-case execution time by reference to the model of the processor's timing behaviour. This is done without running the code.

MORE

Hybrid (measurement and static analysis)

Hybrid approaches to worst-case execution time estimation aim to combine the best features of measurement and static analysis whilst avoiding their pitfalls.

Hybrid approaches use a combination of three techniques:

  1. Recognising that the best possible model of an advanced microprocessor is the microprocessor itself, hybrid approaches use online testing to measure the execution time of short sub-paths between decision points in the code.

  2. By contrast, hybrid approaches view static analysis as the best way to determine the overall structure of the code and the paths through it. With a hybrid approach, this offline analysis is supplemented by information obtained during testing, such as numbers of loop iterations, and execution frequencies (modal operation) to build up a model of the overall code structure and determine which combinations of sub-paths form complete and feasible paths through the code.

  3. Finally measurement and path analysis information is combined to compute worst-case execution times in a way that captures execution time variation on individual paths due to hardware effects.
MORE