面向MRU替換策略的Cache分析技術的研究.pdf

1、實時系統(tǒng)對任務的執(zhí)行時間有著苛刻的要求，因此需要保證系統(tǒng)在最壞情況下也能夠滿足時間需求，這就需要知道任務最壞情況執(zhí)行時間(Worst-Case Execution Time，WCET)。Cache作為計算機存儲體系結構中的重要層次，對于任務的執(zhí)行時間有著巨大的影響，因此WCET分析的重要任務之一，就是分析任務在Cache中命中或失效的情況。傳統(tǒng)的Cache分析的研究，普遍假設替換策略為LRU。但是在實際的處理器中，由于硬件實現(xiàn)代價過高，

2、通常不采用LRU替換策略，而是采用各種類LRU的策略，MRU替換算法即是其中的一種。相關研究主要采用抽象解釋技術分析基于LRU替換策略的Cache。但是對于MRU替換策略，由于其替換行為較LRU更加復雜，因此難以使用抽象解釋技術進行分析。
　　基于上述背景，本文提出一種針對MRU替換策略的Cache分析技術。該技術突破了抽象解釋技術的分析框架，提出了一種基于“路徑探索(Path Exploration)”的程序結構分析方法，并在這

3、一新的框架之上，深入挖掘MRU替換策略的特性，針對程序循環(huán)體的不同特性，給出了相應的判定指令命中與失效的理論。我們在McAiT這一時間分析工具中實現(xiàn)了本文所提出的分析方法，采用WCET分析領域公認的測試程序集中的程序進行了實驗。實驗結果表明，本文所提出的方法能夠有效的分析在MRU替換策略下程序指令在Cache中的命中情況，實驗觀測到的最高分析精度的提高達到62％。本文的研究面向實際系統(tǒng)中的Cache替換策略，對于實際應用具有重要意義。同