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.
프로그램의 최장수행시간 분석이란 프로세서가 프로그램을 수행함에 있어서 소요되는 최장시간을 예측하는 것을 의미한다. 이는 실시간 내장 시스템에서 프로그램이 주어진 주기 내에 반응하는 것을 보장하고 제한된 자원을 효율적으로 사용하기 위하여 필요하다. 분석 결과인 예측치는 실제 최장수행시간에 최대한 근접해야 하며, 안전하기 위해서 과소평가 되어서는 안된다. Implicit Path Enumeration(IPE) 기법은 정적인 최장수행시간 분석 방법 중 하나로서, 분석 결과인 예측치는 안전하지만 과다계상되는 경향이 있다. 이는 IPE 기법이 프로그램에서 실행이 불가능한 경로까지도 모두 고려하여 최장수행시간을 분석하기 때문이다. 본 논문에서는 IPE 기법으로 도출한 최장수행시간 예측치가 프로그램에서 실행 가능한 수행시간인가를 검사하는 기법을 제안한다. 만약 예측치가 실행가능하다면, 기존의 IPE 기법이 각 노드의 수행횟수만을 도출하는 반면, 제안된 기법에서는 명시적인 최장 경로를 도출한다. 이 경로를 지나는 입력 데이터를 생성할 수 있으므로, 생성된 입력값으로 프로그램을 직접 실행함으로써 실제 최장수행시간을 계산할 수 있다. 만약 예측치가 실행불가능하다면, 예측치는 과다계상된 값임을 보장할 수 있다. 이 경우, 실제 최장수행시간은 예측치보다는 작다는 것을 이용하여 실제 최장수행시간에 더 근접한 값을 얻을 수 있다. 최장수행시간에 더 근접한 예측치를 반복적으로 구함으로써, 결국 실행가능한 예측치를 구할 수 있다. 본 논문에서는 제안된 기법의 효율성을 보이기 위하여, C 프로그램의 최장수행시간 분석도구인 TimeBounder를 확장하고, 이를 이용하여 다목적 실용위성 2호에 탑재되는 Command and Communication Interface(CCI) 모듈을 대상으로 실험을 수행하였다.
