Search Results

Documents authored by Reineke, Jan

Document
DOI: 10.4230/OASIcs.WCET.2022.2
LLVMTA: An LLVM-Based WCET Analysis Tool

Authors: Sebastian Hahn, Michael Jacobs, Nils Hölscher, Kuan-Hsun Chen, Jian-Jia Chen, and Jan Reineke

Published in: OASIcs, Volume 103, 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)

Abstract
We present llvmta, an academic WCET analysis tool based on the LLVM compiler infrastructure. It aims to enable the evaluation of novel WCET analysis approaches in a state-of-the-art analysis framework without dealing with the complexity of modeling real-world hardware architectures. We discuss the main design decisions and interfaces that allow to implement new analysis approaches. Finally, we highlight various existing research projects whose evaluation has been enabled by llvmta.
Cite as

Sebastian Hahn, Michael Jacobs, Nils Hölscher, Kuan-Hsun Chen, Jian-Jia Chen, and Jan Reineke. LLVMTA: An LLVM-Based WCET Analysis Tool. In 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022). Open Access Series in Informatics (OASIcs), Volume 103, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hahn_et_al:OASIcs.WCET.2022.2,
  author =	{Hahn, Sebastian and Jacobs, Michael and H\"{o}lscher, Nils and Chen, Kuan-Hsun and Chen, Jian-Jia and Reineke, Jan},
  title =	{{LLVMTA: An LLVM-Based WCET Analysis Tool}},
  booktitle =	{20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-244-0},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{103},
  editor =	{Ballabriga, Cl\'{e}ment},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2022.2},
  URN =		{urn:nbn:de:0030-drops-166242},
  doi =		{10.4230/OASIcs.WCET.2022.2},
  annote =	{Keywords: WCET analysis, low-level analysis, LLVM}
}
Document
DOI: 10.4230/OASIcs.WCET.2018.7
Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis

Authors: Darshit Shah, Sebastian Hahn, and Jan Reineke

Published in: OASIcs, Volume 63, 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)

Abstract
In the presence of caches, preemptive scheduling may incur a significant overhead referred to as cache-related preemption delay (CRPD). CRPD is caused by preempting tasks evicting cached memory blocks of preempted tasks, which have to be reloaded when the preempted tasks resume their execution. In this paper we experimentally evaluate state-of-the-art techniques to account for the CRPD during timing analysis. We find that purely synthetically-generated task sets may yield misleading conclusions regarding the relative precision of different CRPD analysis techniques and the impact of CRPD on schedulability in general. Based on task characterizations obtained by static worst-case execution time (WCET) analysis, we shed new light on the state of the art.
Cite as

Darshit Shah, Sebastian Hahn, and Jan Reineke. Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shah_et_al:OASIcs.WCET.2018.7,
  author =	{Shah, Darshit and Hahn, Sebastian and Reineke, Jan},
  title =	{{Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis}},
  booktitle =	{18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
  pages =	{7:1--7:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-073-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{63},
  editor =	{Brandner, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.7},
  URN =		{urn:nbn:de:0030-drops-97532},
  doi =		{10.4230/OASIcs.WCET.2018.7},
  annote =	{Keywords: real-time systems, timing analysis, cache-related preemption delay}
}
Document
DOI: 10.4230/LITES-v005-i001-a003
The Semantic Foundations and a Landscape of Cache-Persistence Analyses

Authors: Jan Reineke

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
We clarify the notion of cache persistence and contribute to the understanding of persistence analysis for caches with least-recently-used replacement.To this end, we provide the first formal definition of persistence as a property of a trace semantics. Based on this trace semantics we introduce a semantics-based, i.e., abstract-interpretation-based persistence analysis framework.We identify four basic persistence analyses and prove their correctness as instances of this analysis framework.Combining these basic persistence analyses via two generic cooperation mechanisms yields a lattice of ten persistence analyses.Notably, this lattice contains all persistence analyses previously described in the literature. As a consequence, we obtain uniform correctness proofs for all prior analyses and a precise understanding of how and why these analyses work, as well as how they relate to each other in terms of precision.
Cite as

Jan Reineke. The Semantic Foundations and a Landscape of Cache-Persistence Analyses. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 03:1-03:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{reineke:LITES-v005-i001-a003,
  author =	{Reineke, Jan},
  title =	{{The Semantic Foundations and a Landscape of Cache-Persistence Analyses}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:52},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a003},
  URN =		{urn:nbn:de:0030-drops-192748},
  doi =		{10.4230/LITES-v005-i001-a003},
  annote =	{Keywords: caches, persistence analysis, WCET analysis}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.WCET.2017
OASIcs, Volume 57, WCET'17, Complete Volume

Authors: Jan Reineke

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract
OASIcs, Volume 57, WCET'17, Complete Volume
Cite as

17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{reineke:OASIcs.WCET.2017,
  title =	{{OASIcs, Volume 57, WCET'17, Complete Volume}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017},
  URN =		{urn:nbn:de:0030-drops-73653},
  doi =		{10.4230/OASIcs.WCET.2017},
  annote =	{Keywords: Performance Analysis and Design Aids, Real-Time and Embedded Systems, Software/ Program Verification, \lbrackOrganization and Design\rbrack Real-Time Systems}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2017.0
Front Matter, Table of Contents, Preface, Committee

Authors: Jan Reineke

Published in: OASIcs, Volume 57, 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)

Abstract
Front Matter, Table of Contents, Preface, Committee
Cite as

17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{reineke:OASIcs.WCET.2017.0,
  author =	{Reineke, Jan},
  title =	{{Front Matter, Table of Contents, Preface, Committee}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{0:i--0:x},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2017.0},
  URN =		{urn:nbn:de:0030-drops-73026},
  doi =		{10.4230/OASIcs.WCET.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committee}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2017.26
Write-Back Caches in WCET Analysis

Authors: Tobias Blaß, Sebastian Hahn, and Jan Reineke

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
Write-back caches are a popular choice in embedded microprocessors as they promise higher performance than write-through caches. So far, however, their use in hard real-time systems has been prohibited by the lack of adequate worst-case execution time (WCET) analysis support. In this paper, we introduce a new approach to statically analyze the behavior of write-back caches. Prior work took an "eviction-focussed perspective", answering for each potential cache miss: May this miss evict a dirty cache line and thus cause a write back? We complement this approach by exploring a "store-focussed perspective", answering for each store: May this store dirtify a clean cache line and thus cause a write back later on? Experimental evaluation demonstrates substantial precision improvements when both perspectives are combined. For most benchmarks, write-back caches are then preferable to write-through caches in terms of the computed WCET bounds.
Cite as

Tobias Blaß, Sebastian Hahn, and Jan Reineke. Write-Back Caches in WCET Analysis. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bla_et_al:LIPIcs.ECRTS.2017.26,
  author =	{Bla{\ss}, Tobias and Hahn, Sebastian and Reineke, Jan},
  title =	{{Write-Back Caches in WCET Analysis}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.26},
  URN =		{urn:nbn:de:0030-drops-71589},
  doi =		{10.4230/LIPIcs.ECRTS.2017.26},
  annote =	{Keywords: write-back caches, real-time systems, WCET analysis, cache analysis}
}
Document
DOI: 10.4230/LITES-v003-i001-a005
A Survey on Static Cache Analysis for Real-Time Systems

Authors: Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi

Published in: LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1

Abstract
Real-time systems are reactive computer systems that must produce their reaction to a stimulus within given time bounds. A vital verification requirement is to estimate the Worst-Case Execution Time (WCET) of programs. These estimates are then used to predict the timing behavior of the overall system. The execution time of a program heavily depends on the underlying hardware, among which cache has the biggest influence. Analyzing cache behavior is very challenging due to the versatile cache features and complex execution environment. This article provides a survey on static cache analysis for real-time systems. We first present the challenges and static analysis techniques for independent programs with respect to different cache features. Then, the discussion is extended to cache analysis in complex execution environment, followed by a survey of existing tools based on static techniques for cache analysis. An outlook for future research is provided at last.
Cite as

Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. A Survey on Static Cache Analysis for Real-Time Systems. In LITES, Volume 3, Issue 1 (2016). Leibniz Transactions on Embedded Systems, Volume 3, Issue 1, pp. 05:1-05:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{lv_et_al:LITES-v003-i001-a005,
  author =	{Lv, Mingsong and Guan, Nan and Reineke, Jan and Wilhelm, Reinhard and Yi, Wang},
  title =	{{A Survey on Static Cache Analysis for Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:48},
  ISSN =	{2199-2002},
  year =	{2016},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v003-i001-a005},
  URN =		{urn:nbn:de:0030-drops-192603},
  doi =		{10.4230/LITES-v003-i001-a005},
  annote =	{Keywords: Hard real-time, Cache analysis, Worst-case execution time}
}
Document
DOI: 10.4230/OASIcs.WCET.2015.65
WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?

Authors: Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange

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

Abstract
Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.
Cite as

Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange. WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 65-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{altmeyer_et_al:OASIcs.WCET.2015.65,
  author =	{Altmeyer, Sebastian and Lisper, Bj\"{o}rn and Maiza, Claire and Reineke, Jan and Rochange, Christine},
  title =	{{WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{65--74},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.65},
  URN =		{urn:nbn:de:0030-drops-52574},
  doi =		{10.4230/OASIcs.WCET.2015.65},
  annote =	{Keywords: mixed criticality, WCET analysis, confidence in WCET estimates}
}
Document
DOI: 10.4230/LITES-v001-i001-a003
Randomized Caches Considered Harmful in Hard Real-Time Systems

Authors: Jan Reineke

Published in: LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1

Abstract
We investigate the suitability of caches with randomized placement and replacement in the context of hard real-time systems. Such caches have been claimed to drastically reduce the amount of information required by static worst-case execution time (WCET) analysis, and to be an enabler for measurement-based probabilistic timing analysis. We refute these claims and conclude that with prevailing static and measurement-based analysis techniques caches with deterministic placement and least-recently-used replacement are preferable over randomized ones.
Cite as

Jan Reineke. Randomized Caches Considered Harmful in Hard Real-Time Systems. In LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1, pp. 03:1-03:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{reineke:LITES-v001-i001-a003,
  author =	{Reineke, Jan},
  title =	{{Randomized Caches Considered Harmful in Hard Real-Time Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{03:1--03:13},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i001-a003},
  URN =		{urn:nbn:de:0030-drops-192450},
  doi =		{10.4230/LITES-v001-i001-a003},
  annote =	{Keywords: Real-time systems, Caches, Randomization, WCET analysis}
}
Document
DOI: 10.4230/OASIcs.WCET.2012.13
An Empirical Evaluation of the Influence of the Load-Store Unit on WCET Analysis

Authors: Mohamed Abdel Maksoud and Jan Reineke

Published in: OASIcs, Volume 23, 12th International Workshop on Worst-Case Execution Time Analysis (2012)

Abstract
Due to the complexity of today’s micro-architectures, the micro-architectural analysis usually constitutes the most time-consuming step in worst-case execution time (WCET) analysis. In this paper, we investigate the influence of the design of the load-store unit (LSU) in the PowerPC 7448 on WCET analysis. To this end, we introduce a simplified variant of the existing design of the LSU by reducing its queue sizes. Using AbsInt's aiT WCET analysis toolchain we determine the resulting WCET bounds and analysis times. For the modified version of the LSU with reduced queue sizes, analysis time is reduced by more than 50% on a set of benchmarks from the Mälardalen suite, while there is little change in the WCET bound.
Cite as

Mohamed Abdel Maksoud and Jan Reineke. An Empirical Evaluation of the Influence of the Load-Store Unit on WCET Analysis. In 12th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 23, pp. 13-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{abdelmaksoud_et_al:OASIcs.WCET.2012.13,
  author =	{Abdel Maksoud, Mohamed and Reineke, Jan},
  title =	{{An Empirical Evaluation of the Influence of the Load-Store Unit on WCET Analysis}},
  booktitle =	{12th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{13--24},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2012.13},
  URN =		{urn:nbn:de:0030-drops-35536},
  doi =		{10.4230/OASIcs.WCET.2012.13},
  annote =	{Keywords: Empirical evaluation, architecture complexity effect, WCET analysis precision, WCET analysis performance, PowerPC 7448, Load-Store Unit}
}
Document
DOI: 10.4230/OASIcs.PPES.2011.22
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.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
DOI: 10.4230/OASIcs.WCET.2010.23
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.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}
}
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.2009.2284
Making Dynamic Memory Allocation Static to Support WCET Analysis

Authors: Jörg Herter and Jan Reineke

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

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.2289
Sound and Efficient WCET Analysis in the Presence of Timing Anomalies

Authors: Jan Reineke and Rathijit Sen

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

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.TrustworthySW.2006.698
Shape Analysis of Sets

Authors: Jan Reineke

Published in: OASIcs, Volume 3, Workshop on Trustworthy Software (2006)

Abstract
Shape Analysis is concerned with determining "shape invariants", i.e. structural properties of the heap, for programs that manipulate pointers and heap-allocated storage. Recently, very precise shape analysis algorithms have been developed that are able to prove the partial correctness of heap-manipulating programs. We explore the use of shape analysis to analyze abstract data types (ADTs). The ADT Set shall serve as an example, as it is widely used and can be found in most of the major data type libraries, like STL, the Java API, or LEDA. We formalize our notion of the ADT Set by algebraic specification. Two prototypical C set implementations are presented, one based on lists, the other on trees. We instantiate a parametric shape analysis framework to generate analyses that are able to prove the compliance of the two implementations to their specification.
Cite as

Jan Reineke. Shape Analysis of Sets. In Workshop on Trustworthy Software. Open Access Series in Informatics (OASIcs), Volume 3, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{reineke:OASIcs.TrustworthySW.2006.698,
  author =	{Reineke, Jan},
  title =	{{Shape Analysis of Sets}},
  booktitle =	{Workshop on Trustworthy Software},
  pages =	{1--19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-02-6},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{3},
  editor =	{Autexier, Serge and Merz, Stephan and van der Torre, Leon and Wilhelm, Reinhard and Wolper, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TrustworthySW.2006.698},
  URN =		{urn:nbn:de:0030-drops-6980},
  doi =		{10.4230/OASIcs.TrustworthySW.2006.698},
  annote =	{Keywords: Shape analysis, adt, algebraic specification, invariants, verification, set implementations, imperative programs}
}
Document
DOI: 10.4230/OASIcs.WCET.2006.671
A Definition and Classification of Timing Anomalies

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

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

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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact