嵌入式軟件編譯時能耗演化優(yōu)化算法①

姚萬慶, 倪友聰,2, 杜 欣, 葉 鵬, 肖如良

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

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

3(武漢紡織大學 數學與計算機學院, 武漢 430073)

能耗是嵌入式系統(tǒng)的關鍵質量屬性.據報道[1], 在嵌入式系統(tǒng)中高達80%的能耗直接與軟件執(zhí)行活動密切相關.因而在電量受限的執(zhí)行環(huán)境中, 降低嵌入式軟件的能耗具有更為重要的價值和意義[2].通過選擇一組最佳編譯選項[3]在給定的執(zhí)行平臺下對嵌入式軟件源代碼進行編譯, 可以獲取能耗更低的可執(zhí)行代碼.與源代碼重構[4]的能耗優(yōu)化技術相比, 基于編譯選項選擇的優(yōu)化不僅可以考慮硬件平臺特性, 而且還能在不修改源代碼的情況下保證功能語義一致性.因此, 編譯選項的選擇優(yōu)化為降低嵌入式軟件能耗提供了一種可行且有效的解決方案.

開源編譯器GCC[5]已廣泛用于嵌入式系統(tǒng)的開發(fā).針對GCC 編譯器的編譯選項選擇優(yōu)化問題可描述為:對于源代碼src 和執(zhí)行平臺platform, 搜索選項選擇方案X = ＜x1, x2,···, xi···, xl＞ (xi∈{0,1}分別表示不選用或選用第i 號選項, l 為可用的選項數), 使得目標函數f(Sftsrc,X)的值最大.f 表示按X 的選項選擇方案對src 進行編譯和鏈接后得到的可執(zhí)行代碼在platform上從開始至結束運行所耗的電能, 較不選用任何選項的方案在能耗上的改進百分比.GCC 編譯器雖已提供了若干標準優(yōu)化等級用于降低可執(zhí)行代碼的執(zhí)行時間和大小.但GCC 編譯器沒有提供專門針對能耗的優(yōu)化等級.最近研究工作已顯示了一些GCC 已有的優(yōu)化等級甚至導致嵌入式軟件能耗增大的情況[6,7].

近年來, 在能耗優(yōu)化這一方面, GCC 編譯選項的選擇問題已成為一個熱門的研究話題[3], 但仍面臨兩個公開挑戰(zhàn).一是GCC 編譯器提供了大量的編譯選項, 構成了龐大且離散的選擇空間.例如針對Hoste 等[8]提出58 個常用于能耗優(yōu)化的編譯選項, 其對應的選擇空間將高達258(大于1017).另一挑戰(zhàn)是編譯選項之間、編譯選項與能耗之間存在著潛在的復雜影響, 給提高搜索效率和優(yōu)化質量帶來相當大的困難.一個編譯選項的選用可能觸發(fā)或使其它編譯選項失效, 不同的編譯選項對能耗所起的效用也不盡相同.目前已涌現(xiàn)出統(tǒng)計、機器學習和演化算法等3 類基于GCC 編譯選項選擇的嵌入式軟件能耗優(yōu)化方法.

統(tǒng)計方法[2]使用部分析因實驗設計技術搜索編譯選項的選擇空間.正交數組被用于定義實驗組和控制組, 通過曼-惠特尼檢驗或克魯斯凱-沃利斯統(tǒng)計檢驗以觀測能耗是否發(fā)生顯著變化, 進而確定選用或不選用的選項.統(tǒng)計方法不僅難以識別任意多個編譯選項之間的影響, 而且受限于搜索空間也難以找到最優(yōu)的編譯選項組.機器學習方法[3,9], 通過構建預測模型以幫助GCC 編譯器或優(yōu)化算法搜索出最佳編譯選項組.構建預測模型分為收集訓練樣本和建立預測模型兩個階段.收集訓練樣本階段是一個迭代過程: 在每個迭代步中, 首先選擇一個嵌入式軟件并計算其特征的值; 接著基于一定策略在選項選擇空間中采樣獲得多個選項組;再利用一個選項組對所選擇的嵌入式軟件進行編譯,并通過執(zhí)行獲取能耗值.基于軟件的特征值、選項組和能耗值可構建出一個訓練樣本.利用收集的訓練樣本集, 建模階段則根據選用的機器學習算法[9]構建相應的預測模型.為了增加嵌入式軟件特征的有用性, 靜態(tài)[10]、動態(tài)[11]和混合[12]等方法被用于確定具體的特征.然而機器學習方法的訓練樣本往往針對特定編譯器版本和特定執(zhí)行平臺, 所構建的預測模型可移植性差.另外, 受制于選項的采樣空間, 機器學習方法也難以獲取高質量的優(yōu)化結果.

為了搜索更大的編譯選項選擇空間, 提高能耗優(yōu)化的質量, 一些演化優(yōu)化算法也被紛紛提出.基因加權的遺傳算法GWGA[13]將權值關聯(lián)到每個基因位, 用于刻畫相應的編譯選項對優(yōu)化目標的重要性, 并在優(yōu)化過程中進行更新.與一元分布評估算法UMDA 類似,GWGA 僅考慮最優(yōu)解中每個選項被選用的概率分布.GWGA 雖能一定程度地加快收斂速度, 但因沒有考慮各個選項之間存在相互影響關系, 容易導致陷入局部最優(yōu).Tree-EDA[14]運用概率樹模型捕獲任意兩個編譯選項之間的影響, 能得到比遺傳算法(GA)、GWGA和UMDA 更好的解質量.為了考慮多個編譯選項之間潛在的影響, 我們提出了基于頻繁模式挖掘的遺傳算法GA-FP[15].GA-FP 在演化過程中將相對于未優(yōu)化前有改進效果的個體信息(包括選用的選項編號和獲得的能耗改進)存入全局事務表, 并在每代種群演化結束后基于全局事務表挖掘頻繁選項模式集, 接著利用頻繁選項模式集中各個選項的能耗標注作為啟發(fā)式信息設計了“增添”和“刪減”兩種單點變異算子, 進而得到了比Tree-EDA 更好的解質量和收斂速度.

然而, GA-FP 算法還存在一些不足: (1)在演化過程中始終固定以優(yōu)化前能耗值作為參考點來判斷個體是否有改進, 并將有改進效果的個體信息存入全局事務表中, 容易導致事務表規(guī)模過大、存儲效率不高的問題.(2)基于全局事務表挖掘頻繁選項模式, 不僅存在挖掘時間長的問題, 而且挖掘出的頻繁選項模式也難以體現(xiàn)較好的時效性.此外, 挖掘出的頻繁選項模式僅給出單個頻繁選項的能耗標注, 而多個頻繁選項同時選用的次數和能耗標注也未予考慮.(3) “增添”和“刪減”變異操作雖能充分利用單個頻繁選項的能耗標注所體現(xiàn)的啟發(fā)式信息進行單點變異, 但仍沒有完全利用多個頻繁選項同時選用的次數和能耗標注等啟發(fā)式信息, 潛在地影響到解質量和收斂速度.針對上述問題, 文中提出一種嵌入式軟件編譯時能耗演化優(yōu)化算法GA-MFPM.GA-MFPM 借助逐代替換參考點和事務表的機制以降低事務表大小; 在此基礎上提出可獲取更多啟發(fā)式信息的繁編譯選項挖掘算法, 并采用逐代挖掘的策略有利于保持頻繁選項模式的時效性; 進一步設計最大頻繁模式匹配算法進行多點變異, 以提高優(yōu)化質量和收斂速度.通過與GA-FP 在5 個不同領域的8 個典型案例下實驗對比的結果表明: GA-MFPM 獲取了較GA-FP 更低的軟件能耗(平均降低2.4%, 最高降低 16.1%)和更快的收斂速度(平均加快57.6%, 最高加快97.5%).

1 GA-MFPM 算法總體流程

GA-MFPM 算法用于求解針對GCC 編譯器并用于嵌入式軟件能耗優(yōu)化的編譯選項選擇問題.其總體流程(算法1)與遺傳算法GA[16]類似.但不同之處在于, GA-MFPM 算法在演化過程中需構建和更新帶能耗改進標注的事務表TTE(the Transaction Table with Energe annotations of options)、挖掘和更新帶能耗改進標注頻繁模式集表TPSFOE+(the Table of Pattern Set of Frequent Options with Energy annotations), 并基于TPSFOE+進行多點變異.下面對它們作一簡要介紹.

(1) 帶能耗改進標注事務表的構建和更新

GA-MFPM 算法利用每代種群中優(yōu)勢個體的信息構造事務表, 并逐代更新事務表.

在構造事務表時, 首先按適應度值f(Sftsrc, X)(能耗改進百分比)從小到大對種群中各個體X 進行排序; 然后將適應度值等于或高于設定參考點值refVal 的個體作為優(yōu)勢個體, 并把這些個體的信息存入事務表.GAMFPM 算法借鑒了多數EDA[17]中優(yōu)勢個體在種群中的占比, 將refVal 設定為種群中各個體適應度值的中值.算法1 第4 行構建初始事務表.下面通過一個例子闡述事務表的構建方法.

例中, 初始種群各個體適應度的中值為8%, 即參考點值refVal=8%.初始種群中有5 個個體的適應度值等于或大于refVal, 現(xiàn)以其中的一個個體X, 其適應度的值f(Sftsrc, X)=10%為例說明一條事務的構建.從圖1所示的個體X 可知其選用8 個選項, 其編號為: {1, 2,3, 6, 12, 13, 15, 16}.依據這些選用的選項及其出現(xiàn)次數, 并將個體X 的適應度值作為能耗標注附加于每個選用的選項, 可分別構建8 個三元組(選用選項, 出現(xiàn)次數, 能耗標注), 如表1 中第2 行的事務.類似地, 利用其它4 個優(yōu)勢個體可分別構建4 條事務, 進而獲得表1 所示的初始事務表.

圖1 個體X

表1 帶能耗標注的選項事務表TTE 的例子

GA-MFPM 算法在每代演化中對事務表進行更新,如算法1 中第14 行和15 行.與對比算法GA-FP 在演化過程中始終固定以優(yōu)化前能耗值作為參考點不同,GA-MFPM 在演化過程中逐代替換參考點和事務表的機制有利于依據優(yōu)勢種群降低事務表大小.

(2)帶能耗改進標注頻繁模式集表的挖掘和更新

算法1 第5 行挖掘獲取初始頻繁選項模式集表TPSFOE+, 而算法1 第17 行至第18 行完成在每代對模式集表TPSFOE+的更新.TPSFOE+的具體挖掘方法將在第2 節(jié)予以詳細闡述.相比于GA-FP, GA-MFPM 在當前代事務表中挖掘出的頻繁選項模式可較好地保持頻繁選項模式的時效性.

(3)啟發(fā)式多點變異方法

算法1 的第11 行給出了基于模式集表TPSFOE+并通過設計的最大匹配算法對個體Xk進行多點變異.較GA-FP 的單點啟發(fā)式變異, GA-MFPM 的多點變異方法有利于提高收斂速度.最大頻繁模式匹配幫助的多點變異將在第3 節(jié)進行重點闡述.

2 挖掘帶能耗標注的頻繁選項模式集

下面先闡述帶能耗改進頻繁選項模式樹FPE的構建, 然后給出挖掘帶能耗改進標注頻繁選項模式相關的定義, 最后結合例子描述帶能耗標注頻繁選項模式的挖掘算法FPE-growth+.

2.1 帶能耗改進頻繁選項模式樹FPE 的構建

GA-MFPM 中FPE樹的數據結構及其構建過程與GA-FP 類似.依照表1 事務表并在最小支持度計數Cmin=3 下, 可構建出圖2 所示的FPE樹.為了便于理解本節(jié)內容, 下面對FPE樹的數據結構作一簡要介紹.

圖2 基于表1 例子事務表TTE 生成的FPE 樹

FPE樹由前綴項樹PT 和項頭表HL 所構成.PT 樹中各結點用選項編號opNm、出現(xiàn)次數count、能耗標注engAno、指向父結點的指針parNode 和指向下一個具有相同選項編號結點的指針nextNode 五個域進行描述.在圖2 橢圓形結點中, 用逗號分隔的是opNm、count 和engAno 的值, 而各結點的parNode 和nextNode 的值分別由實線和虛線弧隱含表示.項頭表HL 中各表項由頻繁選項編號opNm 和結點鏈的頭指針hdLnk 兩個屬性表示.hdLnk 可將相同選項通過結點鏈鏈接起來.圖2 中項頭表HL 最后一行的hdLnk 可將所有的2 號選項結點鏈接起來.

基于FPE樹, 可挖掘出所有帶能耗標注的頻繁選項模式.下一小節(jié)將給出相關的定義.

2.2 挖掘帶能耗改進標注頻繁選項模式相關的定義

定義1.前綴路徑.若node 為FPE樹中的一個非根結點, 則從root 根節(jié)點到node 結點之間的一條路徑稱為node 的前綴路徑.而node 結點稱為該前綴路徑的后綴結點.

前綴路徑可用一個結點序列進行表示.圖2 中灰色背景結點為后綴的前綴路徑path1可用式(1)的結點序列表示.

定義2.條件前綴路徑.設path 是后綴結點node的一條前綴路徑.若將path 上各結點的支持計數和能耗標注分別修改為node 的支持計數和能耗標注, 而獲得的路徑被稱為node 的條件前綴路徑.

條件前綴路徑用于表示前綴路徑上各結點對應選項與后綴結點對應選項共同出現(xiàn)的次數及對應的能耗標注.例如: path1為圖2 灰色背景結點node 的前綴路徑, 用node 的支持計數1 和能耗標注10%分別更新path1上各結點對應值, 可得到式(2)表示的node 的條件前綴路徑path2.它表示選項集{6,1,3,13,16}共同出現(xiàn)1 次且能耗標注為10%.

定義3.頻繁選項的條件前綴路徑集.若nodes 是FPE樹中所有i 號頻繁選項對應的結點集, 以nodes 中各結點為后綴所得條件前綴路徑的集合, 稱為選項i 的條件前綴路徑集, 記為paths|i.

FPE樹中i 號頻繁選項對應的全部結點可沿結點鏈的頭指針hdLnk 遍歷獲取.圖2 中2 號選項對應的結點集, 可通過頭表HL 最后一個表項的頭指針hdLnk 遍歷結點鏈得到.圖2 中2 號選項的條件前綴路徑集由path2, path3和path4所組成.式(2)～式(4)分別給出了path2～path4的表示.它們分別對應結點鏈中第1～3 個結點的條件前綴路徑.

定義4.條件事務表.以i 號頻繁選項的條件前綴路徑集paths|i 中各路徑為事務所構建的事務表, 稱為i 號頻繁選項的條件事務表, 記作TTFE|i.

按圖2 中2 號頻繁選項的條件前綴路徑集{path2,path3, path4}可構建表2 所示的條件事務表.

表2 圖2 中2 號頻繁選項的條件事務表

定義5.條件FPE樹.以i 號頻繁選項的條件事務表TTE|i 作為輸入所構建的FPE樹被稱為頻繁選項i 的條件FPE樹, 記為FPE|i.

按照表2 的2 號頻繁選項條件事務表并在最小支持計數Cmin=3 下, 可構建出圖3 所示的條件FPE樹.

圖3 FPE-growth+以圖2 中2 選項為后綴構建的條件FPE 樹

定義6.頻繁選項模式.若Sop為頻繁選項的編號集, count 和engAno 分別為Sop中各選項共同出現(xiàn)的次數及對應的能耗標注, 則頻繁選項模式fopE+可用三元組(Sop, count, engAno)進行描述.其中: Sop的大小被稱為fopE+的項數, 共同出現(xiàn)次數count 應不小于最小支持計數Cmin, 而engAno 由式(5)定義.式(5)中的函數Π(TE)表示從事務表TTFE的一條事務TE中投影出所選用選項的編號集, 而函數engImpr(TE)表示事務TE的能耗改進百分比值.當fopE+的項數為k 時, 用fopE+(k)進行表示.

對比算法GA-FP 的頻繁選項模式僅給出單個頻繁選項的能耗標注, 而GA-MFPM 則定義了多個頻繁選項同時選用的次數和能耗標注.因而, GA-MFPM 包括了新的挖掘算法.

2.3 帶能耗標注頻繁選項模式的挖掘算法FP Egrowth+

FPE-growth+算法基于FPE樹并采用模式項數漸增的遞歸挖掘方法, 其描述如算法2 所示.FPE-growth+算法包括遞歸出口處理和循環(huán)遞歸處理兩部分, 分別如算法2 第2 行至第8 行、第10 行至18 行.

FPE-growth+算法的遞歸出口條件是當FPE樹為單分支的樹.當滿足出口條件時, 首先依據單分支路徑上非根結點的序列, 枚舉獲得所有非空結點序列的集合SnodeSeq; 然后對SnodeSeq中每個元素nodeSeq 重復做以下步驟: 將nodeSeq 作為頭部連接到后綴結點序列postFixNodes 形成新序列newNodeSeq、計算序列newNodeSeq 中各結點支持計數和能耗標注的最小值,并用它們更新newNodeSeq 序列中各結點的支持計數和能耗標注的值、基于newNodeSeq 序列生成頻繁選項模式fopE+并基于項數將fopE+存入模式集表的對應位置.

循環(huán)遞歸部分是依次對FPE樹項頭表HL 的尾行至頭行進行遞歸處理, 如算法2 第10 行至17 行.遞歸調用前需要構建新后綴結點序列postFixNodes 并輸出頻繁選項模式、構建條件事務表、構建條件FPE樹.FPE-growth+算法在挖掘頻繁選項時, 采用與經典FP 挖掘算法[18]相同的遞歸過程挖掘獲取頻繁選項.僅在挖掘過程中增加了頻繁選項的能耗標注的計算, 如算法2第5 行和第13 行.而該步驟時間復雜性為O(1), 故FPE-growth+算法與經典FP 算法相同.

圖2 所示FPE樹是一棵多分支的樹, 在利用FPEgrowth+算法進行挖掘時, 由于不滿足遞歸出口條件, 需要進入循環(huán)遞歸處理過程.在循環(huán)中, 首先要以圖2 項頭表最后一行的2 號選項為后綴和空的后綴結點序列進行挖掘.下面以此場景為例對FPE-growth+算法進行解釋.

(1) 遞歸調用的處理

1) 構建新的后綴結點序列并輸出頻繁選項模式

沿圖2 頭表最后一行的結點鏈頭指針進行遍歷可得2 號頻繁選項的支持計數和能耗標注分別為3 和31%, 進而可構造一個新結點node(2, 3, 31%).將node 連接到當前后綴結點序列postFixNodes 時, 由于postFixNodes 為空序列, 故連接后得到的postFixNodes=＜(2, 3, 31%)＞.根據postFixNodes 生成的頻繁選項模式fopE+(1)=({2}, 3, 31%), 可將其輸出到模式集表TPSFOE+的1 頻繁選項集中.

2) 構建條件事務表

2 號頻繁選項為后綴的條件事務表TTE| 2 已在定義4 中的例子給出, 如表2 所示.

3) 構建條件FPE樹

根據條件事務表TTE|2 構建條件頻繁模式樹FPE|2 已在定義5 中的例子給出, 如圖3 所示.以FPE|2 和postFixNodes=＜(2, 3, 31%)＞遞歸調用FPE-growth+時,由于FPE|2 樹為一單路徑樹滿足遞歸出口條件, 進行遞歸出口處理.

(2) 遞歸出口中的處理

1) 枚舉獲得所有非空結點序列的集合SnodeSeq

由于圖3 的FPE|2 樹中僅含一個非根結點node(3,3, 31%), 故枚舉生成的SnodeSeq={＜(3, 3, 31%)＞}.

2) 對SnodeSeq中各元素nodeSeq 重復執(zhí)行以下3 個步驟:

① nodeSeq 與后綴結點序列連接獲取新序列newNodeSeq

SnodeSeq中僅包含的一個序列與postFixNodes=＜(2,3, 31%)＞連接后生成新序列newNodeSeq={＜(3, 3,31%)＞, (2, 3, 31%)}.

② 更新序列newNodeSeq 中各結點支持計數和能耗標注

由于newNodeSeq 各結點的支持計數和能耗標注相同, 故更前新后的newNodeSeq 序列相同.

③ 依據newNodeSeq 序列生成頻繁選項模式并輸出

根據序列newNodeSeq={＜(3, 3, 31%)＞, (2, 3,31%)}可生成頻繁選項模式fopE+(2)=({3, 2}, 3, 31%), 可將其輸出到模式集表TPSFOE+的2 頻繁選項集中.

以圖2 的FPE樹和空的后綴結點序列為參數, 調用FPE-growth+算法最終輸出表3 所示的模式集表TPSFOE+.

表3 例子帶能耗標注的頻繁選項模式集表TPSFOE+

3 最大頻繁選項模式匹配幫助的多點變異

不同于GA-FP 中的單點變異, GA-MFPM 采用最大頻繁選項模式匹配幫助的多點變異.多點變異的流程如算法3所示.其主要包括確定變異的位數和位置、最大頻繁選項模式匹配、修改變異位值等3 個步驟.下面以圖4 個體X2={1,1,0,0,0,0,0,0,0,0,0,1,1,0,1,1}和表3 的為例, 闡述最大頻繁選項模式匹配幫助的多點變異操作流程.

圖4 待變異的個體X2

(1)確定變異的位數和位置

確定變異的位數和位置如算法3 的第2 行至第4 行.為了能基于模式集表TPSFOE+提供的啟發(fā)式信息進行變異, 規(guī)定最多變異的位數不超過TPSFOE+中頻繁選項模式的最大項數.利用產生隨機數完成變異的位數和位置的確定.每個變異位置對應于一個選項編號, 進而得到一個選項編號集S0, 假設例中得到的S0={2, 1, 6}.

(2)最大頻繁選項模式匹配

最大頻繁選項模式匹配是指將給定的選項編號集S0與TPSFOE+表中各模式的選項編號集進行最大匹配.通過最大匹配可發(fā)現(xiàn)編號集S0中頻繁出現(xiàn)在優(yōu)勢個體中最長的編號集.

算法3 第5 行至第10 行描述了最大頻繁選項模式匹配的匹配過程:

① 首先基于頻繁選項模式所具有的向下閉包性質[18](k 頻繁選項集的任何子集都應是頻繁的), 在TPSFOE+表的1 頻繁選項模式集SFOPE+(1)中, 將各模式的1 個編號與S0中的編號進行匹配, 并將匹配的編號放入S1 中, 進而獲取S0中頻繁的選項編號, 例中獲取的S1={2,1,6}.

② 然后調用算法4 的最大頻繁模式匹配算法MFPM.MFPM 算法將輸入的選項編號集賦給Stemp后,從大小為|Stemp|的頻繁選項模式集SFOPE+(|Stemp|)開始對Stemp進行最大匹配, 若能匹配上則將匹配結果放入結果頻繁選項模式集Sfop中并退出匹配過程, 否則在SFOPE+(Stemp-1)中進行最大匹配; 直至Stemp為空結束匹配.例中首先在3 頻繁選項模式集上對Stemp={2, 1,6}進行第1 輪最大匹配, 沒有任何匹配的頻繁模式.因而在2 頻繁選項模式集上對Stemp={2,1,6}進行第2 輪最大匹配, 獲取了頻繁模式集Sfop={ ({6,1},4, 41%)}.

(3)修改變異位值

算法3 第7 行至第11 行負責完成個體中變異位值的修改.首先, 將個體X2賦給X2', 并以S0(存放隨機生成的各變異位置)中各元素值為下標, 將X2'對應位的值設為0.例中由S0={2, 1, 6}, 可知X2'的第2, 1, 6 位上的值均設為0.然后, 若基于最大匹配得到頻繁模式集S f o p 不空, 則按S f o p 中各元素的平均能耗標注(engAno/count), 依概率選擇其中一個頻繁模式fopE+,并以fopE+的選項編號集中各元素值為下標, 將X2'對應位的值設為1.

例中最大匹配獲取的Sfop={({6,1},4, 41%)}不為空, 因Sfop只有一個頻繁二項集, 則fopE+={{6,1},4,41%)}因而再將X2'第1 和第6 位上的值設定為1.最終X2'應如圖5 所示, 本例中編號2 和6 位上的值發(fā)生變異, 即2 號選項由選用變?yōu)椴贿x用, 而6 號選項由不選用變?yōu)檫x用.

圖5 變異后的個體X2'

4 案例研究

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

4.1 案例簡介

本文從最新的BEEBS 平臺[6]中選用了8 個案例,如表4 所示, BEEBS 是目前最大的用于嵌入式系統(tǒng)執(zhí)行時間和能耗優(yōu)化的開源基準平臺.綜合考慮以下3 個要素, 從BEEBS 所包含的84 個案例中選取了具有代表性的8 個案例.

表4 實驗案例的應用領域、源代碼的結構特性和操作特性

(1)源代碼的操作特性: 案例涵蓋盡可能影響運行時能耗的各種不同操作.如整型運算強度、浮點運算強度、分支頻度和內存訪問頻度等.

(2)應用領域: 案例覆蓋盡可能多的領域.如汽車、消費、網絡、安全和通訊等.

(3)源代碼的結構特性: 由于基準測試的編譯和大量的編譯選項的存在會極大地影響上述案例的編譯效率, 所以在基準測試源代碼中也會有一系列影響編譯過程的特性.其中包括: 循環(huán)、嵌套循環(huán)、不同的算術類型(8 位、16 位和32 位整型、浮點型等)、函數調用、字符串操作、位操作和數組訪問.表4 給出了選用的8 個案例的應用領域、源代碼的結構特性和操作特性.

4.2 研究問題及其度量指標

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

度量指標: 將GA-MFPM 和GA-FP 最優(yōu)解對應的能耗相對改進百分比I△eng%作為度量指標.在案例源代碼Sftsrc下, I△eng%的定義如式(6)所示, 其值越大越好.在式(6)中, X*GA-FP和 X*GA-MFPM 分別表示GAFP 和GA-MFPM 算法獲得的最優(yōu)解.f(Sftsrc, X*GA-MFPM)和f(Sftsrc, X*GA-FP)分別表示在案例源代碼Sftsrc下GA-FP 和GA-MFPM 算法最優(yōu)解相對于-O0 等級的能耗改進百分比.

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

度量指標: 為了公平比較兩種算法的收斂速度, 將GA-MFPM 相對于GA-FP 首達最優(yōu)時間的減少百分比I△t%作為度量指標.在案例源代碼Sftsrc下, I△t%的定義如式(7)所示, 其值越大越好.式(7)中MinTGA-FP(Sftsrc, X*) 和MinTGA-MFPM(Sftsrc, X*)分別表示在案例源代碼Sftsrc下GA-FP 和GA-MFPM 首達最優(yōu)解 X*所需要的時間.

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

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

4.4 實驗安裝

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

上位機的運行環(huán)境: Intel(R) Core(TM)i5-4590,3.30 GHz 處理器, 8 GB 內存及Ubuntu-16.04.1 操作系統(tǒng).

能耗評估系統(tǒng): 基于STM32F4 板自主研發(fā).

案例軟件優(yōu)化的運行環(huán)境: STM32F103 板.

編譯器和編譯選項: GCC4.9.2, 并選用與GA-FP[15]相同的58 個編譯選項.

(2)算法參數的設定

為了保持公平, 盡可能讓GA-MFPM 采用與GAFP 相同的參數設定, 如表5 所示.但兩個算法的最小支持計數設定有所不同.這是因為GA-MFPM 采用逐代替換事務表的策略.在事務表中, 若每個選項按隨機方式選用, 則每個選項出現(xiàn)的次數應為種群大小N 的一半.而GA-MFPM 期望跟蹤各代種群中優(yōu)勢個體選用選項的特點, 故將Cmin設定為0.6×N.而不是GAFP 中設定的0.1 倍全局事務表大小.

表5 GA-FP 和GA-MFPM 的參數設定

4.5 實驗結果及分析

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

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

表6 給出了GA-MFPM 在這8 個案例下對比GAFP 的能耗改進百分比(I△eng%)的秩和檢驗結果.從表6中第2 列可知p-value 值都遠比置信水平0.05 要小, 這表明GA-MFPM 的I△eng%指標在這8 個案例下的統(tǒng)計意義顯著比GA-FP 的好.從表6 中第3 列可看出在這8 個案例下, GA-MFPM 算法的effect size 值以很明顯的優(yōu)勢優(yōu)于GA-FP.而從圖6 所示的統(tǒng)計盒圖也能直觀反映出一致結論.從表7 的統(tǒng)計量結果能知道: 8 個案例下的I△eng%指標平均值為2.4%, 最大I△eng%指標值可達16.1%.

表6 GA-MFPM 較GA-FP 在8 個案例下能耗改進百分比(I△eng%)的秩和檢驗結果

圖6 GA-MFPM 較GA-FP 在8 個案例下能耗改進百分比(I△eng%)的統(tǒng)計盒圖

表7 GA-MFPM 較GA-FP 在8 個案例下能耗改進百分比(I△eng%)的統(tǒng)計量結果

GA-MFPM 較GA-FP 獲取更好解質量的原因是:GA-MFPM 在逐代挖掘的頻繁模式中保存了多個頻繁選項, 同時標注選用次數和能耗, 可獲取更完整、時效性更好的啟發(fā)式信息, 有利于幫助提高解質量.

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

表8 給出了在8 個案例下收斂速度指標I△t%(相對于GA-FP, GA-MFPM 首達最優(yōu)解耗時的相對減少百分比)的秩和檢驗結果.表8 中第2 列p-value 值都遠比置信水平0.05 要小, 表明GA-MFPM 的I△t%指標在8 個案例下的統(tǒng)計意義顯著比GA-FP 的好.表8中GA-MFPM 首達最優(yōu)解較GA-FP 在大概率上需要更少的時間.表9 可知: 8 個案例下的I△t%指標平均值為57.6%, 最大達到了97.5%.圖7 所示的統(tǒng)計盒圖也能直觀反映出一致結論.

表8 在8 個案例下收斂速度指標I△t% (GA-MFPM 相對于GA-FP 首達最優(yōu)解耗時的減少百分比)秩和檢驗結果

表9 在8 個案例下收斂速度指標I△t% (GA-MFPM 相對于GA-FP 首達最優(yōu)解耗時的減少百分比)的統(tǒng)計量結果

圖7 在8 個案例下收斂速度指標I△t% (GA-MFPM 相對于GA-FP 首達最優(yōu)解耗時的減少百分比)的統(tǒng)計盒圖

GA-MFPM 較GA-FP 獲取更好的收斂速度的原因在于: GA-MFPM 逐代替換參考點的機制可有效降低事務表的大小、借助最大頻繁模式匹配幫助的多點變異可提高變異效率, 進而有利于幫助提高收斂速度.

5 結語

本文將頻繁模式挖掘和最大頻繁模式匹配幫助的多點變異引入到傳統(tǒng)遺傳算法, 提出了一種用于GCC編譯時能耗演化優(yōu)化算法GA-MFPM.GA-MFPM 采用逐代替換判定是否有能耗改進的參考點、逐代構建事務表和逐代挖掘的策略; 在此基礎上提出可獲取更多啟發(fā)式信息的頻繁編譯選項挖掘算法; 進一步設計了最大頻繁模式匹配幫助的多點變異方法.通過案例研究實證了GA-MFPM 的解質量和收斂速度在統(tǒng)計意義上顯著優(yōu)于已有的GA-FP 算法.未來我們將引入代理模型解決GA-MFPM 算法中目標值計算耗時長的問題.