【摘要】：實時系統(tǒng)對任務(wù)的執(zhí)行時間有著苛刻的要求,因此需要保證系統(tǒng)在最壞情況下也能夠滿足時間需求,這就需要知道任務(wù)最壞情況執(zhí)行時間(Worst-Case Execution Time, WCET)。Cache作為計算機存儲體系結(jié)構(gòu)中的重要層次,對于任務(wù)的執(zhí)行時間有著巨大的影響,因此WCET分析的重要任務(wù)之一,就是分析任務(wù)在Cache中命中或失效的情況。傳統(tǒng)的Cache分析的研究,普遍假設(shè)替換策略為LRU。但是在實際的處理器中,由于硬件實現(xiàn)代價過高,通常不采用LRU替換策略,而是采用各種類LRU的策略,MRU替換算法即是其中的一種。相關(guān)研究主要采用抽象解釋技術(shù)分析基于LRU替換策略的Cache。但是對于MRU替換策略,由于其替換行為較LRU更加復(fù)雜,因此難以使用抽象解釋技術(shù)進(jìn)行分析。 基于上述背景,本文提出一種針對MRU替換策略的Cache分析技術(shù)。該技術(shù)突破了抽象解釋技術(shù)的分析框架,提出了一種基于“路徑探索(Path Exploration)"的程序結(jié)構(gòu)分析方法,并在這一新的框架之上,深入挖掘MRU替換策略的特性,針對程序循環(huán)體的不同特性,給出了相應(yīng)的判定指令命中與失效的理論。我們在McAiT這一時間分析工具中實現(xiàn)了本文所提出的分析方法,采用WCET分析領(lǐng)域公認(rèn)的測試程序集中的程序進(jìn)行了實驗。實驗結(jié)果表明,本文所提出的方法能夠有效的分析在MRU替換策略下程序指令在Cache中的命中情況,實驗觀測到的最高分析精度的提高達(dá)到62%。本文的研究面向?qū)嶋H系統(tǒng)中的Cache替換策略,對于實際應(yīng)用具有重要意義。同時,本文所提出的分析框架具有一定的通用性,亦可擴展并應(yīng)用于其他Cache替換策略的分析。
【圖文】：

程序執(zhí)行時間的基本概念Fig.1.1Basicconceptsofexecutiontimesofprograms

東北大學(xué)領(lǐng)士學(xué)位論文 第2章相關(guān)技術(shù)第三種為組相聯(lián)映射，如圖2.4所示。首先Cache分成若干個組，每組包含若干塊，然后主存按照Cache容量分區(qū)，每個區(qū)再根據(jù)Cache的分組情況同樣的分成如干組，每組中包含的塊數(shù)與Cache中每組塊數(shù)一致。前面介紹過，組相聯(lián)映射為直接映射和全相聯(lián)映射的折中，主要表現(xiàn)在根據(jù)前面介紹的分組情況，組間采用直接映射，而組內(nèi)采用全相聯(lián)映射。這就結(jié)合了直接映射和全相聯(lián)映射各自的優(yōu)點，且在一定程度上避免了各自的缺點。主存
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TP333

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 江喜平;高德遠(yuǎn);張盛兵;王晶;;CISC中混合Cache的優(yōu)化設(shè)計[J];計算機工程與應(yīng)用;2006年10期

2 李洪;毛志剛;;PLRU替換算法在嵌入式系統(tǒng)cache中的實現(xiàn)[J];微處理機;2010年01期

3 段宗濤,周興社,董明峰;主存儲器訪問調(diào)度技術(shù)研究[J];微電子學(xué)與計算機;2004年10期

4 張鑫;;面向二十一世紀(jì)的嵌入式系統(tǒng)綜述[J];科技創(chuàng)新導(dǎo)報;2009年03期

，

本文編號：2645039