姬孟洛 舒云星 黃辰林 高 翔

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

面向Web的WCET模式自動(dòng)分析系統(tǒng)

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

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

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

實(shí)時(shí)系統(tǒng) WCET 程序模式 程序分析

0 引 言

實(shí)時(shí)系統(tǒng)，包括嵌入式實(shí)時(shí)系統(tǒng)，在進(jìn)行任務(wù)調(diào)度時(shí)，需要事先知道每個(gè)任務(wù)的執(zhí)行時(shí)間。這個(gè)時(shí)間，指的是最壞情況的執(zhí)行時(shí)間WCET[1]。研究獲取WCET值的方法是實(shí)時(shí)系統(tǒng)的重要研究領(lǐng)域，它不僅應(yīng)用于可調(diào)度性檢測(cè)，還應(yīng)用于非實(shí)時(shí)系統(tǒng)性能分析和嵌入式系統(tǒng)的耗電量分析[2]。

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

實(shí)時(shí)系統(tǒng)，尤其是嵌入式實(shí)時(shí)系統(tǒng)，通常都有模式。系統(tǒng)的一個(gè)模式定義了該系統(tǒng)以及其中相關(guān)任務(wù)的一種特殊行為。舉例來說，一個(gè)系統(tǒng)通常有啟動(dòng)模式和正常模式，甚至有正常模式和緊急模式。

利用程序模式能夠更精確地計(jì)算任務(wù)WCET。這體現(xiàn)在三個(gè)方面。其一，根據(jù)程序不同的模式，分別計(jì)算各模式的WCET，取其中最大的WCET，比不加區(qū)分計(jì)算出的WCET要精確[4-5]。其二，不同的模式，其要求的WCET往往不同。其三，類似于WCET參數(shù)化分析，每一個(gè)模式都有一個(gè)由輸入?yún)?shù)值范圍構(gòu)成的表達(dá)式，因此，在任務(wù)執(zhí)行時(shí)才確定模式，從而有更精確的WCET值[6-7]。

針對(duì)WCET分析的缺點(diǎn)，本文實(shí)現(xiàn)一種面向Web的WCET模式自動(dòng)分析系統(tǒng)——WCET Mode Analyzer。該系統(tǒng)允許用戶通過Web方式上傳被分析的源程序，根據(jù)源程序，能夠自動(dòng)確定其模式以及模式對(duì)應(yīng)的輸入?yún)?shù)值表達(dá)式，然后通過選擇專業(yè)人員配置的程序運(yùn)行處理器的特征，從而能夠計(jì)算每一種模式對(duì)應(yīng)的WCET。

1 背景知識(shí)

實(shí)時(shí)系統(tǒng)程序的WCET靜態(tài)分析(以下簡(jiǎn)稱WCET分析)通常包括三部分：程序執(zhí)行流分析、處理器特征分析以及基于二者信息的WCET計(jì)算。

程序執(zhí)行流分析包括分析循環(huán)的最大迭代范圍、遞歸調(diào)用的深度范圍和不可行路徑等程序流約束信息。不可行路徑是指對(duì)任何輸入數(shù)據(jù)都不可能執(zhí)行的程序路徑。

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

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

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

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

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

基于路徑的方法通過計(jì)算程序中不同路徑的WCET，從中選擇最大的WCET。對(duì)于循環(huán)lp，基于路徑的方法可簡(jiǎn)單表示為：

WCETlp=WCETpath×n

(1)

其中，WCETpath是循環(huán)lp中執(zhí)行時(shí)間最長的路徑path的WCET值，n為循環(huán)lp的迭代次數(shù)。

2 WCET模式自動(dòng)分析方法

基于源程序代碼，本分析方法包括七個(gè)步驟，其中前六個(gè)步驟用于產(chǎn)生模式，最后步驟計(jì)算模式對(duì)應(yīng)的WCET。

2.1 產(chǎn)生任務(wù)的無循環(huán)控制流圖NLCFG

程序控制流圖CFG(ControlFlowGraph)[9]，是對(duì)程序的圖形化表示，由節(jié)點(diǎn)和有向邊組成，它既表示了程序的控制結(jié)構(gòu)信息，也表示了程序語句執(zhí)行的流向。一個(gè)結(jié)構(gòu)化程序由三種基本語句構(gòu)成：復(fù)合語句、條件語句和循環(huán)語句，與之對(duì)應(yīng)，程序CFG也由三種基本結(jié)構(gòu)組成：順序、分支、循環(huán)。

程序CFG節(jié)點(diǎn)分為賦值節(jié)點(diǎn)、分支點(diǎn)和匯聚點(diǎn)。賦值節(jié)點(diǎn)對(duì)應(yīng)于程序的賦值語句，分支節(jié)點(diǎn)對(duì)應(yīng)于條件或循環(huán)語句的條件判斷，此條件也稱為分支謂詞。

程序CFG的邊表示程序的執(zhí)行流向，分支節(jié)點(diǎn)的邊稱作分支，對(duì)應(yīng)于程序中一段要順序執(zhí)行的語句序列。

無循環(huán)控制流圖NLCFG(NoLoopControlFlowGraph)是一種特殊的控制流圖，其與CFG的區(qū)別在于其循環(huán)語句產(chǎn)生的CFG節(jié)點(diǎn)只包括循環(huán)體節(jié)點(diǎn)而不包括分支謂詞節(jié)點(diǎn)及相應(yīng)的回邊。所以產(chǎn)生程序NLCFG是因?yàn)榻?jīng)過循環(huán)迭代的依賴輸入變量的值變得無法確定。

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

獲得程序NLCFG的同時(shí)，也獲得NLCFG節(jié)點(diǎn)與源程序語句的對(duì)應(yīng)關(guān)系，同時(shí)，循環(huán)體節(jié)點(diǎn)也得到標(biāo)識(shí)。

2.2 利用NLCFG確定依賴輸入變量及其對(duì)應(yīng)節(jié)點(diǎn)

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

針對(duì)NLCFG，從入口節(jié)點(diǎn)開始，利用通用單調(diào)數(shù)據(jù)流框[10]，依照深度優(yōu)先策略，可以確定每個(gè)變量是否是依賴輸入變量。

為了確定依賴輸入變量及其對(duì)應(yīng)的NLCFG節(jié)點(diǎn)，為每個(gè)節(jié)點(diǎn)設(shè)立兩個(gè)狀態(tài)：節(jié)點(diǎn)執(zhí)行前狀態(tài)與執(zhí)行后狀態(tài)。節(jié)點(diǎn)前狀態(tài)由所有流向該節(jié)點(diǎn)的節(jié)點(diǎn)后狀態(tài)確定，而節(jié)點(diǎn)后的狀態(tài)則是該節(jié)點(diǎn)執(zhí)行后改變的狀態(tài)。對(duì)于所有流向一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)，如果這些節(jié)點(diǎn)的節(jié)點(diǎn)后狀態(tài)中，該變量是依賴輸入變量，那么，在此節(jié)點(diǎn)的節(jié)點(diǎn)前狀態(tài)中，該變量的狀態(tài)定義為依賴輸入變量。

所謂深度優(yōu)先策略是指，在處理一個(gè)節(jié)點(diǎn)后，對(duì)該節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，按照深度優(yōu)先策略進(jìn)行排隊(duì)處理。首先對(duì)后續(xù)節(jié)點(diǎn)排隊(duì)。排隊(duì)之后，對(duì)隊(duì)列中的第一個(gè)節(jié)點(diǎn)同樣處理，只有在第一個(gè)節(jié)點(diǎn)及其后續(xù)節(jié)點(diǎn)處理完畢或者無法處理之后，才開始處理該節(jié)點(diǎn)隊(duì)列中的第二個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)無法處理是指，如果該節(jié)點(diǎn)有一個(gè)前任節(jié)點(diǎn)的執(zhí)行后狀態(tài)是不確定的。一個(gè)節(jié)點(diǎn)m的前任節(jié)點(diǎn)是一個(gè)節(jié)點(diǎn)集合，滿足：它們都有一條邊指向節(jié)點(diǎn)m。同理，節(jié)點(diǎn)m的后續(xù)節(jié)點(diǎn)是一個(gè)節(jié)點(diǎn)集合，滿足：節(jié)點(diǎn)m有一條邊指向這些節(jié)點(diǎn)。

對(duì)于無法處理的節(jié)點(diǎn)，將該節(jié)點(diǎn)重新排在隊(duì)列末尾?；谏疃葍?yōu)先策略確定依賴輸入變量算法可參考圖1所示。

圖1可以分為兩部分，前半部分圍繞隊(duì)列Q1，根據(jù)節(jié)點(diǎn)對(duì)依賴輸入變量的引用關(guān)系，確定每個(gè)變量的節(jié)點(diǎn)后狀態(tài)是否為依賴輸入變量，其中定義引用變量為依賴輸入變量的節(jié)點(diǎn)為依賴輸入節(jié)點(diǎn)。后半部分圍繞隊(duì)列Q2，確定該節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)的節(jié)點(diǎn)前狀態(tài)。

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

對(duì)于結(jié)構(gòu)化程序，由于NLCFG沒有循環(huán)結(jié)構(gòu)，所以NLCFG為單向有向圖，因此，NLCFG中的節(jié)點(diǎn)是有序的。也因此，所述算法能夠保證快速確定每個(gè)節(jié)點(diǎn)的狀態(tài)。

2.3 確定依賴循環(huán)變量、非輸入分支變量及其節(jié)點(diǎn)

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

針對(duì)一個(gè)循環(huán)體節(jié)點(diǎn)或非依賴輸入分支節(jié)點(diǎn)，首先確定一個(gè)變量在節(jié)點(diǎn)后狀態(tài)中為NOINPUT，然后，利用通用單調(diào)數(shù)據(jù)流框，可以確定所有后續(xù)的NOINPUT變量。

2.4 刪除非依賴輸入節(jié)點(diǎn)產(chǎn)生ICFG

針對(duì)NLCFG，刪除圖中非依賴輸入節(jié)點(diǎn)。刪除的方法仍然按照節(jié)點(diǎn)的基本結(jié)構(gòu)進(jìn)行，所不同的是，一個(gè)分支節(jié)點(diǎn)或者匯合節(jié)點(diǎn)可以是空節(jié)點(diǎn)。所謂空節(jié)點(diǎn)就是不執(zhí)行任何操作的節(jié)點(diǎn)?？展?jié)點(diǎn)對(duì)應(yīng)語句為空語句。

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

2.5 產(chǎn)生ICFG的所有路徑

對(duì)于ICFG，可產(chǎn)生其所有路徑。由于ICFG是單向圖，可按照深度優(yōu)先策略產(chǎn)生所有路徑。

2.6 針對(duì)每條路徑產(chǎn)生其輸入條件

針對(duì)ICFG的每一條路徑，在這個(gè)路徑上只有兩類節(jié)點(diǎn)，一類是賦值節(jié)點(diǎn)，另一類是分支節(jié)點(diǎn)。對(duì)于分支節(jié)點(diǎn)，如果其分支謂詞表達(dá)式是輸入變量的線性表示，則可以構(gòu)造出該分支謂詞針對(duì)輸入變量的線性表達(dá)式。

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

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

(2)

j=1,2,…,m

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

對(duì)于ICFG上的一條路徑，該路徑上每個(gè)分支取向已經(jīng)確定，同時(shí)，每個(gè)分支謂詞對(duì)輸入變量的線性表達(dá)式已知，因此，可以根據(jù)路徑上的分支謂詞構(gòu)造輸入變量的約束組。如果定義目標(biāo)函數(shù)為所有輸入變量累加的最小值，則構(gòu)成一個(gè)典型的線性規(guī)劃求解問題。

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

2.7 模式的WCET分析

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

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

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

對(duì)于指定模式下的WCET分析，不應(yīng)當(dāng)考慮模式不支配的節(jié)點(diǎn)，而相應(yīng)的WCET分析方法保持不變。

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

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

本文采用基于路徑的計(jì)算方法。

3 WCET模式自動(dòng)分析的實(shí)現(xiàn)

在基于抽象解釋的WCET自動(dòng)分析工具NPCA-WCET[11]的基礎(chǔ)上，我們實(shí)現(xiàn)了面向C語言的WCET程序模式自動(dòng)分析。該實(shí)現(xiàn)稱為處理對(duì)象庫 (DLL)，它是一個(gè)具有公共語言運(yùn)行時(shí)CLR(CommonLanguageRuntime)特征的動(dòng)態(tài)連接庫，它還能夠?yàn)镃語言之外的諸如C#語言所調(diào)用。

3.1 處理過程

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

圖2 模式分析的處理過程

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

ICFG分析即包括前述第2節(jié)的前五個(gè)步驟，其結(jié)果產(chǎn)生輸入變量相關(guān)的無循環(huán)控制流圖ICFG以及其對(duì)應(yīng)的所有路徑。針對(duì)其每一條路徑，構(gòu)造對(duì)應(yīng)的線性約束系統(tǒng)，并進(jìn)行求解。求解器采用：如果有解，則該路徑對(duì)應(yīng)一個(gè)模式，線性約束系統(tǒng)就是它的輸入條件；如果無解，這對(duì)應(yīng)一個(gè)不可行路徑。

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

時(shí)間分析根據(jù)程序流信息、緩存分類信息和程序流信息對(duì)于的指令序列，根據(jù)指令系統(tǒng)信息，計(jì)算每個(gè)模式以及整個(gè)函數(shù)的WCET。

3.2 實(shí)現(xiàn)類

WCET模式分析的具體實(shí)現(xiàn)可以通過面向?qū)ο蟮姆椒ㄟM(jìn)行設(shè)計(jì)實(shí)現(xiàn)，其實(shí)現(xiàn)類及對(duì)象關(guān)系如圖3所示。

圖3 WCET模式分析實(shí)現(xiàn)類及對(duì)象關(guān)系

WCET模式分析實(shí)現(xiàn)主要體現(xiàn)在COneFile類上。COneFile關(guān)聯(lián)源文件類CSrcFile和映射文件類CMapFile。通過COneFile類函數(shù)Analyse對(duì)源文件進(jìn)行詞法分析，生成相應(yīng)的Token對(duì)象列表。在Token對(duì)象列表的基礎(chǔ)上，可以通過其函數(shù)GetFunItem進(jìn)行語法分析從而獲取源文件包含的函數(shù)對(duì)象CFunItem，然后，通過類CFunItem的函數(shù)GetModeItem獲取該函數(shù)包含的模式對(duì)象CModeItem和節(jié)點(diǎn)CNode對(duì)象。

可以通過對(duì)CMapFile分析，將源文件對(duì)應(yīng)的指令序列映射到相應(yīng)的函數(shù)及其節(jié)點(diǎn)對(duì)象CNode上。

以上類以及相關(guān)類，生成為具有CLR特性的動(dòng)態(tài)鏈接庫。

從對(duì)象的組織關(guān)系上講，一個(gè)COneFilet對(duì)象包含了一個(gè)源文件CSrcFile對(duì)象，一個(gè)可能的映射文件CMapFile對(duì)象和函數(shù)對(duì)象CFunItem隊(duì)列。映射文件是編譯器產(chǎn)生的源文件與機(jī)器指令的映射列表文件，一般編譯器都具有生成該文件的功能，WCET模式分析器利用此文件建立源文件與其執(zhí)行指令的對(duì)應(yīng)關(guān)系。

函數(shù)對(duì)象CFunItem隊(duì)列包含了該COneFilet對(duì)象的所有函數(shù)。每個(gè)CFunItem包含了CFG節(jié)點(diǎn)CNode隊(duì)列和分析出來的模式，也使用CModeItem隊(duì)列表示。節(jié)點(diǎn)CNode包括分支節(jié)點(diǎn)CBranchNode和賦值節(jié)點(diǎn)CAssignNode，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)兩個(gè)變量表VariableTable，并包含了一個(gè)表達(dá)式，一個(gè)表達(dá)式用變量CVariable和操作符COperator隊(duì)列表示。

4 面向Web的WCET分析系統(tǒng)

利用處理對(duì)象庫 (DLL)提供的WCET模式分析功能，可以實(shí)現(xiàn)具有模式分析功能的系統(tǒng)。本節(jié)實(shí)現(xiàn)一個(gè)面向互聯(lián)網(wǎng)的WCET模式分析器——WCETModeAnalyzer。

之所以將WCETModeAnalyzer設(shè)計(jì)成面向互聯(lián)網(wǎng)不僅是為了便于訪問，更是為了方便角色劃分，將繁瑣且易于出錯(cuò)的配置低層分析部分劃歸作為系統(tǒng)管理員的專業(yè)人員去完成，而將對(duì)應(yīng)用程序的WCET分析計(jì)算使用功能提供給應(yīng)用用戶。

4.1 主要功能

從應(yīng)用的角度看，WCET模式分析器功能比較簡(jiǎn)單。該系統(tǒng)分為兩個(gè)角色：系統(tǒng)管理員和應(yīng)用用戶。

系統(tǒng)管理員負(fù)責(zé)配置CPU和系統(tǒng)參數(shù)。配置CPU包括配置指令系統(tǒng)、主頻和配置高速緩存。對(duì)于CISC指令系統(tǒng)，每條指令對(duì)應(yīng)一個(gè)處理時(shí)間(cycles，節(jié)拍數(shù))。對(duì)于RISC指令系統(tǒng)，定義指令的每個(gè)階之后，對(duì)于每條指令，指定該指令每個(gè)階(stage)占用的節(jié)拍數(shù)。可以對(duì)每一條指令進(jìn)行定義，也可以通過EXCEL表按照指定格式整體錄入。

對(duì)于高速緩存，主要是確定其映射方式和緩存大小。映射方式是指高速緩存與內(nèi)存的映射關(guān)系，有直接映射、全相聯(lián)映射和組相聯(lián)映射三種方式。

4.2 設(shè)計(jì)實(shí)現(xiàn)

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

(1) 網(wǎng)頁設(shè)計(jì)

WCET模式分析器的網(wǎng)頁設(shè)計(jì)分系統(tǒng)管理員和應(yīng)用用戶。系統(tǒng)管理員頁面比較簡(jiǎn)單，僅僅是用來配置CPU。

應(yīng)用用戶的顯示頁面除主題和頁腳，主要由左中右三部分構(gòu)成，左邊為導(dǎo)航樹，中間部分為主顯示區(qū)，右邊為輔助顯示區(qū)。導(dǎo)航樹第一部分為項(xiàng)目配置，后面部分為各個(gè)項(xiàng)目不同視角的顯示。

主顯示區(qū)根據(jù)導(dǎo)航樹的選擇項(xiàng)顯示相應(yīng)的內(nèi)容，而輔助顯示區(qū)則可能顯示對(duì)應(yīng)的輔助內(nèi)容。比如，當(dāng)導(dǎo)航樹選擇一個(gè)源文件的時(shí)候，主顯示區(qū)顯示該文件包含函數(shù)的模式及對(duì)應(yīng)的WCET，而輔助顯示區(qū)則顯示對(duì)應(yīng)的源文件內(nèi)容，如圖4所示。

圖4 面向Web的WCET模式分析系統(tǒng)構(gòu)成

網(wǎng)頁設(shè)計(jì)簡(jiǎn)單但很瑣細(xì)，網(wǎng)頁設(shè)計(jì)的關(guān)鍵在于數(shù)據(jù)存儲(chǔ)和獲取，其由數(shù)據(jù)管理器來完成。

(2) 對(duì)象管理器設(shè)計(jì)

對(duì)象管理器負(fù)責(zé)WCET模式分析器中對(duì)象的組織，其頂層組織如圖5所示。

圖5 面向Web的WCET模式分析系統(tǒng)構(gòu)成

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

5 系統(tǒng)分析實(shí)例

我們選用基準(zhǔn)集SNU-RTBenchmarkSuite進(jìn)行測(cè)試，以Alpha21064為處理器模型，該處理器指令緩存1MB，用戶可以直接選用。SNU-RT基準(zhǔn)集是實(shí)時(shí)系統(tǒng)領(lǐng)域用于WCET分析的基準(zhǔn)程序集[13]。

通過分析，SNU-RT基準(zhǔn)集有17個(gè)程序，其中9個(gè)程序包含的程序具有模式。整體上，17個(gè)程序中有55個(gè)函數(shù)，其中23個(gè)具有模式。圖6為adpcm-test.c程序?qū)?yīng)的顯示頁面部分?？梢钥闯觯瑢?duì)于有模式的函數(shù)，WCET模式分析系統(tǒng)將給出其模式和模式對(duì)應(yīng)的WCET值，對(duì)于沒有模式(或者無法判斷其模式)的函數(shù)，WCET模式分析系統(tǒng)將給出其函數(shù)的WCET值。

圖6 面向Web的WCET模式分析系統(tǒng)顯示頁面

6 結(jié) 語

本文提出了一個(gè)自動(dòng)分析程序WCET模式的新方法，并據(jù)此設(shè)計(jì)實(shí)現(xiàn)一種面向Web的WCET模式分析系統(tǒng)。該系統(tǒng)能夠分析程序模式，計(jì)算任務(wù)以及模式的WCET，從而達(dá)到更精確地計(jì)算實(shí)時(shí)任務(wù)WCET的目的。同時(shí)，利用Web系統(tǒng)的特點(diǎn)，將繁瑣的配置工作交由專業(yè)的系統(tǒng)管理員，應(yīng)用用戶可以直接使用配置好的處理器，從而使配置工作簡(jiǎn)便。通過對(duì)基準(zhǔn)程序進(jìn)行分析實(shí)驗(yàn)，驗(yàn)證了該方案的有效性。

本系統(tǒng)目前僅在RISC類處理器Alpha21064上實(shí)現(xiàn)了C語言程序WCET分析，未來還需要擴(kuò)展到多種類型實(shí)時(shí)用處理器和語言上，比如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] 姬孟洛,王懷民,李夢(mèng)君,等.一種基于抽象解釋和通用單調(diào)數(shù)據(jù)流框架的值范圍分析方法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(11):2020-2026.

[11] 姬孟洛,李軍,王馨,等.一種基于抽象解釋的WCET自動(dòng)分析工具[J].計(jì)算機(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。河南省科技計(jì)劃項(xiàng)目(152300410115)。姬孟洛，高級(jí)工程師，主研領(lǐng)域：實(shí)時(shí)系統(tǒng)，中間件技術(shù)，信息系統(tǒng)分析與設(shè)計(jì)。舒云星，教授。黃辰林，副教授。高翔，講師。

TP311

A

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