Research On Worst-Case Execution Time Of Real-Time Software Estimation

When constructing real-time system, safe and tight estimations of the worst-case execution time (WCET) of programs are needed. To derive program WCET estimations, both the properties of the software and the hardware must be considered. The traditional method to obtain WCET estimations is to test the system and measure the execution time. This is labor-intensive and error-prone work, which unfortunately cannot guarantee that the worst-case is actually found. Static WCET analysis, on the other hand, is capable of generating safe WCET estimations without actually running the program. Such analyses use models of program flow and hardware timing to generate WCET estimations. In static WCET analysis there are three different calculation methods for finding the WCET of a real-time program, namely the Implicit Path Enumeration Technique (IPET), the Path-based calculation method and the Tree-based calculation.This paper mainly presents two Path-based methods for finding the WCET of a program in the presence of infeasible paths without performing exhaustive path enumeration. Firstly, the two methods pre-compute branch constraints in program, then convert these branch constraints to semantic conflicts between node-pair of control flow graph (CFG) and save these semantic conflicts into conflicts array of corresponding program in order to exclude impossible paths when searching path and improve efficiency on searching path. The methods finally select path which has the maximum execution time from possible paths collection. Comparing to some other former methods, the two methods in this paper not only avoid the high cost of path enumeration including possible paths and impossible paths, but also avoid backtracking source node of CFG to find alternative path after excluding impossible paths. They adjust control flow graph (CFG) and update the current path when checking conflicts.In the end this paper gives experiment results for benchmark programs and demonstrates how efficiently and quickly the two approaches can give estimation WCET for real-life control-intensive application by comparing to some other methods.