軟件最壞場景運行時間快速計算方法

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了軟件最壞場景運行時間快速計算方法范文，希望能給你帶來靈感和參考，敬請閱讀。

【摘要】在安全關鍵實時系統(tǒng)設計中，為了保證系統(tǒng)的安全運行，實時任務必須在截止期之前完成，否則將產生嚴重的后果。衡量系統(tǒng)實時性的重要指標是任務的最壞場景運行時間（WorstCaseExecutionTime,WCET）。論文在傳統(tǒng)靜態(tài)WCET分析方法的基礎上，提出了將拓撲排序算法應用到WCET的計算中，較大地提升了WCET的計算效率。

【關鍵詞】安全關鍵；實時系統(tǒng)；WCET

1引言

實時系統(tǒng)中對軟件運行時間，相對于非實時系統(tǒng)來說有著嚴格的時限要求，非實時系統(tǒng)有較高的運行時限容忍度，軟件偶然的運行超時并不會造成嚴重后果，僅僅是降低了系統(tǒng)的吞吐量。而實時系統(tǒng)有剛性的、嚴格的時間限制，軟件運行超出時限后，會導致系統(tǒng)不能實現(xiàn)它的預期目標，或者帶來損害甚至導致系統(tǒng)失效，對于安全關鍵實時系統(tǒng)，系統(tǒng)失效帶來的后果可能是災難性的，故它不允許任何超出時限的錯誤。實時系統(tǒng)的時間性要求更關注的WCET是在目標環(huán)境中的一個給定處理器上，完成一組任務執(zhí)行的最長可能時間，要求在邏輯結果正確的前提下，WCET在分配的時間范圍之內。實時任務的WCET與軟件的輸入、采用的算法以及軟件運行的目標環(huán)境相關。基于程序的源代碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，并獲取程序可能的執(zhí)行路徑信息，以便找出最長路徑。底層分析主要考慮處理器體系架構對軟件運行時間的影響，如何對緩存、流水線、亂序執(zhí)行、分支預測等特性進行建模來提高WCET估計的精度。WCET計算主要研究如何在控制流分析、底層分析的基礎上找出WCET的算法。

2WCET分析技術

WCET分析方法分為三種：動態(tài)測量方法、靜態(tài)分析方法和混合方法。動態(tài)測量是在目標硬件環(huán)境下，基于需求，通過給定不同的輸入對程序進行測試。通過收集程序每次的運行時間可以獲得程序的最大運行時間。然后對結果增加一定的時間余度以防止測量值低于實際的最壞場景下的運行時間，由于測試不能窮舉，所以不能保證結果是安全的。靜態(tài)分析方法是在分析處理器性能特性的基礎上，分析程序源代碼（或目標碼）以獲取程序運行時特征（如訪問的內存地址、循環(huán)邊界等），最后計算程序所占用的處理器時間。主要過程包括：控制流分析、底層分析、WCET計算。典型WCET靜態(tài)分析過程如圖1所示。目前市場上比較成熟的工具有德國Absint公司的aiT[1]?；旌戏椒ㄊ蔷C合運用靜態(tài)分析方法和動態(tài)測量方法，但這里動態(tài)測量與上述動態(tài)測量方法的內容是不相同的。在對程序中的小程序單位（如基本塊）進行動態(tài)測量（即替換了圖1中的底層分析過程）后，再進行靜態(tài)分析得到WCET。本文描述的是WCET靜態(tài)分析方法。

3控制流分析

控制流分析基于程序的源代碼或目標代碼，通過分析程序中的基本塊，對每個函數的控制流進行分析，并獲取程序可能的執(zhí)行路徑信息（執(zhí)行流），以找出最長路徑。控制流分析不考慮軟件運行環(huán)境的硬件信息，分析研究主要集中在控制流的提取、邏輯結構的表示、控制流的表示與轉換（如確定循環(huán)結構）、循環(huán)上界及不可達路徑的確定等?？刂屏鞯奶崛≈饕罁创a（或目標碼）的各種語法結構如：構等（或目標碼中的跳轉、條件跳轉等），而確定循環(huán)最大次數，不可達路徑，需要更多的語義分析，必要時需要通過注解的方式來獲取?？刂屏鞯拿枋龇ㄖ饕校赫Z法樹、域樹、時間樹、控制流圖等[2]。本文基于目標碼來生成函數的控制流圖，如圖2所示。

4底層分析

如果指令是順序執(zhí)行的，則對順序執(zhí)行的程序指令，簡單相加指令周期就可以得到程序運行時間的一個估計。而具有CACHE、流水線、亂序執(zhí)行、分支預測等硬件特性的目標處理器上，這種指令周期相加的計算方法只能得出相當不準確的WCET估計。因此，必須結合處理器各種加速特性對目標碼進行底層分析，才能獲取更為精確的WCET估計。底層分析一般包括：變量值分析、CACHE分析、流水線分析、分支預測分析等。

5WCET計算

WCET的計算是通過結合控制流分析和底層分析的結果來計算程序的WCET估計值，當前主要有三種計算方法：基于隱藏路徑枚舉的計算方法（IPET）、基于樹的計算方法及基于路徑的方法?；贗PET的計算方法通過建立程序流程和基本塊的迭代模型及用數學約束，建立目標函數，對WCET的計算就是進行最大化求解，一般使用的約束包括：結構約束和功能約束。結構約束與程序的控制流有關，功能約束則與循環(huán)邊界、路徑信息和函數調用有關。最大化求解的主要的方法是整數線性規(guī)劃ILP（IntegerLinearProgramming）。本文采用基于IPET的計算方法，但在最后計算階段未使用ILP，而是引入了一種全新的計算方法，基于拓撲排序的計算方法。

5.1拓撲排序簡介

拓撲排序（topological-sort）是指由某個集合上的一個偏序得到該集合上的一個全序的操作。拓撲排序常用來確定一個包含依賴關系集合中，事物發(fā)生的先后順序。拓撲排序是對有向無環(huán)圖中的頂點的一種排序，排序的規(guī)則是：如果存在一條從頂點A到頂點B的路徑，那么在排序中，A排在B的前面。拓撲排序的典型應用是根據作業(yè)或任務的相關性來安排它們的順序。例如，洗衣服時，洗衣機必須先洗出衣服，然后我們才能將衣服放入烘干機。這個特性可以應用到工程上的施工流程。用頂點表示子工程（活動），用有向邊表示活動間的先后關系，這就形成了一個AOV網絡（activityonvertexnetwork）有向圖。我們要對某個工程的施工流程是否可行進行論證，就是必須檢測相應的AOV網絡是否存在回路，一個AOV網絡中如果存在回路，這就意味著某個子工程的開工要以自身的完工為前提條件，這顯然是不可能的。確定AOV網絡是否存在回路則通過拓撲排序來完成。因此，研究拓撲排序算法是很有實際意義的。

5.2拓撲排序算法在WCET中的應用

從圖2可以看出，函數的控制流圖就是一個典型的有向圖。頂點表示程序基本塊，有向邊表示基本塊執(zhí)行的先后順序，如果從基本塊A到基本塊B之間存在一條路徑，則稱基本塊A是基本塊B的前趨，或稱基本塊B是基本塊A的后繼。如果[A,B]是控制流圖中的一條邊，則稱A是B的直接前趨，或稱B是A的直接后繼。拓撲排序的算法如下：①在控制流圖中選取一個函數入口基本塊（沒有前趨）。②在控制流圖中刪除該基本塊及其所發(fā)出的所有邊。③重復執(zhí)行①、②，直至輸出全部沒有前趨的基本塊。當過程結束時，如果有向圖中的所有基本塊均已輸出，則說明有向圖中不存在回路，否則說明有向圖存在回路。使用拓撲排序可以確定有向圖中是否有回路，而在控制流圖中，只有循環(huán)存在時，才會存在回路。因此，使用拓撲排序，不僅可以排列出程序基本塊執(zhí)行的先后順序，還可以準確地確定函數中的循環(huán)起點基本塊和循環(huán)終點基本塊，通過循環(huán)變化后，可以將函數控制流圖變成完整的拓撲結構圖。這樣，計算函數WCET的時間，就轉化成了對拓撲結構中每一個頂點完成時間的計算。函數的WCET實際上就是最后一個頂點完成的時間。

6結語

本文對目前WCET分析技術進行了詳細的研究討論，并給出了一個基于目標碼分析的WCET分析過程。采用拓撲排序算法，極大地簡化了WCET的計算，WCET計算的時間復雜度為O(n)，其中n表示函數基本塊的數目。經過實際測試的驗證，該方法的運算速度快于ILP。

作者：陳勇 單位：中國航發(fā)控制系統(tǒng)研究所