DROPS

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

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

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

History-based Schemes and Implicit Path Enumeration

Authors: Claire Burguière and Christine Rochange

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

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

Search Results

Documents authored by Burguière, Claire

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

Abstract

Cite as

History-based Schemes and Implicit Path Enumeration

Abstract

Cite as

Thanks for your feedback!

Could not send message