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.2010.36
URN: urn:nbn:de:0030-drops-28235
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2823/
Go to the corresponding OASIcs Volume Portal

Wilhelm, Stephan ; Cullmann, Christoph

Integrating Abstract Caches with Symbolic Pipeline Analysis

pdf-format:
5.pdf (0.4 MB)

Abstract

Static worst-case execution time analysis of real-time tasks is based on abstract models that capture the timing behavior of the processor on which the tasks run. For complex processors, task-level execution time bounds are obtained by a state space exploration which involves the abstract model and the program. Partial state space exploration is not sound. Symbolic methods using binary decision diagrams (BDDs) allow for a full state space exploration of the pipeline, thereby maintaining soundness. Caches are too large to admit an efficient BDD representation. On the other hand, invariants of the cache state can be computed efficiently using abstract interpretation. How to integrate abstract caches with symbolic-state pipeline analysis is an open question. We propose a semi-symbolic domain to solve this problem. Statistical data from industrial-level software and WCET tools indicate that this new domain will enable an efficient analysis.

BibTeX - Entry

@InProceedings{wilhelm_et_al:OASIcs:2010:2823,
  author =	{Stephan Wilhelm and Christoph Cullmann},
  title =	{{Integrating Abstract Caches with Symbolic Pipeline Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{36--43},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Bj{\"o}rn Lisper},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2823},
  URN =		{urn:nbn:de:0030-drops-28235},
  doi =		{10.4230/OASIcs.WCET.2010.36},
  note =	{The printed version of the WCET'10 proceedings are published by OCG (www.ocg.at) - ISBN 978-3-85403-268-7},
  annote =	{Keywords: WCET analysis, cache analysis, pipeline analysis}
}

Keywords: WCET analysis, cache analysis, pipeline analysis
Collection: 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)
Issue Date: 2010
Date of publication: 26.11.2010

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