源碼重構優(yōu)化WCET

孟凡奇+蘇小紅+代成雷

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： A文章編號： 2095-2163（2017）06-0173-05

Abstract： To make it clear whether refactoring can optimize WCET， the basic theory of WCET estimation is firstly analyzed， and then the basic principle of WCET optimization is proposed. According to the principle， seven refactoring methods are selected from traditional source code refactoring to optimize WCET. The experimental results show that source code refactoring can reduce WCET， but the result is affected by the configuration of target processor， the control structure of testing program and the optimization level of the compiler. Compared with the traditional compilerbased performance optimization， source code refactoring is more suitable to be used at an early phase of program development. Reasonable usage of refactoring will be helpful to repair timeliness defect in time and then guarantee the timeliness safety of software.

0引言

最差情況執(zhí)行時間（worstcase execution time， WCET）是指程序P在目標處理器X上的執(zhí)行時間T，對于任何輸入，P在X上的執(zhí)行時間都不會超過T。在實時系統(tǒng)中，尤其是新興的、安全關鍵的信息物理系統(tǒng)，例如，汽車的主動剎車系統(tǒng)、無人機的自動巡航系統(tǒng)、智能電網的繼電保護系統(tǒng)等，程序的執(zhí)行時間通常是至關重要的，即使是在最差情況下也不能超出截止期，否則可能造成災難性后果。因此，WCET已經成為評估軟件時效安全性的一個非常重要的指標和參數。

為了獲得理想的WCET，程序員會在性能優(yōu)化階段（通常是在系統(tǒng)開發(fā)后期）利用編譯器對目標代碼進行優(yōu)化 ＼[1＼]。然而，隨著信息物理系統(tǒng)的興起，程序的規(guī)模越來越大，結構也越來越復雜，上述做法面臨以下問題：首先，優(yōu)化時機太遲，如果WCET無法滿足要求，此時修復時效缺陷的成本會遠高于編碼階段；其次，優(yōu)化對象是目標代碼，只能在程序具備編譯、鏈接條件后才能優(yōu)化，且優(yōu)化后的目標代碼不具備可移植性；最后，優(yōu)化依賴于編譯器，且以平均性能的優(yōu)化為主，優(yōu)化WCET的效果并不穩(wěn)定；此外，編譯器優(yōu)化還會給代碼調試造成不便，因而在早期編碼階段常常被禁用。

事實上，為了保證軟件的時效安全，安全關鍵實時系統(tǒng)的開發(fā)應當采用時間預算法＼[2＼]。即，在設計階段為每一個組件預先分配一定資源，包括執(zhí)行軌跡和執(zhí)行時間。編碼時，程序員要時刻關注每個組件的WCET，一旦發(fā)現(xiàn)超時，則認為程序存在時效缺陷，應立即予以修復＼[3-4＼]。相較于傳統(tǒng)方法，源碼重構的優(yōu)點在于：

1）重構是在早期編碼階段設計發(fā)生，因而有助于及時修復時效缺陷。

2）重構對象是源碼，更換目標處理器后無需修改即可復用，有利于降低新系統(tǒng)的開發(fā)成本。

3）重構專門針對WCET，且不受編譯器優(yōu)化規(guī)則的限制，因而優(yōu)化更靈活，效果更穩(wěn)定。

1源碼重構

重構（refactoring）是指在不改變軟件可觀察行為的前提下，使用一系列重構手法調整代碼結構。重構的目的原本是改善代碼設計，提高軟件的可理解性，降低其修改成本＼[2＼]。而在本文中，重構的目的是在不改變軟件可觀察行為的前提下，通過對源碼結構的調整降低WCET。

1.1優(yōu)化原則分析

程序的WCET受到代碼結構、處理器配置等軟硬件方面的多重影響，當程序規(guī)模較大、處理器結構較為復雜時，獲得實際WCET的可能性很小。人們只能采用變通的方法去估計WCET，例如，隱藏路徑枚舉技術（implicit path enumeration technology， IPET）。

基于IPET的WCET分析大致可以分為3步：底層分析、高層分析和WCET計算。其中，底層分析主要是為目標處理器建模，包括Cache、流水線、分支預測和指令執(zhí)行時間等。高層分析主要是構建控制流圖、分析可行路徑和循環(huán)邊界等。WCET計算則是使用整數線性規(guī)劃尋求公式（1）的最優(yōu)解，所得結果就是整個程序的WCET。公式（1）的數學表述如下：WCET=max（∑ni=1Wceti×Counti） （1）式中，n代表程序的目標代碼被劃分成基本塊的數量；Wceti代表基本塊Bi的WCET；Counti是Bi的執(zhí)行次數，需要利用整數線性規(guī)劃在定理1的約束下求解。顯然，若Counti=0，則基本塊Bi對于程序的WCET沒有貢獻；相反，所有滿足Counti>0的基本塊則構成了程序的最差情況執(zhí)行路徑（worst-case execution path， WCEP）。endprint