WCET determination tool for embedded systems software

ABSTRACT

Embedded systems are special-purpose computer systems within environments such as automotive, avionic, telecommunication, etc. As these systems often perform time-critical control tasks, it is necessary to precisely predict their behaviour. Software-based solutions on the one hand provide high flexibility. On the other hand, especially when multiple software processes are to be executed concurrently on the same hardware, the software approach makes prediction more difficult. Predictions essentially rely on the knowledge of when a software process terminates. For a reasonable system architecture it has to be known at an early stage of design time to scale the system well. Dynamic factors such as cache usage, amount of data, and availability of shared resources have great impact on the result. Thus, tools are necessary to determine execution time as accurate as possible. The execution time is commonly approximated by determining the interval of best and worst case execution time (BCET & WCET). While the BCET can be roughly estimated by evaluating the shortest path the achievement of good approximations for the WCET is heavy. Considering all possible execution paths of the analysed program as well as the effects of the underlying architecture on the timing properties affected by pipelining and caches create a hard issue to solve. Nevertheless these figures are important in certification processes in the application fields given above as well as performance prediction and solving design issues. Another motivation is the lack of tools targeted to an intermediate level of abstraction. In general tools are re-targetable frameworks analysing high-level code with sophisticated algorithms or similar algorithms are applied to low-level code that lacks context and type information.

REFERENCES

• 1: B. Frey. PowerPC Architecture Book. International Business Machines Corporation, Nov. 2005.
• 2: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.456-461, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217570]
• 3: Jan Staschulat , Rolf Ernst, Worst case timing analysis of input dependent data cache behavior, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.227-236, July 05-07, 2006 [doi>10.1109/ECRTS.2006.33]