Visualization and Formalization of User Constraints for Tight Estimation of Worst-Case Execution Time

Jong-In LEE  Ho-Jung BANG  Tai-Hyo KIM  Sung-Deok CHA 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.1  pp.24-31
Publication Date: 2009/01/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
worst-case execution time,  user constraint,  control flow graph,  finite automata, 

Full Text: PDF(1.2MB)

Summary: 
Automated static timing analysis methods provide a safe but usually overestimated worst-case execution time (WCET) due to infeasible execution paths. In this paper, we propose a visual language, User Constraint Language (UCL), to obtain a tight WCET estimation. UCL provides intuitive visual notations with which users can easily specify various levels of flow information to characterize valid execution paths of a program. The user constraints specified in UCL are translated into finite automata. The combined automaton, constructed by a cross-production of the automata for program and user constraints, reflects the static structure and possible dynamic behavior of the program. It contains only the execution paths satisfying user constraints. A case study using part of a software program for satellite flight demonstrates the effectiveness of UCL and our approach.