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.2006.667
URN: urn:nbn:de:0030-drops-6677
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/667/
Go to the corresponding OASIcs Volume Portal

Gustaffson, Jan ; Ermedahl, Andreas ; Lisper, Björn
Tightening WCET Bounds

Algorithms for Infeasible Path Calculation

pdf-format:
WCET_GustafssonJan.667.pdf (0.4 MB)

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. One key component in static WCET analysis is to derive flow information, such as loop bounds and infeasible paths for the analysed program. Such flow information can be provided as either as annotations by the user, can be automatically calculated by a flow analysis, or by a combination of both. To make the analysis as simple, automatic and safe as possible, this flow information should be calculated automatically with no or very limited user interaction. In this paper we present three novel algorithms to calculate infeasible paths. The algorithms are all designed to be simple and efficient, both in terms of generated flow facts and in analysis running time. The algorithms have been implemented and tested for a set of WCET benchmarks programs.

BibTeX - Entry

@InProceedings{gustaffson_et_al:OASIcs:2006:667,
  author =	{Jan Gustaffson and Andreas Ermedahl and Bj{\"o}rn Lisper},
  title =	{{Algorithms for Infeasible Path Calculation}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Frank Mueller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/667},
  URN =		{urn:nbn:de:0030-drops-6677},
  doi =		{10.4230/OASIcs.WCET.2006.667},
  annote =	{Keywords: Worst case execution time, real-time, control flow analysis, abstract interpretation, infeasible paths }
}

Keywords: Worst case execution time, real-time, control flow analysis, abstract interpretation, infeasible paths
Collection: 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)
Issue Date: 2006
Date of publication: 23.08.2006

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