Worst Case Execution Time (WCET) is a crucial information for scheduling real-time systems. During the past decade, static WCET analysis has been an active research field because it is (semi-)automatic as well as capable of guaranteeing safeness of the estimate. In general, static methods tend to over-approximate WCET estimates because information on infeasible path is hard to manage efficiently and to apply in computations.
This dissertation proposes a technique that maintains and utilizes the feasibility information in a compact manner. Our technique encodes infeasible paths using BDD whose operations perform the summarization and query processes in linear time. Moreover, the technique is extendable to any analyses that require feasibility tests. Experiments we have conducted show that this technique reduces the space for maintaining infeasible paths up to by 90% without loss of accuracy.
This dissertation, moreover, presents techniques to utilize the resulting information on infeasible paths in static WCET analyses. In this research, we mainly focus on two representative methods: Implicit Path Enumeration Technique (IPET) and path-based technique. IPET uses Integer Linear Programming(ILP) to calculate a WCET estimate. The information, therefore, must be captured as flow facts, conjunctive linear constraints on the execution counts of basic blocks. For IPET, we propose a technique to encode the information into flow facts automatically. Our encoding technique, moreover, generates flows facts that contain at most one disjunction because disjunctions in flow facts decrease performance of the analysis significantly.
For path-based technique using graph traversal algorithms for WCET estimation, this dissertation presents a technique that avoids many useless feasibility tests through BDD-based construction of CFG. The CFG is extracted from information on infeasible paths generated by our summarization technique efficiently. With the resulting CFG, path-based technique can prune many feasibility tests and graph-modifications to exclude infeasible paths.
최장 수행시간은 실시간 시스템을 스케쥴링하는데 있어서 가장 기본적인 정보중 하나이다. 이를 예측하기 위한 방법들 중 정적 분석 기법은 자동화가 가능하고 실제 최장 수행시간이 예측값보다 항상 더 작다는 것을 보장하기 때문에, 과거 수년간 활발한 연구활동이 이루어져왔다. 하지만, 정적기법은 수행 불가능한 경로를 미리 추출하고 이를 효율적으로 관리하며 예측값 계산에 반영하는 것이 어렵기 때문에, 그 결과값이 과다계상되는 것이 일반적이다.
이 연구에서는 특정 경로가 실제로 수행 가능한 지에 대한 정보를 효율적으로 관리하고 이를 정적 최장 수행시간 분석에 적용하기 위한 기법을 제안한다. 제안된 기법에서는 수행 불가능한 경로들을 관리하기 위하여 binary decision diagram (BDD)를 사용한다. BDD 연산자들은 수행 불가능한 경로들에 대한 요약된 정보를 추출하고 특정 경로가 수행 불가능한지 판별하는 과정을 매우 효율적으로 구현하는 데 사용할 수 있다. 추출된 요약 정보는 수행 가능성 판별이 필요한 다른 많은 분야에서도 일반적으로 사용될 수 있다. 수행된 실험에서는 기존의 방법이 사용하는 저장 공간의 최소 10%만을 이용하여 같은 정보를 관리할 수 있었다.
다음으로 이 연구에서는 대표적인 두가지 정적 최장 수행시간 예측기법인 implicit path enumeration technique (IPET) 및 경로 기반 기법을 대상으로 하여 어떻게 추출된 요약정보를 활용할 수 있는지 제안한다. IPET는 integer linear programming을 사용하여 최장 수행시간을 예측하기 때문에 이를 위한 모든 정보는 flow fact의 형태로 표현되어야 한다. 여기서 flow fact는 프로그램 기본 블록들의 수행회수에 대한 선형 제약사항의 형태이다. 따라서 이 연구에서는 요약 정보를 flow fact의 형태로 자동으로 변환하기 위한 방법을 제안한다. 이때 생성된 flow fact들에 disjunction들이 포함되면 될수록 예측값 계산에 소요되는 시간이 기하급수적으로 증가하기 때문에 제안된 기법에서 최대 한개의 disjunction만을 포함한 효율적인 flow fact를 생성한다. 반면 경로 기반 분석은 최대 수행시간 예측값을 계산하기 위하여 제어그래프 순회 알고리즘을 사용한다. 본 연구에서는 요약 정보를 불필요한 제어그래프변경 및 재계산을 생략할 수 있는 데 이용하여 경로 기반 분석의 효율성을 높일 수 있는 기법을 제안한다.
