基于隱藏路徑枚舉技術(shù)的最差情況執(zhí)行時(shí)間分析原理淺析

孟凡奇

摘 要：最差情況執(zhí)行時(shí)間分析是系統(tǒng)實(shí)時(shí)性評估、任務(wù)可調(diào)度性分析以及軟硬件協(xié)同設(shè)計(jì)的基礎(chǔ)，本文以Chronos工具為例，對最常用的隱藏路徑枚舉技術(shù)的基本原理進(jìn)行簡要分析。

關(guān)鍵詞：隱藏路徑枚舉技術(shù)；最差情況執(zhí)行時(shí)間；實(shí)時(shí)性

最差情況執(zhí)行時(shí)間（Worst-case Execution Time，WCET）分析通常被分為動態(tài)、靜態(tài)和混合3種方法。其中，靜態(tài)方法通常要經(jīng)過：控制流分析；處理器建模；WCET計(jì)算3個(gè)處理環(huán)節(jié)。隱藏路徑枚舉技術(shù)（Implicit Path Enumeration Technique，IPET）是靜態(tài)WCET分析方法在計(jì)算環(huán)節(jié)最常用的技術(shù)。

1 基本原理

該方法的基本思想是在分析程序控制流圖的基礎(chǔ)上，使用整數(shù)線性規(guī)劃求解最長執(zhí)行路徑。為了進(jìn)一步說明隱藏路徑枚舉法的基本原理，首先介紹基本塊的定義。

定義1 基本塊[1]是目標(biāo)程序中這樣的連續(xù)語句序列：（1）只有第一條語句可以有多個(gè)入口；（2）只有最后一條語句可以有多個(gè)出口；（3）內(nèi)部不含分支、跳轉(zhuǎn)語句。

2 舉例分析

下面以程序“insertsort.c”為例介紹IPET方法。首先對源程序（圖1（a）所示）進(jìn)行編譯生成可執(zhí)行程序，然后對可執(zhí)行程序反匯編，并生成控制流圖如圖2（a）所示。

該控制流圖的字符表達(dá)形式如圖1（b）所示，其中“3： 400358：[4，3]”的含義是基本塊3的起始地址是400358，可以到達(dá)基本塊4和基本塊3。在獲得控制流圖的基礎(chǔ)上，針對基本塊的執(zhí)行次數(shù)（即，循環(huán)上界、不可行路徑）添加約束，其字符表達(dá)形式如圖1（c）所示。例如，“c0.0=1”的含義是過程P0中的基本塊B0的執(zhí)行次數(shù)是1次。接下來需要根據(jù)控制流圖和約束生成整數(shù)線性規(guī)劃所需的計(jì)算表達(dá)式。這里需要用到以下定理[2]：

定理1 基本塊的執(zhí)行次數(shù)等于流入該基本塊的所有邊的執(zhí)行次數(shù)，也等于從該基本塊流出的所有邊的執(zhí)行次數(shù)。即：

其中，NB表示基本塊B的執(zhí)行次數(shù)。 表示從基本塊B流出的所有邊的執(zhí)行次數(shù)。 表示流入到基本塊B的所有邊的執(zhí)行次數(shù)[2]。

為了計(jì)算圖1（a）中程序的最差執(zhí)行時(shí)間，需要使用整數(shù)線性規(guī)劃求解基本塊B2的執(zhí)行次數(shù)NB2，以使WCET最大化，即：

其中，NBi是基本塊Bi的執(zhí)行次數(shù)。Ci為基本塊Bi的執(zhí)行時(shí)間，利用指令模型、Cache模型、流水線模型及分支預(yù)測模型計(jì)算得到。

除了圖2中已知和推理出來的表達(dá)式以外，還可以利用定理1從圖2（c）得到以下表達(dá)式：

顯然，由于基本塊NB2的執(zhí)行時(shí)間有C2>0，在其他基本塊的執(zhí)行次數(shù)已經(jīng)確定的情況下，NB2越大，整個(gè)程序的執(zhí)行時(shí)間越長。因此，整數(shù)線性規(guī)劃求解的結(jié)果必然是NB2=9。至此，所有基本塊的執(zhí)行次數(shù)都已確定，利用公式2即可獲得程序的WCET估計(jì)值。

綜上所述，隱藏路徑枚舉技術(shù)在實(shí)際應(yīng)用中表現(xiàn)出了比較好的求解效率。盡管如此，由于其基于整數(shù)線性規(guī)劃，而整數(shù)線性規(guī)劃的描述能力并非是最強(qiáng)的，依然無法描述復(fù)雜的程序控制流程信息。同時(shí)，整數(shù)線性規(guī)劃問題的求解效率會隨著程序復(fù)雜度的提高而大幅增加。

[參考文獻(xiàn)]

[1]孫昌愛，金茂忠，劉超，等.程序執(zhí)行時(shí)間的靜態(tài)預(yù)估與可視化分析方法[J].軟件學(xué)報(bào)，2003，14（1）：68-75.

[2]Li X，Liang Y，Mitra T，et al.Chronos：A timing analyzer for embedded software[J].Science of Computer Programming，2007， 69（1）：56-67.