12 Search Results for "Puschner, Peter"


Document
Constant-Loop Dominators for Single-Path Code Optimization

Authors: Emad Jacob Maroun, Martin Schoeberl, and Peter Puschner

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)


Abstract
Single-path code is a code generation technique specifically designed for real-time systems. It guarantees that programs execute the same instruction sequence regardless of runtime conditions. Single-path code uses loop bounds to ensure all loops iterate a fixed number of times equal to their upper loop bound. When the lower and upper bounds are equal, the loop must iterate the same number of times, which we call a constant loop. In this paper, we present the constant-loop dominance relation on control-flow graphs. It is a variation of the traditional dominance relation that considers constant loops to find basic blocks that are always executed the same number of times. Using this relation, we present an optimization that reduces the code needed to manage single-path code. Our evaluation shows significant performance improvements, with one example of up to 90%, with mostly minor effects on code size.

Cite as

Emad Jacob Maroun, Martin Schoeberl, and Peter Puschner. Constant-Loop Dominators for Single-Path Code Optimization. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{maroun_et_al:OASIcs.WCET.2023.7,
  author =	{Maroun, Emad Jacob and Schoeberl, Martin and Puschner, Peter},
  title =	{{Constant-Loop Dominators for Single-Path Code Optimization}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{7:1--7:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.7},
  URN =		{urn:nbn:de:0030-drops-184361},
  doi =		{10.4230/OASIcs.WCET.2023.7},
  annote =	{Keywords: single-path, dominators, algorithms, optimization, control-flow graph}
}
Document
Vicuna: A Timing-Predictable RISC-V Vector Coprocessor for Scalable Parallel Computation

Authors: Michael Platzer and Peter Puschner

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)


Abstract
In this work, we present Vicuna, a timing-predictable vector coprocessor. A vector processor can be scaled to satisfy the performance requirements of massively parallel computation tasks, yet its timing behavior can remain simple enough to be efficiently analyzable. Therefore, vector processors are promising for highly parallel real-time applications, such as advanced driver assistance systems and autonomous vehicles. Vicuna has been specifically tailored to address the needs of real-time applications. It features predictable and repeatable timing behavior and is free of timing anomalies, thus enabling effective and tight worst-case execution time (WCET) analysis while retaining the performance and efficiency commonly seen in other vector processors. We demonstrate our architecture’s predictability, scalability, and performance by running a set of benchmark applications on several configurations of Vicuna synthesized on a Xilinx 7 Series FPGA with a peak performance of over 10 billion 8-bit operations per second, which is in line with existing non-predictable soft vector-processing architectures.

Cite as

Michael Platzer and Peter Puschner. Vicuna: A Timing-Predictable RISC-V Vector Coprocessor for Scalable Parallel Computation. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{platzer_et_al:LIPIcs.ECRTS.2021.1,
  author =	{Platzer, Michael and Puschner, Peter},
  title =	{{Vicuna: A Timing-Predictable RISC-V Vector Coprocessor for Scalable Parallel Computation}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.1},
  URN =		{urn:nbn:de:0030-drops-139323},
  doi =		{10.4230/LIPIcs.ECRTS.2021.1},
  annote =	{Keywords: Real-time Systems, Vector Processors, RISC-V}
}
Document
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-dev.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
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-dev.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
Improving System-Level Verification of SystemC Models with SPIN

Authors: Martin Elshuber, Susanne Kandl, and Peter Puschner

Published in: OASIcs, Volume 31, 1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013)


Abstract
SystemC is a de-facto industry standard for developing, modelling, and simulating embedded systems. As embedded systems become more and more integrated into many aspects of human lives (e.g., transportation, surveillance systems, ...), failures of embedded systems might cause dangerous hazards to individuals or groups. Guaranteeing safety of such systems makes formal verification crucial. In this paper we present a novel approach for verifying SystemC models with SPIN. Focusing on system-level verification we reuse compiled and executable code from the original model and embed it into the verifier generated by SPIN. In contrast to most other approaches, which require a complete model transformation, in our approach the transformation focuses only on the relevant parts of the model while leaving functional blocks untransformed. Our technique aims at reducing the state vector size managed by the verifier of SPIN, at improving state exploration performance by avoiding unnecessary model transformation steps, and at concentrating on verifying properties that emerge from the composition of multiple functional units.

Cite as

Martin Elshuber, Susanne Kandl, and Peter Puschner. Improving System-Level Verification of SystemC Models with SPIN. In 1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013). Open Access Series in Informatics (OASIcs), Volume 31, pp. 74-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{elshuber_et_al:OASIcs.FSFMA.2013.74,
  author =	{Elshuber, Martin and Kandl, Susanne and Puschner, Peter},
  title =	{{Improving System-Level Verification of SystemC Models with SPIN}},
  booktitle =	{1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013)},
  pages =	{74--79},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-56-9},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{31},
  editor =	{Choppy, Christine and Sun, Jun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FSFMA.2013.74},
  URN =		{urn:nbn:de:0030-drops-40915},
  doi =		{10.4230/OASIcs.FSFMA.2013.74},
  annote =	{Keywords: SystemC, SPIN, Promela, System-Level Verification}
}
Document
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-dev.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}
}
Document
A Code Policy Guaranteeing Fully Automated Path Analysis

Authors: Benedikt Huber and Peter Puschner

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


Abstract
Calculating the worst-case execution time (WCET) of real-time tasks is still a tedious job. Programmers are required to provide additional information on the program flow, analyzing subtle, context dependent loop bounds manually. In this paper, we propose to restrict written and generated code to the class of programs with input-data independent loop counters. The proposed policy builds on the ideas of single-path code, but only requires partial input-data independence. It is always possible to find precise loop bounds for these programs, using an efficient variant of abstract execution. The systematic construction of tasks following the policy is facilitated by embedding knowledge on input-data dependence in function interfaces and types. Several algorithms and benchmarks are analyzed to show that this restriction is indeed a good candidate for removing the need for manual annotations.

Cite as

Benedikt Huber and Peter Puschner. A Code Policy Guaranteeing Fully Automated Path Analysis. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 77-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{huber_et_al:OASIcs.WCET.2010.77,
  author =	{Huber, Benedikt and Puschner, Peter},
  title =	{{A Code Policy Guaranteeing Fully Automated Path Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{77--88},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.77},
  URN =		{urn:nbn:de:0030-drops-28274},
  doi =		{10.4230/OASIcs.WCET.2010.77},
  annote =	{Keywords: WCET analysis, path analysis, single-path code, SSA form}
}
Document
Teaching WCET Analysis in Academia and Industry: A Panel Discussion

Authors: Niklas Holsti, Guillem Bernat, Christian Ferdinand, Peter Puschner, and Reinhard Wilhelm

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)


Abstract
The last item on the programme of the WCET'09 workshop was a panel discussion on "Teaching WCET analysis in academia and industry". The panelists presented three position statements to initiate a general discussion of the subject. This summary contains the panelists' position statements and notes of the panel discussion.

Cite as

Niklas Holsti, Guillem Bernat, Christian Ferdinand, Peter Puschner, and Reinhard Wilhelm. Teaching WCET Analysis in Academia and Industry: A Panel Discussion. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{holsti_et_al:OASIcs.WCET.2009.2278,
  author =	{Holsti, Niklas and Bernat, Guillem and Ferdinand, Christian and Puschner, Peter and Wilhelm, Reinhard},
  title =	{{Teaching WCET Analysis in Academia and Industry: A Panel Discussion}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2278},
  URN =		{urn:nbn:de:0030-drops-22780},
  doi =		{10.4230/OASIcs.WCET.2009.2278},
  annote =	{Keywords: WCET analysis, teaching, courses}
}
Document
Is Chip-Multiprocessing the End of Real-Time Scheduling?

Authors: Martin Schoeberl and Peter Puschner

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)


Abstract
Chip-multiprocessing is considered the future path for performance enhancements in computer architecture. Eight processor cores on a single chip are state-of-the art and several hundreds of cores on a single die are expected in the near future. General purpose computing is facing the challenge how to use the many cores. However, in embedded real-time systems thread-level parallelism is naturally used. In this paper we assume a system where we can dedicate a single core for each thread. In that case classic real-time scheduling disappears. However, the threads, running on their dedicated core, still compete for a shared resource, the main memory. A time-sliced memory arbiter is used to avoid timing influences between threads. The schedule of the arbiter is integrated into the worst-case execution time (WCET) analysis. The WCET results are used as a feedback to regenerate the arbiter schedule. Therefore, we schedule memory access instead of CPU time.

Cite as

Martin Schoeberl and Peter Puschner. Is Chip-Multiprocessing the End of Real-Time Scheduling?. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.WCET.2009.2288,
  author =	{Schoeberl, Martin and Puschner, Peter},
  title =	{{Is Chip-Multiprocessing the End of Real-Time Scheduling?}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2288},
  URN =		{urn:nbn:de:0030-drops-22885},
  doi =		{10.4230/OASIcs.WCET.2009.2288},
  annote =	{Keywords: WCET analysis, multicore, chip multiprocessing, memory access scheduling}
}
Document
On Composable System Timing, Task Timing, and WCET Analysis

Authors: Peter Puschner and Martin Schoeberl

Published in: OASIcs, Volume 8, 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08) (2008)


Abstract
The complexity of hardware and software architectures used in today's embedded systems make a hierarchical, composable timing analysis impossible. This paper describes the source of this complexity in terms of mechanisms and side effects that determine variations in the timing of single tasks and entire applications. Based on these observations, the paper proposes strategies to reduce the complexity. It shows the positive effects of these strategies on the timing of tasks and on WCET analysis.

Cite as

Peter Puschner and Martin Schoeberl. On Composable System Timing, Task Timing, and WCET Analysis. In 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08). Open Access Series in Informatics (OASIcs), Volume 8, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{puschner_et_al:OASIcs.WCET.2008.1662,
  author =	{Puschner, Peter and Schoeberl, Martin},
  title =	{{On Composable System Timing, Task Timing, and WCET Analysis}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Kirner, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2008.1662},
  URN =		{urn:nbn:de:0030-drops-16622},
  doi =		{10.4230/OASIcs.WCET.2008.1662},
  annote =	{Keywords: Real-time systems, timing analysis, WCET analysis, predictable timing, composability}
}
Document
Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis

Authors: Raimund Kirner and Peter Puschner

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


Abstract
Tools for worst-case execution time (WCET) analysis request several code annotations from the user. However, most of them could be avoided or being annotated more comfortably if the compilers would support WCET analysis. This paper provides a clear categorization of code annotations for WCET analysis and discusses the positive impact on code annotations a compiler-support on WCET analysis would have.

Cite as

Raimund Kirner and Peter Puschner. Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis. In 5th International Workshop on Worst-Case Execution Time Analysis (WCET'05). Open Access Series in Informatics (OASIcs), Volume 1, pp. 41-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{kirner_et_al:OASIcs.WCET.2005.815,
  author =	{Kirner, Raimund and Puschner, Peter},
  title =	{{Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis}},
  booktitle =	{5th International Workshop on Worst-Case Execution Time Analysis (WCET'05)},
  pages =	{41--45},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2005.815},
  URN =		{urn:nbn:de:0030-drops-8154},
  doi =		{10.4230/OASIcs.WCET.2005.815},
  annote =	{Keywords: Worst-Case Execution Time, WCET, Code Annotations, Path Information, Compiler, Real-Time}
}
Document
Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-Lookup

Authors: Raimund Kirner, Markus Grössing, and Peter Puschner

Published in: OASIcs, Volume 4, 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) (2006)


Abstract
Trigonometric functions are often needed in embedded real-time software. To fulfill concrete resource demands, different implementation strategies of trigonometric functions are possible. In this paper we analyze the resource demands of iterative calculations compared to other implementation strategies, using the trigonometric functions as a case study. By analyzing the worst-case execution time (WCET) of the different calculation techniques of trigonometric functions we got the surprising result that the WCET of iterative calculations is quite competitive to alternative calculation techniques, while their economics on memory demand is far superior. Finally, a discussion of the general applicability of the obtained results is given as a design guide for embedded software.

Cite as

Raimund Kirner, Markus Grössing, and Peter Puschner. Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-Lookup. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{kirner_et_al:OASIcs.WCET.2006.669,
  author =	{Kirner, Raimund and Gr\"{o}ssing, Markus and Puschner, Peter},
  title =	{{Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-Lookup}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{4},
  editor =	{Mueller, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2006.669},
  URN =		{urn:nbn:de:0030-drops-6694},
  doi =		{10.4230/OASIcs.WCET.2006.669},
  annote =	{Keywords: Worst-case execution time, WCET analysis, table lookup, iterative computation, Taylor series, resource demands}
}
  • Refine by Author
  • 12 Puschner, Peter
  • 4 Schoeberl, Martin
  • 3 Huber, Benedikt
  • 3 Prokesch, Daniel
  • 2 Kirner, Raimund
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time system architecture
  • 1 Computer systems organization → Real-time systems
  • 1 General and reference → Performance
  • 1 Theory of computation → Control primitives
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 5 WCET analysis
  • 2 Compiler
  • 2 single-path code
  • 1 Code Annotations
  • 1 Graph Transformation
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 2 2009
  • 1 2006
  • 1 2007
  • 1 2008
  • 1 2010
  • Show More...

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