陽松苡,倪友聰,2,杜 欣,2,賈建華,肖如良

1(福建師范大學(xué) 計算機與網(wǎng)絡(luò)空間安全學(xué)院,福州 350117) 2(福建師范大學(xué) 福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心,福州 350117) 3(景德鎮(zhèn)陶瓷大學(xué) 信息工程學(xué)院,江西 景德鎮(zhèn) 333403)

1 引 言

開源編譯器LLVM[1]具有高度模塊化的特點和跨語言跨硬件平臺的編譯優(yōu)化能力,現(xiàn)已廣泛用于各類軟件的開發(fā)中.LLVM提供了大量用于優(yōu)化非功能性屬性的編譯選項并且這些選項可在編譯優(yōu)化過程的不同階段被應(yīng)用,進而產(chǎn)生不同優(yōu)化效果的可執(zhí)行代碼.LLVM開發(fā)者雖已基于領(lǐng)域知識以及在典型應(yīng)用和常用硬件平臺下的實驗結(jié)果提供了-O0、-O1、-O2和-O3(分別表示不做任何優(yōu)化、基礎(chǔ)級優(yōu)化、高級優(yōu)化和最高級優(yōu)化)等標(biāo)準(zhǔn)優(yōu)化等級,但運用這些標(biāo)準(zhǔn)等級對應(yīng)的選項序列往往只能得到平均好的優(yōu)化結(jié)果[2,3].

如何針對給定的硬件平臺和應(yīng)用程序搜索最佳LLVM選項序列以獲取具有更優(yōu)非功能屬性的可執(zhí)行代碼一直是編譯優(yōu)化領(lǐng)域的公開問題和熱點問題[2,3].解決這一問題將面臨兩個主要的挑戰(zhàn):一是龐大且離散的選項序列優(yōu)化空間.若一個特定版本LLVM提供n個選項,規(guī)定序列長度為n(每個選項均有機會使用)并且選項可重復(fù)使用時,則由不同選項序列所構(gòu)成的離散優(yōu)化空間將高達nn.對于LLVM10.01中-O2等級對應(yīng)序列出現(xiàn)的84個選項而言,其優(yōu)化空間就將超過10160;二是選項之間存在復(fù)雜交互.序列中一個選項的應(yīng)用可使得后續(xù)選項生效或失效,使得以不同順序應(yīng)用一組完全相同的選項可得到具有不同非功能屬性優(yōu)化效果的不同版本可執(zhí)行代碼.針對上述挑戰(zhàn),學(xué)術(shù)界和工業(yè)界已開展了許多LLVM編譯優(yōu)化研究工作.早期多以可執(zhí)行代碼大小或執(zhí)行時間為非功能性屬性優(yōu)化目標(biāo),而隨著物聯(lián)網(wǎng)和云計算技術(shù)的廣泛應(yīng)用,有力地推動了長時間運行的嵌入式系統(tǒng)和數(shù)據(jù)中心應(yīng)用的蓬勃發(fā)展.這些系統(tǒng)或應(yīng)用的能耗優(yōu)化[3,4]也已得到越來越多的關(guān)注.

目前國內(nèi)外已涌現(xiàn)出機器學(xué)習(xí)[3,5]和設(shè)計空間搜索(又稱迭代編譯)[6,7]兩類方法.然而這些方法多集中于執(zhí)行時間優(yōu)化,能耗優(yōu)化方面開展的工作還較為稀少.與機器學(xué)習(xí)方法不同,設(shè)計空間搜索方法雖不依賴于離線預(yù)測模型或知識庫而具有較好的可移植性,但在搜索過程中還缺乏有效捕獲和使用選項交互信息的手段,進而影響到求解質(zhì)量和收斂速度.Nobre方法[6]和Georgiou方法[7]雖依賴于標(biāo)準(zhǔn)等級隱含的選項依賴關(guān)系,但尚未考慮硬件平臺和待優(yōu)化應(yīng)用對選項交互的影響,更未從尋優(yōu)過程中動態(tài)捕獲選項交互信息.而Asher方法[8]僅捕獲任意兩個選項之間的交互信息.另外,本文前期雖已針對GCC編譯器運用頻繁模式在線捕獲任意多個選項之間的交互信息,提出了兩種GCC編譯時能耗優(yōu)化遺傳算法GA-FP[9]和FACET[10].但這些工作是在GCC 預(yù)定義的一組選項及其規(guī)定的使用順序下求解選項選擇的優(yōu)化問題,完全不同于本文的選項序列優(yōu)化問題(前者優(yōu)化空間為2n而后者高達nn,假設(shè)GCC與LLVM均提供n個選項).換言之,GA-FP和FACET不適用于LLVM任意序場景下選項交互信息的捕獲,因而仍需重新構(gòu)建選項交互信息的挖掘模型、表示方法和挖掘算法,并在此基礎(chǔ)上設(shè)計新的優(yōu)化算法.與此同時,值得注意的是:目前仍未查閱到在迭代優(yōu)化過程中動態(tài)捕獲和使用與優(yōu)化目標(biāo)進行關(guān)聯(lián)的LLVM選項交互信息的研究工作.根據(jù)大規(guī)模變量且存在變量交互的優(yōu)化問題求解理論[11],這將顯著影響LLVM選項序列的優(yōu)化質(zhì)量和尋優(yōu)速度.

針對上述問題,文中提出一種頻繁序列挖掘幫助的LLVM編譯時能耗優(yōu)化方法.該方法運用帶能耗改進標(biāo)注的頻繁選項序列FOSE表征反復(fù)出現(xiàn)在優(yōu)勢解中的選項子序列及其功效,進一步借助不同序列長度的FOSE捕獲任意多個選項之間交互并利用前綴樹和后綴樹進行表示;在此基礎(chǔ)上,針對迭代尋優(yōu)過程設(shè)計一種FOSE挖掘算法,從而形成可為新解生成提供有用、全面、可高效使用和時效好的選項交互信息挖掘方法;最后基于FOSE的前后綴樹定義了新解生成機制并給出了新解生成的規(guī)則和過程,進而提出一種頻繁選項序列挖掘幫助的LLVM編譯時能耗迭代優(yōu)化算法FHIA-FSM(Fast Heuristic Iteration Algorithm for energy consumption optimization under LLVM based on Frequent options Sequence Mining).考慮到Georgiou方法[7]是目前設(shè)計空間搜索方法中面向能耗優(yōu)化且能最快獲取較好解質(zhì)量的一種LLVM選項序列優(yōu)化方法,而遺傳算法GA是編譯優(yōu)化領(lǐng)域公認在演化足夠長時間后能獲取高質(zhì)量解的一種方法[12].因而,本文以Georgiou方法的優(yōu)化用時和解質(zhì)量分別作為基準(zhǔn)停機時間和基準(zhǔn)解質(zhì)量,并在4個不同領(lǐng)域的7個典型案例下開展實驗研究.統(tǒng)計實驗結(jié)果表明:在基準(zhǔn)停機時間下本文FHIA-FSM較Georgiou和GA的解質(zhì)量平均相對改進最好可達15.52%和101.81%;在達到基準(zhǔn)解質(zhì)量的收斂速度上,FHIA-FSM較Georgiou和GA平均相對改進最好可達18.00%和25.25%.

本文的組織結(jié)構(gòu)如下:第2節(jié)給出了LLVM選項序列優(yōu)化相關(guān)工作;第3節(jié)闡述了FHIA-FSM算法的總體流程;第4節(jié)詳細介紹了基于帶能耗改進標(biāo)注頻繁序列的選項交互信息挖掘方法;第5節(jié)提出了帶能耗改進標(biāo)注頻繁選項序列幫助的新解生成機制;第6節(jié)給出案例研究;第7節(jié)總結(jié)全文并給出未來工作.

2 相關(guān)工作

LLVM編譯選項序列優(yōu)化[2,3]作為一個公開問題一直受到高度關(guān)注,已涌現(xiàn)出機器學(xué)習(xí)和設(shè)計空間搜索兩類主要的方法.

2.1 機器學(xué)習(xí)方法

機器學(xué)習(xí)方法[3,5]通過離線學(xué)習(xí)構(gòu)建預(yù)測模型或知識庫,并進一步借助優(yōu)化算法獲取待優(yōu)化應(yīng)用的最佳選項序列.這類方法已被應(yīng)用于優(yōu)化執(zhí)行時間[13-20]和能耗[21],其可分為預(yù)測選用選項和搜索空間約簡兩個子類.

預(yù)測選用選項方法首先抽取各基準(zhǔn)應(yīng)用的靜態(tài)[14,21]或靜動態(tài)混合[13]代碼特征并按一定策略對選項或選項序列空間進行迭代搜索,進而生成樣本集;然后運用神經(jīng)網(wǎng)絡(luò)[13-15]和強化學(xué)習(xí)[21]等機器學(xué)習(xí)算法構(gòu)建可預(yù)測當(dāng)前代碼特征下選用選項的模型;最后運用迭代優(yōu)化算法通過重復(fù)3個步驟(抽取待優(yōu)化應(yīng)用代碼特征、在線查詢預(yù)測模型得到選用選項和施加選項到待優(yōu)化應(yīng)用),直至達到預(yù)設(shè)的序列最大長度或選用的選項不發(fā)生變化而停機.

而搜索空間約簡方法先通過離線構(gòu)建以基準(zhǔn)應(yīng)用及其最優(yōu)選項序列為條目的知識庫,再運用模糊聚類[16]、K近鄰算法[17]、層次聚類[18]或遺傳算法[19,20]選擇出一組將用于待優(yōu)化應(yīng)用的選項或選項序列,由它們作為排序元素可形成約簡后的搜索空間.進一步利用隨機采樣[16]、遺傳算法[17,20]、推薦算法[18]或蟻群算法[19]搜索待優(yōu)化應(yīng)用的最佳選項序列.

機器學(xué)習(xí)方法多集中于執(zhí)行時間優(yōu)化.該類方法常?；谔囟ǖ挠布脚_和一組特定的基準(zhǔn)應(yīng)用并以離線方式構(gòu)建預(yù)測模型或知識庫,當(dāng)實際優(yōu)化環(huán)境中的硬件平臺發(fā)生變化或者被優(yōu)化應(yīng)用與基準(zhǔn)應(yīng)用差異較大時,離線訓(xùn)練方式獲得的預(yù)測模型或知識庫的精度都將受到較大影響,從而引發(fā)機器學(xué)習(xí)方法可移值性差的問題.

2.2 設(shè)計空間搜索方法

與機器學(xué)習(xí)方法不同,設(shè)計空間搜索方法無需離線構(gòu)建的模型或知識庫,而是借助已有的或在線構(gòu)建的選項交互啟發(fā)式信息并使用搜索算法在選項序列的優(yōu)化空間中尋找具有最優(yōu)執(zhí)行時間[6,8]或最優(yōu)能耗[7]的解.

Nobre等人[6]根據(jù)優(yōu)化等級或開發(fā)者提供的選項間依賴關(guān)系構(gòu)造出一種加權(quán)有向圖.圖中的結(jié)點表示選項,弧表示弧頭選項依賴弧尾選項,而弧上的權(quán)值由依賴關(guān)系出現(xiàn)的次數(shù)確定.Nobre等人還基于選項依賴圖提出了一種圖采樣生成候選解的迭代優(yōu)化算法.Asher等人[8]通過在線遍歷所有長度為2的選項序列,構(gòu)建了選項交互的加權(quán)有向圖.圖中的結(jié)點表示選項,弧上標(biāo)注了應(yīng)用弧表示的二元選項序列可獲取相對-O3等級的執(zhí)行時間加速比、較單獨使用弧頭和弧尾選項的效果得分以及到達該弧的路徑等3種信息.在此基礎(chǔ)上,Asher等人將選項序列優(yōu)化形式化為尋找哈密爾頓路徑問題,并提出一種多項式時間復(fù)雜性的近似求解算法.Georgiou等人[7]以-O2等級對應(yīng)序列α所確定的選項間順序依賴關(guān)系,運用迭代刪除算法從α最后一個選項開始依次剔除一個選項,并對迭代中獲得的各選項序列進行能耗評估,以輸出具有最優(yōu)能耗的選項序列.Georgiou算法是目前設(shè)計空間搜索方法中能最快獲取較好解質(zhì)量的一種方法.

設(shè)計空間搜索方法多面向執(zhí)行時間優(yōu)化.該類方法多依賴于LLVM等級所隱含的或LLVM開發(fā)者所提供的選項交互信息,而這些信息難以適用于任意一個由硬件平臺、編譯器版本和待優(yōu)化應(yīng)用程序所構(gòu)成的優(yōu)化環(huán)境.另外,這類方法仍缺少捕獲任意多個選項之間交互的手段.更為重要的是,目前仍未查閱到在迭代尋優(yōu)過程中動態(tài)捕獲和使用與優(yōu)化目標(biāo)定量關(guān)聯(lián)的任意多個選項之間交互信息的研究工作.這從一定程度上影響了設(shè)計空間搜索方法的求解質(zhì)量和求解速度.

3 頻繁序列挖掘幫助的LLVM編譯時能耗迭代優(yōu)化算法FHIA-FSM

FHIA-FSM算法采用序列編碼(xi∈{1,2,…,n})表示候選解X.其中,LLVM選項從1開始至n進行編號.FHIA-FSM算法中能耗優(yōu)化目標(biāo)函數(shù)fEnv(X)定義為:在給定硬件平臺、LLVM和待優(yōu)化應(yīng)用源代碼及典型輸入所構(gòu)成的優(yōu)化環(huán)境Env下,解X相對于-O2等級對應(yīng)序列獲取的能耗改進百分比(降低能耗的百分比).

FHIA-FSM算法在傳統(tǒng)迭代優(yōu)化算法中融入了頻繁序列挖掘方法和啟發(fā)式新解生成機制,詳細步驟見算法1.FHIA-FSM算法主要包括初始候選解集S生成、基于S構(gòu)建初始的帶能耗改進標(biāo)注的選項序列事務(wù)數(shù)據(jù)庫DBE、挖掘生成帶能耗改進標(biāo)注的頻繁選項序列前綴樹prefixTreeE和后綴樹postfixTreeE、基于前綴樹prefixTreeE和后綴樹postfixTreeE的新解生成等主要步驟.

如算法1所示,第5～第9步給出了初始DBE的構(gòu)建,其形式如表1所示.在傳統(tǒng)序列事務(wù)基礎(chǔ)上DBE中的各事務(wù)TE增加了能耗改進標(biāo)注fEnv(X),從而將選項序列與其功效進行了定量關(guān)聯(lián).其可用三元組TE(tid,X,fEnv(X))進行表示,TE中各元素分別表示事務(wù)ID、選項序列(解)和能耗改進標(biāo)注.進一步地,在迭代優(yōu)化過程中DBE被不斷更新,如第17步所示.另外,第12步的挖掘輸出頻繁選項序列前綴樹prefixTreeE和后綴樹postfixTreeE,以及第14步的新解生成將在第4和第5節(jié)進行詳細闡述.

表1 帶能耗改進標(biāo)注的選項序列事務(wù)數(shù)據(jù)庫DBE示例Table 1 Example of option sequence transaction database DBE with energy consumption improvement annotation

算法1.頻繁序列挖掘幫助的LLVM編譯時能耗迭代優(yōu)化算法FHIA-FSM

輸入:初始解集大小N,優(yōu)化環(huán)境Env

輸出:最優(yōu)解X*

1. 迭代次數(shù)t←1;

2. 產(chǎn)生大小為N的候選解集S={X1,X2,…,Xi,…,XN}(1≤?i≤N,Xk∈Ω).其中,N-1個候選解由拉丁超立方體采樣產(chǎn)生,而另一個解為-O2等級對應(yīng)的解;

3. 事務(wù)標(biāo)識tID←0,DBE←?;//DBE初始化為空集

4.FOR(S中每個候選解Xi)DO

5. 計算Xi的目標(biāo)值fEnv(Xi);//Xi較LLVM的-O2等級對應(yīng)的序列能耗改進百分比;

6.IF(fEnv(Xi)> 0)THEN//有能耗改進效果,則更新DBE

7.tID←tID+1;

8. 將帶能耗改進標(biāo)注的選項序列事務(wù)TE(tID,Xi,fEnv(Xi))加入DBE;

9.ENDIF

10.ENDFOR

11.WHILE(未達到預(yù)設(shè)的停機時間或解質(zhì)量)DO

12. 基于DBE挖掘生成帶能耗標(biāo)注的頻繁選項序列前綴樹prefixTreeE和后綴樹postfixTreeE;

13.FOR(S中每個候選解Xi)DO

14. 基于Xi、前綴樹prefixTreeE和后綴樹postfixTreeE生成新解Yi;

15. 計算Yi的能耗目標(biāo)值fEnv(Yi);

16.IF(fEnv(Yi)>fEnv(Xi))THEN

17. 在DBE中查找Xi對應(yīng)的事務(wù)TE,若存在則用Yi和fEnv(Yi)分別替換TE中的Xi和fEnv(Xi);

18. 將S中Xi用Yi替換;

19.ENDIF

20.ENDFOR

21.t←t+1;

22.ENDWHILE

23. 輸出S中最優(yōu)解X*;

24. 結(jié)束算法運行.

4 帶能耗改進標(biāo)注的頻繁選項序列挖掘方法

帶能耗改進標(biāo)注的頻繁選項序列挖掘方法包括選項交互信息的挖掘模型和表示方法,以及具體的挖掘算法prefixspan+.

4.1 選項交互信息的挖掘模型和表示方法

圖1給出了選項交互信息的挖掘模型和表示方法.其基于尋優(yōu)過程中帶能耗改進標(biāo)注的頻繁選項序列事務(wù)數(shù)據(jù)庫DBE,并采用提出的prefixspan+算法挖掘生成帶能耗改進標(biāo)注的頻繁選項序列前綴樹prefixTreeE和后綴樹postfixTreeE.選項交互信息的挖掘模型和表示方法為新解生成提供了有用、全面、可高效使用和時效性好的啟發(fā)式信息.具體地:

圖1 選項交互信息的挖掘模型和表示方法Fig.1 Mining model and representation method for option interaction information

1)有用性

SupDBE(β)=|{TE|TE∈DBE∧β?TE·X}|

(1)

Eβ=∑TE∈DBE∧β?TE·XTE·fEnv(X)

(2)

2)全面性及可高效使用性

因而,將任意多個選項的頻繁交互運用帶能耗改進標(biāo)注的頻繁選項序列前綴樹prefixTreeE和后綴樹postfixTreeE形式進行表示.進而為選項序列尋優(yōu)過程提供全面并可高效使用的啟發(fā)式信息.

3)時效性

考慮到選項序列優(yōu)化算法尋優(yōu)過程中獲取的解集在不斷變化,根據(jù)生成的新解對當(dāng)前數(shù)據(jù)庫DBE進行更新,以保留更為優(yōu)異的解,圖1上部矩形框中示意了DBE的更新過程.其中:當(dāng)前DBE中灰色背景指示的事務(wù)TE將被基于TE生成并且更為優(yōu)異的新解Y替換.因而,從不斷變化DBE挖掘出的帶能耗標(biāo)注的頻繁選項序列可為迭代尋優(yōu)過程提供最新的選項交互啟發(fā)式信息.

4.2 帶能耗改進標(biāo)注的頻繁選項序列挖掘算法

基于DBE并通過對經(jīng)典和高效的prefixspan算法[22]進行擴展和改造,提出一種帶能耗改進標(biāo)注的頻繁選項序列挖掘算法prefixspan+.

圖2 以最小支持計數(shù)為2對圖1中更新后數(shù)據(jù)庫的遞歸挖掘過程示意圖Fig.2 Diagram of recursive mining process after the database in figure 1 has been updated(the minimum support count is 2)

①以β=< >為前綴和α=<1>為后綴連接生成新序列γ=β°α=<1>.此時γ=α,故γ與α的支持計數(shù)和能耗改進標(biāo)注相同;

圖3 插入頻繁序列至前綴樹之前和之后的圖示Fig.3 Diagram on before and after inserting frequent

算法2.帶能耗改進標(biāo)注的頻繁選項序列挖掘算法prefixspan+

輸入:指向前綴樹prefixTreeE待插入子結(jié)點的結(jié)點指針ptrpre,指向后綴樹postfixTreeE根結(jié)點的指針ptrpost,頻繁選項序列β,最小支持計數(shù)Supmin,以β為前綴的投影數(shù)據(jù)庫DBE|β

輸出:VOID

1.IF(DBE|β中事務(wù)數(shù)目小于Supmin)THEN

2.RETRUN;

3.ENDIF

4. 掃描數(shù)據(jù)庫DBE|β,并在掃描過程中按式(1)和式(2)分別計算每個選項op所對應(yīng)序列α=的支持計數(shù)SupDBE(α)和能耗改進標(biāo)注Eα,并生成頻繁選項序列集合

6. 生成序列γ=β°α,用于表示以β為前綴和α為后綴,并經(jīng)連接生成的頻繁選項序列;

10. 構(gòu)建γ的前綴投影數(shù)據(jù)庫DBE|γ,其等于(DBE|β)|α;

11. 以ptrpre、ptrpost、γ、Supmin和DBE|γ為參數(shù),遞歸調(diào)用prefixspan+算法;

12.ENDFOR

算法3.帶能耗改進標(biāo)注的頻繁選項序列插入前綴樹算法insertpre

輸出:待插子結(jié)點的新指針ptrpre

2. 在ptrpre指向結(jié)點的哈希表中增加一個表項,該表項的鍵值為α對應(yīng)選項,值為指針ptrnewNode;

3.ptrpre←ptrnewNode;

4. 返回ptrpre;

圖4 插入頻繁序列至后綴樹之前和之后的圖示Fig.4 Diagram on before and after inserting frequent

算法4.帶能耗改進標(biāo)注的頻繁選項序列插入后綴樹算法insertpost

輸出:VOID

1.i←序列γ的長度len,ptrpar←ptrpost;//ptrpar指示待插位置

2.WHILE(i>0)DO//逆序插入γ中各元素

3. 以γ[i]為鍵在ptrpar指向結(jié)點的哈希表中查找,并獲取指向匹配子結(jié)點的指針ptrchd;

4.IF(ptrchd不為空)THEN//匹配成功

5.IF(ptrchd指向結(jié)點的頻繁序列的支持計數(shù)小于SupDBE(γ))THEN//更新結(jié)點中頻繁序列的標(biāo)注

6.ptrchd指向結(jié)點對應(yīng)的頻繁序列的支持計數(shù)和能耗改進標(biāo)注分別置為SupDBE(γ)和Eγ;

7.ENDIF

8.ELSE

11. 在ptrpar指向結(jié)點的哈希表中增加一個表項,該表項的鍵值為γ[i]選項,值為指針ptrnewNode;

12.ptrpar←ptrnewNode;

13.ENDIF

14.i←i-1;

15.ENDWHILE

5 帶能耗改進標(biāo)注頻繁選項序列幫助的新解生成機制

帶能耗改進標(biāo)注頻繁選項序列幫助的新解生成機制以前綴樹prefixTreeE和后綴樹postfixTreeE作為啟發(fā)式信息設(shè)計了一組與新解生成相關(guān)的規(guī)則,并進一步定義了具體的新解生成過程.

5.1 與新解生成相關(guān)的規(guī)則

下面以圖1中前綴樹prefixTreeE和后綴樹postfixTreeE,以及解X=<5,6,3,2,7>中連續(xù)子序列α=<3,2>為例闡述前綴匹配、后綴匹配和概率選擇等與新解生成相關(guān)的規(guī)則.

1)前綴匹配規(guī)則

將解X=中確定的連續(xù)子序列α=(1≤strt≤end}生成式(3)定義的選項-平均功效集Sop作為匹配結(jié)果;若匹配不成功,則將空集?作為匹配結(jié)果.式(3)中chd.β[end-strt+2]表示孩子結(jié)點chd中選項序列最后一個元素對應(yīng)的選項op.

例中,α=<3,2>在圖1前綴樹中匹配獲得孩子結(jié)點集Schd={(<3,2,1>,2,16%),(<3,2,4>,2,17%)},如圖1中prefixTreeE虛線框中白色背景指示的兩個結(jié)點,匹配路徑已用灰色的弧在前綴樹中標(biāo)出.根據(jù)式(3)計算的匹配結(jié)果Sop={(1,8%),(4,8.5%)}.

(3)

2)后綴匹配規(guī)則

將解X=中確定的連續(xù)子序列α=(1}生成式(4)定義的選項-平均功效集Sop作為匹配結(jié)果;若匹配不成功,則將空集?作為匹配結(jié)果.式(4)中chd.γ[1]表示孩子結(jié)點chd中選項序列第一個元素對應(yīng)的選項.

例中,α=<3,2>在圖1后綴樹中匹配獲得孩子結(jié)點集Schd={(<1,3,2>,2,17%),(<4,3,2>,2,18%)},如圖1中postfixTreeE虛線框中白色背景指示的兩個結(jié)點,匹配路徑已用灰色的弧在后綴樹中標(biāo)出.而根據(jù)式(4)計算的匹配結(jié)果Sop={(1,8.5%),(4,9%)}.

(4)

3)概率選擇規(guī)則

概率選擇操作根據(jù)前綴匹配或后綴匹配規(guī)則的匹配結(jié)果Sop按概率選中某個選項.具體地,若Sop=?,則按等概率從優(yōu)化問題提供的n個選項中隨機選擇一個;若Sop≠?,則按式(5)定義的概率pj選擇選項j.式(5)中j為Sop中出現(xiàn)的選項,而avgUtilj為選項j對應(yīng)的平均功效.

(5)

例中后綴匹配規(guī)則的匹配結(jié)果Sop={(1,8.5%),(4,9%)},則選擇選項1的概率p1=8.5%/(8.5%+9%)≈48.6%,而選擇選項4的概率p4=9%/(8.5%+9%)≈51.4%.

5.2 新解生成過程

基于上一節(jié)設(shè)計的前綴匹配、后綴匹配和概率選擇3種規(guī)則,算法5給出了新解生成過程的詳細步驟.

算法5.新解生成算法

輸入:解X=

輸出:新解Y

1.i←隨機產(chǎn)生0或1,Y←X;

2.IF(i==0)THEN// 按前綴匹配生成新解

3. 隨機產(chǎn)生起始位置strt和結(jié)束位置end(1≤strt≤end;

4. 運用前綴匹配規(guī)則,并按式(3)獲取匹配結(jié)果Sop(選項-平均功效集);

5. 基于Sop并運用概率選擇規(guī)則,獲取選中的選項j;

6. 將Y中第end+1元素更新為j;

7.ELSE// 按后綴匹配生成新解

8. 隨機產(chǎn)生起始位置strt和結(jié)束位置end(1;

9. 運用后綴匹配規(guī)則,并按式(4)獲取匹配結(jié)果Sop(選項-平均功效集);

10. 基于Sop并運用概率選擇規(guī)則,獲取選中的選項j;

11. 將Y中第strt-1元素更新為j;

12.ENDIF

13. 輸出Y并結(jié)束算法運行;

算法5第3行～第6行給出了基于前綴匹配的新解生成過程,而第8行～第11行給出了基于后綴匹配的新解生成過程.例中X=<5,6,3,2,7>,若前綴匹配和后綴匹配兩種新解生成過程中隨機產(chǎn)生的起始位置strt和結(jié)束位置end都分別為2和3,則前者和后者獲取的匹配結(jié)果分別為Sop={(1,8%),(4,8.5%)}、Sop={(1,8.5%),(4,9%)}.假定按平均功效大概率選中選項,則前者和后者都會選中選項4.因而,前者生成的新解Y=<5,6,3,2,4>,而后者對應(yīng)的新解Y=<5,4,3,2,7>.

6 案例研究

本節(jié)給出了實驗研究.其中6.1節(jié)簡介了實驗案例;6.2節(jié)給出了實驗中使用的統(tǒng)計方法;6.3介紹了實驗安裝;6.4節(jié)設(shè)定了需要研究的問題,同時展示了實驗結(jié)果并給出實驗分析.

6.1 案例簡介

通過綜合考慮應(yīng)用領(lǐng)域、源代碼的結(jié)構(gòu)特性和操作特性3個要素,本文從包含應(yīng)用程序最多、用于嵌入式系統(tǒng)執(zhí)行時間和能耗優(yōu)化的開源基準(zhǔn)平臺BEEBS[23]中選取了7個具有代表性的應(yīng)用程序作為案例,如表2所示.這些案例涵蓋了安全、網(wǎng)絡(luò)、汽車和消費4個領(lǐng)域,并覆蓋了函數(shù)調(diào)用、嵌套循環(huán)、位操作、字符串操作、單循環(huán)和數(shù)組訪問等常見源代碼結(jié)構(gòu)特性,同時也盡可能多地包括影響運行時能耗的整型運算強度、浮點運算強度、分支頻度和內(nèi)存訪問頻度等不同的源代碼操作特性,并在表2中用“低”、“中”和“高”對強度或頻度進行分級.

表2 實驗案例的基本情況Table 2 Basic information of experimental case

6.2 使用的統(tǒng)計方法

6.3 實驗安裝

1)實驗環(huán)境

表3給出實驗環(huán)境的具體配置.

表3 實驗環(huán)境配置Table 3 Experimental environment configuration

2)算法參數(shù)的設(shè)定

表4給出了FHIA-FSM和GA算法下的參數(shù)設(shè)定,符號NA表示不包含對應(yīng)參數(shù).而Georgiou算法[7]不含任何參數(shù).

表4 FHIA-FSM和 GA算法參數(shù)設(shè)置Table 4 Parameter settings of FHIA-FSM and GA algorithms

6.4 實驗研究的問題、結(jié)果及分析

考慮到Georgiou算法[7]與本文FHIA-FSM算法同為基于設(shè)計空間搜索并且面向最小化能耗的LLVM選項序列優(yōu)化方法,與此同時Georgiou算法也是目前設(shè)計空間搜索方法中能最快獲取較好解質(zhì)量的一種方法.而遺傳算法GA是編譯優(yōu)化領(lǐng)域公認在演化足夠長時間后能獲取高質(zhì)量解的一種方法[12].因而本文以Georgiou算法的優(yōu)化用時和解質(zhì)量分別作為停機基準(zhǔn)時間和基準(zhǔn)解質(zhì)量,并在表2所示的4個不同領(lǐng)域的7個典型案例下圍繞求解質(zhì)量和收斂速度兩個問題開展實驗研究.

1)問題1(求解質(zhì)量):按照基準(zhǔn)停機時間,本文的FHIA-FSM算法較Georgiou算法和GA算法能否得到更優(yōu)的選項序列,使得案例應(yīng)用程序的運行時能耗更低?通過回答這一問題,可以驗證FHIA-FSM算法的有用性.

表5給出了在基準(zhǔn)停機時間下FHIA-FSM、GA和Georgiou 3種算法針對各個案例所獲取最佳目標(biāo)值(相對-O2等級最好的能耗改進百分比)的統(tǒng)計量結(jié)果.表5中FHIA-FSM同時優(yōu)于GA和Georgiou的值已被加粗表示.由表5的統(tǒng)計量結(jié)果可知:FHIA-FSM在7個案例下最佳目標(biāo)值的平均值都較GA和Georgiou更優(yōu);除fdct案例外,在其它6個案例最佳目標(biāo)值的最大值中,FHIA-FSM也都較GA和Georgiou更優(yōu);FHIA-FSM在7個案例下最佳目標(biāo)值的最小值也較GA更優(yōu).與此同時,GA在7個案例下最佳目標(biāo)值的平均值和最小值均劣于Georgiou;除fdct、float_matmult和int_matmult 3個案例外,在其它4個案例最佳目標(biāo)值的最大值中,GA也均劣于Georgiou.

表5 在基準(zhǔn)停機時間下本文FHIA-FSM、GA和Georgiou 3種算法針對各個案例所獲取最佳目標(biāo)值(相對于-O2等級的能耗改進百分比)的統(tǒng)計量結(jié)果Table 5 Statistical results of the best target value(the percentage of energy consumption improvement relative to -O2 level) obtained by FHIA-FSM,GA and Georgiou algorithms for each case under the baseline downtime

表6進一步給出了本文FHIA-FSM分別與GA和Georgiou針對基準(zhǔn)停機時間下各案例最佳目標(biāo)值(相對于-O2等級的能耗改進百分比)的秩和檢驗結(jié)果.表6中的第2列和第4列中的p-value值在全部7個案例下均遠小于置信水平0.05,這從統(tǒng)計意義角度表明FHIA-FSM在基準(zhǔn)停機時間下解質(zhì)量顯著優(yōu)于GA和Georgiou.表6中第3列和第5列中effect size的值在所有7個案例下均大于0.8,這表明FHIA-FSM較GA和Georgiou能以較大概率上獲得更優(yōu)的解.圖6所給出的統(tǒng)計盒圖也直觀地得到一致結(jié)論.

圖6 在基準(zhǔn)停機時間下FHIA-FSM、GA和Georgiou3種算法針對各案例所獲取目標(biāo)值fEnv(X*)(相對于-O2等級的能耗改進百分比)的統(tǒng)計盒圖Fig.6 Boxplot of target value fEnv(X*)(the percentage of energy consumption improvement relative to -O2 level) obtained by FHIA-FSM,GA and Georgiou algorithms for each case under the baseline downtime

表6 本文FHIA-FSM分別與GA和Georgiou針對基準(zhǔn)停機時間下各案例最佳目標(biāo)值(相對于-O2等級的能耗改進百分比)的秩和檢驗結(jié)果Table 6 Rank-sum test results of the best target value(the percentage of energy consumption improvement relative to -O2 level)obtained by FHIA-FSM,GA and Georgiou for each case under the baseline downtime

為了進一步量化FHIA-FSM對解質(zhì)量的改進情況,表7給出了FHIA-FSM較GA和Georgiou在基準(zhǔn)停機時間下各案例解質(zhì)量的平均相對改進百分比.從表7可以看出:各案例中FHIA-FSM較GA和Georgiou在解質(zhì)量上均有較大提升,而且相對GA的提升更為顯著.解質(zhì)量的平均相對改進最好情況發(fā)生在blowfish案例中,FHIA-FSM較GA和Georgiou在解質(zhì)量上分別提升了101.81%和15.52%.

表7 本文FHIA-FSM較GA和Georgiou在基準(zhǔn)停機時間下各案例解質(zhì)量(目標(biāo)值)的平均相對改進百分比Table 7 Average relative improvement percentage of solution quality(target value)for each case under baseline downtime when HIA-FSM compares with GA and Georgiou

表5、表6、圖6和表7的結(jié)果表明:不使用任何啟發(fā)式信息的GA算法獲取的解質(zhì)量多劣于使用啟發(fā)式信息進行尋優(yōu)的算法FHIA-FSM和 Georgiou.這實證了啟發(fā)式信息對于設(shè)計空間搜索這類LLVM選項序列優(yōu)化方法提高解質(zhì)量的重要性;此外,本文FHIA-FSM使用帶能耗改進標(biāo)注的頻繁選項序列捕獲選項交互的啟發(fā)式信息較Georgiou使用標(biāo)準(zhǔn)等級隱含的選項依賴關(guān)系作為啟發(fā)式信息對于提高解質(zhì)量更為有效.因而,在基準(zhǔn)停機時間下本文提出的FHIA-FSM較GA和Georgiou從統(tǒng)計意義上可獲得更優(yōu)的編譯選項序列,使得各案例應(yīng)用程序的運行能耗更低.

2)問題2(收斂速度):本文FHIA-FSM算法較Georgiou算法和GA算法能否以更少的計算時間達到基準(zhǔn)解質(zhì)量? 通過回答這一問題,可以進一步驗證FHIA-FSM算法效率.亦即FHIA-FSM可否以更快的速度收斂得到基準(zhǔn)質(zhì)量的解.

為了避免測量噪聲并進行歸一化對比,在各案例中以Georgiou算法達到基準(zhǔn)解質(zhì)量時的優(yōu)化用時作為基準(zhǔn)時間T0,定義計算時間改進百分比IΔt%作為度量指標(biāo),如式(6)所示.式(6)中,T為FHIA-FSM或GA在達到基準(zhǔn)解質(zhì)量所花費的計算時間.

(6)

表8給出了本文FHIA-FSM、GA和Georgiou 3種算法針對各案例在達到基準(zhǔn)解質(zhì)量時計算時間改進百分比的統(tǒng)計量結(jié)果.表8中FHIA-FSM同時優(yōu)于GA和Georgiou的值已被加粗表示.此外,在各案例中均以Georgiou的優(yōu)化結(jié)果作基準(zhǔn)停機時間和基準(zhǔn)解質(zhì)量,故表8中Georgiou的IΔt%指標(biāo)值均為0.由表8的統(tǒng)計量結(jié)果可知:FHIA-FSM在7個案例下IΔt%的平均值和最大值均較GA和Georgiou更優(yōu);FHIA-FSM在7個案例下IΔt%的最小值也較GA更優(yōu).與此同時,GA在全部的7個案例下IΔt%的平均值和最小值均劣于Georgiou;除fdct、float_matmult和int_matmult案例外,其它4個案例IΔt%的最大值GA也都劣于Georgiou.

表8 本文FHIA-FSM、GA和Georgiou 3種算法針對各案例在達到基準(zhǔn)解質(zhì)量時計算時間改進百分比的統(tǒng)計量結(jié)果Table 8 Statistical results of the runtime improvement percentage obtained by FHIA-FSM, GA and Georgiou algorithms for each case under the baseline solution quality

表9 本文FHIA-FSM分別與GA和Georgiou 針對各案例在達到基準(zhǔn)解質(zhì)量時計算時間改進百分比的秩和檢驗結(jié)果Table 9 Rank-sum test results of the runtime improvement percentage obtained by FHIA-FSM,GA and Georgiou for each case under the baseline solution quality

圖7 FHIA-FSM、GA和Georgiou 3種算法針對各案例達到基準(zhǔn)解質(zhì)量下計算時間改進百分比IΔt%的統(tǒng)計盒圖Fig.7 Boxplotof runtime improvement percentage IΔt% obtained by FHIA-FSM,GA and Georgiou algorithms for each case under the baseline solution quality

為了量化FHIA-FSM對收斂速度的改進情況,表10給出了FHIA-FSM較GA和Georgiou在各案例達到基準(zhǔn)解質(zhì)量時計算時間的平均相對改進百分比.從表10可以看出:各案例中FHIA-FSM較GA和Georgiou在收斂速度上均有較大提升,而且相對GA的提升更為顯著.FHIA-FSM較GA和Georgiou在收斂速度的平均相對改進最好情況分別發(fā)生在blowfish和int_matmult案例中,其分別提升了25.25%和18%.

表10 本文FHIA-FSM較GA和Georgiou在各案例達到基準(zhǔn)解質(zhì)量時計算時間的相對改進百分比Table 10 Relative improvement percentage of runtime when HIA-FSM compares with GA and Georgiou under baseline solution quality for each case

表8、表9、圖7和表10的結(jié)果表明:在達到基準(zhǔn)解質(zhì)量過程中,不使用任何啟發(fā)式信息的GA算法較使用啟發(fā)式信息進行尋優(yōu)的算法FHIA-FSM和Georgiou需要消耗更多的計算時間.這說明啟發(fā)式信息對于設(shè)計空間搜索這類LLVM選項序列優(yōu)化方法不僅對于提高解質(zhì)量,而且對于加快收斂速度也具有重要的作用;此外,本文FHIA-FSM使用帶能耗改進標(biāo)注的頻繁選項序列捕獲選項交互的啟發(fā)式信息較Georgiou使用標(biāo)準(zhǔn)等級隱含的選項依賴關(guān)系作為啟發(fā)式信息能更為有效地提高收斂速度.

7 總結(jié)和未來工作

文中提出一種頻繁序列挖掘幫助的LLVM編譯時能耗優(yōu)化方法,以緩解現(xiàn)有設(shè)計空間搜索優(yōu)化方法因求解過程中缺乏有效捕獲和使用選項交互信息的手段而導(dǎo)致解質(zhì)量不高和求解速度不快的問題.本文的具體貢獻如下:

1)通過挖掘帶能耗改進標(biāo)注的頻繁選項序列FOSE構(gòu)建選項交互信息的挖掘模型并利用前綴樹和后綴樹進行表示,該挖掘模型及表示方法可用于獲取任意多個選項之間交互信息;

2)針對迭代尋優(yōu)過程設(shè)計了一種FOSE挖掘算法,FOSE挖掘算法可為新解生成提供有用、全面、可高效使用和時效好的選項交互信息;

3)提出了一種頻繁選項序列挖掘幫助的LLVM編譯時能耗迭代優(yōu)化算法FHIA-FSM,FHIA-FSM算法設(shè)計了基于FOSE的前后綴樹定義的新解生成機制,該新解生成機制可幫助提高新解生成質(zhì)量,從而有助于提高算法收斂速度.

未來工作將面向LLVM選項復(fù)雜交互場景開展選項選擇研究,以有效降低LLVM選項序列優(yōu)化問題的解空間,達到進一步減少優(yōu)化用時的目的.