Search Results

Documents authored by Wilhelm, Stephan

Document
DOI: 10.4230/OASIcs.WCET.2010.36
Integrating Abstract Caches with Symbolic Pipeline Analysis

Authors: Stephan Wilhelm and Christoph Cullmann

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

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.
Cite as

Stephan Wilhelm and Christoph Cullmann. Integrating Abstract Caches with Symbolic Pipeline Analysis. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 36-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{wilhelm_et_al:OASIcs.WCET.2010.36,
  author =	{Wilhelm, Stephan and Cullmann, Christoph},
  title =	{{Integrating Abstract Caches with Symbolic Pipeline Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{36--43},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.36},
  URN =		{urn:nbn:de:0030-drops-28235},
  doi =		{10.4230/OASIcs.WCET.2010.36},
  annote =	{Keywords: WCET analysis, cache analysis, pipeline analysis}
}
Document
DOI: 10.4230/OASIcs.WCET.2007.1190
Towards Symbolic State Traversal for Efficient WCET Analysis of Abstract Pipeline and Cache Models

Authors: Stephan Wilhelm and Björn Wachter

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

Abstract
Static program analysis is a proven approach for obtaining safe and tight upper bounds on the worst-case execution time (WCET) of program tasks. It requires an analysis on the microarchitectural level, most notably pipeline and cache analysis. In our approach, the integrated pipeline and cache analysis operates on sets of possible abstract hardware states. Due to the growth of CPU complexity and the existence of timing anomalies, the analysis must handle an increasing number of possible abstract states for each program point. Symbolic methods have been proposed as a way to reduce memory consumption and improve runtime in order to keep pace with the growing hardware complexity. This paper presents the advances made since the original proposal and discusses a compact representation of abstract caches for integration with symbolic pipeline analysis.
Cite as

Stephan Wilhelm and Björn Wachter. Towards Symbolic State Traversal for Efficient WCET Analysis of Abstract Pipeline and Cache Models. 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{wilhelm_et_al:OASIcs.WCET.2007.1190,
  author =	{Wilhelm, Stephan and Wachter, Bj\"{o}rn},
  title =	{{Towards Symbolic State Traversal for Efficient WCET Analysis of Abstract Pipeline and Cache Models}},
  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.1190},
  URN =		{urn:nbn:de:0030-drops-11904},
  doi =		{10.4230/OASIcs.WCET.2007.1190},
  annote =	{Keywords: WCET, worst-case execution time, hard real-time, embedded systems, abstract interpretation, pipeline analysis, cache analysis, symbolic state traversal BDD}
}
Document
DOI: 10.4230/OASIcs.WCET.2005.814
Efficient Analysis of Pipeline Models for WCET Computation

Authors: Stephan Wilhelm

Published in: OASIcs, Volume 1, 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05) (2007)

Abstract
Worst-case execution time (WCET) prediction for modern CPU’s cannot make local assumptions about the impact of input information on the global worst-case because of the existence of timing anomalies. Therefore, static analyses on the hardware level must consider a large subset of the reachable states of the underlying hardware model. As the number of states grows, WCET prediction can become infeasible because of the increase in computation time and memory consumption. This paper presents a solution for this problem by defining the static analysis of processor pipelines for WCET computation in terms of operations on binary decision diagrams (BDD’s).
Cite as

Stephan Wilhelm. Efficient Analysis of Pipeline Models for WCET Computation. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 37-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{wilhelm:OASIcs.WCET.2005.814,
  author =	{Wilhelm, Stephan},
  title =	{{Efficient Analysis of Pipeline Models for WCET Computation}},
  booktitle =	{5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
  pages =	{37--40},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-24-8},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{1},
  editor =	{Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.814},
  URN =		{urn:nbn:de:0030-drops-8149},
  doi =		{10.4230/OASIcs.WCET.2005.814},
  annote =	{Keywords: Worst-case execution time prediction, pipeline analysis, timing anomalies, binary decision diagrams}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact