毛金玲

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

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

中圖分類(lèi)號(hào)：UG64 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2015）02（b）-0012-02

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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] 孫昌愛(ài)，金茂忠.基于程序插裝的動(dòng)態(tài)測(cè)試技術(shù)實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng)，2001（12）：1475-1479.