多層Cache的需求分析與總體設計

毛金玲

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

關鍵詞：多層Cache分析 WCET分析 多層抽象解釋

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

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

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

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

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

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

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

2 系統(tǒng)的具體實現(xiàn)目標

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

①程序層次結構的分析：實現(xiàn)多層Cache分析，最初始也是最關鍵的功能之一，就是對程序的層次結構進行正確的分析和劃分。以一個簡單的二層嵌套循環(huán)為例，在我們的分析中，我們首先將整個程序看成是一個最外層的循環(huán)，我們稱它位于第1層；那么，第一層實際的循環(huán)，就位于程序的第2層，內層嵌套循環(huán)位于程序的第3層。需要有一個正確的算法，能夠把一個復雜程序的循環(huán)嵌套層次正確分析出來。

②抽象解釋Cache分析技術的實現(xiàn)：需要實現(xiàn)一個基于抽象解釋的Cache分析模塊，該模塊能夠將上一步分析得到的不同層次的局部程序作為輸入，利用傳統(tǒng)的抽象解釋分析方法，分析局部程序中的指令的局部行為特征。

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

3 系統(tǒng)總體設計

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

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

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

4 結語

從對基于抽象解釋技術的多層Cache需求分析中可以得出，系統(tǒng)的功能性需求相對來說比較易于實現(xiàn)，而非功能性需求由于涉及的范圍很廣，加上諸多外在因素的影響則比較嚴格。對于非功能性需求影響最大的就是系統(tǒng)的架構，所以在設計和實現(xiàn)系統(tǒng)時，要在對系統(tǒng)的架構給予充分重視的前提下，實現(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].中國科學技術大學，2007.