Research On Cache Analysis Techniques For The MRU Replacement Policy

Real-Time Systems have stringent requirements on the timing of the real-time tasks. Usually it is required that the timing properties are satisfied even in the worst case, which makes it a mandatory task to estimate the Worst-Case Execution Time (WCET) of the tasks. As a major level of the memory hierarchy, Cache plays an important role in the execution time of tasks, so one major task in WCET analysis is to estimate the Cache hit/miss properties for a given replacement policy. In traditional research on Cache analysis, LRU replacement is usually assumed. While in real processors, LRU is not applied due to the high cost in hardware design; instead, real-life processors usually implement pseudo-LRU replacements, among which MRU is a common one. The dominating analysis technique for LRU replacement is Abstract Interpretation, but this technique can hardly be used to analyze MRU replacement, since MRU has a more complex behaviors.According to this background, we proposed a technique to analyze Caches with MRU replacement. Our technique breaks the domination of Abstract Interpretation in Cache analysis, and uses a "Path Exploration" based framework to analyze the programs. Based on this framework, we analyzed the properties of MRU replacement, and proposed theories to predict Cache hit/miss for different loop structures. The techniques proposed in this thesis are implemented in the McAiT timing analysis tool, and experiments are conducted on the programs from the well-known WCET benchmark suite. Experimental results show that our approach can greatly improve the analysis precision for the MRU replacement, and the maximal observed improvement in the analysis precision is62%. Since MRU is used in real-life processors, our approach can be applied in real systems. Besides, the analysis technique proposed in this thesis can also be generalized to analyze replacement policies other than MRU.