9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)

Document

Complete Volume

DOI: 10.4230/OASIcs.WCET.2009

OASIcs, Volume 10, WCET'09, Complete Volume

Authors: Niklas Holsti

Abstract

OASIcs, Volume 10, WCET'09, Complete Volume

Cite as

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

Copy BibTex To Clipboard

@Proceedings{holsti:OASIcs.WCET.2009,
  title =	{{OASIcs, Volume 10, WCET'09, Complete Volume}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009},
  URN =		{urn:nbn:de:0030-drops-35729},
  doi =		{10.4230/OASIcs.WCET.2009},
  annote =	{Keywords: Performance of Systems, Software/Program Verification}
}

Document

Front Matter

DOI: 10.4230/OASIcs.WCET.2009.2295

WCET 2009 -- Preface to 9th International Workshop on Worst-Case Execution Time Analysis

Authors: Niklas Holsti

Abstract

On June 30, 2009, thirty-five people from nine countries and three continents met in Trinity College, Dublin, to hold the 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09, http://www.artist-embedded.org/artist/WCET-2009.html). The workshop was organised as a satellite event of the 21st Euromicro Conference on Real-Time Systems (ECRTS'09, http://ecrts09.dsg.cs.tcd.ie). The final proceedings here presented contain the workshop papers as updated in response to the discussion at the workshop, the abstract of the invited talk by prof. Petru Eles, and a summary of the panel discussion that concluded the workshop. The slide presentations can be retrieved from the workshop web-site referenced above.

Cite as

9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. i-iv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{holsti:OASIcs.WCET.2009.2295,
  author =	{Holsti, Niklas},
  title =	{{WCET 2009 -- Preface to 9th International Workshop on Worst-Case Execution Time Analysis}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{i--iv},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2295},
  URN =		{urn:nbn:de:0030-drops-22958},
  doi =		{10.4230/OASIcs.WCET.2009.2295},
  annote =	{Keywords: Worst-case execution time, WCET analysis, real-time systems, scheduling}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2278

Teaching WCET Analysis in Academia and Industry: A Panel Discussion

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

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

DOI: 10.4230/OASIcs.WCET.2009.2290

A Generic Framework for Blackbox Components in WCET Computation

Authors: Clément Ballabriga, Hugues Cassé, and Marianne De Michiel

Abstract

Validation of embedded hard real-time systems requires the computation of the Worst Case Execution Time (WCET). Although these systems make more and more use of Components Off The Shelf (COTS), the current WCET computation methods are usually applied to whole programs: these analysis methods require access to the whole system code, that is incompatible with the use of COTS. In this paper, after discussing the specific cases of the loop bounds estimation and the instruction cache analysis, we show in a generic way how static analysis involved in WCET computation can be pre-computed on COTS in order to obtain component partial results. These partial results can be distributed with the COTS, in order to compute the WCET in the context of a full application. We describe also the information items to include in the partial result, and we propose an XML exchange format to represent these data. Additionally, we show that the partial analysis enables us to reduce the analysis time while introducing very little pessimism.

Cite as

Clément Ballabriga, Hugues Cassé, and Marianne De Michiel. A Generic Framework for Blackbox Components in WCET Computation. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ballabriga_et_al:OASIcs.WCET.2009.2290,
  author =	{Ballabriga, Cl\'{e}ment and Cass\'{e}, Hugues and De Michiel, Marianne},
  title =	{{A Generic Framework for Blackbox Components in WCET Computation}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--12},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2290},
  URN =		{urn:nbn:de:0030-drops-22907},
  doi =		{10.4230/OASIcs.WCET.2009.2290},
  annote =	{Keywords: WCET analysis, components, COTS, XML}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2279

ALF - A Language for WCET Flow Analysis

Authors: Jan Gustafsson, Andreas Ermedahl, Björn Lisper, Christer Sandberg, and Linus Källberg

Abstract

Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is the flow analysis, which derives bounds on the number of times different code entities can be executed. Examples of flow information derived by a flow analysis are loop bounds and infeasible paths. Flow analysis can be performed on source code, intermediate code, or binary code: for the latter, there is a proliferation of instruction sets. Thus, flow analysis must deal with many code formats. However, the basic flow analysis techniques are more or less the same regardless of the code format. Thus, an interesting option is to define a common code format for flow analysis, which also allows for easy translation from the other formats. Flow analyses for this common format will then be portable, in principle supporting all types of code formats which can be translated to this format. Further, a common format simplifies the development of flow analyses, since only one specific code format needs to be targeted. This paper presents such a common code format, the ALF language (ARTIST2 Language for WCET Flow Analysis).

Cite as

Jan Gustafsson, Andreas Ermedahl, Björn Lisper, Christer Sandberg, and Linus Källberg. ALF - A Language for WCET Flow Analysis. 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{gustafsson_et_al:OASIcs.WCET.2009.2279,
  author =	{Gustafsson, Jan and Ermedahl, Andreas and Lisper, Bj\"{o}rn and Sandberg, Christer and K\"{a}llberg, Linus},
  title =	{{ALF - A Language for WCET Flow Analysis}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2279},
  URN =		{urn:nbn:de:0030-drops-22791},
  doi =		{10.4230/OASIcs.WCET.2009.2279},
  annote =	{Keywords: WCET analysis, flow analysis, ALF WCET analysis, flow analysis, ALF}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2285

Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions

Authors: Claire Burguière, Jan Reineke, and Sebastian Altmeyer

Abstract

In preemptive real-time systems, scheduling analyses need - in addition to the worst-case execution time - the context-switch cost. In case of preemption, the preempted and the preempting task may interfere on the cache memory. These interferences lead to additional reloads in the preempted task. The delay due to these reloads is referred to as the cache-related preemption delay (CRPD). The CRPD constitutes a large part of the context-switch cost. In this article, we focus on the computation of upper bounds on the CRPD based on the concepts of useful cache blocks (UCBs) and evicting cache blocks (ECBs). We explain how these concepts can be used to bound the CRPD in case of direct-mapped caches. Then we consider set-associative caches with LRU, FIFO, and PLRU replacement. We show potential pitfalls when using UCBs and ECBs to bound the CRPD in case of LRU and demonstrate that neither UCBs nor ECBs can be used to bound the CRPD in case of FIFO and PLRU. Finally, we sketch a new approach to circumvent these limitations by using the concept of relative competitiveness.

Cite as

Claire Burguière, Jan Reineke, and Sebastian Altmeyer. Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions. 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{burguiere_et_al:OASIcs.WCET.2009.2285,
  author =	{Burgui\`{e}re, Claire and Reineke, Jan and Altmeyer, Sebastian},
  title =	{{Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2285},
  URN =		{urn:nbn:de:0030-drops-22856},
  doi =		{10.4230/OASIcs.WCET.2009.2285},
  annote =	{Keywords: WCET analysis, caches, set-associative, preemption, CRPD}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2281

Comparison of Implicit Path Enumeration and Model Checking Based WCET Analysis

Authors: Benedikt Huber and Martin Schoeberl

Abstract

In this paper, we present our new worst-case execution time (WCET) analysis tool for Java processors, supporting both implicit path enumeration (IPET) and model checking based execution time estimation. Even though model checking is significantly more expensive than IPET, it simplifies accurate modeling of pipelines and caches. Experimental results using the UPPAAL model checker indicate that model checking is fast enough for typical tasks in embedded applications, though large loop bounds may lead to long analysis times. To obtain a tool which is able to cope with larger applications, we recommend to use model checking for more important code fragments, and combine it with the IPET approach.

Cite as

Benedikt Huber and Martin Schoeberl. Comparison of Implicit Path Enumeration and Model Checking Based WCET Analysis. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{huber_et_al:OASIcs.WCET.2009.2281,
  author =	{Huber, Benedikt and Schoeberl, Martin},
  title =	{{Comparison of Implicit Path Enumeration and Model Checking Based WCET Analysis}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--12},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2281},
  URN =		{urn:nbn:de:0030-drops-22810},
  doi =		{10.4230/OASIcs.WCET.2009.2281},
  annote =	{Keywords: WCET analysis, model checking, IPET, Java, JOP, UPPAAL}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2292

Extending the Path Analysis Technique to Obtain a Soft WCET

Authors: Paul Keim, Amanda Noyes, Andrew Ferguson, Joshua Neal, and Christopher Healy

Abstract

This paper discusses an efficient approach to statically compute a WCET that is "soft" rather than "hard". The goal of most timing analysis is to determine a guaranteed WCET; however this execution time may be far above the actual distribution of observed execution times. A WCET estimate that bounds the execution time 99% of the time may be more useful for a designer in a soft real-time environment. This paper discusses an approach to measure the execution time distribution by a hardware simulator, and a path-based timing analysis approach to derive a static estimation of this same distribution. The technique can find a soft WCET for loops having any number of paths.

Cite as

Paul Keim, Amanda Noyes, Andrew Ferguson, Joshua Neal, and Christopher Healy. Extending the Path Analysis Technique to Obtain a Soft WCET. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{keim_et_al:OASIcs.WCET.2009.2292,
  author =	{Keim, Paul and Noyes, Amanda and Ferguson, Andrew and Neal, Joshua and Healy, Christopher},
  title =	{{Extending the Path Analysis Technique to Obtain a Soft WCET}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--9},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2292},
  URN =		{urn:nbn:de:0030-drops-22922},
  doi =		{10.4230/OASIcs.WCET.2009.2292},
  annote =	{Keywords: WCET analysis, soft real-time, path-based, distribution}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2282

From Trusted Annotations to Verified Knowledge

Authors: Adrian Prantl, Jens Knoop, Raimund Kirner, Albrecht Kadlec, and Markus Schordan

Abstract

WCET analyzers commonly rely on user-provided annotations such as loop bounds, recursion depths, region- and program constants. This reliance on user-provided annotations has an important drawback. It introduces a Trusted Annotation Basis into WCET analysis without any guarantee that the user-provided annotations are safe, let alone sharp. Hence, safety and accuracy of a WCET analysis cannot be formally established. In this paper we propose a uniform approach, which reduces the trusted annotation base to a minimum, while simultaneously yielding sharper (tighter) time bounds. Fundamental to our approach is to apply model checking in concert with other more inexpensive program analysis techniques, and the coordinated application of two algorithms for Binary Tightening and Binary Widening, which control the application of the model checker and hence the computational costs of the approach. Though in this paper we focus on the control of model checking by Binary Tightening and Widening, this is embedded into a more general approach in which we apply an array of analysis methods of increasing power and computational complexity for proving or disproving relevant time bounds of a program. First practical experiences using the sample programs of the Mälardalen benchmark suite demonstrate the usefulness of the overall approach. In fact, for most of these benchmarks we were able to empty the trusted annotation base completely, and to tighten the computed WCET considerably.

Cite as

Adrian Prantl, Jens Knoop, Raimund Kirner, Albrecht Kadlec, and Markus Schordan. From Trusted Annotations to Verified Knowledge. 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{prantl_et_al:OASIcs.WCET.2009.2282,
  author =	{Prantl, Adrian and Knoop, Jens and Kirner, Raimund and Kadlec, Albrecht and Schordan, Markus},
  title =	{{From Trusted Annotations to Verified Knowledge}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2282},
  URN =		{urn:nbn:de:0030-drops-22828},
  doi =		{10.4230/OASIcs.WCET.2009.2282},
  annote =	{Keywords: WCET analysis, annotations, binary tightening, binary widening, model checking, CBMC}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2288

Is Chip-Multiprocessing the End of Real-Time Scheduling?

Authors: Martin Schoeberl and Peter Puschner

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

DOI: 10.4230/OASIcs.WCET.2009.2284

Making Dynamic Memory Allocation Static to Support WCET Analysis

Authors: Jörg Herter and Jan Reineke

Abstract

Current worst-case execution time (WCET) analyses do not support programs using dynamic memory allocation. This is mainly due to the unpredictable cache performance when standard memory allocators are used. We present algorithms to compute a static allocation for programs using dynamic memory allocation. Our algorithms strive to produce static allocations that lead to minimal WCET times in a subsequent WCET analyses. Preliminary experiments suggest that static allocations for hard real-time applications can be computed at reasonable computational costs.

Cite as

Jörg Herter and Jan Reineke. Making Dynamic Memory Allocation Static to Support WCET Analysis. 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{herter_et_al:OASIcs.WCET.2009.2284,
  author =	{Herter, J\"{o}rg and Reineke, Jan},
  title =	{{Making Dynamic Memory Allocation Static to Support WCET Analysis}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2284},
  URN =		{urn:nbn:de:0030-drops-22846},
  doi =		{10.4230/OASIcs.WCET.2009.2284},
  annote =	{Keywords: WCET analysis, dynamic memory allocation, heap}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2287

Predictable Implementation of Real-Time Applications on Multiprocessor Systems on Chip

Authors: Petru Eles

Abstract

Worst-case execution time (WCET) analysis and, in general, the predictability of real-time applications implemented on multiprocessor systems has been addressed only in very restrictive and particular contexts. One important aspect that makes the analysis difficult is the estimation of the system's communication behavior. The traffic on the bus does not solely originate from data transfers due to data dependencies between tasks, but is also affected by memory transfers as result of cache misses. As opposed to the analysis performed for a single processor system, where the cache miss penalty is constant, in a multiprocessor system each cache miss has a variable penalty, depending on the bus contention. This affects the tasks' WCET which, however, is needed in order to perform system scheduling. At the same time, the WCET depends on the system schedule due to the bus interference. In this context, we present an approach to worst-case execution time analysis and system scheduling for real-time applications implemented on multiprocessor SoC architectures. We will also address the bus scheduling policy and its optimization, which are of huge importance for the performance of such predictable multiprocessor applications.

Cite as

Petru Eles. Predictable Implementation of Real-Time Applications on Multiprocessor Systems on Chip. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{eles:OASIcs.WCET.2009.2287,
  author =	{Eles, Petru},
  title =	{{Predictable Implementation of Real-Time Applications on Multiprocessor Systems on Chip}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--1},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2287},
  URN =		{urn:nbn:de:0030-drops-22875},
  doi =		{10.4230/OASIcs.WCET.2009.2287},
  annote =	{Keywords: WCET analysis, multiprocessor, SoC, system scheduling}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2289

Sound and Efficient WCET Analysis in the Presence of Timing Anomalies

Authors: Jan Reineke and Rathijit Sen

Abstract

Worst-Case-Execution-Time (WCET) analysis computes upper bounds on the execution time of a program on a given hardware platform. Abstractions employed for static timing analysis can lead to non-determinism that may require the analyzer to evaluate an exponential number of choices even for straight-line code. Pruning the search space is potentially unsafe because of "timing anomalies" where local worst-case choices may not lead to the global worst-case scenario. In this paper we present an approach towards more efficient WCET analysis that uses precomputed information to safely discard analysis states.

Cite as

Jan Reineke and Rathijit Sen. Sound and Efficient WCET Analysis in the Presence of Timing Anomalies. 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{reineke_et_al:OASIcs.WCET.2009.2289,
  author =	{Reineke, Jan and Sen, Rathijit},
  title =	{{Sound and Efficient WCET Analysis in the Presence of Timing Anomalies}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2289},
  URN =		{urn:nbn:de:0030-drops-22894},
  doi =		{10.4230/OASIcs.WCET.2009.2289},
  annote =	{Keywords: WCET analysis, timing anomalies, domino effect}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2291

Statistical-Based WCET Estimation and Validation

Authors: Jeffery Hansen, Scott Hissam, and Gabriel A. Moreno

Abstract

In this paper we present a measurement-based approach that produces both a WCET (Worst Case Execution Time) estimate, and a prediction of the probability that a future execution time will exceed our estimate. Our statistical-based approach uses extreme value theory to build a model of the tail behavior of the measured execution time value. We validate our approach using an industrial data set comprised of over 150 sampled components and nearly 200 million sample execution times. Each trace is divided into two segments, with one used to make the WCET estimate, and the second used check our prediction of the fraction of future execution time samples that exceed our WCET estimate. We show that compared to WCET estimates derived from the worst-case observed time, our WCET estimates significantly improve the ability to predict the probability that our WCET estimate is exceeded.

Cite as

Jeffery Hansen, Scott Hissam, and Gabriel A. Moreno. Statistical-Based WCET Estimation and Validation. 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{hansen_et_al:OASIcs.WCET.2009.2291,
  author =	{Hansen, Jeffery and Hissam, Scott and Moreno, Gabriel A.},
  title =	{{Statistical-Based WCET Estimation and Validation}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2291},
  URN =		{urn:nbn:de:0030-drops-22916},
  doi =		{10.4230/OASIcs.WCET.2009.2291},
  annote =	{Keywords: WCET analysis, measurement-based, extreme value theory, EVT, Gumbel}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2283

WCET Analysis of Multi-Level Set-Associative Data Caches

Authors: Benjamin Lesage, Damien Hardy, and Isabelle Puaut

Abstract

Nowadays, the presence of cache hierarchies tends to be a common trend in processor architectures, even in hardware for real-time embedded systems. Caches are used to fill the gap between the processor and the main memory, reducing access times based on spatial and temporal locality properties of tasks. Cache hierarchies are going even further however at the price of increased complexity. In this paper, we present a safe static data cache analysis method for hierarchies of non-inclusive caches. Using this method, we show that considering the cache hierarchy in the context of data caches allows tighter estimates of the worst case execution time than when considering only the first cache level. We also present considerations about the update policy for data caches.

Cite as

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. WCET Analysis of Multi-Level Set-Associative Data Caches. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{lesage_et_al:OASIcs.WCET.2009.2283,
  author =	{Lesage, Benjamin and Hardy, Damien and Puaut, Isabelle},
  title =	{{WCET Analysis of Multi-Level Set-Associative Data Caches}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--12},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2283},
  URN =		{urn:nbn:de:0030-drops-22837},
  doi =		{10.4230/OASIcs.WCET.2009.2283},
  annote =	{Keywords: WCET analysis, data cache, multi-level, set-associative}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2286

WCET-aware Software Based Cache Partitioning for Multi-Task Real-Time Systems

Authors: Sascha Plazar, Paul Lokuciejewski, and Peter Marwedel

Abstract

Caches are a source of unpredictability since it is very difficult to predict if a memory access results in a cache hit or miss. In systems running multiple tasks steered by a preempting scheduler, it is even impossible to determine the cache behavior since interrupt-driven schedulers lead to unknown points of time for context switches. Partitioned caches are already used in multi-task environments to increase the cache hit ratio by avoiding mutual eviction of tasks from the cache. For real-time systems, the upper bound of the execution time is one of the most important metrics, called the Worst-Case Execution Time (WCET). In this paper, we use partitioning of instruction caches as a technique to achieve tighter WCET estimations since tasks can not be evicted from their partition by other tasks. We propose a novel WCET-aware cache partitioning algorithm, which determines the optimal partition size for each task with focus on decreasing the system's WCET for a given set of possible partition sizes. Employing this algorithm, we are able to decrease the WCET depending on the number of tasks in a set by up to 34%. On average, reductions between 12% and 19% can be achieved.

Cite as

Sascha Plazar, Paul Lokuciejewski, and Peter Marwedel. WCET-aware Software Based Cache Partitioning for Multi-Task Real-Time Systems. 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{plazar_et_al:OASIcs.WCET.2009.2286,
  author =	{Plazar, Sascha and Lokuciejewski, Paul and Marwedel, Peter},
  title =	{{WCET-aware Software Based Cache Partitioning for Multi-Task Real-Time Systems}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2286},
  URN =		{urn:nbn:de:0030-drops-22860},
  doi =		{10.4230/OASIcs.WCET.2009.2286},
  annote =	{Keywords: WCET analysis, cache partitioning}
}

Document

DOI: 10.4230/OASIcs.WCET.2009.2280

Worst-Case Timing Estimation and Architecture Exploration in Early Design Phases

Authors: Stefana Nenova and Daniel Kästner

Abstract

Selecting the right computing hardware and configuration at the beginning of an industrial project is an important and highly risky task, which is usually done without much tool support, based on experience gathered from previous projects. We present TimingExplorer - a tool to assist in the exploration of alternative system configurations in early design phases. It is based on AbsInt’s aiT WCET Analyzer and provides a parameterizable core that represents a typical architecture of interest. TimingExplorer requires (representative) source code and enables its user to take an informed decision which processor configurations are best suited for his/her needs. A suite of TimingExplorers will facilitate the process of determining what processors to use and it will reduce the risk of timing problems becoming obvious only late in the development cycle and leading to a redesign of large parts of the system.

Cite as

Stefana Nenova and Daniel Kästner. Worst-Case Timing Estimation and Architecture Exploration in Early Design Phases. 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{nenova_et_al:OASIcs.WCET.2009.2280,
  author =	{Nenova, Stefana and K\"{a}stner, Daniel},
  title =	{{Worst-Case Timing Estimation and Architecture Exploration in Early Design Phases}},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2280},
  URN =		{urn:nbn:de:0030-drops-22807},
  doi =		{10.4230/OASIcs.WCET.2009.2280},
  annote =	{Keywords: WCET estimation, architecture exploration WCET estimation, architecture exploration}
}

OASIcs, Volume 10

9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)

Event

Editor

Publication Details

Access Numbers

Documents

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Filters

Thanks for your feedback!

Could not send message