*banner
 

Toward Precise PLRU Cache Analysis
Daniel Grund, Jan Reineke

Citation
Daniel Grund, Jan Reineke. "Toward Precise PLRU Cache Analysis". Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, Bjoern Lisper (ed.), 28-39, July, 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.

Electronic downloads

Citation formats  
  • HTML
    Daniel Grund, Jan Reineke. <a
    href="http://chess.eecs.berkeley.edu/pubs/845.html"
    >Toward Precise PLRU Cache Analysis</a>,
    Proceedings of 10th International Workshop on Worst-Case
    Execution Time (WCET) Analysis, Bjoern Lisper (ed.), 28-39,
    July, 2010.
  • Plain text
    Daniel Grund, Jan Reineke. "Toward Precise PLRU Cache
    Analysis". Proceedings of 10th International Workshop
    on Worst-Case Execution Time (WCET) Analysis, Bjoern Lisper
    (ed.), 28-39, July, 2010.
  • BibTeX
    @inproceedings{GrundReineke10_TowardPrecisePLRUCacheAnalysis,
        author = {Daniel Grund and Jan Reineke},
        title = {Toward Precise PLRU Cache Analysis},
        booktitle = {Proceedings of 10th International Workshop on
                  Worst-Case Execution Time (WCET) Analysis},
        editor = {Bjoern Lisper},
        pages = {28-39},
        month = {July},
        year = {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 deï¬ne a must-analysis that
                  is more precise than prior ones by excluding
                  spurious logarithmic-time eviction. },
        URL = {http://chess.eecs.berkeley.edu/pubs/845.html}
    }
    

Posted by Jan Reineke on 9 Jul 2011.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

You are not logged in 
©2002-2017 Chess