Volume

OASIcs, Volume 4

6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)



Thumbnail PDF

Publication Details

  • published at: 2006-08-23
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
  • ISBN: 978-3-939897-03-3
  • DBLP: db/conf/wcet/wcet2006

Access Numbers

Documents

No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 4, WCET'06, Complete Volume

Authors: Frank Mueller


Abstract
OASIcs, Volume 4, WCET'06, Complete Volume

Cite as

6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Proceedings{mueller:OASIcs.WCET.2006,
  title =	{{OASIcs, Volume 4, WCET'06, Complete Volume}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-03-3},
  ISSN =	{2190-6807},
  year =	{2012},
  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},
  URN =		{urn:nbn:de:0030-drops-35661},
  doi =		{10.4230/OASIcs.WCET.2006},
  annote =	{Keywords: Performance of Systems, Software/Program Verification}
}
Document
Front Matter
2006 WCET Preface -- Proceedings of the 6th Intl. Workshop on Worst-Case Execution Time Analysis (WCET'06)

Authors: Frank Mueller


Abstract
On the 4th of July, 2006, the 6th International Workshop onWorst-Case Execution Time Analysis (WCET'06) was held in Dresden, Germany, co-located with the 18th Euromicro International Conference on Real-Time Systems (ECRTS'06), both with support of Euromicro Technical Committee. The goal of the workshop was to bring together people from academia, tool vendors and users in industry that are interested in all aspects of timing analysis for real-time systems. The workshop provided a relaxed forum to present and discuss new ideas, new research directions, and to review current trends in this area. The workshop was based on short presentations that should encourage discussion by the attendees.

Cite as

6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{mueller:OASIcs.WCET.2006.679,
  author =	{Mueller, Frank},
  title =	{{2006 WCET Preface -- Proceedings of the 6th Intl. Workshop on Worst-Case Execution Time Analysis (WCET'06)}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{i--vii},
  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.679},
  URN =		{urn:nbn:de:0030-drops-6796},
  doi =		{10.4230/OASIcs.WCET.2006.679},
  annote =	{Keywords: WCET'06, workshop proceedings, preface}
}
Document
2006 WCET Abstracts Collection -- 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis

Authors: Frank Mueller


Abstract
On the 4th of July, 2006, the 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06) was held in Dresden, Germany, co-located with the 18th Euromicro International Conference on Real-Time Systems (ECRTS'06), both with support of Euromicro Technical Committee. The goal of the workshop was to bring together people from academia, tool vendors and users in industry that are interested in all aspects of timing analysis for real-time systems. The workshop provided a relaxed forum to present and discuss new ideas, new research directions, and to review current trends in this area. The workshop was based on short presentations that encouraged discussion by the attendees. Abstracts of the presentations are put together in this paper. Links to extended abstracts or full papers are provided. The first section directs to the preface of the proceedings.

Cite as

Frank Mueller. 2006 WCET Abstracts Collection -- 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{mueller:OASIcs.WCET.2006.680,
  author =	{Mueller, Frank},
  title =	{{2006 WCET Abstracts Collection -- 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--7},
  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.680},
  URN =		{urn:nbn:de:0030-drops-6805},
  doi =		{10.4230/OASIcs.WCET.2006.680},
  annote =	{Keywords: WCET'06, workshop proceedings, abstracts collection}
}
Document
A Definition and Classification of Timing Anomalies

Authors: Jan Reineke, Björn Wachter, Stefan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker


Abstract
Timing Anomalies are characterized by counterintuitive timing behaviour. A locally faster execution leads to an increase of the execution time of the whole program. The presence of such behaviour makes WCET analysis more difficult: It is not safe to assume local worst-case behaviour wherever the analysis encounters uncertainty. Existing definitions of Timing Anomalies are rather imprecise and intuitive in nature. Some do not cover all kinds of known Timing Anomalies. After giving an overview of related work, we give a concise formal definition of Timing Anomalies. We then begin to identify different classes of anomalies. One of these classes, coined Scheduling Timing Anomalies, coincides with previous restricted definitions.

Cite as

Jan Reineke, Björn Wachter, Stefan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A Definition and Classification of Timing Anomalies. 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{reineke_et_al:OASIcs.WCET.2006.671,
  author =	{Reineke, Jan and Wachter, Bj\"{o}rn and Thesing, Stefan and Wilhelm, Reinhard and Polian, Ilia and Eisinger, Jochen and Becker, Bernd},
  title =	{{A Definition and Classification of Timing Anomalies}},
  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.671},
  URN =		{urn:nbn:de:0030-drops-6713},
  doi =		{10.4230/OASIcs.WCET.2006.671},
  annote =	{Keywords: Timing analysis, Worst-case execution time, Timing anomalies, Scheduling Anomalies, Abstraction}
}
Document
A Framework for the Busy Time Calculation of Multiple Correlated Events

Authors: Simon Schliecker, Matthias Ivers, Jan Staschulat, and Rolf Ernst


Abstract
Many approaches to determine the response time of a task have difficulty to model tasks with multiple memory or coprocessor accesses with variable access times during the execution. As the request times highly depend on system setup and state, they can not be trivially bounded. If they are bounded by a constant value, large discrepancies between average and worst case make the focus on single worst cases vulnerable to overestimation. We present a novel approach to include remote busy time in the execution time analysis of tasks. We determine the time for multiple requests by a task efficiently and and far less conservative than previous approaches. These requests may be disturbed by other events in the system. We show how to integrate such a multiple event busy time analysis to take into account behavior of tasks that voluntarily suspend themselves and require multiple data from remote parts of the system.

Cite as

Simon Schliecker, Matthias Ivers, Jan Staschulat, and Rolf Ernst. A Framework for the Busy Time Calculation of Multiple Correlated Events. 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{schliecker_et_al:OASIcs.WCET.2006.676,
  author =	{Schliecker, Simon and Ivers, Matthias and Staschulat, Jan and Ernst, Rolf},
  title =	{{A Framework for the Busy Time Calculation of Multiple Correlated Events}},
  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.676},
  URN =		{urn:nbn:de:0030-drops-6767},
  doi =		{10.4230/OASIcs.WCET.2006.676},
  annote =	{Keywords: Response time analysis, multiple memory accesses, multiprocessor, hard real-time, busy time}
}
Document
Algorithms for Infeasible Path Calculation

Authors: Jan Gustaffson, Andreas Ermedahl, and Björn Lisper


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.

Cite as

Jan Gustaffson, Andreas Ermedahl, and Björn Lisper. Algorithms for Infeasible Path Calculation. 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{gustaffson_et_al:OASIcs.WCET.2006.667,
  author =	{Gustaffson, Jan and Ermedahl, Andreas and Lisper, Bj\"{o}rn},
  title =	{{Algorithms for Infeasible Path Calculation}},
  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.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}
}
Document
Combining Symbolic Execution and Path Enumeration in Worst-Case Execution Time Analysis

Authors: Djemai Kebbal and Pascal Sainrat


Abstract
his paper examines the problem of determining bounds on execution time of real-time programs. Execution time estimation is generally useful in real-time software verification phase, but may be used in other phases of the design and execution of real-time programs (scheduling, automatic parallelizing, etc.). This paper is devoted to the worst-case execution time (WCET) analysis. We present a static WCET analysis approach aimed to automatically extract flow information used in WCET estimate computing. The approach combines symbolic execution and path enumeration. The main idea is to avoid unfolding loops performed by symbolic execution-based approaches while providing tight and safe WCET estimate.

Cite as

Djemai Kebbal and Pascal Sainrat. Combining Symbolic Execution and Path Enumeration in Worst-Case Execution Time Analysis. 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{kebbal_et_al:OASIcs.WCET.2006.675,
  author =	{Kebbal, Djemai and Sainrat, Pascal},
  title =	{{Combining Symbolic Execution and Path Enumeration in Worst-Case Execution Time Analysis}},
  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.675},
  URN =		{urn:nbn:de:0030-drops-6753},
  doi =		{10.4230/OASIcs.WCET.2006.675},
  annote =	{Keywords: Static WCET analysis, flow analysis, symbolic execution, path enumeration, loop analysis}
}
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


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}
}
Document
Design of a WCET-Aware C Compiler

Authors: Heiko Falk, Paul Lokuciejewski, and Henrik Theiling


Abstract
This paper presents techniques to tightly integrate worst-case execution time information into a compiler framework. Currently, a tight integration of WCET information into the compilation process is strongly desired, but only some ad-hoc approaches have been reported currently. Previous publications mainly used self-written WCET estimators with very limited functionality and preciseness during compilation. A very tight integration of a high quality industry-relevant WCET analyzer into a compiler was not yet achieved up to now. This work is the first to present techniques capable of achieving such a tight coupling between a compiler and the WCET analyzer aiT. This is done by automatically translating the assembly-like contents of the compiler's low-level intermediate representation (LLIR) to aiT's exchange format CRL2. Additionally, the results produced by the WCET analyzer are automatically collected and re-imported into the compiler infrastructure. The work described in this paper is smoothly integrated into a C compiler environment for the Infineon TriCore processor. It opens up new possibilities for the design of WCET-aware optimizations in the future. The concepts for extending the compiler infrastructure are kept very general so that they are not limited to WCET information. Rather, it is possible to use our structures also for multi-objective optimization of e.g. best-case execution time (BCET) or energy dissipation.

Cite as

Heiko Falk, Paul Lokuciejewski, and Henrik Theiling. Design of a WCET-Aware C Compiler. 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{falk_et_al:OASIcs.WCET.2006.673,
  author =	{Falk, Heiko and Lokuciejewski, Paul and Theiling, Henrik},
  title =	{{Design of a WCET-Aware C Compiler}},
  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.673},
  URN =		{urn:nbn:de:0030-drops-6733},
  doi =		{10.4230/OASIcs.WCET.2006.673},
  annote =	{Keywords: WCET, compiler, multi-objective, intermediate representation, ICD-C, LLIR, CRL2, aiT}
}
Document
History-based Schemes and Implicit Path Enumeration

Authors: Claire Burguière and Christine Rochange


Abstract
The Implicit Path Enumeration Technique is often used to compute the WCET of control-intensive programs. This method does not consider execution paths as ordered sequences of basic blocks but instead as lists of basic blocks with their respective execution counts. This way of describing an execution path is adequate to compute its execution time, provided that safe individual WCETs for the blocks are known. Recently, a model for branch prediction has been integrated into WCET computation with IPET. This model generates safe estimations of the branch misprediction counts. However, we show in this paper that these counts can be over-estimated because IPET does consider simplified flow information that do not completely reflect the program semantics. We show how additional information on nested loops can be specified so that the model provides tighter WCET estimations.

Cite as

Claire Burguière and Christine Rochange. History-based Schemes and Implicit Path Enumeration. 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{burguiere_et_al:OASIcs.WCET.2006.670,
  author =	{Burgui\`{e}re, Claire and Rochange, Christine},
  title =	{{History-based Schemes and Implicit Path Enumeration}},
  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.670},
  URN =		{urn:nbn:de:0030-drops-6703},
  doi =		{10.4230/OASIcs.WCET.2006.670},
  annote =	{Keywords: WCET, IPET (Implicit Path Enumeration Technique), branch prediction}
}
Document
Loop Nest Splitting for WCET-Optimization and Predictability Improvement

Authors: Heiko Falk and Martin Schwarzer


Abstract
This paper presents the influence of the loop nest splitting source code optimization on the worst-case execution time (WCET). Loop nest splitting minimizes the number of executed if-statements in loop nests of embedded multimedia applications. Especially loops and if-statements of high-level languages are an inherent source of unpredictability and loss of precision for WCET analysis. This is caused by the fact that it is difficult to obtain safe and tight worst-case estimates of an application's flow of control through these high-level constructs. In addition, the corresponding control flow redirections expressed at the assembly level reduce predictability even more due to the complex pipeline and branch prediction behavior of modern embedded processors. The analysis techniques for loop nest splitting are based on precise mathematical models combined with genetic algorithms. On the one hand, these techniques achieve a significantly more homogeneous structure of the control flow. On the other hand, the precision of our analyses leads to the generation of very accurate high-level flow facts for loops and if-statements. The application of our implemented algorithms to three real-life multimedia benchmarks leads to average speed-ups by 25.0% - 30.1%, while WCET is reduced between 34.0% and 36.3%.

Cite as

Heiko Falk and Martin Schwarzer. Loop Nest Splitting for WCET-Optimization and Predictability Improvement. 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{falk_et_al:OASIcs.WCET.2006.674,
  author =	{Falk, Heiko and Schwarzer, Martin},
  title =	{{Loop Nest Splitting for WCET-Optimization and Predictability Improvement}},
  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.674},
  URN =		{urn:nbn:de:0030-drops-6743},
  doi =		{10.4230/OASIcs.WCET.2006.674},
  annote =	{Keywords: Loop Nest Splitting, Source Code Optimization, WCET, ACET, flow facts, polytope}
}
Document
PapaBench: a Free Real-Time Benchmark

Authors: Fadia Nemer, Hugues Cassé, Pascal Sainrat, Jean-Paul Bahsoun, and Marianne De Michiel


Abstract
This paper presents PapaBench, a free real-time benchmark and compares it with the existing benchmark suites. It is designed to be valuable for experimental works in WCET computation and may be also useful for scheduling analysis. This bench is based on the Paparazzi project that represents a real-time application, developed to be embedded on different Unmanned Aerial Vehicles (UAV). In this paper, we explain the transformation process of Paparazzi applied to obtain the PapaBench. We provide a high level AADL model, which reflects the behaviors of each component of the system and their interactions. As the source project, Paparazzi, PapaBench is delivered under the GNU license and is freely available to all researchers. Unlike other usual benchmarks widely used for WCET computation, this one is based on a real and complete real-time embedded application.

Cite as

Fadia Nemer, Hugues Cassé, Pascal Sainrat, Jean-Paul Bahsoun, and Marianne De Michiel. PapaBench: a Free Real-Time Benchmark. 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{nemer_et_al:OASIcs.WCET.2006.678,
  author =	{Nemer, Fadia and Cass\'{e}, Hugues and Sainrat, Pascal and Bahsoun, Jean-Paul and De Michiel, Marianne},
  title =	{{PapaBench: a Free Real-Time Benchmark}},
  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.678},
  URN =		{urn:nbn:de:0030-drops-6783},
  doi =		{10.4230/OASIcs.WCET.2006.678},
  annote =	{Keywords: Real-Time Benchmark, Complete Application, Worst Case Execution Time (WCET) Computation, Modeling}
}
Document
PLRU Cache Domino Effects

Authors: Christoph Berg


Abstract
Domino effects have been shown to hinder a tight prediction of worst case execution times (WCET) on real-time hardware. First investigated by Lundqvist and Stenström, domino effects caused by pipeline stalls were shows to exist in the PowerPC by Schneider. This paper extends the list of causes of domino effects by showing that the pseudo LRU (PLRU) cache replacement policy can cause unbounded effects on the WCET. PLRU is used in the PowerPC PPC755, which is widely used in embedded systems, and some x86 models.

Cite as

Christoph Berg. PLRU Cache Domino Effects. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET'06). Open Access Series in Informatics (OASIcs), Volume 4, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{berg:OASIcs.WCET.2006.672,
  author =	{Berg, Christoph},
  title =	{{PLRU Cache Domino Effects}},
  booktitle =	{6th International Workshop on Worst-Case Execution Time Analysis (WCET'06)},
  pages =	{1--3},
  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.672},
  URN =		{urn:nbn:de:0030-drops-6723},
  doi =		{10.4230/OASIcs.WCET.2006.672},
  annote =	{Keywords: Embedded systems, predictability, cache memory, PLRU, domino effects, timing anomalies}
}
Document
Towards Formally Verifiable WCET Analysis for a Functional Programming Language

Authors: Kevin Hammond, Christian Ferdinand, Reinhold Heckmann, Roy Dyckhoff, Martin Hofman, Steffen Jost, Hans-Wolfgang Loidl, Greg Michaelson, Robert Pointon, Norman Scaife, Jocelyn Sérot, and Andy Wallace


Abstract
This paper describes ongoing work aimed at the construction of formal cost models and analyses to yield verifiable guarantees of resource usage in the context of real-time embedded systems. Our work is conducted in terms of the domain-specific language Hume, a language that combines functional programming for computations with finitestate automata for specifying reactive systems. We outline an approach in which high-level information derived from source-code analysis can be combined with worst-case execution time information obtained from high quality abstract interpretation of low-level binary code.

Cite as

Kevin Hammond, Christian Ferdinand, Reinhold Heckmann, Roy Dyckhoff, Martin Hofman, Steffen Jost, Hans-Wolfgang Loidl, Greg Michaelson, Robert Pointon, Norman Scaife, Jocelyn Sérot, and Andy Wallace. Towards Formally Verifiable WCET Analysis for a Functional Programming Language. 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{hammond_et_al:OASIcs.WCET.2006.677,
  author =	{Hammond, Kevin and Ferdinand, Christian and Heckmann, Reinhold and Dyckhoff, Roy and Hofman, Martin and Jost, Steffen and Loidl, Hans-Wolfgang and Michaelson, Greg and Pointon, Robert and Scaife, Norman and S\'{e}rot, Jocelyn and Wallace, Andy},
  title =	{{Towards Formally Verifiable WCET Analysis for a Functional Programming Language}},
  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.677},
  URN =		{urn:nbn:de:0030-drops-6773},
  doi =		{10.4230/OASIcs.WCET.2006.677},
  annote =	{Keywords: Worst-case execution time, functional programming, Hume, cost model, asynchronous, finite state machine}
}

Filters


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