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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

定義6(優(yōu)化問題).用于嵌入式軟件能耗優(yōu)化的編譯選項(xiàng)選擇問題可描述為搜索滿足公式(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算法主要包括初始化隨機(jī)種群、計(jì)算種群中個(gè)體的適應(yīng)度值、更新帶能耗改進(jìn)標(biāo)注的編譯選項(xiàng)事務(wù)表、挖掘帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集、種群中個(gè)體做交叉操作、種群中個(gè)體做啟發(fā)式變異操作、按輪盤賭選擇出下一代種群等主要步驟.下面僅對與頻繁模式挖掘和啟發(fā)式變異相關(guān)的步驟作簡要介紹.

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

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

Table 2 An example for transaction tableTTEwith energy consumption annotations of compilation options表2 帶能耗改進(jìn)標(biāo)注的編譯選項(xiàng)事務(wù)表TTE的例子

3 挖掘帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集

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

3.1 與頻繁編譯選項(xiàng)模式相關(guān)的定義

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

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

定義8(頻繁編譯選項(xiàng)).稱i號編譯選項(xiàng)是一個(gè)頻繁編譯選項(xiàng),當(dāng)且僅當(dāng)cnt(i)大于或等于預(yù)設(shè)的最小支持計(jì)數(shù)Cmin.

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

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

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

定義11(帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式).設(shè)fpcmpOpt是帶能耗改進(jìn)標(biāo)注的編譯選項(xiàng)集合:

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

3.2 FPE樹的數(shù)據(jù)結(jié)構(gòu)

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

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

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

3.3 基于FPE樹的挖掘算法

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

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 例子的帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集表

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

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

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

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

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

? 插入表5事務(wù)表TTFE第1行事務(wù)中的各頻繁編譯選項(xiàng).由于每次遞歸插入時(shí),根結(jié)點(diǎn)root沒有匹配的孩子結(jié)點(diǎn),故依次生成5個(gè)新結(jié)點(diǎn),建立FPE樹的第1個(gè)分支,如圖4所示.

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

? 依次插入表5第3行～第5行事務(wù)中的各編譯選項(xiàng),可輸出表2事務(wù)表TTE對應(yīng)的FPE樹,如圖2所示.

· 步驟4.基于步驟3得到的FPE樹,使用挖掘算法獲取如表4所示的帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集.

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 對事務(wù)表TTE進(jìn)行篩選和排序后獲取的頻繁編譯選項(xiàng)事務(wù)表TTFE

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

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

4 變異操作

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

4.1 變異操作相關(guān)定義

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

例如,個(gè)體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}.挖掘獲得的帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集如表4所示.設(shè)從SS(X)中隨機(jī)選取2個(gè)元素構(gòu)成的編譯選項(xiàng)編號集合為ScmpOptNm={3,13},從表4的頻繁編譯選項(xiàng)模式集中對應(yīng)的4行可分別投影出4個(gè)編譯選項(xiàng)編號集:{13,6,3},{13,6,1},{13,3,1},{1,3,6}.僅第1個(gè)和第3個(gè)集合包含ScmpOptNm={3,13},并且這兩個(gè)集合與ScmpOptNm的差集都被SU(X)包含,故fpMatch+({3,13})={{(13,30%),(6,82%),(3,60%)},{(13,30%),(3,60%),(1,60%)}}.

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

其中,fCOpt.cmpOptNm表示頻繁編譯選項(xiàng)fCOpt的編譯選項(xiàng)編號.

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

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

例如,個(gè)體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}.

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

4.2 增添操作

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

設(shè)個(gè)體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}.挖掘獲得的帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集見表4.假定表6第5步從SS(X)中隨機(jī)選取k=2個(gè)元素組成待變異的編譯選項(xiàng)編號集合為ScmpOptNm={3,13},根據(jù)定義13可得fCOptMatch+({3,13})={(6,82%),(1,60%)},其過程分析見定義13的例子說明.故表6第6步得到頻繁編譯選項(xiàng)集SfCOpt={(6,82%),(1,60%)}.由表6第10步知:

因而,分別以0.58和0.42概率選擇6號和1號編譯選項(xiàng).假設(shè)選中6號編譯選項(xiàng),則通過表6第13步將X下標(biāo)為6的碼值替換成1,得到了新個(gè)體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給出了按刪減操作的具體過程.

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

假定個(gè)體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}.挖掘獲得的帶能耗改進(jìn)標(biāo)注的頻繁編譯選項(xiàng)模式集如表4所示.設(shè)表7第6步從SS(X)中隨機(jī)選取k=2個(gè)元素構(gòu)成的編譯選項(xiàng)編號集合為ScmpOptNm={3,16},根據(jù)定義14可得fpMatch-({3,16})={{(16,30%)},{(3,40%)}},其過程分析見定義14下的例子說明.因而,表7第7步得到SfCOpt={{(16,30%)},{(3,40%)}}.由表7第11步可知,

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

5 案例研究

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

5.1 案例簡介

本文從BEEBS平臺[18]中選用涵蓋安全、網(wǎng)絡(luò)、通信、汽車和消費(fèi)這5個(gè)領(lǐng)域的8個(gè)案例,表8給出了這些案例的應(yīng)用領(lǐng)域和代碼量.

Table 8 Application domains and code size in the experimental cases表8 實(shí)驗(yàn)案例的應(yīng)用領(lǐng)域和代碼量

5.2 研究問題及其度量指標(biāo)

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

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

其中,

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

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

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

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

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

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

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

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

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

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

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

5.4 實(shí)驗(yàn)安裝

(1) 實(shí)驗(yàn)環(huán)境

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

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

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

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

5.5 實(shí)驗(yàn)結(jié)果及分析

下面具體給出問題1和問題2的實(shí)驗(yàn)結(jié)果及分析.

(1) 問題1(解質(zhì)量)的實(shí)驗(yàn)結(jié)果及分析

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

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個(gè)案例下-O0和-O3最優(yōu)等級以及GA-FP和Tree-EDA算法20次運(yùn)行最優(yōu)解對應(yīng)的能耗 (J)

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

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

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

從表12的統(tǒng)計(jì)量結(jié)果可知,8個(gè)案例下的IΔeng%指標(biāo)平均值為2.5%,最大IΔeng%指標(biāo)值可達(dá)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個(gè)案例下能耗改進(jìn)百分比(IΔeng%)的秩和檢驗(yàn)結(jié)果

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

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個(gè)案例下能耗改進(jìn)百分比(IΔeng%)的統(tǒng)計(jì)量結(jié)果

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

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

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

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

Table 13 Rank sum test results of the convergence speed metricIΔi% in 8 cases表13 在8個(gè)案例下收斂速度指標(biāo)IΔi%的秩和檢驗(yàn)結(jié)果

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

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

(3) 問題3(最優(yōu)解中編譯選項(xiàng)的正相關(guān)性)的結(jié)果及分析

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

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

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

Table 16 Statistical results of positive correlation metricIPC% in the optimal solutions under 8 cases表16 在8個(gè)案例下最優(yōu)解中編譯選項(xiàng)正相關(guān)性指標(biāo)IPC%的統(tǒng)計(jì)量結(jié)果

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

(4) 問題4(編譯選項(xiàng)的使用頻度)的結(jié)果及分析

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

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

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

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

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