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

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

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

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