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

孟凡奇+蘇小紅+代成雷

摘要： 關(guān)鍵詞： 中圖分類號(hào)： 文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 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í)行時(shí)間（worstcase execution time， WCET）是指程序P在目標(biāo)處理器X上的執(zhí)行時(shí)間T，對(duì)于任何輸入，P在X上的執(zhí)行時(shí)間都不會(huì)超過(guò)T。在實(shí)時(shí)系統(tǒng)中，尤其是新興的、安全關(guān)鍵的信息物理系統(tǒng)，例如，汽車的主動(dòng)剎車系統(tǒng)、無(wú)人機(jī)的自動(dòng)巡航系統(tǒng)、智能電網(wǎng)的繼電保護(hù)系統(tǒng)等，程序的執(zhí)行時(shí)間通常是至關(guān)重要的，即使是在最差情況下也不能超出截止期，否則可能造成災(zāi)難性后果。因此，WCET已經(jīng)成為評(píng)估軟件時(shí)效安全性的一個(gè)非常重要的指標(biāo)和參數(shù)。

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

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

1）重構(gòu)是在早期編碼階段設(shè)計(jì)發(fā)生，因而有助于及時(shí)修復(fù)時(shí)效缺陷。

2）重構(gòu)對(duì)象是源碼，更換目標(biāo)處理器后無(wú)需修改即可復(fù)用，有利于降低新系統(tǒng)的開(kāi)發(fā)成本。

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

1源碼重構(gòu)

重構(gòu)（refactoring）是指在不改變軟件可觀察行為的前提下，使用一系列重構(gòu)手法調(diào)整代碼結(jié)構(gòu)。重構(gòu)的目的原本是改善代碼設(shè)計(jì)，提高軟件的可理解性，降低其修改成本＼[2＼]。而在本文中，重構(gòu)的目的是在不改變軟件可觀察行為的前提下，通過(guò)對(duì)源碼結(jié)構(gòu)的調(diào)整降低WCET。

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

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

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