WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction Caches
- 1 November 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 456-466
- https://doi.org/10.1109/rtss.2008.10
Abstract
With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, cache hierarchy, multiple cores), many processors now have a set-associative L2 cache. Thus, there is a need for considering cache hierarchies when validating the temporal behavior of real-time systems, in particular when estimating tasks' worst-case execution times (WCETs). In this paper, we propose a safe static instruction cache analysis method for multi-level non-inclusive caches. The proposed method is experimented on medium-size and large programs. We show that the method is reasonably tight. We further show that in all cases WCET estimations are much tighter when considering the cache hierarchy than when considering only the L1 cache. An evaluation of the analysis time is conducted, demonstrating that analyzing the cache hierarchy has a reasonable computation time.Keywords
This publication has 15 references indexed in Scilit:
- Improving the First-Miss Computation in Set-Associative Instruction CachesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- The worst-case execution-time problem—overview of methods and survey of toolsACM Transactions on Embedded Computing Systems, 2008
- WCET-Centric Software-controlled Instruction Caches for Hard Real-Time SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference PatternsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Accurate estimation of cache-related preemption delayPublished by Association for Computing Machinery (ACM) ,2003
- A modular and retargetable framework for tree-based WCET analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Timing Analysis for Instruction CachesReal-Time Systems, 2000
- Fast and Precise WCET Prediction by Separated Cache and Path AnalysesReal-Time Systems, 2000
- Computing Maximum Task Execution Times — A Graph-Based ApproachReal-Time Systems, 1997
- Calculating the maximum execution time of real-time programsReal-Time Systems, 1989