DROPS

Document

DOI: 10.4230/OASIcs.WCET.2017.2

Best Practice for Caching of Single-Path Code

Authors: Martin Schoeberl, Bekim Cilku, Daniel Prokesch, and Peter Puschner

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract

Single-path code has some unique properties that make it interesting to explore different caching and prefetching alternatives for the stream of instructions. In this paper, we explore different cache organizations and how they perform with single-path code.

Cite as

Martin Schoeberl, Bekim Cilku, Daniel Prokesch, and Peter Puschner. Best Practice for Caching of Single-Path Code. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.WCET.2017.2,
  author =	{Schoeberl, Martin and Cilku, Bekim and Prokesch, Daniel and Puschner, Peter},
  title =	{{Best Practice for Caching of Single-Path Code}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{2:1--2:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Reineke, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.2},
  URN =		{urn:nbn:de:0030-drops-73050},
  doi =		{10.4230/OASIcs.WCET.2017.2},
  annote =	{Keywords: single-path code, method cache, prefetching}
}

Document

DOI: 10.4230/OASIcs.WCET.2014.103

Towards Automated Generation of Time-Predictable Code

Authors: Daniel Prokesch, Benedikt Huber, and Peter Puschner

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract

Knowledge of the worst-case execution time of software components is essential in safety-critical hard real-time systems. The analysis thereof is not trivial as the execution time depends on many factors, including the underlying hardware platform, the program structure, and the code produced by the compiler. Often, the execution time is variable and highly sensitive to the input data the program has to process. This paper presents a code transformation applicable in a compiler backend that produces time-predictable code. The resulting code contains a single input-data independent execution path, in order to obtain programs of stable timing behaviour. The transformation technique has been validated by applying it on a number of benchmarks. Experiments show a reduction of execution time variability, at acceptable costs for the single execution path.

Cite as

Daniel Prokesch, Benedikt Huber, and Peter Puschner. Towards Automated Generation of Time-Predictable Code. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 103-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{prokesch_et_al:OASIcs.WCET.2014.103,
  author =	{Prokesch, Daniel and Huber, Benedikt and Puschner, Peter},
  title =	{{Towards Automated Generation of Time-Predictable Code}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{103--112},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014.103},
  URN =		{urn:nbn:de:0030-drops-46090},
  doi =		{10.4230/OASIcs.WCET.2014.103},
  annote =	{Keywords: Single-Path, Graph Transformation, Predictable Code, Compiler}
}

Document

DOI: 10.4230/OASIcs.WCET.2012.91

A Formal Framework for Precise Parametric WCET Formulas

Authors: Benedikt Huber, Daniel Prokesch, and Peter Puschner

Published in: OASIcs, Volume 23, 12th International Workshop on Worst-Case Execution Time Analysis (2012)

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.

Cite as

Benedikt Huber, Daniel Prokesch, and Peter Puschner. A Formal Framework for Precise Parametric WCET Formulas. In 12th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 23, pp. 91-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{huber_et_al:OASIcs.WCET.2012.91,
  author =	{Huber, Benedikt and Prokesch, Daniel and Puschner, Peter},
  title =	{{A Formal Framework for Precise Parametric WCET Formulas}},
  booktitle =	{12th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{91--102},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-41-5},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{23},
  editor =	{Vardanega, Tullio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2012.91},
  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}
}

Search Results

Documents authored by Prokesch, Daniel

Best Practice for Caching of Single-Path Code

Abstract

Cite as

Towards Automated Generation of Time-Predictable Code

Abstract

Cite as

A Formal Framework for Precise Parametric WCET Formulas

Abstract

Cite as

Thanks for your feedback!

Could not send message