Checking feasibility of worst-case execution time derived by implicit-path enumeration technique

Abstract

Worst-Case Execution Time(WCET) analysis is essential for developing a real-time embedded system. It predicts an upper bound of execution time of a program for assuring response time and utilizing hardware resources. Analysis result, i.e. WCET estimate, must be as close as possible to actual WCET and must not be underestimated. Implicit-Path Enumeration Technique(IPET), a static WCET analysis method, analyzes all of program paths to produce a safe estimate that is not underestimated. However, it tends to overestimate WCET since it takes even infeasible paths into consideration. In this paper, we propose an approach to check feasibility of a WCET estimate derived by IPET. If the estimate is feasible, our approach provides a feasible WCET path, while IPET merely produces execution count of nodes in a program flow graph. We can generate input data that traverse the path, and measure the actual WCET by running the program with the input. If the estimate is infeasible, i.e. WCET is overestimated, we feed back the information that actual WCET is smaller than the estimate, to get a tighter estimate in IPET. By iterating WCET estimation and its feasibility check, we can eventually get a feasible estimate. To demonstrate effectiveness of our approach, we experimented on CCI module that is embedded in Korea Multi-Purpose Satellite, using extended TimeBounder. TimeBounder, a WCET analyzer of C programs, is extended to check feasibility of an estimate and to get a feasible estimate if the estimate is infeasible.