倪友聰,吳 瑞,杜 欣,葉 鵬,李汪彪,肖如良

1(福建師范大學 數(shù)學與信息學院,福建 福州 350117)

2(武漢紡織大學 數(shù)學與計算機學院,湖北 武漢 430200)

3(福建師范大學 光電與信息工程學院,福建 福州 350117)

4(福建省公共服務大數(shù)據挖掘與應用工程技術研究中心(福建師范大學),福建 福州 350117)

能耗是嵌入式軟件的關鍵質量屬性,特別是在電量受限的執(zhí)行環(huán)境中,降低嵌入式軟件的能耗具有更為重要的價值和意義[1].與嵌入式軟件源代碼級的能耗優(yōu)化相比,編譯時能耗優(yōu)化具有無需改動源代碼,并且可保證功能語義一致性的優(yōu)點.作為一款開源編譯器,GCC[2]已廣泛應用于嵌入式軟件源代碼的編譯.GCC提供常用的幾種優(yōu)化等級,利用每種優(yōu)化等級所預設的一組編譯選項對軟件源代碼進行編譯,能實現(xiàn)可執(zhí)行代碼的質量優(yōu)化.然而,對于特定的軟件源代碼、特定的執(zhí)行平臺和特定的優(yōu)化目標,GCC的優(yōu)化等級往往難以獲得最佳的優(yōu)化效果.此外,GCC編譯選項數(shù)目眾多,選擇空間十分龐大.例如GCC4.9.2提供了188個編譯選項,其選擇空間高達2188.依靠程序員人工選擇編譯選項不僅十分困難,而且也難以保證優(yōu)化質量.更為重要的是,GCC提供的優(yōu)化等級多集中于執(zhí)行時間和目標代碼大小的優(yōu)化,而未針對能耗優(yōu)化的場景.Pallister的研究成果[3]已表明,使用GCC的某些優(yōu)化等級對嵌入式軟件進行編譯時,甚至出現(xiàn)能耗增加的情況.近年來,用于能耗優(yōu)化的 GCC編譯選項的選擇問題已經成為了一個研究熱點[4].基于Hoste等人[5]提出的58個常用于能耗優(yōu)化的編譯選項,已涌現(xiàn)出基于統(tǒng)計的方法、機器學習方法和演化算法這3類主要的優(yōu)化方法[6].

基于統(tǒng)計的方法[7]運用 Mann-Whitney測試為特定的領域嵌入式軟件確定一組有改進效果的編譯選項.具體地,首先,將一組預設的編譯選項應用于多個同類型嵌入式軟件,考察在這組選項中去掉某一編譯選項后的能耗變化情況;再根據Mann-Whitney測試的結果判斷去掉該編譯選項前后是否存在顯著的差異,從而確定該編譯選項是否對能耗有顯著影響;最后,經過多組統(tǒng)計實驗,可找出一組對某一類型嵌入式軟件有能耗改進效果的編譯選項.由于GCC編譯選項眾多且它們之間還存在復雜的影響關系,而基于統(tǒng)計的方法一次僅考查1個選項的模式難以最終獲取對能耗改進效果最佳的編譯選項集合.

機器學習方法[8-10]先通過對訓練樣本集使用機器學習算法訓練得到模型,再利用模型預測與訓練樣本集同屬一類的嵌入式軟件的最優(yōu)編譯選項集合.訓練樣本集中的每個樣本以某一嵌入式軟件作為輸入,并使用迭代編譯的方法找到的最優(yōu)編譯選項集合作為輸出.同類型的多個嵌入式軟件及它們的最優(yōu)編譯選項集合組成了機器學習方法的訓練樣本集.然而,一些研究工作[10,11]已經實證了迭代編譯方法不能在龐大的空間中找到最優(yōu)編譯選項集合.受制于訓練樣本自身的質量,使得機器學習方法得到的模型難以準確預測出真正的最優(yōu)編譯選項集合.

基于演化算法的方法[5,11-14]將編譯時能耗優(yōu)化問題抽象成一個編譯選項選擇優(yōu)化問題,并針對特定的嵌入式軟件和特定的執(zhí)行平臺搜索更大的編譯選項選擇空間,為進一步降低能耗提供了有力支持.Hoste等人運用傳統(tǒng)遺傳算法(genetic algorithm,簡稱 GA)[5,11]獲取了比迭代編譯和編譯器預設的最高優(yōu)化等級更好的編譯選項集合.為了進一步提高解的質量和加快算法的收斂速度,Lin,Nagiub和 Garciarena又提出了一些新的演化算法.Lin等人[12]設計了一種基因加權的遺傳算法,通過對上一代種群中適應度值高的個體所選擇的編譯選項加權,以影響變異概率,從而加快了收斂速度.Nagiub等人[13]通過設計新的 pass-over算子,將上一代種群中適應度優(yōu)的個體直接加入到下一代種群,利用保留優(yōu)勢解的策略進一步加快了算法的收斂速度.但Lin等人和Nagiub等人的算法不僅存在過早收斂、易陷入局部最優(yōu)的問題,而且也未考慮編譯選項之間存在相互影響的情況.為了解決這些不足,Garciarena等人[14]提出了雙變量相關分布評估算法(tree estimation of distribution algorithm,簡稱Tree-EDA).Tree-EDA算法考慮了任意兩個編譯選項之間可能存在的相互影響,并在多個案例下與 GA和單變量分布評估算法(univariate marginal distribution algorithm,簡稱 UMDA)[15]進行了對比實驗,實驗結果表明,Tree-EDA算法能獲取比GA和UMDA更好的解質量和收斂速度.然而Tree-EDA僅考慮了任意兩個編譯選項之間的相互影響,而未涉及多個選項之間可能存在的相互作用.

為了探究多個編譯選項之間的相互作用對解質量和收斂速度的影響,本文提出了一種基于頻繁模式挖掘的遺傳算法,并將其命名為GA-FP.GA-FP算法記錄演化過程中有能耗改進效果的個體,并建立帶能耗標注的事務表.GA-FP算法利用帶能耗標注的事務表,并通過擴展傳統(tǒng)的頻繁模式樹挖掘算法,挖掘出現(xiàn)頻度高且能耗改進大的一組編譯選項,并將其作為啟發(fā)式信息,引入了“增添”和“刪減”兩種新的變異算子幫助提高解質量和加快收斂速度.通過與Tree-EDA在5個不同領域的8個典型案例下實驗對比的結果表明,本文的GA-FP算法不僅能更有效降低軟件能耗(平均降低2.5%,最高降低21.1%),而且還能在獲得不劣于Tree-EDA能耗優(yōu)化效果的前提下更快地收斂(平均加快34.5%,最高加快83.3%);最優(yōu)解中編譯選項的相關性分析,進一步驗證了所設計變異算子的有效性.

本文第1節(jié)給出問題描述.第2節(jié)闡述GA-FP算法的總體流程.第3節(jié)詳細介紹挖掘帶能耗改進標注的頻繁編譯模式集.第 4節(jié)提出“增添”和“刪減”兩個變異算子.第 5節(jié)給出案例研究及實驗結果.第 6節(jié)總結全文并給出未來工作.

1 問題描述

下面給出用于嵌入式軟件能耗優(yōu)化的GCC編譯選項選擇問題的形式化描述.

定義1(優(yōu)化空間Ω).若對GCC編譯器支持的編譯選項從1至l進行編號,則優(yōu)化空間Ω可定義為公式(1)所示的l元序偶集.

其中,xi=0或1分別表示選用或不選用編譯選項i.

定義2(選用和未選用的編譯選項集).對于優(yōu)化空間Ω中一個元素X,其所定義的選用和未選用的編譯選項集分別用SS(X)和SU(X)表示.它們分別由公式(2)和公式(3)定義.

定義3(能耗評估).能耗評估函數(shù)EvE(Sftexe)用于計算一個嵌入式軟件可執(zhí)行代碼Sftexe在某一特定輸入下,從開始運行至結束所消耗的電能(如圖1所示).

Fig.1 Schematic diagram of energy consumption calculation圖1 能耗計算示意圖

EvE(Sftexe)的定義如公式(4)所示.

其中,Tj和Tj+1分別表示Sftexe在特定輸入下,執(zhí)行過程中的第j和j+1功率測量的采樣點;T0和Tn分別為Sftexe執(zhí)行的開始時刻和結束時刻;Pj和Pj+1分別表示第j和j+1采樣點測得的瞬時功率.通過累加相鄰兩個采樣時刻點和對應功率所形成的梯形的面積,可計算Sftexe執(zhí)行過程中實際能耗的近似值.基于STM32F4開發(fā)板,我們研發(fā)了一套能耗評估系統(tǒng),實現(xiàn)了EvE(Sftexe)函數(shù)的功能.

定義4(編譯和鏈接).定義函數(shù)cmpLnk0(Sftsrc)和函數(shù)cmpLnk(Sftsrc,X)分別表示運用GCC編譯器缺省的-O0等級(不選用任何編譯選項)、SS(X)選用的編譯選項集,對一個嵌入式軟件源代碼Sftsrc進行編譯和鏈接后所得到的可執(zhí)行代碼.

定義5(目標函數(shù)).定義函數(shù)f(Sftsrc,X)用于計算相對于-O0等級,使用SS(X)編譯選項集獲得Sftsrc對應的可執(zhí)行代碼在運行時能耗所降低的百分比.f(Sftsrc,X)的定義如公式(5)所示.

定義6(優(yōu)化問題).用于嵌入式軟件能耗優(yōu)化的編譯選項選擇問題可描述為搜索滿足公式(6)的最優(yōu)解X*.

2 GA-FP算法流程

GA-FP算法用于求解公式(6)定義的優(yōu)化問題,它在傳統(tǒng)遺傳算法[16]中融入了頻繁模式挖掘和啟發(fā)式變異的方法,其流程見表1.

Table 1 Flow of GA-FP algorithm表1 GA-FP算法的流程

GA-FP算法主要包括初始化隨機種群、計算種群中個體的適應度值、更新帶能耗改進標注的編譯選項事務表、挖掘帶能耗改進標注的頻繁編譯選項模式集、種群中個體做交叉操作、種群中個體做啟發(fā)式變異操作、按輪盤賭選擇出下一代種群等主要步驟.下面僅對與頻繁模式挖掘和啟發(fā)式變異相關的步驟作簡要介紹.

· 更新帶能耗改進標注的編譯選項事務表發(fā)生在每個個體的適應度值計算后.具體地,通過表1中的第7步～第 13步,將有能耗改進效果的個體Xk的信息作為一條事務收集到形如表2的事務表TTE(the transaction table with energe annotations of compilation options)中.每條事務TE(a transaction with energe annotations)是三元組(編譯選項編號、出現(xiàn)次數(shù)和能耗改進標注)的有序列表,它用于依次保存Xk選用的一組編譯選項及能耗改進效果的信息.為了便于挖掘,在TE的每個三元組中,出現(xiàn)次數(shù)固定為 1、能耗改進標注值為Xk相對于GCC的-O0等級降低能耗的百分比(對應于f(Sftsrc,Xk)).能耗改進標注表達了一個編譯選項參與了多大能耗改進幅度的事務.

· 挖掘帶能耗改進標注的頻繁編譯選項模式集(表1中的第15步)以及“增添”和“刪減”兩種啟發(fā)式變異操作(表1中的第19步～第23步)將分別在下面的第3節(jié)和第4節(jié)給予詳細的闡述.

Table 2 An example for transaction tableTTEwith energy consumption annotations of compilation options表2 帶能耗改進標注的編譯選項事務表TTE的例子

3 挖掘帶能耗改進標注的頻繁編譯選項模式集

與一般的事務不同,表2中每個事務TE中的每個編譯選項被標注了所參與事務的能耗改進信息,因而在挖掘過程中不僅需要考慮各個編譯選項在事務表中出現(xiàn)的頻度,而且還要體現(xiàn)各個編譯選項所參與事務的能耗改進情況.文中通過擴展經典的頻繁模式樹挖掘算法[17],挖掘出帶能耗改進標注的頻繁編譯選項模式集.下面先給出與頻繁編譯選項模式相關的定義,然后介紹與帶能耗改進標注的頻繁模式樹(簡記為FPE樹)的數(shù)據結構,再闡述基于FPE樹的挖掘算法,最后給出一個例子來解釋整個頻繁編譯選項模式集的挖掘過程.

3.1 與頻繁編譯選項模式相關的定義

定義7(編譯選項的支持計數(shù)).i號編譯選項的支持計數(shù)cnt(i)由公式(7)和公式(8)定義.

從定義7和定義8不難看出,cnt(i)是i號編譯選項在整個事務表TTE中出現(xiàn)的次數(shù).例如在表2的例子事務表TTE中,cnt(1)=3.

定義8(頻繁編譯選項).稱i號編譯選項是一個頻繁編譯選項,當且僅當cnt(i)大于或等于預設的最小支持計數(shù)Cmin.

定義9(編譯選項集的支持計數(shù)).若ScmpOptNm是編譯選項編號的集合,則ScmpOptNm對應的編譯選項集的支持計數(shù)用cntS(ScmpOptNm)進行表示.cntS(ScmpOptNm)由公式(9)和公式(10)定義.

從公式(9)和公式(10)不難看出,cntS(ScmpOptNm)是ScmpOptNm的各個編譯選項在事務表TTE各條事務中同時出現(xiàn)的次數(shù).例如在表2的例子事務表TTE中,6號和3號組成的編譯選項集{6,3}的支持計數(shù)cntS({6,3})=3.

定義 10(頻繁編譯選項模式).若ScmpOptNm和Cmin分別是編譯選項編號的集合和預設的最小支持計數(shù),則ScmpOptNm對應的編譯選項集是頻繁編譯選項模式,當且僅當cntS(ScmpOptNm)≥Cmin.

定義11(帶能耗改進標注的頻繁編譯選項模式).設fpcmpOpt是帶能耗改進標注的編譯選項集合:

其中,cmpOptNm和engAno分別表示編譯選項編號和能耗改進標注.若投影fpcmpOpt中每個元素的cmpOptNm而獲得的編譯選項集是滿足定義10的頻繁編譯選項模式,則稱fpcmpOpt是一個帶能耗改進標注的頻繁編譯選項模式.當|fpcmpOpt|=k,稱fpcmpOpt為帶能耗標注的k頻繁編譯選項模式,并簡記為.

3.2 FPE樹的數(shù)據結構

與傳統(tǒng)FP樹[17]的數(shù)據結構類似,FPE樹也是由前綴項樹PT和項頭表HL所構成,但FPE樹融入了能耗標注,如圖2所示.前綴項樹 PT包含一個根結點root和若干棵前綴項子樹,PT樹的每個結點用cmpOptNm,count,engAno,parNode和nextNode這5個屬性描述,它們分別表示編譯選項編號、編譯選項出現(xiàn)次數(shù)、能耗改進標注、指向父結點的指針和指向下一個具有相同編譯選項編號的結點的指針.在圖2橢圓形表示的結點中,逗號分隔的3個數(shù)值分別是cmpOptNm,count和engAno的值,而根結點root中的這3個數(shù)值為空null.圖2中,實線和虛線弧間接定義了每個結點的parNode和nextNode的值.沒有虛線弧的結點,其nextNode值為空null.與傳統(tǒng)FP樹不同之處在于,FPE樹的結點引入了能耗改進標注的描述.

Fig.2 FPE tree derived from the example transaction tableTTEshown in table 2圖2 基于表2例子事務表TTE生成的FPE樹

項頭表HL的每個表項用cmpOptNm和hdLnk兩個屬性進行描述,這兩個屬性分別表示編譯選項編號和結點鏈(虛線弧構成的鏈)的頭指針.通過結點鏈,可將同一個編譯選項鏈接起來.例如,圖2中項頭表HL最后一行的頭指針hdLnk將前綴樹PT中所有出現(xiàn)16號編譯選項的結點(灰色背景指示)鏈接起來.

3.3 基于FPE樹的挖掘算法

表3給出了帶能耗改進標注的頻繁編譯選項模式的挖掘算法FPE-growth.當以帶能耗改進標注的編譯選項事務表TTE和最小支持計數(shù)Cmin作為參數(shù)調用 FPE-growth,可輸出頻繁編譯選項模式集表,其包含了所有的k頻繁編譯選項模式集.對圖2的FPE樹運用FPE-growth算法可輸出表4所示的頻繁編譯選項模式集表.

Table 3 FPE-growth algorithm表3 FPE-growth算法

Table 4 Table for the set of frequent pattern of compilation options with energy annotations in the example表4 例子的帶能耗改進標注的頻繁編譯選項模式集表

3.4 算法執(zhí)行的實例

本節(jié)將FPE-growth算法的一個輸入參數(shù)事務表TTE設為表2所示的事務表,另一個輸入參數(shù)最小支持計數(shù)Cmin設為3,闡述FPE-growth算法執(zhí)行過程.下面通過該算法中構建初始FPE樹、在FPE樹中插入頻繁編譯選項和挖掘帶能耗改進標注的頻繁編譯選項模式集表等關鍵步驟進行說明.

· 步驟1.基于表2所示的帶能耗改進效果的事務表TTE,生成一棵如圖3所示的初始FPE樹,包括前綴項樹PT和項頭表HL.

· 步驟2.通過掃描事務表TTE按最小支持計數(shù)3篩選出頻繁編譯選項,并按照支持計數(shù)降序排列,生成一張如表5所示排序后的頻繁編譯選項事務表TTFE.

· 步驟3.將頻繁編譯選項事務表TTFE各事務中的頻繁編譯選項按行依次插入到FPE樹,最終獲得如圖2所示的FPE樹.具體細節(jié)如下.

? 插入表5事務表TTFE第1行事務中的各頻繁編譯選項.由于每次遞歸插入時,根結點root沒有匹配的孩子結點,故依次生成5個新結點,建立FPE樹的第1個分支,如圖4所示.

? 插入表4事務表TTFE第2行事務中各頻繁編譯選項.在圖4的FPE樹基礎上,將表5事務表TTFE第2行事務的各頻繁編譯選項依次插入到FPE樹時,由于插入第1個頻繁編譯選項(其編號、支持計數(shù)和能耗改進標注分別為6、1和10%)時,root結點有一個匹配的孩子結點(如圖4灰色背景的結點,其支持計數(shù)和能耗改進標注分別為 1和 12%),需要將這個孩子結點的計數(shù)和能耗改進標注分別與表5第2行事務中6號編譯選項的支持計數(shù)和能耗改進標注進行累加并更新為count=2和engAno=22%.類似地,插入表5第2行的第2和第 3個頻繁編譯選項.而當插入第 4個頻繁編譯選項(其編號、支持計數(shù)和能耗改進標注分別為 2、1和 10%)時,此時的根結點(1,2,22%)下沒有匹配的孩子結點,在根結點(1,2,22%)下新建一個孩子結點,并將表3第2行事務中2號編譯選項的支持計數(shù)和能耗改進標注賦值給該孩子結點的對應屬性,從而得到 FPE樹的第2個分支.同理,將第5個頻繁編譯選項插入到FPE樹得到圖5所示的FPE樹.

? 依次插入表5第3行～第5行事務中的各編譯選項,可輸出表2事務表TTE對應的FPE樹,如圖2所示.

· 步驟4.基于步驟3得到的FPE樹,使用挖掘算法獲取如表4所示的帶能耗改進標注的頻繁編譯選項模式集.

Fig.3 Initial FPE tree in the example圖3 例子初始的FPE樹

Table 5 Transaction tableTTFEof frequent compilation options obtained by selecting and sorting the transaction tableTTE表5 對事務表TTE進行篩選和排序后獲取的頻繁編譯選項事務表TTFE

Fig.4 FPE tree obtained by inserting frequent compilation options of 1st row in Table 5 TTFE圖4 將表5事務表TTFE第1行事務中各頻繁編譯選項插入后得到的FPE樹

Fig.5 FPE tree obtained by inserting frequent compilation options of 1st and 2nd rows in Table 5TTFE圖5 將表5事務表TTFE第1行和第2行事務中各頻繁編譯選項插入后得到的FPE樹

4 變異操作

GA-FP算法引入了“增添”和“刪減”作為兩種啟發(fā)式變異操作,這兩種操作以帶能耗改進標注的頻繁編譯選項模式集為啟發(fā)式信息,下面給出相關定義后,再給出它們的具體操作步驟.

4.1 變異操作相關定義

定義12(頻繁編譯選項模式的加1匹配).若SS(X)和SU(X)分別是個體X指示的已選用和未選用的編譯選項編號集,并且從SS(X)中隨機選取k個元素(1≤k≤|SS(X)|)構成編譯選項編號集合為ScmpOptNm,則ScmpOptNm的頻繁編譯選項模式的加1匹配由公式(11)定義.

例如,個體X={0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,1},則SS(X)={3,5,9,10,11,13,14,16},SU(X)={1,2,4,6,7,8,12,15}.挖掘獲得的帶能耗改進標注的頻繁編譯選項模式集如表4所示.設從SS(X)中隨機選取2個元素構成的編譯選項編號集合為ScmpOptNm={3,13},從表4的頻繁編譯選項模式集中對應的4行可分別投影出4個編譯選項編號集:{13,6,3},{13,6,1},{13,3,1},{1,3,6}.僅第1個和第3個集合包含ScmpOptNm={3,13},并且這兩個集合與ScmpOptNm的差集都被SU(X)包含,故fpMatch+({3,13})={{(13,30%),(6,82%),(3,60%)},{(13,30%),(3,60%),(1,60%)}}.

定義13(頻繁編譯選項的加1匹配).若ScmpOptNm是從個體X的已選用編譯選項編號集中隨機抽取大小為k的子集,ScmpOptNm的頻繁編譯選項模式加1匹配為fpMatch+(ScmpOptNm),并且fpMatch+(ScmpOptNm)不空,則ScmpOptNm的頻繁編譯選項加1匹配fCOptMatch+(ScmpOptNm)由公式(12)定義.

其中,fCOpt.cmpOptNm表示頻繁編譯選項fCOpt的編譯選項編號.

例如,在上例的fpMatch+({3,13})中,兩個頻繁編譯選項模式可分別投影出 2個編譯選項編號集{13,6,3},{13,3,1}.這兩個集合與ScmpOptNm={3,13}的差集分別為{6},{1}.根據差集,可從fpMatch+({3,13})中獲取.

定義 14(頻繁編譯選項模式的減 1匹配).若個體X的已選用和未選用的編譯選項編號集分別為SS(X)和SU(X),并且從SS(X)中隨機選取k個元素(1≤k≤|SS(X)|)構成編譯選項編號集為ScmpOptNm,則ScmpOptNm的頻繁編譯選項模式減1匹配fpMatch-(ScmpOptNm)由公式(13)定義.

例如,個體X={0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,1},則SS(X)={3,5,9,10,11,13,14,16},SU(X)={1,2,4,6,7,8,12,15}.

挖掘獲得的帶能耗改進標注的頻繁編譯選項模式集如表4所示.設從SS(X)中隨機選取2個元素構成的編譯選項編號集合為ScmpOptNm={3,16},從表4的頻繁編譯選項模式集包含 6個元素:{(16,30%)},{(13,30%)},{(2,31%)},{(1,30%)},{(3,40%)}和{(6,41%)}.僅第1和第5個元素的編譯選項編號被包含于ScmpOptNm={3,16},故

4.2 增添操作

表6給出了按增添操作的具體流程.當個體X沒有選用任何編譯選項,則采取隨機單點變異方式將X的一位由0變1;否則,實施啟發(fā)式增添編譯選項.下面沿用定義12和定義13中使用的例子解釋增添操作過程中的啟發(fā)式變異.

設個體X={0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,1},則SS(X)={3,5,9,10,11,13,14,16},SU(X)={1,2,4,6,7,8,12,15}.挖掘獲得的帶能耗改進標注的頻繁編譯選項模式集見表4.假定表6第5步從SS(X)中隨機選取k=2個元素組成待變異的編譯選項編號集合為ScmpOptNm={3,13},根據定義13可得fCOptMatch+({3,13})={(6,82%),(1,60%)},其過程分析見定義13的例子說明.故表6第6步得到頻繁編譯選項集SfCOpt={(6,82%),(1,60%)}.由表6第10步知:

因而,分別以0.58和0.42概率選擇6號和1號編譯選項.假設選中6號編譯選項,則通過表6第13步將X下標為6的碼值替換成1,得到了新個體X′={0,0,1,0,1,1,0,0,1,1,1,0,1,1,0,1}.

Table 6 Flow of “Add” operation表6 “增添”操作的流程

4.3 刪減操作

表7給出了按刪減操作的具體過程.

若個體X沒有選用任何編譯選項,則不做刪減操作.當個體X僅選用 1個編譯選項,則刪減這個編譯選項.除此兩種情況外,實施啟發(fā)式刪減編譯選項.沿用定義14所舉的例子說明刪減操作過程的啟發(fā)式變異.

假定個體X={0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,1},則SS(X)={3,5,9,10,11,13,14,16},SU(X)={1,2,4,6,7,8,12,15}.挖掘獲得的帶能耗改進標注的頻繁編譯選項模式集如表4所示.設表7第6步從SS(X)中隨機選取k=2個元素構成的編譯選項編號集合為ScmpOptNm={3,16},根據定義14可得fpMatch-({3,16})={{(16,30%)},{(3,40%)}},其過程分析見定義14下的例子說明.因而,表7第7步得到SfCOpt={{(16,30%)},{(3,40%)}}.由表7第11步可知,

故分別以0.57和0.43概率選擇16號和3號編譯選項.假設選中16號編譯選項進行移除,而保留潛在能耗效果改進更好的3號編譯選項.通過表7第15步,將X下標為16的碼值替換成0,得到了新個體:

5 案例研究

本節(jié)給出了案例研究.第5.1節(jié)簡介了實驗案例.第5.2節(jié)提出了要驗證的問題及度量標準.第5.3節(jié)說明了實驗中使用的統(tǒng)計方法.第5.4節(jié)介紹了實驗安裝.第5.5節(jié)展示了實驗結果并進行了分析.

5.1 案例簡介

本文從BEEBS平臺[18]中選用涵蓋安全、網絡、通信、汽車和消費這5個領域的8個案例,表8給出了這些案例的應用領域和代碼量.

Table 8 Application domains and code size in the experimental cases表8 實驗案例的應用領域和代碼量

5.2 研究問題及其度量指標

問題1(解質量).本文GA-FP算法較之Tree-EDA算法能否得到更優(yōu)的編譯選項組合,使得案例的運行能耗更低?Tree-EDA是目前以能耗為優(yōu)化目標并可獲取較優(yōu)編譯選項組合的一種算法.通過回答這一問題,可以驗證GA-FP算法的有效性.

度量指標.將 GA-FP和 Tree-EDA最優(yōu)解對應的能耗相對改進百分比IΔeng%作為度量指標.在案例源代碼Sftsrc下,IΔeng%的定義如公式(14)所示,其值越大越好.

其中,

問題2(收斂速度).與Tree-EDA算法相比,GA-FP算法能否加快收斂速度?通過回答這一問題進一步驗證GA-FP算法的有效性.

度量指標.為了公平比較兩種算法的收斂速度,將 GA-FP達到不劣于 Tree-EDA最優(yōu)解對應最小迭代次數(shù)的相對減少百分比IΔi%作為度量指標.在案例源代碼Sftsrc下,IΔi%的定義如公式(15)所示,其值越大越好.

其中,MinTree-EDA(Sftsrc,X*)和MinGA-FP(Sftsrc,X*)分別表示在案例源代碼Sftsrc下,Tree-EDA和GA-FP獲取最優(yōu)解X*所需要的最小迭代次數(shù).

問題3(最優(yōu)解中編譯選項的正相關性).與Tree-EDA算法相比,本文GA-FP算法所獲得的最優(yōu)解中編譯選項之間是否存在更強的正相關性?依賴于具體的軟件源代碼和執(zhí)行平臺中與能耗相關的特征,GCC多個編譯選項之間呈現(xiàn)不相關、負相關和正相關等不同的影響關系.通過回答這一問題,可揭示 GA-FP比 Tree-EDA獲得更好的解質量和更快的收斂速度的原因.亦即 GA-FP在出現(xiàn)頻度高且對能耗有顯著改進效果的一組編譯選項基礎上,引入的啟發(fā)式變異應使得獲取的最優(yōu)解中包括更多正相關的編譯選項.

度量指標.一組正相關編譯選項是指:若從中移除任何一個選項,將使能耗的優(yōu)化效果顯著變差.考慮到GA-FP和Tree-EDA最優(yōu)解中包含的編譯選項在數(shù)目上的差異,將正相關選項在最優(yōu)解中所占的比例作為度量指標IPC%(X*),以公正地比較最優(yōu)解中各選項間的正相關性.IPC%(X*)的定義如公式(16)所示,其值越大越好.

其中,X+表示從最優(yōu)解X*選用的編譯選項開始.運用文獻[7]提出的正交數(shù)組和曼-惠特尼秩和檢驗相結合的方法,得到的正相關的編譯選項集.

問題4(編譯選項的使用頻度).在GA-FP算法對8個案例能耗優(yōu)化結果中,各個編譯選項的使用頻度如何?通過對每個編譯選項使用頻度的分析,可以幫助人們在選用GCC編譯選項時給出一些有用的借鑒和參考.

度量指標.在 GA-FP算法m次運行各個案例的結果中,每個編譯選項xi的使用頻度Ifq%(xi)作為度量指標,其定義如公式(17)所示.

其中,useNum(xi,k,j)表示GA-FP算法在第k次運行第j個案例所得最優(yōu)解中編譯選項xi的使用次數(shù).Ifq%(xi)的值越大,說明編譯選項xi在8個案例中的使用頻度越高.

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

考慮到演化算法的隨機性,GA-FP算法和Tree-EDA算法被分別獨立運行20次,并進行統(tǒng)計檢驗.本文采用Wilcoxom秩和檢驗[19]方法對實驗數(shù)據進行統(tǒng)計分析,并將置信水平α的值設置為 0.05.為了進一步觀測對比數(shù)據的差異程度(effect size),本文還使用Vargha-Delaney[19]的作為effect size的直觀度量.的值域為[0,1],其值越大,說明差異程度越大.

5.4 實驗安裝

(1) 實驗環(huán)境

上位機的運行環(huán)境為Intel(R) Core(TM)i5-4590,3.30GHz處理器,8G內存及ubuntu-16.04.1操作系統(tǒng).能耗評估系統(tǒng)是基于STM32F4板自主研發(fā).被優(yōu)化案例軟件的運行環(huán)境采用STM32F103板.編譯器和編譯選項使用GCC4.9.2,并選用與Tree-EDA[14]相同的58個編譯選項.

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

為了公平起見,GA-FP盡可能采用與Tree-EDA 相同的參數(shù)設定.表9給出了GA-FP和Tree-EDA的參數(shù)設定.表9中的符號NA表示GA-FP或Tree-EDA不包含對應的參數(shù).

Table 9 Parameter settings of Tree-EDA and GA-FP表9 Tree-EDA和GA-FP的參數(shù)設定

5.5 實驗結果及分析

下面具體給出問題1和問題2的實驗結果及分析.

(1) 問題1(解質量)的實驗結果及分析

表10給出了8個案例下-O0等級和-O3最優(yōu)等級以及GA-FP和Tree-EDA算法20次運行最優(yōu)解對應的能耗情況.從表10可以看出,對于每個案例,GA-FP和Tree-EDA在平均情況和最好情況下都能獲取比-O3等級更優(yōu)的編譯選項集;GA-FP在最壞情況下對于全部案例也能得到優(yōu)于-O3等級的編譯選項集,而Tree-EDA在2D FIR和Float_Matrix兩個案例卻得到劣于-O3等級的結果;并且對于所有8個案例,GA-FP算法在平均情況、最壞情況和最好情況下都獲得了比Tree_EDA和-O3等級更優(yōu)的編譯選項集.

Table 10 Energy consumption of the optimal solutions obtained by -O0 level,-O3 level,Tree-EDA and GA-FP by 20 runs in 8 cases (J)表10 8個案例下-O0和-O3最優(yōu)等級以及GA-FP和Tree-EDA算法20次運行最優(yōu)解對應的能耗 (J)

表11進一步給出了GA-FP和Tree-EDA在8個案例下能耗改進百分比(IΔeng%)的秩和檢驗結果.

表11中第2列p-value值均小于置信水平0.05.這表明在8個案例下GA-FP的IΔeng%指標在統(tǒng)計意義上顯著優(yōu)于Tree-EDA.從表11中第3列的effect size值可以看出,GA-FP算法在Crc32和Dijstra兩個案例下,以概率1優(yōu)于Tree-EDA;在2D FIR、Blowfish、Cubic、FDCT、Float_Matrix和Int_Matrix這6個案例下,以較大概率在解質量上優(yōu)于Tree-EDA.

圖6所給出的統(tǒng)計盒圖也從直觀上得到一致結論.

從表12的統(tǒng)計量結果可知,8個案例下的IΔeng%指標平均值為2.5%,最大IΔeng%指標值可達21.1%.

Table 11 Rank sum test results of energy consumption improvement percentageIΔeng% of GA-FP compared with Tree-EDA under 8 cases表11 GA-FP較之Tree-EDA在8個案例下能耗改進百分比(IΔeng%)的秩和檢驗結果

Fig.6 Boxplot using energy consumption improvement percentageIΔeng% of GA-FP compared with Tree-EDA圖6 GA-FP較之Tree-EDA在8個案例下能耗改進百分比(IΔeng%)的統(tǒng)計盒圖

Table 12 Statistical results of energy consumption improvement percentageIΔeng% of GA-FP compared with Tree-EDA under 8 cases表12 GA-FP較之Tree-EDA在8個案例下能耗改進百分比(IΔeng%)的統(tǒng)計量結果

(2) 問題2(收斂速度)的結果及分析

表13給出了在8個案例下收斂速度指標IΔi%(GA-FP達到不劣于Tree-EDA最優(yōu)解對應最小迭代次數(shù)的相對減少百分比)的秩和檢驗結果.表13中第2列p-value值均小于置信水平0.05,表明在8個案例下,GA-FP的IΔi%指標在統(tǒng)計意義上顯著優(yōu)于Tree-EDA.表13中第3列的effect size值均大于等于0.8,說明GA-FP算法比Tree-EDA算法在大概率上具有更快的收斂速度.

從表14可看出,8個案例下的IΔi%指標平均值(GA-FP達到不劣于Tree-EDA最優(yōu)解對應最小迭代次數(shù)的相對減少百分比)為34.5%,最大達到了83.3%.

圖7所給出的統(tǒng)計盒圖(GA-FP達到不劣于Tree-EDA最優(yōu)解對應最小迭代次數(shù)的相對減少百分比)也直觀地得到一致結論.

Table 13 Rank sum test results of the convergence speed metricIΔi% in 8 cases表13 在8個案例下收斂速度指標IΔi%的秩和檢驗結果

Table 14 Statistical results of convergence speed metricIΔi% in 8 cases表14 在8個案例下收斂速度指標IΔi%的統(tǒng)計量結果

Fig.7 Boxplot using convergence speed metricIΔi% under 8 cases圖7 收斂速度指標IΔi%的統(tǒng)計盒圖

(3) 問題3(最優(yōu)解中編譯選項的正相關性)的結果及分析

表15給出了在8個案例下,Tree-EDA和GA-FP算法獲得的最優(yōu)解中編譯選項正相關性指標IPC%(正相關編譯選項在最優(yōu)解中所占的比例)的秩和檢驗結果,表15中第2列p-value值均小于置信水平0.05,表明在8個案例下,GA-FP的IPC%指標在統(tǒng)計意義上顯著優(yōu)于 Tree-EDA.除了 Blowfish、Cubic和 Dijstra這 3個案例外,表15中第3列的effect size值均大于0.8,這表明與Tree-EDA算法相比,GA-FP算法獲得最優(yōu)解中的各編譯選項之間在大概率上具有更強的正相關性.

表16給出了在8個案例下,Tree-EDA和GA-FP算法獲得的最優(yōu)解中編譯選項正相關性指標IPC%(正相關編譯選項在最優(yōu)解中所占的比例)的統(tǒng)計結果.從表16可以看出,GA-FP算法的IPC%指標在8個案例下的平均值和最小值均優(yōu)于Tree-EDA算法;僅在Cubic和Blowfish案例下,IPC%指標在最大值上GA-FP算法分別劣于和等于 TreeEDA算法.圖8所給出的統(tǒng)計盒圖也直觀地得到一致結論.該實驗結果說明:相比于 Tree-EDA算法,在GA-FP算法獲得最優(yōu)解中,各編譯選項之間存在更強的正相關性.進而實證了文中在頻繁模式集基礎上引入“增添”和“刪減”兩種變異算子的有效性.

Table 15 Rank sum test results of positive correlation metricIPC% in the optimal solutions under 8 cases表15 在8個案例下最優(yōu)解中編譯選項正相關性指標IPC%的秩和檢驗結果

Table 16 Statistical results of positive correlation metricIPC% in the optimal solutions under 8 cases表16 在8個案例下最優(yōu)解中編譯選項正相關性指標IPC%的統(tǒng)計量結果

Fig.8 Boxplot using positive correlation metricIPC% in the optimal solutions under 8 cases圖8 在8個案例下最優(yōu)解中編譯選項正相關性指標IPC%的統(tǒng)計盒圖

(4) 問題4(編譯選項的使用頻度)的結果及分析

圖9給出了8個案例在以能耗為優(yōu)化目標下,每個GCC編譯選項的使用頻度情況.圖9橫軸中的數(shù)字表示編譯選項的編號;而縱軸則通過不同顏色標識出不同案例下各編譯選項的使用頻度,并通過累加各案例中每個編譯選項的使用頻度得出度量指標Ifq%(xi)的值.橫軸中所有編譯選項編號按照Ifq%(xi)的值從左向右降序排列.從圖9可以看出,在8個案例中,-freorder-blocks(43號)、-fschedule-insns2(47號)以及-fgcse(39號)依次為使用頻度最高的 3個編譯選項;而-falign-functions=0(29號)、-fno-reorder-blocks-and-partition(34號)和-fexpensiveoptimizations(38號)依次為使用頻度最低的3個編譯選項.

Fig.9 Histogram using the frequency metricIfq%(xi) of each compilation option under 8 cases圖9 在8個案例下各編譯選項使用頻度指標Ifq%(xi)的柱狀圖

6 總結和未來工作

本文將頻繁模式挖掘和啟發(fā)式變異引入到傳統(tǒng)遺傳算法,提出一種用于GCC編譯時能耗優(yōu)化的算法GAFP.該算法通過考慮多個編譯選項之間可能存在的相互影響,并在演化過程中使用頻繁模式挖掘方法找出一組出現(xiàn)頻度高且能耗改進幅度大的編譯選項.在此基礎上,進一步設計了“增添”和“刪減”兩種新的變異算子.通過案例研究,實證了 GA-FP的解質量和收斂速度在統(tǒng)計意義上顯著優(yōu)于 Tree-EDA;最優(yōu)解中編譯選的相關性分析,進一步驗證了所設計變異算子的有效性.

本文在利用頻繁模式挖掘時僅考慮對能耗有改進效果的編譯選項組合,未涉及那些對能耗改進有負影響的編譯選項集合,未來工作將綜合考慮這些編譯選項集合進一步優(yōu)化現(xiàn)有的算法.另外,當前的優(yōu)化算法在進行能耗評估時仍存在耗時長的問題,未來擬引入代理模型幫助解決這一問題.