基于MPA與靜態(tài)預(yù)估的最壞執(zhí)行時間分析方法

李軍義，李 雙，張 焱，李仁發(fā)

（1.湖南大學(xué)信息科學(xué)與工程學(xué)院，長沙 411000；2.湖南省嵌入式與網(wǎng)絡(luò)計算重點實驗室，長沙 411000）

基于MPA與靜態(tài)預(yù)估的最壞執(zhí)行時間分析方法

李軍義1，2，李 雙1，2，張 焱1，2，李仁發(fā)1，2

（1.湖南大學(xué)信息科學(xué)與工程學(xué)院，長沙 411000；2.湖南省嵌入式與網(wǎng)絡(luò)計算重點實驗室，長沙 411000）

針對現(xiàn)有嵌入式系統(tǒng)最壞執(zhí)行時間（WCET）的靜態(tài)分析方法效率低下問題，利用最小傳播算法對程序流進行分析，獲得程序中每一個基本塊的最小樹約束，通過象征性循環(huán)上界約束對所求函數(shù)中的內(nèi)部循環(huán)變量進行再次約束，并結(jié)合最小樹約束獲得程序的WCET表達式。使用靜態(tài)預(yù)估分析方法對每一個基本塊的底層指令周期進行絕對估值，將底層指令周期代入WCET表達式計算出程序最終的WCET值。實驗結(jié)果表明，與基于程序控制流程圖的程序執(zhí)行時間靜態(tài)分析方法相比，該方法在保證程序分析精度的同時，大幅提高了分析效率。

嵌入式軟件；實時性；最壞執(zhí)行時間；最小傳播算法；靜態(tài)預(yù)估分析

DO I：10.3969/j.issn.1000-3428.2015.10.015

1 概述

嵌入式軟件的實時性指標是保證軟件安全性和可靠性的重要標準，因此，嵌入式軟件對程序的執(zhí)行時間有著嚴格要求。對任務(wù)執(zhí)行有嚴格的時間約束，不允許任何延時的系統(tǒng)稱為硬實時系統(tǒng)，可以容許任務(wù)在一定范圍內(nèi)的延時稱為軟實時系統(tǒng)。一般而言，最壞執(zhí)行時間（Worst-case Execution Time， WCET）分析都是針對硬實時系統(tǒng)。WCET分析是指計算給定應(yīng)用程序代碼片段執(zhí)行時間的上限，這里代碼片段執(zhí)行時間定義為執(zhí)行代碼片段所花費的處理器時間。

在大部分工業(yè)生產(chǎn)中，通常使用一種首尾相連的測試方法來預(yù)估程序代碼片執(zhí)行時間的上界和下界，這種方法通常被稱為動態(tài)時序分析。在該研究領(lǐng)域，同時還存在一種通過分析程序流信息和處理

器特性來預(yù)估程序執(zhí)行時間的方法，這種方法稱為靜態(tài)方法。動態(tài)方法主要通過點對點的測試獲取程序的WCET值，動態(tài)測試方法普遍會低估程序的WCET值。而靜態(tài)方法由于能通過靜態(tài)分析獲取程序保守的WCET上界，成為研究領(lǐng)域的主流方法，但靜態(tài)分析方法會高估程序的WCET值。一般而言，靜態(tài)分析方法高估程序WCET值的程度與通過程序流分析和底層分析獲得的約束表達式數(shù)量成反比。WCET測試靜態(tài)方法通過程序路徑分析和底層建模，獲取程序的安全時間上界。靜態(tài)方法的計算過程一般分為3個步驟：程序流分析，底層分析以及計算。

本文采用靜態(tài)分析方法對程序進行WCET估值，利用MPA算法對程序流進行分析，得到程序每個節(jié)點的最大執(zhí)行次數(shù)，并由底層分析得出對應(yīng)節(jié)點的最壞執(zhí)行時間，由此得到程序的WCET值。

2 相關(guān)研究

程序流分析的研究對象是程序的源代碼，首先通過抽象解釋對程序語義進行分析，尋找程序狀態(tài)不變節(jié)點，例如變量 χ的取值在3～5之間。抽象分析方法不需要精確知道整個程序的執(zhí)行節(jié)點，文獻［1］提出一種基于抽象解釋的點陣模型，該模型用程序流圖對程序語義進行分析，簡化分析過程，在允許結(jié)果不嚴格精確的條件下，提高分析效率。文獻［2-3］分別采用數(shù)值域分析和節(jié)點線性近似值分析來抽象程序節(jié)點的關(guān)系。文獻［4］提出一種新的分析方法：一致性分析，該方法可用于數(shù)值向量化，發(fā)現(xiàn)節(jié)點的特殊屬性。當程序較復(fù)雜時，程序通常會產(chǎn)生依賴于另一個節(jié)點的約束，例如 P節(jié)點的變量χ在節(jié)點q處取值小于2y，這種復(fù)雜約束稱為多面體域，文獻［5-6］提出了對多面體域的分析方法。通過對程序源代碼執(zhí)行路徑的分析，結(jié)合抽象解釋，產(chǎn)生類似于程序流圖（Program Flow Graph，PFG）的節(jié)點流圖。程序流分析的目的主要是獲得節(jié)點之間的約束關(guān)系圖，然后通過 PIP（Parametric Integer（Linear）Programming）方法［7］對約束進行線性化。PIP方法在一段時間內(nèi)是程序流分析的主要方法，具有代表性的分析工具是Pip lib［8］工具。但在最小傳播算法（Minimum Propagation Algorithm，MPA）［9］提出后，由于MPA算法具有較低的時間復(fù)雜度和分析代價，成為替代PIP分析方法的常用方法。

底層分析在程序流分析的基礎(chǔ)上，分析每一個節(jié)點運行的機器時間上界。底層分析可以通過對每個節(jié)點進行機器指令分析獲得。因為對計算機底層cache結(jié)構(gòu)、處理器結(jié)構(gòu)和流水線結(jié)構(gòu)分析能獲得更多的約束方程，所以底層分析逐漸成為WCET分析的一個全新領(lǐng)域。但是底層分析獲得的約束和反饋必須和程序流分析中的節(jié)點約束相結(jié)合，才能精確程序的WCET上界。

文獻［10］通過對指令cache的分析，結(jié)合CCG（Cache Conflict Graph）產(chǎn)生約束方程。產(chǎn)生的約束方程通過節(jié)點入口、出口在程序流分析的接口進行合并，產(chǎn)生更加精確的時間上界。文獻［11］通過分析每一個節(jié)點在處理器中的狀態(tài)，來獲得更多的線性約束。理論上cache分析技術(shù)可以使靜態(tài)分析誤差精確到2%～2.5%，但是，當對較大或較復(fù)雜程序進行分析時，對每一條語句進行復(fù)雜分析會使靜態(tài)分析變得異常繁瑣。同時，當程序塊較小時，函數(shù)調(diào)用過程中上下文切換時間、中斷時間會產(chǎn)生更多的時間開銷，因此，底層分析不能太過復(fù)雜。文獻［12-13］對不同共享總線進行分析，但是它們都沒有與管道、程序路徑分析相結(jié)合，并且分析過程都是基于體系結(jié)構(gòu)簡單的時間異常自由體系。在底層分析方法中，還存在一種將抽象解釋和共享總線、指令 cache相結(jié)合的方法［14］，但是目前還不能確定將該方法應(yīng)用于多核處理器和共享總線中是否穩(wěn)定。為增加研究人員對多核系統(tǒng)的研究，文獻［15］提出可預(yù)測多核體系，文獻［16］提出代碼轉(zhuǎn)換的可預(yù)測運行模型。但是這 2種方法都不能查找WCET高估的代碼源。文獻［17-18］對共享總線或cache單獨建模，但并未和程序分支以及處理器體系相結(jié)合。綜上所述，在多核 WCET分析中，對微型體系組件進行建模分析的研究進展緩慢。靜態(tài)預(yù)估分析技術(shù)［19］將程序的中間語言作為底層分析節(jié)點，其產(chǎn)生的匯編語言能和MPA算法中的節(jié)點邊相對應(yīng)，所以，本文使用靜態(tài)預(yù)估分析方法對程序進行底層分析。

3 WCET分析方法

本節(jié)將簡要介紹MPA算法的運算過程，同時給出WCET分析過程中基本塊的定義以及MPA算法運算過程中的條件簡化規(guī)則，最后介紹基于靜態(tài)預(yù)估分析獲取底層指令周期的新方法。

3.1 MPA算法模型

文獻［5］介紹了基于參數(shù)WCET分析方法，文獻［9］更加詳細地介紹該方法的分析步驟。參數(shù)分析方法使用式（1）對程序的WCET值進行計算：

其中，PCFP是對程序進行程序流分析和底層分析后得到的節(jié)點函數(shù)；ECFP為該程序節(jié)點底層機器周期的最大執(zhí)行次數(shù)，ECFP的計算過程和PCFP相似。通過式（1）便能計算出程序的 WCET值。

其中，cq是程序節(jié)點的WCET值；Pq是程序節(jié)點執(zhí)行次數(shù)的上界。使用式（2）能夠計算得到程序流分析的節(jié)點函數(shù)。MPA算法使用基本塊分析法，將具有相同機器周期的語句或若干語句定義成基本塊，得到 PCFL=λP0，P1，P2，…，Pn，其中，n是基本塊的個數(shù)。由于靜態(tài)預(yù)估分析方法并不要求每個基本塊機器周期相同，因此本文方法將基本塊定義如下：

定義1（順接） 對于任意語句或基本塊i，j，如果i運行之后必定會運行j，則有Statementi和Statementj存在順接關(guān)系，且Statementi是Statementj的前順接，定義為Pre（Statementj）=Statementi。Statementj是Statementi的后順接，定義為suc（Statementi）=Statementj。

定義2（基本塊） 基本塊 Bi，j可以由有限條語句組成，并且任意基本塊運行結(jié)束狀態(tài)唯一，不存在2種不同的運行結(jié)束狀態(tài)。

定義3（組合塊） 如果存在 Pre（Bi，n）=Bm，n，并且eχecute1（Bi，n）=eχecute2（Bi，n）=…=eχecuten（Bi，n），則基本塊Bi，n為由Bi，j和 Bm，n，組合成的新基本塊，稱為組合塊。如果2個基本塊能組成組合塊，用組合塊的WCET值替代組成組合塊的原模塊的WCET值能提高測試效率，簡化測試過程。

如果某行是跳轉(zhuǎn)語句或者分支語句，則它不能和其他基本塊形成組合塊。因為如果它是組合塊，將與定義2矛盾。

定理（MPA簡化） 在使用MPA算法獲取節(jié)點χm約束的過程中，如果 χm的約束條件 χm≤χk，且對于所有的χk≤χa+χb，存在a=m或b=m，則條件χk≤χa+χb可以省略。

證明：因為當存在約束條件χm≤χk時，m已經(jīng)加入隊列 conteχt，當遇到 χk≤χa+χb時，因為隊列由于使用PIP算法計算WCET值的時間復(fù)雜度較大，甚至存在計算瓶頸，而MPA算法時間復(fù)雜度較小，自動化程度較高，因此現(xiàn)在研究領(lǐng)域大多使用M PA算法替換PIP算法。MPA算法計算PCFP公式如下：conteχt和集合｛a，b｝交集不為空，χk≤χa+χb被過濾，等價于條件χk≤χa+χb被去除，得證。

3.2 基于靜態(tài)預(yù)估分析的底層指令周期獲取

MPA算法和PIP算法都是基于參數(shù)的WCET計算方法，為了計算程序的WCET，ECFP值必須經(jīng)過底層分析獲得。隨著處理器的運算速度加快，處理器的運算結(jié)構(gòu)越來越復(fù)雜，目前還沒有工具能對代碼運行過程中流水線、處理器的變化作出精確的估計。對每一條語句進行繁瑣的流水線分析將會嚴重影響程序WCET值的分析速度。特別是對較大程序進行WCET分析時，過度注重處理器細節(jié)將會使程序的靜態(tài)分析過程工程量巨大。所以，本文將采用程序底層指令周期靜態(tài)預(yù)估分析技術(shù)對程序進行底層分析。該方法在某種程度上忽略流水線結(jié)構(gòu)，無論是多流水線處理器還是單流水線處理器，都使用單流水線估計代碼塊的WCET值。該計算方法具有快捷準確的優(yōu)點，雖然對于多核、多流水線的處理器將會產(chǎn)生一定的高估，但這種高估并不會產(chǎn)生較大的影響。

靜態(tài)預(yù)估可視化分析方法通過分析中間代碼段與源程序中語句的對應(yīng)關(guān)系，提取和計算CPU周期數(shù)。該方法將程序的分析過程分為3層：可視化分析層，源代碼分析層和匯編代碼分析層?？梢暬治鰧拥姆治鲞^程類似于程序流分析，通過分析程序流，獲得程序基本塊的樹形結(jié)構(gòu)。但是可視化分析過程并沒有使用象征性上界預(yù)估、PIP方法或MPA方法獲得程序流的嚴謹約束，存在不足。而MPA算法具有自動計算，時間復(fù)雜度較低等優(yōu)點，本文方法使用MPA算法代替可視化分析過程進行頂層分析。源代碼分析層是代碼底層分析的過度階段，通過對樹形結(jié)構(gòu)進行分析，獲取代碼基本塊。匯編代碼分析層最終將基本塊編譯成底層匯編代碼。通過計算基本塊的機器指令周期，獲得程序的每個基本塊的機器指令周期值。

4 基于MPA和靜態(tài)預(yù)估的WCET分析方法

4.1 WCET分析方法

本文方法綜合MPA算法和靜態(tài)預(yù)估可視化分析技術(shù)，測試流程如圖1所示。首先使用MPA算法對程序進行分析，獲得程序的數(shù)據(jù)流約束。然后在獲得數(shù)據(jù)流約束的基礎(chǔ)上，查看是否存在文獻［20］中提到的6種特殊循環(huán)，如果存在，則使用循環(huán)上界約束增加約束。最后使用經(jīng)過處理之后的約束和底層分析后獲得的指令周期獲取程序最終的WCET值。

圖1 WCET方法的測試流程

4.2 基于WCET方法的測試程序

基于WCET方法的測試程序具體如下：

上述測試程序L中函數(shù)fun的功能是計算整形二維矩陣a中m行～n行元素的和，本文將展示如何通過WCET方法測試該函數(shù)的WCET值。

本文對該程序進行程序流分析，得到如圖2所示的程序節(jié)點圖。程序的每一個代碼節(jié)點都有相應(yīng)的參數(shù)容量，定義該參數(shù)容量為 P0，P1，…，P8，由圖2的分析可以得到程序的約束關(guān)系：

圖2 測試程序L的程序節(jié)點

通過MPA算法對χ0，χ1，…，χ8節(jié)點構(gòu)造MPA樹，然后計算節(jié)點的 MPA值（構(gòu)造過程參考文獻［5］），得到所有節(jié)點的M in-Tree值tq為：

該程序的WCET值定義如式（3）所示：

其中，λn表示基本塊 n的機器周期，λn值需要通過靜態(tài)預(yù)估分析獲取。

MPA算法在計算 P0，P1，…，P8的過程中，最終獲得的是基于輸入?yún)?shù)表示的函數(shù)。對于圖2中函數(shù)內(nèi)部循環(huán)控制變量j，使用文獻［20］中的6個基本樣例中的意外終止循環(huán)獲得循環(huán)上界：

得到如下簡化結(jié)果：

其中，λ0，λ1，…，λ8為相應(yīng)代碼塊的機器指令指令周期，需要通過底層分析獲得。本文方法使用靜態(tài)預(yù)估可視化分析方法進行底層分析。式（3）中的 λ0，λ1，…，λ8可以通過源代碼分析和匯編代碼分析獲得，從而計算出程序的WCET值。

底層分析代碼1具體如下：

底層分析代碼2具體如下：

上面2段底層分析代碼展示了使用本文方法進行指令分析的處理過程。其中，代碼1是在代碼編譯成底層匯編代碼之后 P5的底層分析代碼。可以看出，編號為10的代碼與編號為12的代碼之間的部分恰好等價于 MPA算法 P5邊的值 λ5。這為MPA算法在該方法中進行程序流分析提供了良好的契合點。通過對代碼1進行指令分析可以得到λ5的值。而代碼 2則是圖 2中 P7，P8，P2指令周期代碼。以此類推，還可以得到 λ0，λ1，…，λ8匯編指令周期值，從而得到 λ0，λ1，…，λ8結(jié)果集。

程序最終PWCET化簡為：

由于調(diào)用函數(shù)進行入棧和出棧操作運行11+ 19個指令周期，因此最后調(diào)用函數(shù) fun的指令周期值為：

（1）當n＜m時，PWCETL=384；

（2）當nm≥0時，PWCETL=378+323（n-m）。

假如fun函數(shù)在晶振為10 MHz、1個機器周期由6個狀態(tài)周期組成的處理器中運行并被調(diào)用，則運行fun（1，4）的最壞執(zhí)行時間為1.608 m s。同樣使用基于控制流程圖的可視化時間分析方法獲得的運行時間為 1.488 ms，由此可見，本文方法計算的WCET值結(jié)果比原方法計算出的WCET值高。分析其原因主要有：（1）MPA算法雖然減少了算法時間復(fù)雜度，提高結(jié)果精確性，但是由于MPA算法主要根據(jù)程序節(jié)點關(guān)系進行遞歸，因此會產(chǎn)生一定的高估。如測試程序L中，當取m=n時，本文方法分析結(jié)果為384，而實際情況是357，因為MPA算法根據(jù)路徑節(jié)點關(guān)系多計算了一次 P4，P5，P6。 （2）本文方法使用文獻［20］獲得循環(huán)上界，在保證WCET安全性的同時，提高了WCET的估計值。

5 實驗與結(jié)果分析

Malardalen基準程序中的duff，expint，fac，ludcmp，recursion 5個程序能較直觀地反映基準程序WCET值與程序的循環(huán)次數(shù)、遞歸次數(shù)、程序執(zhí)行路徑的關(guān)系，因此選擇這 5個程序通過控制參數(shù)分別分析其WCET值，將這些程序在晶振為10 MHz、1個機器周期由6個狀態(tài)周期組成的處理器中運行并被調(diào)用。

表1是本文方法與基于程序控制流程圖的程序執(zhí)行時間靜態(tài)分析方法［19］的對比，第1列是基準程序名稱，第2列是基準程序中與WCET值相關(guān)的參數(shù)值，第3列數(shù)據(jù)表示文獻［19］方法得出的WCET值，第4列本文方法測試得出的WCET值，第5列表示2種方法測試WCET的差異值，第6列是2種方法得到的WCET差值相對于文獻［19］方法的高估百分比。

表1 2類方法的預(yù)估WCET值對比

由表1可知，本文方法對比于文獻［19］方法測試的WCET值略高，當程序非常簡單，程序節(jié)點很少的情況下，2種方法測試得到的WCET值差異比較大，但差異值依然在合理范圍內(nèi)。但隨著程序節(jié)點的增多，程序復(fù)雜度增大，差異值越來越小，趨近于0，由此可見，本文方法對大型復(fù)雜程序測試的值很穩(wěn)定。但是使用MPA算法替換程序控制流程圖的方法，與底層分析相結(jié)合，在大型復(fù)雜程序中更具適應(yīng)性，并且大大減輕了手工分析的復(fù)雜與低效性，使高層源代碼層語句時間分析向自動化測試方向更前進了一步。

6 結(jié)束語

本文提出一種基于MPA和靜態(tài)預(yù)估的WCET分析方法。該方法使用MPA算法改進靜態(tài)預(yù)估可視化分析，對原靜態(tài)預(yù)估分析方法的中間代碼進行分析，將程序底層匯編代碼同MPA算法中邊節(jié)點對應(yīng)，然后結(jié)合象征性上界約束對頂層程序流中特殊循環(huán)結(jié)構(gòu)進行分析，獲得最終精確的WCET值。該方法較好地契合了WCET分析領(lǐng)域底層分析與程序流解析脫節(jié)的研究現(xiàn)狀，為頂層分析技術(shù)與先進底層分析技術(shù)的高效整合提供了借鑒。本文通過實例展示了新方法的分析過程，并與基于程序控制流程圖的程序執(zhí)行時間靜態(tài)分析方法的測試結(jié)果進行對比。雖然本文方法的測試結(jié)果會產(chǎn)生一定的高估，但由于引入M PA算法進行自動化測試，相比于手工測試方法有很大的改進。隨著處理器技術(shù)的發(fā)展，底層處理器結(jié)構(gòu)越來越復(fù)雜，下一步工作將主要以底層分析為主，提高WECT分析的效率及精確度。

［1］ Cousot P，Cousot R C P，Cousot R.Abstract Interpretation：A Unified Lattice Model for Static Analysis of Program s by Construction or Approximation of Fixpoints［C］//Proceedings of the 4th ACM Symposium on Principles of Programming Languages. New York，USA：ACM Press，1977：238-252.

［2］ MinéA.The Octagon Abstract Domain［J］.Higher Order Symbolically Computing，2006，19（1）：31-67.

［3］ Cousot P，Halbwachs N.Automatic Discovery of Linear Roximation of Fixpoints［C］//Proceedings of the 5th ACM Symposium on Principles of Programming Languages.New York，USA：ACM Press，1978：84-97.

［4］ Philippe G.Static Analysis of Arithmetical Congruences［J］.International Journal of Computer Mathematics，1989，30（3/4）：165-199.

［5］ Lisper B.Fully Automatic Parametric Worst-case Execution Time Analysis［C］//Proceedings of the 3rd International Workshop on Worst-case Execution Tim e Analysis.Washington D.C.，USA：IEEE Press，2003：77-80.

［6］ Bygde S.Static WCET Analysis Based on Abstract Interpretation and Counting of Elements［EB/OL］.（2010-03-15）.http：//www.mrtc.mdh.se/index.php？choice=publications&id=2144.

［7］ Feautrier P.Parametric Integer Programming［J］. Operations Research，1988，22（3）：243-268.

［8］ Piplib Website［EB/OL］.（2009-11-07）.http：//www. piplib.org/.

［9］ Stefan B，Andreas E，Bj?rn L.An Efficient Algorithm for Parametric WCET Calculation［J］.Journal of System s Architecture，2011，57（6）：614-624.

［10］ Li Y T S，Malik S，Wolfe A.Performance Estimation of Embedded Software with Instruction Cache Modeling［J］.ACM Transactions on Design Automation of Electronic System s，1999，4（3）：257-279.

［11］ Chattopadhyay S，Kee C L，Roychoudhury A，et al.A Unified WCET Analysis Framework for Multi-core Platforms［C］//Proceedings of the 18th IEEE International Real-time and Em bedded Technology and Applications Symposium.Washington D.C.，USA：IEEE Press，2012：319-329.

［12］ Rosen J.Bus Access Optimization for Predictable Implementation of Real-time Applications on Multiprocessor System s-on-chip［C］//Proceedings of the 28th IEEE International Real-time Systems Symposium. Washington D.C.，USA：IEEE Press，2007.

［13］ Chattopadhyay S，Roychoudhury A，Mitra T.Modeling Shared Cache and Bus in Multi Core Platforms for Timing Analysis［C］//Proceedings of SCOPES’10. Washington D.C.，USA：IEEE Press，2010：99-108.

［14］ Lv Mingsong.Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software［C］//Proceedings of the 31st Real-time Systems Symposium.Washington D.C.，USA：IEEE Press，2010：339-349.

［15］ Marco P.Hardware Support for WCET Analysis of Hard Real-time Multicore Systems［C］//Proceedings of the 36th Annual International Symposium on Computer Architecture.New York，USA：ACM Press，2009.

［16］ Pellizzoni R.A Predictable Execution Model for COTS-based Em bedded System s［C］//Proceedings of the 17th Real-time and Em bedded Technology and Applications Symposium.Washington D.C.，USA：IEEE Press，2011：269-279.

［17］ Yan Jun，Zhang Wei.WCET Analysis for Multi-core Processors with Shared L2 Instruction Caches［C］// Proceedings of RTAS’08.W ashington D.C.，USA：IEEE Press，2008：80-89.

［18］ Li Yan.Timing Analysis of Concurrent Program s Running on Shared Cache Multi-cores［C］//Proceedings of RTSS’09.Washington D.C.，USA：IEEE Press，2009：57-67.

［19］ 孫昌愛，金茂忠，劉 超.程序執(zhí)行時間的靜態(tài)預(yù)估與可視化分析方法［J］.軟件學(xué)報，2004，4（1）：69-75.

［20］ Knoop J，Kovács L，Zwirchmayr J.Symbolic Loop Bound Computation for WCET Analysis［M］.Berlin，Germany：Springer，2012.

編輯 陸燕菲

Worst-case Execution Time Analysis Method Based on MPA and Static Prediction

LI Junyi1，2，LI Shuang1，2，ZHANG Yan1，2，LI Renfa1，2
（1.College of Information Science and Engineering，Hunan University，Changsha 411000，China；2.Key Laboratory for Em bedded and Network Computing of Hunan Province，Changsha 411000，China）

Aiming at the problem of low efficiency for embedded system Worst-case Execution Time（WCET）static analysis methods，this paper uses Minimum Propagation Algorithm（MPA）to analyze the program flow and obtain the m in-tree of each code block.Then it gets more strict constraints through the analysis of inner loop variables of function by symbolic loop bounds computation，and gets a WCET expression through constraints of m in-tree and the loop bounds. Finally，it uses static prediction method to solve the WCET by absolute valuation of underlying instruction cycle of each basic block，and calculates the final WCET value.Experimental results show that this method increases the analysis efficiency as well as ensures accuracy com pared with program execution time static analysis method based on process control flow diagram.

embedded software；real-time；Worst-case Execution Time（WCET）；Minimum Propagation Algorithm（MPA）；static prediction analysis

李軍義，李 雙，張 焱，等.基于 MPA與靜態(tài)預(yù)估的最壞執(zhí)行時間分析方法［J］.計算機工程，2015，41（10）：76-82.

英文引用格式：Li Junyi，Li Shuang，Zhang Yan，et al.Worst-case Execution Time Analysis Method Based on MPA and Static Prediction［J］.Computer Engineering，2015，41（10）：76-82.

1000-3428（2015）10-0076-07

A

TP393

廣東省產(chǎn)學(xué)研合作重大專項基金資助項目（2012-391）。

李軍義（1970-），男，副教授、博士，主研方向：嵌入式軟件，軟件測試；李 雙、張 焱，碩士研究生；李仁發(fā)，教授、博士生導(dǎo)師。

2014-09-28

2014-11-23E-mail：junyilee@hnu.edu.cn