面向Web的WCET模式自動分析系統

姬孟洛 舒云星 黃辰林 高 翔

1(洛陽理工學院計算機與信息工程學院 河南 洛陽 471023)2(洛陽理工學院對外合作處 河南 洛陽 471023)3(國防科技大學計算機學院 湖南 長沙 410073)

面向Web的WCET模式自動分析系統

姬孟洛1舒云星2黃辰林3高 翔1

1(洛陽理工學院計算機與信息工程學院 河南 洛陽 471023)2(洛陽理工學院對外合作處 河南 洛陽 471023)3(國防科技大學計算機學院 湖南 長沙 410073)

針對傳統的WCET(Worst-Case Execution Time)分析方法面臨的精度不高和用戶使用繁瑣問題，提出一種自動分析程序模式的方法并據此設計實現了一個面向Web的WCET分析系統。首先在對源程序進行分析的基礎上，利用程序控制流程圖，通過數據流框架進行切片，獲得依賴于輸入變量的無循環控制流程圖ICFG。然后，通過對ICFG每條路徑求解，獲得程序的模式及其輸入表達式，并計算其對應的WCET。最后，將上述分析方法設計實現為針對C語言的動態鏈接庫(DLL)，并利用該DLL實現一個面向Web的WCET自動分析系統——WCET Mode Analyzer。WCET Mode Analyzer對基準程序的分析結果，驗證了該方案的有效性和應用的簡便性。

實時系統 WCET 程序模式 程序分析

0 引 言

實時系統，包括嵌入式實時系統，在進行任務調度時，需要事先知道每個任務的執行時間。這個時間，指的是最壞情況的執行時間WCET[1]。研究獲取WCET值的方法是實時系統的重要研究領域，它不僅應用于可調度性檢測，還應用于非實時系統性能分析和嵌入式系統的耗電量分析[2]。

獲取WCET值的主要方法是靜態分析。WCET靜態分析根據程序的執行流和運行程序的處理器特性這兩方面的信息來估算程序的WCET。而配置這些信息復雜、繁瑣且易于出錯。同時，靜態分析要求安全，也就是給出的估值不能低于任務可能執行時間的最大值。因此，傳統的WCET分析方法通常具有易于高估任務WCET值和不易使用的缺點[2-3]。

實時系統，尤其是嵌入式實時系統，通常都有模式。系統的一個模式定義了該系統以及其中相關任務的一種特殊行為。舉例來說，一個系統通常有啟動模式和正常模式，甚至有正常模式和緊急模式。

利用程序模式能夠更精確地計算任務WCET。這體現在三個方面。其一，根據程序不同的模式，分別計算各模式的WCET，取其中最大的WCET，比不加區分計算出的WCET要精確[4-5]。其二，不同的模式，其要求的WCET往往不同。其三，類似于WCET參數化分析，每一個模式都有一個由輸入參數值范圍構成的表達式，因此，在任務執行時才確定模式，從而有更精確的WCET值[6-7]。

針對WCET分析的缺點，本文實現一種面向Web的WCET模式自動分析系統——WCET Mode Analyzer。該系統允許用戶通過Web方式上傳被分析的源程序，根據源程序，能夠自動確定其模式以及模式對應的輸入參數值表達式，然后通過選擇專業人員配置的程序運行處理器的特征，從而能夠計算每一種模式對應的WCET。

1 背景知識

實時系統程序的WCET靜態分析(以下簡稱WCET分析)通常包括三部分：程序執行流分析、處理器特征分析以及基于二者信息的WCET計算。

程序執行流分析包括分析循環的最大迭代范圍、遞歸調用的深度范圍和不可行路徑等程序流約束信息。不可行路徑是指對任何輸入數據都不可能執行的程序路徑。

處理器特征分析就是分析程序目標代碼的實際執行時間，即建立執行時間模型，此分析也稱為低層分析。對于無高速緩存、無流水線的傳統CISC(Complex Instruction Set Computer)指令，其每條指令的執行時間是固定的。因此，任意兩條指令的執行時間，就是其所包含的每條指令的執行時間累加。此方法稱為Time schema方法。

流水線的WCET的分析方法通常是利用保留表[8]。此時，兩條指令的執行時間就是兩條指令對應的兩個保留表連接之后，從第一條指令第一個階(stage)到最后一條指令的最后一個階之間的指令周期(cycle)數。

高速緩存的WCET典型分析方法是把每條指令的訪問進行分類，分為4類：總是丟失(always miss)、總是命中(always hit)、第一次訪問丟失后續命中(first miss)和第一次訪問命中后續丟失(first hit)，然后根據不同訪問類型計算緩存引起WCET[2-3,8]。

WCET計算就是在已知程序執行流和執行時間模型的情況下，為程序計算WCET估值[2-3]。這里簡單介紹基于樹的方法和基于路徑的方法。

基于樹的方法根據復合、條件和循環語句所形成語法樹，通過遍歷程序的語法分析樹，自底向上逐步計算整個程序的WCET估值。此方法也稱為Time schema方法。常用于CISC指令集的計算。

基于路徑的方法通過計算程序中不同路徑的WCET，從中選擇最大的WCET。對于循環lp，基于路徑的方法可簡單表示為：

WCETlp=WCETpath×n

(1)

其中，WCETpath是循環lp中執行時間最長的路徑path的WCET值，n為循環lp的迭代次數。

2 WCET模式自動分析方法

基于源程序代碼，本分析方法包括七個步驟，其中前六個步驟用于產生模式，最后步驟計算模式對應的WCET。

2.1 產生任務的無循環控制流圖NLCFG

程序控制流圖CFG(ControlFlowGraph)[9]，是對程序的圖形化表示，由節點和有向邊組成，它既表示了程序的控制結構信息，也表示了程序語句執行的流向。一個結構化程序由三種基本語句構成：復合語句、條件語句和循環語句，與之對應，程序CFG也由三種基本結構組成：順序、分支、循環。

程序CFG節點分為賦值節點、分支點和匯聚點。賦值節點對應于程序的賦值語句，分支節點對應于條件或循環語句的條件判斷，此條件也稱為分支謂詞。

程序CFG的邊表示程序的執行流向，分支節點的邊稱作分支，對應于程序中一段要順序執行的語句序列。

無循環控制流圖NLCFG(NoLoopControlFlowGraph)是一種特殊的控制流圖，其與CFG的區別在于其循環語句產生的CFG節點只包括循環體節點而不包括分支謂詞節點及相應的回邊。所以產生程序NLCFG是因為經過循環迭代的依賴輸入變量的值變得無法確定。

按照程序的三種基本語句，分析源程序，能夠產生程序的NLCFG。與程序CFG表示類似，程序NLCFG的節點可用數字標識，邊可以用節點的二元組表示，比如邊(m,n)表示從節點m到節點n的有向邊。

獲得程序NLCFG的同時，也獲得NLCFG節點與源程序語句的對應關系，同時，循環體節點也得到標識。

2.2 利用NLCFG確定依賴輸入變量及其對應節點

依賴輸入變量可以遞歸定義為：由輸入變量定義的變量是依賴輸入變量，由輸入變量和依賴輸入變量定義的變量也是依賴輸入變量。

針對NLCFG，從入口節點開始，利用通用單調數據流框[10]，依照深度優先策略，可以確定每個變量是否是依賴輸入變量。

為了確定依賴輸入變量及其對應的NLCFG節點，為每個節點設立兩個狀態：節點執行前狀態與執行后狀態。節點前狀態由所有流向該節點的節點后狀態確定，而節點后的狀態則是該節點執行后改變的狀態。對于所有流向一個節點的節點，如果這些節點的節點后狀態中，該變量是依賴輸入變量，那么，在此節點的節點前狀態中，該變量的狀態定義為依賴輸入變量。

所謂深度優先策略是指，在處理一個節點后，對該節點的后續節點，按照深度優先策略進行排隊處理。首先對后續節點排隊。排隊之后，對隊列中的第一個節點同樣處理，只有在第一個節點及其后續節點處理完畢或者無法處理之后，才開始處理該節點隊列中的第二個節點。一個節點無法處理是指，如果該節點有一個前任節點的執行后狀態是不確定的。一個節點m的前任節點是一個節點集合，滿足：它們都有一條邊指向節點m。同理，節點m的后續節點是一個節點集合，滿足：節點m有一條邊指向這些節點。

對于無法處理的節點，將該節點重新排在隊列末尾?；谏疃葍炏炔呗源_定依賴輸入變量算法可參考圖1所示。

圖1可以分為兩部分，前半部分圍繞隊列Q1，根據節點對依賴輸入變量的引用關系，確定每個變量的節點后狀態是否為依賴輸入變量，其中定義引用變量為依賴輸入變量的節點為依賴輸入節點。后半部分圍繞隊列Q2，確定該節點的后續節點的節點前狀態。

圖1 基于深度優先策略的依賴輸入變量確定算法

對于結構化程序，由于NLCFG沒有循環結構，所以NLCFG為單向有向圖，因此，NLCFG中的節點是有序的。也因此，所述算法能夠保證快速確定每個節點的狀態。

2.3 確定依賴循環變量、非輸入分支變量及其節點

一個變量如果在循環體中定義，則該變量為依賴循環變量。一個變量如果在定義中引用了依賴循環變量，則該變量同樣為依賴循環變量。同樣，一個變量如果在非依賴輸入分支謂詞的分支中定義，則該變量為依賴非輸入分支變量。一個變量如果在定義中引用了依賴非輸入分支變量，則該變量同樣為依賴非輸入分支變量。以上兩類變量統稱為非依賴輸入變量NOINPUT。

針對一個循環體節點或非依賴輸入分支節點，首先確定一個變量在節點后狀態中為NOINPUT，然后，利用通用單調數據流框，可以確定所有后續的NOINPUT變量。

2.4 刪除非依賴輸入節點產生ICFG

針對NLCFG，刪除圖中非依賴輸入節點。刪除的方法仍然按照節點的基本結構進行，所不同的是，一個分支節點或者匯合節點可以是空節點。所謂空節點就是不執行任何操作的節點。空節點對應語句為空語句。

最終形成的無循環控制流圖NLCFG為輸入變量相關的NLCFG，標記為ICFG(InputdependentControlFlowGraph)。

2.5 產生ICFG的所有路徑

對于ICFG，可產生其所有路徑。由于ICFG是單向圖，可按照深度優先策略產生所有路徑。

2.6 針對每條路徑產生其輸入條件

針對ICFG的每一條路徑，在這個路徑上只有兩類節點，一類是賦值節點，另一類是分支節點。對于分支節點，如果其分支謂詞表達式是輸入變量的線性表示，則可以構造出該分支謂詞針對輸入變量的線性表達式。

假定輸入表示為X=，m是輸入變量的個數，假定一個分支謂詞可以表示為X的線性函數F(X)=d1x1+…+dmxm+c，由于任意給定一個輸入，沿著該路徑執行該分支節點之前的所有輸入和賦值語句，從而能夠計算該謂詞的值，因此能夠計算出謂詞線性表達式的各參數dj：

dj=(F(I0+(0,…,△ij,…,0))-F(I0))/△ij

(2)

j=1,2,…,m

其中I0=(i1,…,ij,…,im)為任一輸入，△ij為任一不為0的增量。

對于ICFG上的一條路徑，該路徑上每個分支取向已經確定，同時，每個分支謂詞對輸入變量的線性表達式已知，因此，可以根據路徑上的分支謂詞構造輸入變量的約束組。如果定義目標函數為所有輸入變量累加的最小值，則構成一個典型的線性規劃求解問題。

利用線性規劃解析器，即可解得輸入變量的值或者是范圍，此即為該ICFG路徑的輸入條件，此條件即為該模式對應的輸入條件。如果線性規劃問題無解，則說明該路徑為不可行路徑。

2.7 模式的WCET分析

假定md是任務M的一個模式，如果M中路徑P屬于md中路徑，則稱路徑P由模式md支配。如果路徑P由模式md支配，則路徑P上的節點/基本塊也由模式md支配。即：一個節點/基本塊由模式md支配，如果M中存在一條路徑P，滿足：md支配路徑P且該節點/基本塊在P上。

一個語句真值(true)/ 假值(false)控制依賴于b，如果當b為true/false時才執行該語句[9]。對于模式md的每個謂詞b，有兩個語句集合，它們分別真值和假值控制依賴于b。

根據模式md支配的路徑P，能夠確定md中每個謂詞b的取值(true/false)。如果b的取值為true，則真值控制依賴于b的節點由模式md支配，而假值控制依賴于b的節點模式md不支配。反之亦成立。

對于指定模式下的WCET分析，不應當考慮模式不支配的節點，而相應的WCET分析方法保持不變。

對于指定模式md下的Timeschema計算，只需考慮md支配的分支或者基本塊即可。流水線的計算按照路徑的方法進行。對于指定模式md下的WCET高速緩存分析，只需考慮miss情況。一條指令被劃分miss，只有當存在一個md支配的控制流中該位置的其它程序線也可能被緩存，也就是它和另一個md支配的程序線的緩存發生沖突。否則，它是hit。

對于指定模式md下的基于路徑的計算，式(1)中WCETpath對應循環lp的最長路徑Path有限制，Path應當是由md支配的路徑。如果循環lp中最長路徑Path不是由md支配的，則檢查循環lp中次長路徑。顯然循環lp中至少有一條模式md支配的路徑，因此最終能夠得到由md支配的最長路徑Path。

本文采用基于路徑的計算方法。

3 WCET模式自動分析的實現

在基于抽象解釋的WCET自動分析工具NPCA-WCET[11]的基礎上，我們實現了面向C語言的WCET程序模式自動分析。該實現稱為處理對象庫 (DLL)，它是一個具有公共語言運行時CLR(CommonLanguageRuntime)特征的動態連接庫，它還能夠為C語言之外的諸如C#語言所調用。

3.1 處理過程

處理對象庫 (DLL)的主要處理邏輯包括三部分：詞法和語法分析(parse)、模式分析，以及指定模式的WCET分析，如圖2所示。

圖2 模式分析的處理過程

在圖2中，首先對C源程序進行詞法和語法分析，生成程序結構信息的對象表示，其中包括控制流圖、輸入變量表和變量表。對程序結構信息進行程序流信息分析即用于獲取WCET分析的流信息。這些信息包括：函數調用關系、遞歸調用關系、循環的界限以及不可行路徑等。程序流分析方法是基于抽象解釋[12]支持的變量值范圍傳播[10]。

ICFG分析即包括前述第2節的前五個步驟，其結果產生輸入變量相關的無循環控制流圖ICFG以及其對應的所有路徑。針對其每一條路徑，構造對應的線性約束系統，并進行求解。求解器采用：如果有解，則該路徑對應一個模式，線性約束系統就是它的輸入條件；如果無解，這對應一個不可行路徑。

緩存分析利用高速緩存的配置信息以及程序流信息和映射文件提供的指令序列，對每條指令和數據緩存操作進行分類，已備時間分析使用。

時間分析根據程序流信息、緩存分類信息和程序流信息對于的指令序列，根據指令系統信息，計算每個模式以及整個函數的WCET。

3.2 實現類

WCET模式分析的具體實現可以通過面向對象的方法進行設計實現，其實現類及對象關系如圖3所示。

圖3 WCET模式分析實現類及對象關系

WCET模式分析實現主要體現在COneFile類上。COneFile關聯源文件類CSrcFile和映射文件類CMapFile。通過COneFile類函數Analyse對源文件進行詞法分析，生成相應的Token對象列表。在Token對象列表的基礎上，可以通過其函數GetFunItem進行語法分析從而獲取源文件包含的函數對象CFunItem，然后，通過類CFunItem的函數GetModeItem獲取該函數包含的模式對象CModeItem和節點CNode對象。

可以通過對CMapFile分析，將源文件對應的指令序列映射到相應的函數及其節點對象CNode上。

以上類以及相關類，生成為具有CLR特性的動態鏈接庫。

從對象的組織關系上講，一個COneFilet對象包含了一個源文件CSrcFile對象，一個可能的映射文件CMapFile對象和函數對象CFunItem隊列。映射文件是編譯器產生的源文件與機器指令的映射列表文件，一般編譯器都具有生成該文件的功能，WCET模式分析器利用此文件建立源文件與其執行指令的對應關系。

函數對象CFunItem隊列包含了該COneFilet對象的所有函數。每個CFunItem包含了CFG節點CNode隊列和分析出來的模式，也使用CModeItem隊列表示。節點CNode包括分支節點CBranchNode和賦值節點CAssignNode，每個節點對應兩個變量表VariableTable，并包含了一個表達式，一個表達式用變量CVariable和操作符COperator隊列表示。

4 面向Web的WCET分析系統

利用處理對象庫 (DLL)提供的WCET模式分析功能，可以實現具有模式分析功能的系統。本節實現一個面向互聯網的WCET模式分析器——WCETModeAnalyzer。

之所以將WCETModeAnalyzer設計成面向互聯網不僅是為了便于訪問，更是為了方便角色劃分，將繁瑣且易于出錯的配置低層分析部分劃歸作為系統管理員的專業人員去完成，而將對應用程序的WCET分析計算使用功能提供給應用用戶。

4.1 主要功能

從應用的角度看，WCET模式分析器功能比較簡單。該系統分為兩個角色：系統管理員和應用用戶。

系統管理員負責配置CPU和系統參數。配置CPU包括配置指令系統、主頻和配置高速緩存。對于CISC指令系統，每條指令對應一個處理時間(cycles，節拍數)。對于RISC指令系統，定義指令的每個階之后，對于每條指令，指定該指令每個階(stage)占用的節拍數?？梢詫γ恳粭l指令進行定義，也可以通過EXCEL表按照指定格式整體錄入。

對于高速緩存，主要是確定其映射方式和緩存大小。映射方式是指高速緩存與內存的映射關系，有直接映射、全相聯映射和組相聯映射三種方式。

4.2 設計實現

WCET模式分析器主要由三部分組成：網頁響應、對象管理器和處理對象庫(DLL)。處理對象庫如前所述。

(1) 網頁設計

WCET模式分析器的網頁設計分系統管理員和應用用戶。系統管理員頁面比較簡單，僅僅是用來配置CPU。

應用用戶的顯示頁面除主題和頁腳，主要由左中右三部分構成，左邊為導航樹，中間部分為主顯示區，右邊為輔助顯示區。導航樹第一部分為項目配置，后面部分為各個項目不同視角的顯示。

主顯示區根據導航樹的選擇項顯示相應的內容，而輔助顯示區則可能顯示對應的輔助內容。比如，當導航樹選擇一個源文件的時候，主顯示區顯示該文件包含函數的模式及對應的WCET，而輔助顯示區則顯示對應的源文件內容，如圖4所示。

圖4 面向Web的WCET模式分析系統構成

網頁設計簡單但很瑣細，網頁設計的關鍵在于數據存儲和獲取，其由數據管理器來完成。

(2) 對象管理器設計

對象管理器負責WCET模式分析器中對象的組織，其頂層組織如圖5所示。

圖5 面向Web的WCET模式分析系統構成

COneFile的組織如前所述。CCPU對象包括指令集和高速緩存等，主要用于低層分析。

5 系統分析實例

我們選用基準集SNU-RTBenchmarkSuite進行測試，以Alpha21064為處理器模型，該處理器指令緩存1MB，用戶可以直接選用。SNU-RT基準集是實時系統領域用于WCET分析的基準程序集[13]。

通過分析，SNU-RT基準集有17個程序，其中9個程序包含的程序具有模式。整體上，17個程序中有55個函數，其中23個具有模式。圖6為adpcm-test.c程序對應的顯示頁面部分?？梢钥闯觯瑢τ谟心Ｊ降暮瘮?，WCET模式分析系統將給出其模式和模式對應的WCET值，對于沒有模式(或者無法判斷其模式)的函數，WCET模式分析系統將給出其函數的WCET值。

圖6 面向Web的WCET模式分析系統顯示頁面

6 結 語

本文提出了一個自動分析程序WCET模式的新方法，并據此設計實現一種面向Web的WCET模式分析系統。該系統能夠分析程序模式，計算任務以及模式的WCET，從而達到更精確地計算實時任務WCET的目的。同時，利用Web系統的特點，將繁瑣的配置工作交由專業的系統管理員，應用用戶可以直接使用配置好的處理器，從而使配置工作簡便。通過對基準程序進行分析實驗，驗證了該方案的有效性。

本系統目前僅在RISC類處理器Alpha21064上實現了C語言程序WCET分析，未來還需要擴展到多種類型實時用處理器和語言上，比如ARM類處理器和C++語言。

[1]DavisRI,BurnsA.Asurveyofhardreal-timeschedulingformultiprocessorsystems[J].ACMComputingSurveys(CSUR),2011,43(4):1-41.

[2]WilhelmR,EngblomJ,ErmedahlA,etal.Theworst-caseexecution-timeproblem-overviewofmethodsandsurveyoftools[J].ACMTransactionsonEmbeddedComputingSystems(TECS),2008,7(3):196-206.

[3]PuschnerP,BurnsA.Guesteditorial:areviewofworst-caseexecution-timeanalysis[J].Real-TimeSystems,2000,18(2-3):115-128.

[4]WilhelmR,LucasP,ParshinO,etal.ImprovingtheprecisionofWCETanalysisbyinputconstraintsandmodel-derivedflowconstraints[M]//ChakrabortyS,Ebersp?cherJ.AdvancesinReal-TimeSystems.Berlin:Springer-Verlag,2012:123-143.

[5]JiML,WangJ,LiS,etal.Automatedworst-caseexecutiontimeanalysisbasedonprogrammodes[J].TheComputerJournal,2009,52(5):530-544.

[6]BallabrigaC,ForgetJ,LipariG.Context-sensitiveparametricWCETanalysis[C]//15thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Lund,Sweden,2015:54-64.

[7]ZwirchmayrJ,SotinP,BonenfantA,etal.IdentifyingrelevantparameterstoimproveWCETanalysis[C]//14thInternationalWorkshoponWorst-CaseExecutionTimeAnalysis,Madrid,Spain,2014:93-102.

[8]HealyCA,ArnoldRD,MuellerF,etal.Boundingpipelineandinstructioncacheperformance[J].IEEETransactionsonComputers,1999,48(1):53-70.

[9]TipF.Asurveyofprogramslicingtechniques[J].JournalofProgrammingLanguages,1995,3(3):121-189.

[10] 姬孟洛,王懷民,李夢君,等.一種基于抽象解釋和通用單調數據流框架的值范圍分析方法[J].計算機研究與發展,2006,43(11):2020-2026.

[11] 姬孟洛,李軍,王馨,等.一種基于抽象解釋的WCET自動分析工具[J].計算機工程,2006,32(14):54-56.

[12]CousotP,CousotR.Abstractinterpretation:aunifiedlatticemodelforstaticanalysisofprogramsbyconstructionorapproximationoffixpoints[C]//Proceedingsofthe4thACMSymposiumonPrinciplesofProgrammingLanguages,LosAngeles,CA,USA,1977:238-252.

[13]SATABS.SNUReal-TimeBenchmarks[OL].http://www.cprover.org/satabs/examples/SNU_Real_Time_Benchmarks/.

AN AUTOMATIC WCET ANALYSIS SYSTEM FOR WEB

Ji Mengluo1Shu Yunxing2Huang Chenlin3Gao Xiang1

1(SchoolofComputerandInformationEngineering,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)2(DepartmentofForeignCooperation,LuoyangInstituteofScienceandTechnology,Luoyang471023,Henan,China)3(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha410073,Hunan,China)

In light of the problems of deficient precision and troublesome usage the traditional WCET analysis systems usual suffer, a new automatic analysis method based on program modes is proposed and a WCET analysis system on the idea of the method for Web is designed. Firstly, a method is presented based on the analysis of source code which produces an acyclic input parameter dependent control flow graph called ICFG by using program control flow graph and a specific program slicing under data flow framework. Secondly, by constructing a solution system for each path in ICFG, a mode and its input parameter expression maybe conducted, and the WCET value of a mode can be computed. Finally,a Dynamic link library (DLL) is implemented based on the method above for C language in order to be used by different systems,and an automated analysis system in the Web by using the DLL is realized, which is called WCET Mode Analyzer. The result for a Benchmark implemented by the analysis system shows the effectiveness of the solution and the characteristics of using conveniently.

Real-time systems WCET Program mode Program analysis

2015-12-25。河南省科技計劃項目(152300410115)。姬孟洛，高級工程師，主研領域：實時系統，中間件技術，信息系統分析與設計。舒云星，教授。黃辰林，副教授。高翔，講師。

TP311

A

10.3969/j.issn.1000-386x.2017.02.042