DROPS

Document

DOI: 10.4230/OASIcs.WCET.2008.1659

Towards an Automatic Parametric WCET Analysis

Authors: Stefan Bygde and Björn Lisper

Published in: OASIcs, Volume 8, 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08) (2008)

Abstract

Static WCET analysis obtains a safe estimation of the WCET of a program. The timing behaviour of a program depends in many cases on input, and an analysis could take advantage of this information to produce a formula in input variables as estimation of the WCET, rather than a constant. A method to do this was suggested in [12]. We have implemented a working prototype of the method to evaluate its feasibility in practice. We show how to reduce complexity of the method and how to simplify parts of it to make it practical for implementation. The prototype implementation indicates that the method presented in [12] successfully can be implemented for a simple imperative language, mostly by using existing libraries.

Cite as

Stefan Bygde and Björn Lisper. Towards an Automatic Parametric WCET Analysis. In 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08). Open Access Series in Informatics (OASIcs), Volume 8, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bygde_et_al:OASIcs.WCET.2008.1659,
  author =	{Bygde, Stefan and Lisper, Bj\"{o}rn},
  title =	{{Towards an Automatic Parametric WCET Analysis}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  pages =	{1--9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Kirner, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2008.1659},
  URN =		{urn:nbn:de:0030-drops-16592},
  doi =		{10.4230/OASIcs.WCET.2008.1659},
  annote =	{Keywords: WCET, Flow Analysis, Parametric, Symbolic}
}

Document

DOI: 10.4230/OASIcs.WCET.2007.1194

Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

Authors: Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Björn Lisper

Published in: OASIcs, Volume 6, 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07) (2007)

Abstract

Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea is to bound the number of different states in the loop which can influence the exit conditions. Given that the loop terminates, this number provides an upper loop bound. An algorithm based on the approach has been implemented in our WCET analysis tool SWEET. We evaluate the algorithm on a number of standard WCET benchmarks, giving evidence that it is capable to derive valid bounds for many types of loops.

Cite as

Andreas Ermedahl, Christer Sandberg, Jan Gustafsson, Stefan Bygde, and Björn Lisper. Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis. In 7th International Workshop on Worst-Case Execution Time Analysis (WCET'07). Open Access Series in Informatics (OASIcs), Volume 6, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{ermedahl_et_al:OASIcs.WCET.2007.1194,
  author =	{Ermedahl, Andreas and Sandberg, Christer and Gustafsson, Jan and Bygde, Stefan and Lisper, Bj\"{o}rn},
  title =	{{Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis}},
  booktitle =	{7th International Workshop on Worst-Case Execution Time Analysis (WCET'07)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-05-7},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{6},
  editor =	{Rochange, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2007.1194},
  URN =		{urn:nbn:de:0030-drops-11946},
  doi =		{10.4230/OASIcs.WCET.2007.1194},
  annote =	{Keywords: WCET analysis, loop-bound analysis, program slicing, abstract interpretation, invariant analysis}
}

Search Results

Documents authored by Bygde, Stefan

Towards an Automatic Parametric WCET Analysis

Abstract

Cite as

Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis

Abstract

Cite as

Thanks for your feedback!

Could not send message