基于MPA與靜態預估的最壞執行時間分析方法

李軍義，李 雙，張 焱，李仁發

（1.湖南大學信息科學與工程學院，長沙 411000；2.湖南省嵌入式與網絡計算重點實驗室，長沙 411000）

基于MPA與靜態預估的最壞執行時間分析方法

李軍義1，2，李 雙1，2，張 焱1，2，李仁發1，2

（1.湖南大學信息科學與工程學院，長沙 411000；2.湖南省嵌入式與網絡計算重點實驗室，長沙 411000）

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

嵌入式軟件；實時性；最壞執行時間；最小傳播算法；靜態預估分析

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

1 概述

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

在大部分工業生產中，通常使用一種首尾相連的測試方法來預估程序代碼片執行時間的上界和下界，這種方法通常被稱為動態時序分析。在該研究領域，同時還存在一種通過分析程序流信息和處理

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

本文采用靜態分析方法對程序進行WCET估值，利用MPA算法對程序流進行分析，得到程序每個節點的最大執行次數，并由底層分析得出對應節點的最壞執行時間，由此得到程序的WCET值。

2 相關研究

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

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

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

3 WCET分析方法

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

3.1 MPA算法模型

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

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

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

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

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

定義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值能提高測試效率，簡化測試過程。

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

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

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

3.2 基于靜態預估分析的底層指令周期獲取

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

靜態預估可視化分析方法通過分析中間代碼段與源程序中語句的對應關系，提取和計算CPU周期數。該方法將程序的分析過程分為3層：可視化分析層，源代碼分析層和匯編代碼分析層。可視化分析層的分析過程類似于程序流分析，通過分析程序流，獲得程序基本塊的樹形結構。但是可視化分析過程并沒有使用象征性上界預估、PIP方法或MPA方法獲得程序流的嚴謹約束，存在不足。而MPA算法具有自動計算，時間復雜度較低等優點，本文方法使用MPA算法代替可視化分析過程進行頂層分析。源代碼分析層是代碼底層分析的過度階段，通過對樹形結構進行分析，獲取代碼基本塊。匯編代碼分析層最終將基本塊編譯成底層匯編代碼。通過計算基本塊的機器指令周期，獲得程序的每個基本塊的機器指令周期值。

4 基于MPA和靜態預估的WCET分析方法

4.1 WCET分析方法

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

圖1 WCET方法的測試流程

4.2 基于WCET方法的測試程序

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

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

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

圖2 測試程序L的程序節點

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

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

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

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

得到如下簡化結果：

其中，λ0，λ1，…，λ8為相應代碼塊的機器指令指令周期，需要通過底層分析獲得。本文方法使用靜態預估可視化分析方法進行底層分析。式（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結果集。

程序最終PWCET化簡為：

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

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

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

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

5 實驗與結果分析

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

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

表1 2類方法的預估WCET值對比

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

6 結束語

本文提出一種基于MPA和靜態預估的WCET分析方法。該方法使用MPA算法改進靜態預估可視化分析，對原靜態預估分析方法的中間代碼進行分析，將程序底層匯編代碼同MPA算法中邊節點對應，然后結合象征性上界約束對頂層程序流中特殊循環結構進行分析，獲得最終精確的WCET值。該方法較好地契合了WCET分析領域底層分析與程序流解析脫節的研究現狀，為頂層分析技術與先進底層分析技術的高效整合提供了借鑒。本文通過實例展示了新方法的分析過程，并與基于程序控制流程圖的程序執行時間靜態分析方法的測試結果進行對比。雖然本文方法的測試結果會產生一定的高估，但由于引入M PA算法進行自動化測試，相比于手工測試方法有很大的改進。隨著處理器技術的發展，底層處理器結構越來越復雜，下一步工作將主要以底層分析為主，提高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］ 孫昌愛，金茂忠，劉 超.程序執行時間的靜態預估與可視化分析方法［J］.軟件學報，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與靜態預估的最壞執行時間分析方法［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

廣東省產學研合作重大專項基金資助項目（2012-391）。

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

2014-09-28

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