多層Cache分析模塊的設(shè)計與測試

毛金玲

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

關(guān)鍵詞：WCET 測試數(shù)據(jù) 多層Cache分析

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

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

1 系統(tǒng)設(shè)計原則

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

2 系統(tǒng)總體設(shè)計

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

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

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

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

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

3 參數(shù)配置與測試程序集

系統(tǒng)體系結(jié)構(gòu)參數(shù)主要包括Cache的相連度、Cache的塊大小、Cache中包含的Cache組的數(shù)量和指令到內(nèi)存存取時間等。該實驗將這幾項特性的參數(shù)配置為如表1所示。所有的循環(huán)上限設(shè)置為10。

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

4 實驗結(jié)果

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

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

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

5 結(jié)語

該文主要介紹了實驗是在什么樣的系統(tǒng)配置和測試數(shù)據(jù)集上開展的。通過實驗結(jié)果的對比可以看出，采用多層Cache分析，可以有效的發(fā)掘程序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] 孫昌愛，金茂忠.基于程序插裝的動態(tài)測試技術(shù)實現(xiàn)[J].小型微型計算機系統(tǒng)，2001（12）：1475-1479.