Segment abstraction for worst-case execution time analysis Conference Paper


Author(s): Cerný, Pavol; Henzinger, Thomas A; Kovács, Laura I; Radhakrishna, Arjun; Zwirchmayr, Jakob
Title: Segment abstraction for worst-case execution time analysis
Title Series: LNCS
Affiliation IST Austria
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 forWCET, 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.
Keywords: segment tree; Benchmark suites; Integer Linear Programming; Linear algebra package; Standard frameworks; Wcet analysis; Worst-case execution time analysis
Conference Title: ESOP: European Symposium on Programming
Volume: 9032
Conference Dates: April 11-18, 2015
Conference Location: London, UK
ISBN: 978-366246668-1
Publisher: Springer  
Date Published: 2015-04-01
Start Page: 105
End Page: 131
DOI: 10.1007/978-3-662-46669-8_5
Notes: This research was supported in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), the Austrian National Research Network RiSE (FWF grants S11402-N23), the Swedish VR grant D0497701, the WWTF PROSEED grant ICT C-050, the French National Research Agency grant W-SEPT (ANR-12-INSE-0001), NSF Expeditions award CCF 1138996, DARPA under agreement FA8750-14-2-0263, and a gift from the Intel Corporation.
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Pavol Černý
    25 Cerný
Related IST Austria Work