多層Cache分析模塊的設計與測試

毛金玲

摘 要：該文主要介紹了實驗是在什么樣的系統配置和測試數據集上開展的。通過實驗結果的對比可以看出，采用多層Cache分析，可以有效的發掘程序Cache訪問的局部特性，得到更加精確的WCET估計值。

關鍵詞：WCET 測試數據 多層Cache分析

中圖分類號：UG64 文獻標識碼：A 文章編號：1672-3791（2015）02（b）-0012-02

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

1 系統設計原則

根據服務對象以及功能性需求，人們認為“基于抽象解釋技術的多層Cache分析”模塊的設計應符合以下原則。（1）功能穩定。Cache是處理機微體系結構中的重要組成部件，因此Cache分析模塊也是一個WCET分析工具中的核心組件。其分析結果，直接影響到工具的其它分析功能。因此，該模塊的分析必須保證功能完整穩定，把可能出現的錯誤降到最低。（2）規范性。從軟件周期上來考慮，軟件維護階段在軟件生命周期或生存期中占較大比重，有的可達軟件生存周期的50%～70%。因此，在該軟件的設計過程中，在各方面都應該遵從業界廣為接受的軟件開發規范，以盡可能提高后期軟件的可維護性。（3）良好的可擴展性。可擴展性是軟件工程追求的目標，能夠大大提高軟件的復用程度，降低開發成本。從該文所設計的軟件自身特性來看，未來還有很大的功能擴展空間。為此，該軟件的設計應盡可能模塊化，并具有良好的層次結構。各模塊與各層次之間定義明確的接口。這樣在未來增加新功能的過程中，可以利用已有的功能實現更加復雜的功能，并大大增加代碼的可重用性。

2 系統總體設計

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

在這一小節中，主要介紹給定一個程序的控制流程圖，如何從中抽取程序的層次結構。在介紹這一功能的實現之前，首先用一個簡單的例子，闡明對于一個一般的程序，它的層次結構應該是一種什么樣的構造。

圖2表示了一個復雜的程序控制流程圖，該文將利用這個控制流程圖來介紹程序層次結構的概念。首先，為了簡化表達，把整個程序看作是一個最外層的循環體，這樣，整個大圖就占據一個程序的層次，稱其為Level-0，如圖中虛線所示。在這個程序的控制流程圖中，可以看到，最上層的結構是一個分支結構，有一個循環，Loop1，位于程序左邊的分支中；有兩個循環，Loop2和Loop3，位于程序右邊的分支中，且Loop3位于Loop2中，前者是后者的內層嵌套循環。根據這一關系，可知，Loop1和Loop2都是整個程序中的第一級循環，因此這兩個循環都屬于Level-0的下一個層次，稱其為Level-1。類似的，Loop3位于Loop2的內部，因此，它存在于Loop2所在層次的下一層，稱其為Level-2。

以上程序的層次結構，也可以通過圖3所示的樹形結構進行表示。其中，整個程序所在的Level-0是樹的根節點，它有兩個樹枝節點，分別對應于位于Level-1的Loop1和Loop2；Loop2又有一個葉子節點，為Loop3，位于Level-2。

對于一個程序及其對應的控制流程圖而言，需要得到的就是圖3所示的層次結構。在下面一小節中，將介紹采用什么算法將一個給定的控制流程圖對應的層次結構抽取出來。

3 參數配置與測試程序集

系統體系結構參數主要包括Cache的相連度、Cache的塊大小、Cache中包含的Cache組的數量和指令到內存存取時間等。該實驗將這幾項特性的參數配置為如表1所示。所有的循環上限設置為10。

實驗部分所采用的程序是從Mlardalen測試程序集中選取的6個測試程序。表2列出了關于這6個測試程序的一些基本信息，包括程序中包含的指令條數和循環個數等，這些信息能夠在一定程度上反映出程序的復雜度。

4 實驗結果

針對上一小節所給出的體系結構特性參數，也就是系統Cache配置參數，針對LRU替換算法，分別計算表2中的6個測試程序的WCET估計值。實驗結果如表3所示。該文分別給出了兩組實驗結果。第一組實驗結果對應于傳統的單層Cache分析方法，第二組實驗結果對應于本文設計實現的多層Cache分析方法。通過對比兩種方法所得到的實驗數據，可以分析該文所提出的分析方法的優點。

該文定義單層Cache分析的WCET估計值為W1，多層Cache分析的的WCET估計值為W2，那么該文定義分析精度的提高為：（W1、W2）/W1。

從上面的實驗結果可以看出，通過采用多層Cache分析，平均可以將程序的WCET分析精度提高大約9%。其中，bs程序的分析結果沒有任何提高，這是因為該程序中的循環體非常小，都能夠被放入整個Cache中，因此不存在外層循環不足夠放入Cache而內層循環可以放入Cache的情況，因此，對于這種特殊的程序，多層分析的效果無法展現出來。matmult程序的分析精度的提高幅度也不是很大，這是因為該程序的循環體也同樣都比較小。雖然該程序的執行時間較長，但是由于循環體的大小問題，能夠通過多層分析獲得的精度提高有限。其他的測試程序比較有效的展現了采用多層分析能夠得到的分析精度的提高。

5 結語

該文主要介紹了實驗是在什么樣的系統配置和測試數據集上開展的。通過實驗結果的對比可以看出，采用多層Cache分析，可以有效的發掘程序Cache訪問的局部特性，得到更加精確的WCET估計值。

參考文獻

[1] Yau-Tsun Steven Li，Sharad Malik， Andrew Wolfe.Efficient Microarchitecture Modeling and Path Analysis for Real-Time Software [A]. Proceedings of the IEEE Real-Time Systems Symposium [C]，1995：298.

[2] Andreas Ermedahl.A Modular Tool Architecture for Worst-Case Execution Time Analysis [D].Sweden：Uppsala University，2003.

[3] 孫昌愛，金茂忠.基于程序插裝的動態測試技術實現[J].小型微型計算機系統，2001（12）：1475-1479.