(A) static analysis technique for improving accuracy of worst case execution time estimation = 최장 수행 시간 예측의 정확도 향상을 위한 정적 분석 기법

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-bas...
Advisors
Cha, Sung-Deokresearcher차성덕researcher
Publisher
한국과학기술원
Issue Date
2007
Identifier
263525/325007  / 020005087
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학전공, 2007.2, [ vi, 68 p. ]

Keywords

Worst Case Execution Time; Real-time System; Static Analysis; 정적 분석; 최장 수행 시간; 실시간 시스템

URI
http://hdl.handle.net/10203/33221
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=263525&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 174
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0