Static Cache Analysis for Real-Time Systems
LRU, FIFO, PLRU
Buch in deiner Nähe kaufen
Beschreibung
After two decades of caches in RT systems, we make cache analysis fit for non-LRU policies
Static cache analysis is an indispensable part of static timing analysis, which is employed to verify the timing behavior of programs in safety-critical systems.
This thesis extends the applicability of cache analysis to caches with FIFO and PLRU replacement policies. These are more often employed than the LRU policy, on which previous work has focused, yet they are disproportionately more difficult to analyze.
We identify a generic framework for cache analysis that couples several cache analyses in order to increase their precision by cooperation; though without abandoning separation of concerns.
For the FIFO policy we contribute two must- and one may-analysis. One must-analysis exploits information about cache misses to subsequently be able to predict cache hits. The other two analyses are based on the novel principle of static phase detection: If memory access sequences can be partitioned into phases---subsequences with the same or similar accesses---one can predict hits or misses, respectively. Instantiating the framework with the three analyses results in an analysis that tightly approximates the FIFO behavior and clearly outperforms previous approaches.
For the PLRU policy we contribute a strongest complete abstraction, which distinguishes cache states if and only if they exhibit different replacement behavior. Based thereon, we present an incomplete analysis that is able to exclude spurious logarithmic-time eviction of cache contents.
Autor*in
Daniel Grund
Themen in »Static Cache Analysis for Real-Time Systems«
First In First Out Least Recently Used Pseudo Least Recently Used WCET cache analysis caches embedded systems real-time systems timing analysis worst-case execution time analysis