What do you mean: no-one can tell me what the actual WCET is?

2012-10-01

Given that we’re a company that makes a tool that helps you to find the worst-case execution time (WCET) of your code, it might be surprising to hear us say that it’s (generally) not possible to give an exact value for WCET.

So what do we mean by an exact value for WCET?

WCET for a computational task is defined as the maximum length of time the task could take to execute on a specific hardware platform. This excludes any time spent executing other tasks or interrupts. This single value occurs when the execution of the code follows the longest path through the code, in the presence of the worst possible hardware state (the largest set of cache misses, the most interrupts, etc), which represents a vanishingly small probability of it just occurring.

Despite academic research over the last thirty years, there currently is no way to find the "actual WCET" for any reasonably large piece of code running on a modern processor. Instead, the aim of WCET analysis when applied in the context of real, live, engineering projects must be to find a useful and valid approximation of the actual WCET.

Techniques for calculating WCET estimates may be optimistic or pessimistic. An optimistic value is one that is less than the actual WCET. Likewise a pessimistic value is one that is greater than the actual value.

Although it seems natural to err on the side of caution, performing WCET analysis that is guaranteed never to be optimistic typically results in a predicted WCET value that is so pessimistic that it is of no practical use. For example, if your WCET analysis assumes that every cache access results in a cache miss, either your system will be unable to meet its deadlines or there’s no need to deploy your system with the cache enabled.

Many avionics systems today use manual measurements to determine WCET. These will be optimistic (unless you happen to hit the exact set of circumstances that cause the worst-case execution time to occur – you might win the lottery too).

Next week we’ll tell you how RapiTime provides a solution that is somewhere in the middle of these techniques.