基于抽象解釋技術的多層Cache分析的設計與實現

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

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

中圖分類號：TP311.1

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

1 系統總體設計

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

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

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

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

2 基于抽象解釋的Cache分析功能的設計與實現

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

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

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

Must、May和Persistence分析都是根據程序的控制流程信息來對抽象的指令Cache狀態進行分析的，并且這三種分析所對應的分析過程都是一個不斷迭代的過程。當這三種分析都各自收斂到一個固定點（Fixpoint）的時候，這三種分析便可以結束對抽象的指令Cache狀態的分析。此時，根據此抽象的指令Cache狀態中的內容可以確定出此程序中每條指令在指令Cache中的命中情況，從而可以得到關于這些指令的分類情況。

2.2 多層Cache分析的主要過程

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

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

Persistence分析算法

功能：給定一個循環體，對其進行Persistence分析

函數名稱：Persistence_Analysis （ loop ）

輸入：mloop_t類型的循環體——loop

輸出：每條指令的Persitence分析結果，記錄在相應的指令信息中

3 整數線性規劃問題建模

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

利用這一結果將程序的WCET計算問題，用一個整數線性規劃問題進行描述。

3.1 目標函數

計算程序的WCET，就是用整數線性規劃的方式將程序的執行時間加以表示，然后讓整數線性規劃的求解器來求這個表達式的最大值。因此需要設計目標函數，可以表示為公式（1）的形式。

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

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

3.2 路徑信息約束

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

公式（3）表明，一個基本塊的執行次數，等于它對應的所有入邊被執行的次數之和，也等于它對應的所有出邊被執行的次數之和。

3.3 循環次數約束

還需要一些約束來表明程序的循環最多會執行多少次。假定對于某個循環體，Xi是循環體的尾節點（Tail），Xj是循環體的入節點（Entry），循環最多執行p次，那么可以知道，循環體的入節點每執行一次，循環體的尾節點最多可以執行p次。為了表達這一信息，引入了循環次數約束，其形式如公式（4）所示。

3.4 基本塊失效總次數約束

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

將上述的目標函數和所有的約束組合成為一個整數線性規劃的問題，通過求解目標函數所表達的極值問題，可以求解出程序的WCET。

4 結束語

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

參考文獻：

[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-），女，遼寧海城人，設備工程系，講師，碩士，研究方向：軟件開發。

作者單位：遼寧建筑職業學院，遼寧遼陽 111000