3 Search Results for "Grund, Daniel"


Document
Impact of DM-LRU on WCET: A Static Analysis Approach

Authors: Renato Mancuso, Heechul Yun, and Isabelle Puaut

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)


Abstract
Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache.

Cite as

Renato Mancuso, Heechul Yun, and Isabelle Puaut. Impact of DM-LRU on WCET: A Static Analysis Approach. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{mancuso_et_al:LIPIcs.ECRTS.2019.17,
  author =	{Mancuso, Renato and Yun, Heechul and Puaut, Isabelle},
  title =	{{Impact of DM-LRU on WCET: A Static Analysis Approach}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.17},
  URN =		{urn:nbn:de:0030-drops-107546},
  doi =		{10.4230/LIPIcs.ECRTS.2019.17},
  annote =	{Keywords: real-time, static cache analysis, abstract interpretation, LRU, deterministic memory, static cache locking, dynamic cache locking, cache profiling, WCET analysis}
}
Document
A Template for Predictability Definitions with Supporting Evidence

Authors: Daniel Grund, Jan Reineke, and Reinhard Wilhelm

Published in: OASIcs, Volume 18, Bringing Theory to Practice: Predictability and Performance in Embedded Systems (2011)


Abstract
In real-time systems, timing behavior is as important as functional behavior. Modern architectures turn verification of timing aspects into a nightmare, due to their "unpredictability". Recently, various efforts have been undertaken to engineer more predictable architectures. Such efforts should be based on a clear understanding of predictability. We discuss key aspects of and propose a template for predictability definitions. To investigate the utility of our proposal, we examine above efforts and try to cast them as instances of our template.

Cite as

Daniel Grund, Jan Reineke, and Reinhard Wilhelm. A Template for Predictability Definitions with Supporting Evidence. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 22-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{grund_et_al:OASIcs.PPES.2011.22,
  author =	{Grund, Daniel and Reineke, Jan and Wilhelm, Reinhard},
  title =	{{A Template for Predictability Definitions with Supporting Evidence}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{22--31},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and 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.PPES.2011.22},
  URN =		{urn:nbn:de:0030-drops-30785},
  doi =		{10.4230/OASIcs.PPES.2011.22},
  annote =	{Keywords: predictability, uncertainty, precision}
}
Document
Toward Precise PLRU Cache Analysis

Authors: Daniel Grund and Jan Reineke

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


Abstract
Schedulability analysis for hard real-time systems requires bounds on the execution times of its tasks. To obtain useful bounds in the presence of caches, cache analysis is mandatory. The subject-matter of this article is the static analysis of the tree-based PLRU cache replacement policy (pseudo least-recently used), for which the precision of analyses lags behind those of other policies. We introduce the term subtree distance, which is important for the update behavior of PLRU and closely linked to the peculiarity of PLRU that allows cache contents to be evicted in "logarithmic time". Based on an abstraction of subtree distance, we define a must-analysis that is more precise than prior ones by excluding spurious logarithmic-time eviction.

Cite as

Daniel Grund and Jan Reineke. Toward Precise PLRU Cache Analysis. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 23-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{grund_et_al:OASIcs.WCET.2010.23,
  author =	{Grund, Daniel and Reineke, Jan},
  title =	{{Toward Precise PLRU Cache Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{23--35},
  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.23},
  URN =		{urn:nbn:de:0030-drops-28226},
  doi =		{10.4230/OASIcs.WCET.2010.23},
  annote =	{Keywords: Cache Analysis, PLRU Replacement, PLRU Tree}
}
  • Refine by Author
  • 2 Grund, Daniel
  • 2 Reineke, Jan
  • 1 Mancuso, Renato
  • 1 Puaut, Isabelle
  • 1 Wilhelm, Reinhard
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems
  • 1 Theory of computation → Caching and paging algorithms

  • Refine by Keyword
  • 1 Cache Analysis
  • 1 LRU
  • 1 PLRU Replacement
  • 1 PLRU Tree
  • 1 WCET analysis
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 1 2019

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