基于抽象解釋技術(shù)的多層Cache分析的設(shè)計(jì)與實(shí)現(xiàn)

摘 要：在WCET分析中，最重要的一類工作就是Cache分析。目前，大多數(shù)的基于抽象解釋技術(shù)的Cache分析中，分析算法是作用于整個(gè)程序的，如果能夠根據(jù)程序的層次結(jié)構(gòu)，挖掘程序執(zhí)行在Cache中的局部特性，那么就可以有效的提高WCET的分析精度?；谶@一需求，本文主要研究基于抽象解釋技術(shù)的多層Cache分析，研究的主要內(nèi)容包括：程序?qū)哟谓Y(jié)構(gòu)的分析，基于抽象解釋技術(shù)的多層Cache分析和整數(shù)線性規(guī)劃問題的建模與WCET求解，采用多層Cache分析能有效的提高WCET的分析精度。

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

中圖分類號：TP311.1

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

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

圖1為WCET分析工具總體分析框架，展示了WCET分析工具完整的工作流程。其中綠色的模塊表示的是本文研究的主體工作在整個(gè)工具中所處的位置。

在本工具中，待分析的程序?yàn)镃代碼編寫，通過面向SimpleScalar平臺(tái)的gcc交叉編譯器，可以將源程序編譯為PISA指令集的可執(zhí)行程序，這個(gè)可執(zhí)行程序就是WCET分析工具的直接輸入。程序讀入工具之后，分析工具將可執(zhí)行程序進(jìn)行反編譯，提取詳細(xì)的指令信息，并生成程序的CFG。程序的CFG表示了程序的流程結(jié)構(gòu)，這一信息將成為處理器行為分析的輸入。處理器行為分析目前主要包括Cache分析。Cache分析的結(jié)果主要是判斷程序的指令或數(shù)據(jù)在Cache中的命中情況。循環(huán)變量、不可行路徑等信息可以由用戶手工輸入，這些輸入為“功能性約束條件”，根據(jù)下一步計(jì)算的需要，這些約束條件將被映射為不同模型中所需要的形式。

在程序流程、處理器行為分析、以及功能性約束等信息都齊備以后，需要采用某種手段計(jì)算求解程序的WCET。藍(lán)色線條部分表示的是基于隱式路徑枚舉的計(jì)算方法。根據(jù)計(jì)算需要，程序流程信息、處理器行為信息、功能性約束等分別被轉(zhuǎn)化為線性約束描述的“控制流程約束”、“處理器行為約束”以及“映射后的功能約束”等，這些約束與目標(biāo)函數(shù)結(jié)合起來，就形成了一個(gè)整數(shù)線性規(guī)劃的問題，這一問題可以交付商業(yè)的求解軟件（如CPLEX）或開源的數(shù)學(xué)規(guī)劃求解軟件（如lp_solve）進(jìn)行求解，最終得到程序的WCET值。在另外一條分支上，可執(zhí)行程序可以交給SimpleScalar模擬器進(jìn)行模擬執(zhí)行，用以獲得程序的WCET觀測值，它通常用來和WCET估計(jì)值進(jìn)行比較，以粗略的分析后者的精確程度。

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

2 基于抽象解釋的Cache分析功能的設(shè)計(jì)與實(shí)現(xiàn)

2.1 基于抽象解釋的Cache分析基本思想

通過對程序執(zhí)行過程的靜態(tài)模擬，分析出由于程序的執(zhí)行而造成的Cache中內(nèi)容的變化情況，并從中提取出在此程序執(zhí)行過程中的每一個(gè)訪存操作在Cache中的命中情況。在抽象解釋技術(shù)中，用一個(gè)抽象的Cache狀態(tài)（Abstract Cache State）來表示一系列具體的Cache狀態(tài)（Concrete Cache State）。同時(shí)，他們還為抽象的Cache狀態(tài)定義了一些抽象的Cache動(dòng)作函數(shù)，這些動(dòng)作函數(shù)是Update函數(shù)和Join函數(shù)，其中Update函數(shù)是用來對抽象Cache狀態(tài)中的內(nèi)容進(jìn)行更新的，而Join函數(shù)則是用來合并兩個(gè)抽象Cache狀態(tài)中的內(nèi)容的。這些抽象的Cache動(dòng)作函數(shù)在一定程度上能夠反映出由于程序的執(zhí)行而對Cache中的內(nèi)容所造成的影響。因此，抽象的Cache狀態(tài)以及這些抽象的Cache動(dòng)作函數(shù)能夠在抽象空間內(nèi)對Cache的具體行為進(jìn)行完整的描述。在對程序執(zhí)行過程的靜態(tài)模擬過程中，抽象Cache狀態(tài)中的內(nèi)容將會(huì)按照所規(guī)定的動(dòng)作函數(shù)而發(fā)生變化。

基于抽象解釋技術(shù)的Cache分析方法針對抽象的指令Cache狀態(tài)主要采用三種分析，它們分別是Must分析、May分析和Persistence分析。Must分析是用來確定哪些指令在指令Cache中一定是命中的；而May分析則能夠確定出哪些指令在指令Cache中是可能命中的，根據(jù)這一結(jié)果可以判斷出那些在指令Cache中一定不命中的指令。Persistence分析能夠識別出那些一旦被載入到指令Cache中就不會(huì)再被替換出去的指令。

Must、May和Persistence分析都是根據(jù)程序的控制流程信息來對抽象的指令Cache狀態(tài)進(jìn)行分析的，并且這三種分析所對應(yīng)的分析過程都是一個(gè)不斷迭代的過程。當(dāng)這三種分析都各自收斂到一個(gè)固定點(diǎn)（Fixpoint）的時(shí)候，這三種分析便可以結(jié)束對抽象的指令Cache狀態(tài)的分析。此時(shí)，根據(jù)此抽象的指令Cache狀態(tài)中的內(nèi)容可以確定出此程序中每條指令在指令Cache中的命中情況，從而可以得到關(guān)于這些指令的分類情況。

2.2 多層Cache分析的主要過程

根據(jù)Must，May，Persistence分析的目標(biāo)，在本文的多層Cache分析中，擬采用如下的分析方法：（1）對于最頂層的循環(huán)，也就是程序本身，分別進(jìn)行Must，May和Persistence分析；（2）對于非最頂層的循環(huán)，只進(jìn)行Persistence分析。

在本文的實(shí)現(xiàn)中，采用了文獻(xiàn)[2]中的Must、May和Persistence分析方法。由于三個(gè)分析的流程是類似的，因此僅以本文所用到的最主要的Persistence分析，介紹抽象解釋對一個(gè)循環(huán)體進(jìn)行分析的主要算法。Must和May分析是類似的。

Persistence分析算法

功能：給定一個(gè)循環(huán)體，對其進(jìn)行Persistence分析

函數(shù)名稱：Persistence_Analysis （ loop ）

輸入：mloop_t類型的循環(huán)體——loop

輸出：每條指令的Persitence分析結(jié)果，記錄在相應(yīng)的指令信息中

3 整數(shù)線性規(guī)劃問題建模

通過對多層Cache分析，得到了程序每條指令在各個(gè)層次上的Persistence分析結(jié)果（在最外層，還有Must和May分析的結(jié)果）。例如一條指令A(yù)位于第三層次的某個(gè)循環(huán)體內(nèi)，那么指令A(yù)一定也屬于某個(gè)第二層次的循環(huán)體以及某個(gè)第一層次的循環(huán)體。指令A(yù)在這三個(gè)層次對應(yīng)的循環(huán)體中，都有相應(yīng)的Persistence分析結(jié)果。

利用這一結(jié)果將程序的WCET計(jì)算問題，用一個(gè)整數(shù)線性規(guī)劃問題進(jìn)行描述。

3.1 目標(biāo)函數(shù)

計(jì)算程序的WCET，就是用整數(shù)線性規(guī)劃的方式將程序的執(zhí)行時(shí)間加以表示，然后讓整數(shù)線性規(guī)劃的求解器來求這個(gè)表達(dá)式的最大值。因此需要設(shè)計(jì)目標(biāo)函數(shù)，可以表示為公式（1）的形式。

其中，Ci表示每個(gè)基本塊執(zhí)行一次的執(zhí)行時(shí)間，Xi表示每個(gè)基本塊執(zhí)行的次數(shù)。將各個(gè)基本塊的總的執(zhí)行時(shí)間求和，并求其最大值，便可得到程序的WCET。其中，Ci又可以表示為三個(gè)部分，CAM、CAH、CFM分別對應(yīng)于當(dāng)前基本塊中，所有AM、AH、FM指令對應(yīng)的執(zhí)行時(shí)間。由于本文對程序進(jìn)行多層分析，因此CFM可以進(jìn)一步被表達(dá)為公式（2）的形式。

對于所有被判定為FM的指令，必須區(qū)分它是在哪一個(gè)層次上被判定為FM的。假定在第j層次上，有mj條指令被判定為FM，那么用 表示這mj條指令失效的次數(shù)，用 表示這mj條指令命中的次數(shù)。因此，所有的FM指令最終的執(zhí)行時(shí)間表達(dá)式可以用公式（2）來表達(dá)。

3.2 路徑信息約束

為了求解這個(gè)整數(shù)線性規(guī)劃的問題，還需要一些約束。在研究WCET分析問題中，第一類約束是路徑信息約束，如公式（3）所示。

公式（3）表明，一個(gè)基本塊的執(zhí)行次數(shù)，等于它對應(yīng)的所有入邊被執(zhí)行的次數(shù)之和，也等于它對應(yīng)的所有出邊被執(zhí)行的次數(shù)之和。

3.3 循環(huán)次數(shù)約束

還需要一些約束來表明程序的循環(huán)最多會(huì)執(zhí)行多少次。假定對于某個(gè)循環(huán)體，Xi是循環(huán)體的尾節(jié)點(diǎn)（Tail），Xj是循環(huán)體的入節(jié)點(diǎn)（Entry），循環(huán)最多執(zhí)行p次，那么可以知道，循環(huán)體的入節(jié)點(diǎn)每執(zhí)行一次，循環(huán)體的尾節(jié)點(diǎn)最多可以執(zhí)行p次。為了表達(dá)這一信息，引入了循環(huán)次數(shù)約束，其形式如公式（4）所示。

3.4 基本塊失效總次數(shù)約束

在公式（2）中，描述一個(gè)基本塊中，所有被判定為FM指令的執(zhí)行時(shí)間。對于其中的失效和命中次數(shù)變量，還需要根據(jù)其所在的層次，施加必要的約束。以一個(gè)位于某個(gè)第二層循環(huán)體的基本塊Xi為例，假定它所屬的第一、二層的循環(huán)體的入節(jié)點(diǎn)分別為X1，X2。那么，可以有公式（5～8）的一些約束。這些約束描述了在某個(gè)特定循環(huán)層次上，被判定為FM的指令，其失效次數(shù)的上限，以及失效次數(shù)和命中次數(shù)之和為多少。

將上述的目標(biāo)函數(shù)和所有的約束組合成為一個(gè)整數(shù)線性規(guī)劃的問題，通過求解目標(biāo)函數(shù)所表達(dá)的極值問題，可以求解出程序的WCET。

4 結(jié)束語

通過對6個(gè)測試程序進(jìn)行實(shí)驗(yàn)，可以看出，通過多層Cache分析，可以有效的提高WCET的分析精度。實(shí)際效果，根據(jù)程序自身的特性不同而不同。對于那些循環(huán)體很小的程序，多層Cache分析的精度收益不大；但是對于外層循環(huán)體很大（難以完全裝入Cache）而內(nèi)層循環(huán)體很小的程序，采用多層Cache分析能夠有效提高分析精度。

參考文獻(xiàn)：

[1]Jane， W.S. Liu. Real-Time Systems. Pearson Education，2002.

[2]Ferdinand C， Wilhelm R. Fast and Efficient Cache Behavior Prediction for Real-Time Systems [J].Real-Time System， 1999，17（2-3）：131-181.

[3]Yau-Tsun Steven Li and Sharad Malik. Performance Analysis of Embedded Software Using Implicit Path Enumeration [A].in Workshop on Languages， Compilers and Tools for Real-Time Systems [C].1995，456-461.

作者簡介：毛金玲（1974-），女，遼寧海城人，設(shè)備工程系，講師，碩士，研究方向：軟件開發(fā)。

作者單位：遼寧建筑職業(yè)學(xué)院，遼寧遼陽 111000