License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2012.91
URN: urn:nbn:de:0030-drops-35608
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3560/
Go to the corresponding OASIcs Volume Portal

Huber, Benedikt ; Prokesch, Daniel ; Puschner, Peter

A Formal Framework for Precise Parametric WCET Formulas

pdf-format:
p091-huber.pdf (0.5 MB)

Abstract

Parametric worst-case execution time (WCET) formulas are a valuable tool to estimate the impact of input data properties on the WCET at design time, or to guide scheduling decisions at runtime. Previous approaches to parametric WCET analysis either provide only informal ad-hoc solutions or tend to be rather pessimistic, as they do not take flow constraints other than simple loop bounds into account. We develop a formal framework around path- and frequency expressions, which allow us to reason about execution frequencies of program parts. Starting from a reducible control flow graph and a set of (parametric) constraints, we show how to obtain frequency expressions and refine them by means of sound approximations, which account for
more sophisticated flow constraints. Finally, we obtain closed-form parametric WCET formulas by means of partial evaluation. We developed a prototype, implementing our solution to parametric WCET analysis, and compared existing approaches within our setting. As our framework
supports fine-grained transformations to improve the precision of parametric formulas, it allows to focus on important flow relations in order to avoid intractably large formulas.

BibTeX - Entry

@InProceedings{huber_et_al:OASIcs:2012:3560,
  author =	{Benedikt Huber and Daniel Prokesch and Peter Puschner},
  title =	{{A Formal Framework for Precise Parametric WCET Formulas}},
  booktitle =	{12th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{91--102},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-41-5},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{23},
  editor =	{Tullio Vardanega},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3560},
  URN =		{urn:nbn:de:0030-drops-35608},
  doi =		{10.4230/OASIcs.WCET.2012.91},
  annote =	{Keywords: Worst-case execution time analysis, parametric WCET analysis, path expressions, frequency expressions, algebraic framework}
}

Keywords: Worst-case execution time analysis, parametric WCET analysis, path expressions, frequency expressions, algebraic framework
Collection: 12th International Workshop on Worst-Case Execution Time Analysis
Issue Date: 2012
Date of publication: 10.07.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI