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

孟凡奇

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

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

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

1 基本原理

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

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

2 舉例分析

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

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

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

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

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

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

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

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

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

[參考文獻]

[1]孫昌愛，金茂忠，劉超，等.程序執(zhí)行時間的靜態(tài)預估與可視化分析方法[J].軟件學報，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.