多層Cache的需求分析與總體設(shè)計(jì)

毛金玲

摘要：從對(duì)基于抽象解釋技術(shù)的多層Cache需求分析中可以得出，系統(tǒng)的功能性需求相對(duì)來說比較易于實(shí)現(xiàn)，而非功能性需求由于涉及的范圍很廣，加上諸多外在因素的影響則比較嚴(yán)格。對(duì)于非功能性需求影響最大的就是系統(tǒng)的架構(gòu)，所以在設(shè)計(jì)和實(shí)現(xiàn)系統(tǒng)時(shí)，要在對(duì)系統(tǒng)的架構(gòu)給予充分重視的前提下，實(shí)現(xiàn)功能性需求，最后介紹了系統(tǒng)的總體設(shè)計(jì)框架。

關(guān)鍵詞：多層Cache分析 WCET分析 多層抽象解釋

本文設(shè)計(jì)并實(shí)現(xiàn)了“基于抽象解釋技術(shù)的多層Cache分析”。該分析方法按照程序中循環(huán)的嵌套關(guān)系，首先將程序劃分成若干個(gè)層次。之后，按照傳統(tǒng)基于抽象解釋技術(shù)的分析手段，針對(duì)每個(gè)層次對(duì)應(yīng)的循環(huán)體，分別進(jìn)行分析，探索程序的局部Cache訪問特性。最終，根據(jù)各個(gè)層次的分析得到的結(jié)果，進(jìn)行整數(shù)線性規(guī)劃的編碼，并計(jì)算出更加精確的WCET估計(jì)值。

1 基于抽象解釋技術(shù)的多層Cache需求分析

進(jìn)行層次化分析的主要目的，是發(fā)掘程序局部的Cache訪問特性，從而提高Cache分析的精度。層次化Cache分析的意義，可以通過一個(gè)例子進(jìn)行簡(jiǎn)單的說明。

圖1表示了一個(gè)帶有兩層循環(huán)的程序的控制流程圖，其中Loop1是外層循環(huán)，Loop2是內(nèi)層循環(huán)。其中，圖中的每個(gè)節(jié)點(diǎn)是一個(gè)包含若干條指令的基本塊。為了討論問題方便，不失一般性，我們假定每個(gè)基本塊只包含一條指令。我們假定，外層循環(huán)中的A指令和內(nèi)層循環(huán)中的B、C指令都映射到了一個(gè)兩路組相聯(lián)（2-Way Associative）的Cache組中。我們以PERSISTENCE分析為例，說明進(jìn)行層次化分析，可以提高分析的精確性。

如果對(duì)圖1所示的程序進(jìn)行PERSISTENCE分析，我們會(huì)發(fā)現(xiàn)，由于A、B、C三個(gè)指令都映射到了同一個(gè)Cache組中，且該Cache的相聯(lián)度為2，所以如果對(duì)整個(gè)程序進(jìn)行PERSISTENCE分析，A、B、C三條指令都無法被判斷為First Miss（FM）。如果不能得到這一結(jié)果，在進(jìn)行WCET估計(jì)的時(shí)候，A、B、C三條指令都將被當(dāng)做Always Miss（AM）指令來處理。也就是說，在進(jìn)行WCET估計(jì)的時(shí)候，這三條指令每次執(zhí)行，都被看作是失效（Miss）。

但是，如果我們對(duì)內(nèi)層循環(huán)Loop2的行為進(jìn)一步分析，會(huì)發(fā)現(xiàn)，在絕大多數(shù)情況下，B和C指令在Cache中還是命中的。因?yàn)閷?duì)于內(nèi)層循環(huán)而言，一旦進(jìn)入內(nèi)層循環(huán)執(zhí)行，B和C第一次在Cache中都可能是不命中，因?yàn)榭赡茉谙惹暗膱?zhí)行中，指令A(yù)已經(jīng)占據(jù)了Cache組中的一個(gè)位置，導(dǎo)致B和C失效。但是在內(nèi)層循環(huán)的其它次執(zhí)行過程中，B和C都將是命中，因?yàn)榈谝惠喌膱?zhí)行已經(jīng)將這兩條指令都載入了Cache組中。換言之，B和C的行為特性是：程序每次進(jìn)入內(nèi)層循環(huán)，B和C最多各發(fā)生1次失效，在其它各次執(zhí)行中，B和C在Cache中都將為命中。

顯然，如果我們能夠按照循環(huán)層次，對(duì)程序的局部進(jìn)行分析，是有可能發(fā)現(xiàn)那些在面向整個(gè)程序進(jìn)行分析無法分析出來的Cache命中，因此可以提高分析的精確性。雖然圖1僅僅是一個(gè)簡(jiǎn)單的示例程序，考慮在大規(guī)模的程序中，尤其是那些外層循環(huán)體較大而內(nèi)層循環(huán)體較小的程序中，上面的這種情況可能廣泛存在，因此，采用多層分析優(yōu)化分析精度，具有很大的提升空間。這就是開展本文研究工作的真實(shí)意義所在。

2 系統(tǒng)的具體實(shí)現(xiàn)目標(biāo)

基于抽象解釋技術(shù)的多層Cache分析，其使用到的核心技術(shù)仍舊是原始的基于抽象解釋技術(shù)的分析方法。本文工作與傳統(tǒng)工作的不同，就是將程序根據(jù)循環(huán)嵌套關(guān)系劃分為若干個(gè)層次，為每個(gè)層次的局部程序進(jìn)行抽象解釋分析，得到局部的分析結(jié)果，最后再根據(jù)不同層次得到的結(jié)果，給出一種基于整數(shù)線性規(guī)劃（Interger Linear Programming， ILP）的求解表示，并計(jì)算程序的WCET估計(jì)值。為此，本文所設(shè)計(jì)的軟件部分，應(yīng)該包含如下幾個(gè)具體功能：

①程序?qū)哟谓Y(jié)構(gòu)的分析：實(shí)現(xiàn)多層Cache分析，最初始也是最關(guān)鍵的功能之一，就是對(duì)程序的層次結(jié)構(gòu)進(jìn)行正確的分析和劃分。以一個(gè)簡(jiǎn)單的二層嵌套循環(huán)為例，在我們的分析中，我們首先將整個(gè)程序看成是一個(gè)最外層的循環(huán)，我們稱它位于第1層；那么，第一層實(shí)際的循環(huán)，就位于程序的第2層，內(nèi)層嵌套循環(huán)位于程序的第3層。需要有一個(gè)正確的算法，能夠把一個(gè)復(fù)雜程序的循環(huán)嵌套層次正確分析出來。

②抽象解釋Cache分析技術(shù)的實(shí)現(xiàn)：需要實(shí)現(xiàn)一個(gè)基于抽象解釋的Cache分析模塊，該模塊能夠?qū)⑸弦徊椒治龅玫降牟煌瑢哟蔚木植砍绦蜃鳛檩斎?，利用傳統(tǒng)的抽象解釋分析方法，分析局部程序中的指令的局部行為特征。

③基于多層抽象解釋分析結(jié)果的ILP描述的生成：在進(jìn)行完抽象解釋的分析之后，我們得到的結(jié)果是程序指令在各個(gè)層次上的Cache命中與否的結(jié)果。利用這個(gè)結(jié)果，我們可以計(jì)算出程序（或者局部程序）中每個(gè)基本塊的WCET估計(jì)值。為了得到整個(gè)程序的WCET估計(jì)值，我們還需要利用“隱式路徑枚舉”技術(shù)，將各個(gè)層次得到的分析結(jié)果進(jìn)行建模，通過求解對(duì)應(yīng)的ILP問題，最終計(jì)算出程序的WCET估計(jì)值。

3 系統(tǒng)總體設(shè)計(jì)

圖2表示了本文所屬的WCET分析工具完整的工作流程。其中綠色的模塊表示的是本文的工作在整個(gè)工具中所處的位置。下面，我們將對(duì)整個(gè)工具的工作流程作以簡(jiǎn)要介紹。我們首先介紹不增加本文工作的，WCET分析的原有工作流程。之后，再重點(diǎn)介紹本文所增加的主要功能。

根據(jù)本文所設(shè)計(jì)的“基于抽象解釋的多層Cache分析”的功能需求，本文工作對(duì)該WCET分析工具的擴(kuò)充主要體現(xiàn)為三個(gè)方面：

第一，在原來的分析流程完成了“路徑分析”并得到了程序的控制流程圖（CFG）之后，本文的工作增加了一個(gè)功能，就是對(duì)程序的整體CFG進(jìn)行分析，獲得依照嵌套循環(huán)來劃分的程序的層次結(jié)構(gòu)。第二，在已經(jīng)存在的基于抽象解釋的Cache分析模塊的基礎(chǔ)上，我們對(duì)其進(jìn)行了改進(jìn)，使之能夠有效地分析局部程序?qū)?yīng)的局部CFG。第三，我們擴(kuò)充了原有的“處理器行為約束”功能，使得分層次Cache分析得到的結(jié)果能夠被建模到ILP描述中，并參與WCET計(jì)算，最終獲得更加精確的分析結(jié)果。

4 結(jié)語

從對(duì)基于抽象解釋技術(shù)的多層Cache需求分析中可以得出，系統(tǒng)的功能性需求相對(duì)來說比較易于實(shí)現(xiàn)，而非功能性需求由于涉及的范圍很廣，加上諸多外在因素的影響則比較嚴(yán)格。對(duì)于非功能性需求影響最大的就是系統(tǒng)的架構(gòu)，所以在設(shè)計(jì)和實(shí)現(xiàn)系統(tǒng)時(shí)，要在對(duì)系統(tǒng)的架構(gòu)給予充分重視的前提下，實(shí)現(xiàn)功能性需求。

參考文獻(xiàn)：

[1]Hennessy J，Patterson D.Computer Architecture：A Quantitative Approachz[M].Morgan Kuafmann，1996.

[2]Damien G.Study of Different Cache Line Replacement Algorithms in Embedded Systems[D].ARM France SAS Les Cardoulines B2-Route des.

[3]付雄.利用程序分析和優(yōu)化提高Cache性能[D].中國科學(xué)技術(shù)大學(xué)，2007.