License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2010.23
URN: urn:nbn:de:0030-drops-28226
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2822/
Go to the corresponding OASIcs Volume Portal

Grund, Daniel ; Reineke, Jan

Toward Precise PLRU Cache Analysis

pdf-format:
4.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{grund_et_al:OASIcs:2010:2822,
  author =	{Daniel Grund and Jan Reineke},
  title =	{{Toward Precise PLRU Cache Analysis}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{23--35},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Bj{\"o}rn Lisper},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2822},
  URN =		{urn:nbn:de:0030-drops-28226},
  doi =		{10.4230/OASIcs.WCET.2010.23},
  note =	{The printed version of the WCET'10 proceedings are published by OCG (www.ocg.at) - ISBN 978-3-85403-268-7},
  annote =	{Keywords: Cache Analysis, PLRU Replacement, PLRU Tree}
}

Keywords: Cache Analysis, PLRU Replacement, PLRU Tree
Collection: 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)
Issue Date: 2010
Date of publication: 26.11.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI