@inproceedings{cerny2015segment,
author = {Cerny, Pavol and Henzinger, Thomas A. and Kovacs, Laura and Radhakrishna, Arjun and Zwirchmayr, Jakob},
title = {Segment Abstraction for Worst-Case Execution Time Analysis},
booktitle = {European Symposium on Programming Languages and Systems (ESOP)},
year = {2015},
month = {April},
abstract = {In the standard framework for worst-case execution time (WCET) analysis of programs, the main data structure is a single instance of integer linear programming (ILP) that represents the whole program. The instance of this NP-hard problem must be solved to find an estimate for WCET, and it must be refined if the estimate is not tight. We propose a new framework for WCET analysis, based on abstract segment trees (ASTs) as the main data structure. The ASTs have two advantages. First, they allow computing WCET by solving a number of independent small ILP instances. Second, ASTs store more expressive constraints, thus enabling a more efficient and precise refinement procedure. In order to realize our framework algorithmically, we develop an algorithm for WCET estimation on ASTs, and we develop an interpolation-based counterexample-guided refinement scheme for ASTs. Furthermore, we extend our framework to obtain parametric estimates of WCET. We experimentally evaluate our approach on a set of examples from WCET benchmark suites and linear-algebra packages. We show that our analysis, with comparable effort, provides WCET estimates that in many cases significantly improve those computed by existing tools.},
url = {http://approjects.co.za/?big=en-us/research/publication/segment-abstraction-for-worst-case-execution-time-analysis/},
}