劉 慧，趙榮彩，王 琦

(1.解放軍信息工程大學數(shù)學工程與先進計算國家重點實驗室，河南 鄭州 450001;2.河南師范大學計算機與信息工程學院，河南 新鄉(xiāng) 453007)

1 引言

計算機體系結(jié)構的不斷發(fā)展使得應用程序越來越依賴于程序性能優(yōu)化技術，以獲得更高的運行時性能，優(yōu)化種類越來越多，優(yōu)化技術日益復雜。編譯器開發(fā)者所面對的各種程序優(yōu)化技術常常都是非常復雜的，甚至是NP問題，如代碼生成階段的指令調(diào)度問題等。這樣的問題當前沒有一個普遍適用的方法可以得到最優(yōu)解，編譯器開發(fā)者通常借助啟發(fā)式方法得到問題的近似最優(yōu)解。另一方面，編譯器所面向的硬件結(jié)構是非常復雜，且迅速發(fā)展的，當硬件結(jié)構發(fā)生改變時，優(yōu)化技術也需要進行相應調(diào)整。這些都對程序優(yōu)化技術提出了多方面的要求，必須有針對性地對目標程序及應用平臺進行優(yōu)化選擇，才能更好地提升程序性能。

程序性能優(yōu)化涉及對程序的各種變換，一些行之有效的程序優(yōu)化除了必須合法，即保持程序語義外，還需要使用相應的優(yōu)化參數(shù)。優(yōu)化參數(shù)的恰當選擇能夠顯著縮短程序運行時間，而使用不恰當?shù)膬?yōu)化參數(shù)會使程序性能改善幅度很小，甚至比未使用該優(yōu)化方法之前還低。因此，優(yōu)化參數(shù)選擇是程序性能優(yōu)化必須解決的核心問題之一。當前編譯器設計者通常利用其經(jīng)驗進行勞動密集型源代碼修改，通過測試多個優(yōu)化參數(shù)選項，從而為特定應用選擇較高性能的優(yōu)化參數(shù)。目前為止，研究人員提出了兩種主要方法來解決程序優(yōu)化參數(shù)的選擇問題：迭代編譯(Iterative Compilation)[1,2]和基于機器學習的迭代編譯方法[3 - 5]。

迭代編譯通過挖掘各種程序優(yōu)化參數(shù)，生成一系列程序版本，在目標平臺上執(zhí)行程序并選擇具有最大性能提升的程序版本，性能優(yōu)化效果顯著優(yōu)于靜態(tài)編譯。然而，迭代編譯過程中變換參數(shù)及變換集合的選取、變換的實施順序和實施次數(shù)等，均導致巨大的優(yōu)化搜索空間。同時，迭代編譯是一種機械式搜索，缺少對以前所獲得經(jīng)驗的使用，為了減少搜索的盲目性，有時還需要人為干預。當數(shù)據(jù)規(guī)模變大時，開發(fā)者任務繁重。

近年來，人們提出將人工智能的方法應用在迭代編譯上，提出基于機器學習的編譯優(yōu)化方法[3,7,8]。Milepost是一種基于機器學習的編譯器，能自動調(diào)整優(yōu)化參數(shù)，改進不同架構上特定程序的執(zhí)行時間和代碼大小等[8,9]。Leather等[10]提出一種學習靜態(tài)代碼特征的方法，用于優(yōu)化過程中的編譯器啟發(fā)。Ding等[11]提出一種變量輸入分析法，模型自動確定當不同的優(yōu)化策略適合不同輸入時使用何種算法進行優(yōu)化。Martins等[12]通過遺傳算法指導的聚類設計空間探索技術，提出一種應用相關優(yōu)化選擇方法。Kulkarni等[13]通過在函數(shù)級粒度窮盡探索優(yōu)化空間，用搜索樹算法解決優(yōu)化選擇問題。Ballal和Kumar等[14,15]提出基于遺傳編程的編譯優(yōu)化，利用多核處理器上的并行遺傳編程進行編譯優(yōu)化選擇。但是，現(xiàn)有研究存在以下問題：(1)多數(shù)研究使用遺傳算法對程序變換優(yōu)化參數(shù)空間進行搜索，但使用遺傳算法進行搜索時，搜索時間過長，效率較低。速度快、性能好的搜索算法對于提升優(yōu)化參數(shù)選擇性能具有重要的意義。(2)在對程序特征進行抽取時，多采用靜態(tài)特征表示方法。然而，研究表明動態(tài)特征表示方法通常比靜態(tài)方法能實現(xiàn)更好的預測性能，但使用動態(tài)信息需要實際運行程序至少一次，很多情況下還需要多次運行，以收集這些特征。如何有效結(jié)合靜態(tài)和動態(tài)特征對程序進行表示，是需要深入研究的問題。(3)參數(shù)化代碼變換問題中，程序特征與優(yōu)化參數(shù)之間、優(yōu)化參數(shù)與優(yōu)化參數(shù)之間存在復雜的依賴關系。如何把這些復雜關系通過有效的機器學習模型進行表示，是基于機器學習的編譯優(yōu)化參數(shù)選擇需要進一步研究的重點問題。

針對以上存在的問題，本文提出一種選擇編譯器優(yōu)化參數(shù)以最大化目標程序性能的方法：基于監(jiān)督學習的程序變換優(yōu)化參數(shù)選擇方法SLOPS(Supervised Learning based Optimization Parameters Selection)，該方法通過使用監(jiān)督學習模型表示編譯優(yōu)化參數(shù)選擇問題中復雜的依賴關系，在監(jiān)督學習框架下實施函數(shù)級優(yōu)化參數(shù)選擇決策。本文的主要貢獻如下：

(1)提出一種改進的粒子群PSO(Particle Swarm Optimization)算法進行程序變換優(yōu)化參數(shù)的優(yōu)化空間搜索，解決優(yōu)化參數(shù)的有約束多目標優(yōu)化問題，在兩種平臺上相對于編譯器默認標準優(yōu)化級別分別實現(xiàn)了1.45×和1.42×平均加速。

(2)提出使用動靜混合的特征表示方法表示程序，通過主成分分析PCA(Principal Component Analysis)將高維特征數(shù)據(jù)降維，利用線性變換將高維空間中的特征數(shù)據(jù)映射到低維空間，在最小均方誤差意義下獲取對原始特征數(shù)據(jù)的表示。

(3)基于程序特征和最佳優(yōu)化參數(shù)構成SLOPS模型樣本數(shù)據(jù)，分別采用k近鄰法和softmax回歸建立統(tǒng)計模型、實施優(yōu)化參數(shù)選擇。給定新的目標程序，抽取函數(shù)特征作為SLOPS模型輸入，通過模型中存儲的知識預測最佳優(yōu)化參數(shù)，k近鄰法和softmax回歸模型在兩種平臺上相對于編譯器默認標準優(yōu)化分別實現(xiàn)1.28×和1.36×及1.25×和1.34×平均加速。

本文的結(jié)構安排如下：第2節(jié)介紹程序變換優(yōu)化參數(shù)選擇模型；第3節(jié)介紹一種改進的粒子群算法，用于優(yōu)化參數(shù)的優(yōu)化空間搜索；第4節(jié)介紹程序特征表示方法；第5節(jié)介紹基于監(jiān)督學習的優(yōu)化參數(shù)預測方法；第6節(jié)是實驗和分析；最后總結(jié)全文。

2 程序變換優(yōu)化參數(shù)選擇模型

2.1 優(yōu)化參數(shù)定義

為更好地描述程序變換優(yōu)化參數(shù)選擇問題，首先對該問題進行定義。

定義1變換(Transformation)是一個部分函數(shù)f，其輸入是代碼C，輸出是等價語義的代碼，即f對代碼C中的一部分進行重寫變換生成語義等價的代碼。

定義2優(yōu)化參數(shù)(Optimization Parameters)是參數(shù)化變換中所包含的性能關鍵參數(shù)，如程序優(yōu)化變換循環(huán)展開、循環(huán)分塊、數(shù)組填充對應的變換參數(shù)分別是展開因子、分塊因子和數(shù)組填充因子。

假設程序使用s個性能關鍵的參數(shù){q1,q2,…,qs}，則將每個參數(shù)稱為一個優(yōu)化參數(shù)qi。s個優(yōu)化參數(shù)的有序組合稱為一個優(yōu)化參數(shù)向量，記為q。優(yōu)化參數(shù)選擇問題表示為選擇合適的優(yōu)化參數(shù)向量q，使目標程序執(zhí)行時間最短。令T(q)是程序采用優(yōu)化參數(shù)向量q后的執(zhí)行時間，那么優(yōu)化參數(shù)搜索問題就轉(zhuǎn)化為組合優(yōu)化問題：選擇向量q={q1,q2,…,qs}，使得執(zhí)行時間T(q)最小，即有約束的多目標優(yōu)化問題，定義為：

minT(q)=(t1(q),t2(q),…,tk(q))

s.t.gi(q)≤0,i=1,2,…,p

hj(q)=0,j=1,2,…,m

q={q1,q2,…,qs},q∈Rs

(1)

依據(jù)對程序變換優(yōu)化參數(shù)的認識，最行之有效的參數(shù)化變換為循環(huán)展開(Loop Unrolling)、數(shù)組填充(Array Padding)、循環(huán)分塊(Loop Tiling)。下面首先對其進行介紹。

(1)循環(huán)展開因子。循環(huán)展開通常用來降低循環(huán)開銷，為具有多個功能單元的處理器提供指令級并行，也有利于指令流水線的調(diào)度和更好地實現(xiàn)數(shù)據(jù)預取技術。然而，不恰當?shù)恼归_會給程序性能帶來負面收益，過度循環(huán)展開會導致寄存器甚至指令緩存區(qū)溢出，展開因子太小會引起寄存器資源浪費，因此循環(huán)展開的關鍵問題是確定展開因子。關于展開因子的約束為：

(2)

其中，ci表示循環(huán)體中對應循環(huán)i所占的寄存器數(shù),Ui為循環(huán)展開因子，NR為處理器中的寄存器數(shù)。

(2)數(shù)組填充因子。數(shù)組填充一般是針對多維數(shù)組進行優(yōu)化的，通過將多維數(shù)組的最低維長度填充為向量寄存器的倍數(shù)，使得每次訪問時都是地址對齊的，避免多維數(shù)組訪問中出現(xiàn)的地址不對齊現(xiàn)象。數(shù)組填充需要額外空間開銷，過大的數(shù)組填充因子會使TLB(Translation Lookaside Buffer)失效數(shù)增加。本文限定數(shù)組填充因子的范圍為0～64。

(3)循環(huán)分塊因子。循環(huán)分塊技術利用仿射變換改變循環(huán)迭代訪存順序，充分利用分塊數(shù)據(jù)重用，減少數(shù)據(jù)移動和Cache 失效，實現(xiàn)分塊之間和塊內(nèi)數(shù)據(jù)并行。分塊因子的選擇決定了分塊代碼的性能，分塊因子約束如公式(3)所示。

(3)

其中，Ti表示分塊因子;Sk表示數(shù)組元素大小;M表示內(nèi)存容量;lk表示數(shù)組維數(shù);循環(huán)嵌套Li(i=1,2,…,n)的分塊因子為bi，當Li的分塊因子bi≠0時，數(shù)組第j維的分塊因子Ti=bi，否則，該維不分塊，Ti=ti，ti表示數(shù)組第j維的元素個數(shù);x(k,j)=1表示數(shù)組第j維分塊，x(k,j)=0表示第j維不分塊。

2.2 程序變換優(yōu)化參數(shù)選擇模型框架

基于監(jiān)督學習的程序變換優(yōu)化參數(shù)選擇模型SLOPS的主要目標是確定要應用于目標程序的最佳編譯優(yōu)化參數(shù)，SLOPS模型將程序特征與編譯器優(yōu)化參數(shù)相關聯(lián)，以最大化程序性能。模型框架如圖1所示，包括兩個主要階段：模型訓練階段和模型使用階段。模型訓練階段將基準程序分為兩部分，一部分作為訓練集P1,P2,…，PN-1，一部分作為測試集PN。采用程序靜態(tài)和動態(tài)特征相結(jié)合的方法抽取程序特征，并通過主成分分析技術對特征維數(shù)進行降維。通過優(yōu)化參數(shù)搜索算法，為訓練集中的程序搜索近似最佳的優(yōu)化參數(shù)組合。采用監(jiān)督學習方法建立統(tǒng)計模型進行模型訓練，模型輸入為函數(shù)特征，模型輸出為函數(shù)的近似最佳優(yōu)化參數(shù)。訓練集中的函數(shù)特征，近似最佳優(yōu)化參數(shù)構成SLOPS模型的訓練樣本。采用留一交叉驗證進行模型訓練，以提升模型精度；模型使用階段抽取新程序的函數(shù)特征，然后基于存儲在SLOPS模型中的知識推斷新應用程序中函數(shù)的最佳編譯優(yōu)化參數(shù)。

Figure 1 Framework of the compiler optimization parameter selection model圖1 編譯器優(yōu)化參數(shù)選擇模型框架

3 優(yōu)化參數(shù)的優(yōu)化空間搜索算法

3.1 標準PSO算法

粒子群算法PSO是一種多點搜索算法，基本思想為：存在D維搜索空間，若干沒有重量和體積的粒子在搜索空間中隨機分布，每個粒子都存在兩個值：位置和速度向量。粒子的位置值表示一個可能解，粒子在解空間里以速度向量的方向移動，每進行一次迭代，粒子都將飛行一段距離，產(chǎn)生一個新的位置，粒子通過適應度函數(shù)判斷個體最優(yōu)位置和群體最優(yōu)位置，并依此決定新的速度向量，繼續(xù)調(diào)整位置，直到最好[16]。標準PSO學習公式為：

vid(k+1)=vid(k)+c1r1(Pid(k)-xid(k))+

c2r2(Pgd(k)-xid(k))

(4)

xid(k+1)=vid(k+1)+xid(k)

(5)

其中，vid=(vi1,vi2,…,viD)，1≤i≤N表示第i個粒子的速度信息；xid=(xi1,xi2,…,xiD)，1≤i≤N表示第i個粒子的位置信息。Pid表示粒子的個體最優(yōu)位置，Pgd表示種群獲得的全局最優(yōu)位置。k為迭代次數(shù)；c1、c2為決定速度變化向量值的學習因子；r1∈[0,1]、r2∈[0,1]表示兩個隨機系數(shù)，是為了避免粒子在搜索過程中飛出搜索空間而增加的。標準PSO算法只能求解無約束的單目標優(yōu)化問題，對于有約束的多目標優(yōu)化問題，需要考慮約束處理方法以及Pareto最優(yōu)解形成的邊界，即Pareto前端。

3.2 自適應多目標粒子群算法

對帶有約束條件的問題進行優(yōu)化時，根據(jù)約束條件定義粒子約束違反程度，將粒子分為可行粒子FP(Feasible Particles)和不可行粒子IFP(InFeasible Particles)。由標準PSO算法可知,種群中某粒子飛入可行域后，當最優(yōu)解存在于可行域邊界時，約束邊界附近的IFP由于可行域內(nèi)全局最優(yōu)解的吸引將偏離邊界，導致約束邊界周圍重要信息的遺漏。因此，本文提出一種通過自適應學習減緩約束附近IFP飛行速度的方法：自適應多目標粒子群算法AMPSO(Adaptive Multi-objective PSO)。

在AMPSO算法中，對于FP按照標準PSO算法更新vid和xid，對于種群進化過程中產(chǎn)生的IFP，采用歸一化處理方法得到其約束違反程度：

(6)

其中，x表示s維優(yōu)化選擇向量，x=(x1,x2,…,xs)，使用Cnor(x)影響IFP學習因子修正vid和xid，得到自適應進化學習公式：

vid(k+1)=vid(k)+c1r1(Pid(k)-xid(k))+

c2Cnor(x)r2(Pgd(k)-xid(k))

(7)

xid(k+1)=vid(k+1)+xid(k)

(8)

依據(jù)自適應進化學習公式(7)和公式(8)，IFP根據(jù)Cnor(x)自適應地進行進化學習：針對約束違反程度較大的粒子，c2Cnor(x)≈c2，粒子保持對全局最優(yōu)解的跟隨能力，可偏離現(xiàn)有位置進行未知可行域搜索。對于約束邊界周圍的粒子具有Cnor(x)≈0，c2Cnor(x) 為極小值，全局最優(yōu)解對該粒子的吸引力減弱，完成約束邊界附近有利信息的搜索。

與標準PSO算法相比，采用AMPSO算法不僅可以提高約束邊界搜索能力，而且能夠充分利用具有不同Cnor(x)的粒子完成全局最優(yōu)搜索，從而保證粒子能快速收斂到真實的Pareto前端。

使用PSO算法尋優(yōu)時，使用擁擠距離CD(Crowding Distance)可以引導粒子從密集的地方向?qū)捤傻牡胤揭苿?，從而提高Pareto解的多樣性，保持算法搜索協(xié)調(diào)性。本文提出一種新的CD計算方法，計算公式為：

(9)

(10)

(11)

基于AMPSO的優(yōu)化參數(shù)選擇算法如算法1所示。

算法1基于自適應進化多目標粒子群算法的優(yōu)化參數(shù)選擇算法

輸入：測試程序P，優(yōu)化參數(shù)個數(shù)n，進化參數(shù)(w,c1,c2)，種群規(guī)模N，Pareto非支配解規(guī)模S，最大迭代次數(shù)M。

輸出：最佳優(yōu)化參數(shù)向量q*及其對應的程序運行時間T(q*)。

Step1對于每個優(yōu)化參數(shù)定義其取值范圍Ω，在給定搜索域內(nèi)初始化種群位置xid和速度vid。

Step2計算種群中各粒子的目標函數(shù)值即程序執(zhí)行時間ti(x)及約束違反程度Cnor(x)。

Step4若當前Pareto非支配解集為空，則選取Cnor(x)最小的粒子作為全局最優(yōu)位置。否則，從Pareto非支配解集中選擇擁擠距離大的解作為全局最優(yōu)位置。

Step5更新各粒子個體最優(yōu)位置：若兩個粒子中一個可行一個不可行，則選擇可行粒子為優(yōu)。若兩個粒子都不可行，則選擇Cnor(x)小的粒子為優(yōu)。若兩個粒子都可行，則基于Pareto支配關系選擇非支配粒子為優(yōu)。

Step6按照AMPSO方式更新所有粒子的位置xid和速度vid。

Step7判斷是否達到最大迭代次數(shù)M,若未達到則返回Step 2;否則，結(jié)束循環(huán)并輸出最佳優(yōu)化參數(shù)向量q*及其對應的最短程序運行時間T(q*)。

如果程序優(yōu)化參數(shù)選擇問題的目標函數(shù)個數(shù)為n，種群規(guī)模為N，Pareto非支配解規(guī)模為L，則算法總體時間復雜度為Ο(n(N+L)2)，即整個算法的計算量主要集中在Pareto非支配解的構造。因此，本文所提出的AMPSO方法不增加算法的整體計算復雜度。

4 程序特征表示

程序特征表示技術可分為兩類：靜態(tài)特征表示和動態(tài)特征表示。使用靜態(tài)特征表示不需要實際運行程序，可以在編譯過程中或語法分析過程中獲取，如指令混合、循環(huán)嵌套深度等。使用動態(tài)信息如性能計數(shù)器表征程序，可以收集運行時的程序多重特征，如Cache行為、停頓周期數(shù)等。采用動態(tài)特征通常比靜態(tài)能實現(xiàn)更好的程序表示。然而，使用動態(tài)信息需要實際運行程序至少一次，很多情況下還需要多次運行程序，以收集這些特征。SLOPS模型使用動靜結(jié)合的特征表示方法DSFC(Dynamic Static Features Combination)，為SLOPS提供更細粒度的輸入。通過主成分分析PCA技術選擇最主要的靜態(tài)和動態(tài)特征進行模型構建。靜態(tài)和動態(tài)特征列表如表1和表2所示。實驗分析表明，由于程序特征值的冗余和協(xié)方差，程序特征可降至5維向量，此時仍能保持99%的數(shù)據(jù)差異性。

Table 1 List of static features表1 靜態(tài)特征列表

5 基于監(jiān)督學習的程序分類方法

5.1 kNN

k近鄰法kNN(k-Nearest Neighbor)是一種常用的監(jiān)督學習方法，以其實現(xiàn)的簡單性及較高的分類準確性在許多領域得到廣泛應用。kNN算法基本思想為：給定測試樣本時，基于某種距離度量找

Table 2 List of dynamic features表2 動態(tài)特征列表

出訓練集中與其最靠近的k個訓練樣本，然后基于這k個鄰居的信息進行預測。通常，在分類問題中可使用“投票法”，即選擇這k個訓練樣本中出現(xiàn)最多的類別標記作為預測結(jié)果?；趉NN的程序分類算法如算法2所示。

算法2基于kNN的程序分類算法

輸入：訓練數(shù)據(jù)集C={(f1,t1),(f2,t2),…,(fn,tn)}，其中fi={p1,p2,…,pl}表示降維后的程序特征向量，ti∈{q1,q2,…,qs}表示相應特征值對應的優(yōu)化參數(shù)的類別。

輸出：新程序f(f表示程序的特征向量)所屬的優(yōu)化參數(shù)類t。

Step1計算新程序f與訓練集中每個樣本fi的距離，將距離從小到大排序，找到與f最近的前k個鄰居 ，距離公式采用歐氏距離(Euclidean Distance)：

(12)

涵蓋這k個點的f的鄰域記為Nk(f)。

Step2在最近鄰集Nk(f)中根據(jù)分類決策決定f的類別t：

i=1,2,…,n;j=1,2,…,s

(13)

其中，sign(ti=qj)為示性函數(shù)，如果ti=qj則值為1，否則為0。表示將最近鄰集中出現(xiàn)最多的標簽指派給t，作為新程序f的優(yōu)化參數(shù)類t。

基于kNN的程序分類算法訓練時間開銷為0，通過線性掃描訓練樣本，對新樣本程序進行優(yōu)化參數(shù)選擇的分類，因此適用于訓練樣本個數(shù)較小的情況。

5.2 softmax回歸

softmax回歸模型是logistic回歸模型在多分類問題上的推廣,softmax回歸可以將多維數(shù)據(jù)分為多個類別，在給出分類結(jié)果的同時給出結(jié)果的概率，因此非常適合程序優(yōu)化參數(shù)選擇的分類問題。

設softmax回歸模型樣本數(shù)為n，來自k個類，則由這些樣本組成的訓練集為{(x(1),y(1)),(x(2),y(2)),…,(x(m),y(m))}，x(i)∈Rn表示程序特征值，標簽y(i)∈{1,2,…,k}表示具有相應特征值的最佳優(yōu)化參數(shù)對應的類別。給定新的程序輸入x，用假設函數(shù)針對每一個類別j估算出概率值p(y=j|x)，出現(xiàn)概率最大的類別即為輸出值。假設函數(shù)公式為：

(14)

(15)

softmax回歸模型的代價函數(shù)為：

(16)

對于J(θ)的最小化問題，目前沒有閉式解法，本文使用梯度下降迭代優(yōu)化算法，求導得到梯度公式：

p(y(i)=j|x(i);θ))]

(17)

將上述偏導數(shù)代入梯度下降算法中，最小化J(θ)，在每一次迭代中，進行如下更新，可獲得最小化J(θ)：

θj=θj-α▽θjJ(θ)，j=1,2,…,k

(18)

(19)

對于任意λ>0，J(θ)變?yōu)閲栏裢购瘮?shù)，得到唯一解。此時Hessian矩陣變?yōu)榭赡婢仃?，采用梯度下降法可保證收斂到全局最優(yōu)解，對J(θ)求導得：

p(y(i)=j|x(i);θ]+λθj

(20)

通過最小化J(θ)，得到softmax回歸模型并實現(xiàn)新程序優(yōu)化參數(shù)選擇的分類。

6 實驗分析

6.1 實驗環(huán)境

我們在兩種平臺上進行SLOPS模型的訓練和評估，模型輸入為程序熱點函數(shù)特征，輸出為最佳優(yōu)化參數(shù)。采用SPEC CPU2006測試集中的2 000個循環(huán)進行模型訓練，使用留一交叉驗證方法提升模型泛化能力。對抽取的循環(huán)采用添加時間戳的方式記錄執(zhí)行時間，為減少噪聲影響，每個樣本運行10次，取執(zhí)行時間平均值。采用訓練后的模型為NPB測試集和表3所示大型計算程序的熱點函數(shù)預測最佳優(yōu)化參數(shù)，驗證模型性能。

平臺I實驗編譯環(huán)境為Linux操作系統(tǒng)，版本為Readhat Enterprise AS 5.0，實驗平臺為國產(chǎn)處理器申威26010，CPU為主頻2.5 GHz，L1 數(shù)據(jù) Cache 為 32 KB，L2 Cache 為 256 KB。

平臺II編譯環(huán)境為Linux操作系統(tǒng)，版本為Readhat Enterprise AS 5.0，實驗平臺為Intel Xeon E5520 處理器，CPU 主頻為2.26 GHz，L1 數(shù)據(jù)Cache為32 KB，L2 Cache 為1 MB。

訓練集：SPEC CPU2006基準程序測試集是由標準性能評價組織開發(fā)的用于評測通用型CPU性能的基準程序測試集，輸入規(guī)模由小到大分為test、train和reference規(guī)模，本文采用reference規(guī)模進行測試。

測試集：NPB測試集是由NASA開發(fā)的程序集，已被廣泛應用于并行計算機測試和比較中。輸入規(guī)?？煞譃镾、W、A、B、C和D共6個等級，本文選擇B規(guī)模進行測試。此外，采用SLOPS模型為如表3所示大型科學計算程序進行優(yōu)化參數(shù)預測。

Table 3 Large scale scientific calculation programs表3 大型科學計算程序

6.2 實驗結(jié)果分析

6.2.1 遺傳算法與AMPSO性能比較

我們通過對比遺傳算法GA(Genetic Algorithm)和AMPSO方法，分析本文提出的AMPSO方法的有效性。對測試集的熱點函數(shù)使用GA進行優(yōu)化參數(shù)搜索的過程是從優(yōu)化空間中選擇最優(yōu)解的過程，為GA創(chuàng)建一組染色體(稱為初始種群)，每個染色體對應一個優(yōu)化參數(shù)向量，染色體中的每個基因?qū)粋€優(yōu)化參數(shù)。采用GA和AMPSO進行程序優(yōu)化參數(shù)搜索時，GA控制參數(shù)設置為：群體規(guī)模大小40，交叉概率0.6，變異概率0.3，最大遺傳代數(shù)50；AMPSO參數(shù)設置為：群體規(guī)模大小20，最大進化代數(shù)30。此時，GA的最優(yōu)解出現(xiàn)在第45代，AMPSO最優(yōu)解出現(xiàn)在第16代。GA和AMPSO的性能比較如圖2所示。

Figure 2 Best fitness comparison between GA and AMPSO圖2 GA與AMPSO最佳適應度比較

實驗結(jié)果表明，雖然GA和AMPSO有共同之處：兩者都開始于隨機初始化種群，使用評價函數(shù)衡量優(yōu)化參數(shù)優(yōu)劣，并根據(jù)由評價函數(shù)得到的適應度值進行一定程度的隨機搜索。但是，AMPSO算法的搜索性能好于GA的，原因在于：(1) AMPSO算法沒有交叉和變異等遺傳操作。AMPSO利用個體在解空間中的速度和位置信息進行個體改變，計算復雜度低于GA。(2) AMPSO算法中粒子具有“記憶”功能。通過自身學習及向其它粒子學習，使下一代解能夠有目標性地從祖先“繼承”更多的信息，在更短的時間內(nèi)找到近似最優(yōu)解。(3) AMPSO算法的信息共享機制不同于GA的。GA中染色體之間共享信息，整個種群以較均勻的速度向最優(yōu)位置移動。而AMPSO中的信息以單向方式移動，只有最佳粒子將信息傳遞給其它粒子，整個搜索過程追隨當前最優(yōu)解。

表4表示對于訓練集SPEC CPU2006，平臺I和平臺 II上分別采用GA與AMPSO搜索的最佳優(yōu)化參數(shù)獲得的相對于GCC 4.5-O3優(yōu)化參數(shù)設置實現(xiàn)的程序性能加速比。

Table 4 SPEC CPU2006 benchmark speedup表4 SPEC CPU2006 測試集加速比

設置函數(shù)循環(huán)展開因子、分塊因子、數(shù)組填充因子分別為(U，T，P)時，程序416.gamess中的form函數(shù)，平臺I上GCC默認優(yōu)化參數(shù)為(1，0，0)，GA和AMPSO搜索到的最佳優(yōu)化參數(shù)分別為(4，0，0)和(8，0，0)，對應的函數(shù)執(zhí)行時間分別為：0.60、0.53和0.52。U=8，T=0，P=0時運行時間最快的原因在于控制流的改變減少了判斷和分支代碼序列總數(shù)，減少了內(nèi)存訪問。

此外，循環(huán)包含具有復制操作的有環(huán)鏈，U=8時可以消除有環(huán)鏈。實驗結(jié)果表明，GA在平臺I和平臺II上分別實現(xiàn)1.22×和1.21×加速，AMPSO分別實現(xiàn)1.26×和1.25×加速，部分AMPSO加速比小于GA的原因是AMPSO有時會陷入局部最優(yōu)解。

Figure 3 Test program speedup on platform I圖3 平臺I測試程序加速比

Figure 4 Test program speedup on platform II圖4 平臺II測試程序加速比

6.2.2 kNN與softmax性能比較

為驗證模型分類效果，我們在平臺I和平臺II上分別比較kNN和softmax回歸預測準確率，結(jié)果如表5所示。其中，GCC表示使用GCC默認優(yōu)化參數(shù)，Cost表示沒有使用最佳參數(shù)時程序執(zhí)行時間代價。兩個平臺上softmax回歸預測準確率分別為0.67和0.63，kNN預測準確率分別為0.63和0.59，而GCC默認優(yōu)化僅為0.15和0.16。實驗結(jié)果表明softmax回歸具有較高的預測準確率，kNN略差于softmax，而使用GCC默認優(yōu)化時，大多數(shù)情況下沒有使用最佳優(yōu)化參數(shù)。實驗結(jié)果還顯示出最佳參數(shù)類分布于所有參數(shù)類，沒有一個參數(shù)類在所有情況下都是最佳的。

圖3和圖4表示使用kNN和softmax回歸模型為NPB測試集和科學計算程序在平臺I和平臺II上預測的優(yōu)化參數(shù)相對于GCC默認優(yōu)化獲得的加速比，Best表示使用AMPSO搜索最佳優(yōu)化參數(shù)時實現(xiàn)的加速。

Table 5 Prediction accuracy on different platforms表5 不同平臺預測準確率

Figure 5 Speedup using different features on platform I圖5 采用不同特征時平臺I測試程序加速比

Figure 6 Speedup using different features on platform II圖6 采用不同特征時平臺II測試程序加速比

實驗表明，kNN和softmax回歸模型對于新程序有較好的預測能力，且softmax模型性能平均優(yōu)于kNN。平臺I上kNN產(chǎn)生的加速比為1.05×～1.6×，平均加速比為1.28×。softmax產(chǎn)生的加速比為1.1×～1.7×，平均加速比為1.36×。其中SWE產(chǎn)生2.1×加速比，SWE中的thin6d函數(shù)，GCC默認優(yōu)化參數(shù)為(2，0，0)，kNN和softmax模型預測的最佳優(yōu)化參數(shù)分別為(2，0，0)和(4，0，1)，對應的函數(shù)執(zhí)行時間為：1.53、1.21和1.12。U=4，T=0，P=1時運行時間最快的原因是設置數(shù)組填充為1可使數(shù)組低維長度為向量化因子的整數(shù)倍，提升程序性能。IS和SP的Best性能略差于softmax，原因在于數(shù)據(jù)收集過程中可能會產(chǎn)生噪聲，且AMPSO搜索會有陷入局部最優(yōu)解。平臺II上kNN產(chǎn)生的加速比為1.1×～1.45×，平均加速比為1.25×，softmax產(chǎn)生的加速比為1.13×～1.55×，平均加速比為1.34×。

6.2.3 采用不同特征時的性能比較

基于softmax回歸模型，對比采用動靜結(jié)合特征表示DSFC、靜態(tài)特征表示Milepost GCC和基于性能計數(shù)器PC(Performance Counter)時的動態(tài)特征性能。Milepost GCC包括以固定長度特征向量表示的靜態(tài)源代碼和中間表示特征，PC能實時采集系統(tǒng)內(nèi)程序性能數(shù)據(jù)，以此分析系統(tǒng)瓶頸、監(jiān)視組件等表現(xiàn)。

圖5和圖6表示softmax回歸模型分別采用DSFC、 Milepost GCC和PC特征時，為NPB測試集和科學計算程序在平臺I和平臺II上預測的優(yōu)化參數(shù)相對于GCC默認優(yōu)化參數(shù)獲得的程序性能加速比。平臺I上WRF程序中的reconst_GS函數(shù)，GCC默認優(yōu)化參數(shù)為(4，0，0)，采用DSFC、 Milepost GCC和PC特征時,softmax模型預測的最佳優(yōu)化參數(shù)分別為(4，32，0)、(4，16，0)、(4，24，0)，對應的函數(shù)執(zhí)行時間分別為：19.21、9.2、13.42和11.32。U=4，T=32，P=0時函數(shù)運行時間最快的原因在于矩陣轉(zhuǎn)置操作，轉(zhuǎn)置操作一定會發(fā)生不連續(xù)的讀或者寫，Cache命中率較低。為提高Cache命中率，進行循環(huán)分塊是較好的解決辦法，分塊大小與Cache大小存在一定相關性。平臺II上GKUA程序中的disk_lt函數(shù)，GCC默認優(yōu)化參數(shù)為(2，0，0)，采用DSFC、 Milepost GCC和PC特征時,softmax模型預測的優(yōu)化參數(shù)分別為(2，32，3)、(2，16，0)和(2，16，3)，函數(shù)執(zhí)行時間分別為：1.97、0.96、1.01和1.26。U=2，T=32，P=3時運行時間最快的原因在于函數(shù)中存在矩陣乘操作，矩陣乘的向量化是外層向量化。矩陣向量訪問時對齊訪問是十分關鍵的，所以應對數(shù)組進行填充。

實驗結(jié)果表明，基于DSFC的特征表示優(yōu)于使用Milepost GCC靜態(tài)特征獲得的性能。原因在于Milepost GCC特征包括基本塊和邊的信息，這些信息是以整個函數(shù)為單位進行靜態(tài)統(tǒng)計的，而DSFC特征表示是靜態(tài)和動態(tài)相結(jié)合的。但是，有些程序如MG采用Milepost GCC特征時性能優(yōu)于DSFC，原因是Milepost GCC有一些靜態(tài)特征沒有包括在DSFC特征中，這可能對特定程序有影響。DSFC特征表示也優(yōu)于單獨使用PC動態(tài)特征表示獲得的性能。因此，實驗結(jié)果表明，在softmax回歸模型中使用DSFC特征表示有利于進一步提升模型優(yōu)化選擇性能。

6.2.4 離線學習和在線預測時間

使用kNN和softmax回歸模型為新程序預測優(yōu)化參數(shù)分為訓練階段(離線完成)和預測階段(在線完成)。訓練階段一次性完成，收集訓練數(shù)據(jù)所需時間取決于訓練集中程序數(shù)量。表6表示平臺I和平臺II上SPEC CPU2006作為訓練集、WRF作為目標程序的各階段時間。采用SLOPS方法雖然需要若干天時間進行數(shù)據(jù)收集和模型訓練，但對于新的目標程序只需要很短的時間就可以完成較好的優(yōu)化參數(shù)預測。

Table 6 WRF offline learning and online prediction time表6 WRF離線學習和在線預測時間

7 結(jié)束語

本文提出一種選擇編譯器優(yōu)化參數(shù)的新方法——基于監(jiān)督模型的函數(shù)級優(yōu)化參數(shù)選擇方法SLOPS，該方法基于監(jiān)督學習技術自動生成編譯器優(yōu)化參數(shù)，針對程序的循環(huán)展開因子、分塊因子、數(shù)組填充因子等優(yōu)化參數(shù)進行決策。在兩種平臺上分別以改進的粒子群算法AMPSO進行優(yōu)化參數(shù)的優(yōu)化空間搜索，解決優(yōu)化參數(shù)的有約束多目標優(yōu)化問題。使用動靜結(jié)合的特征表示方法，在最小均方誤差意義下獲取對原始特征數(shù)據(jù)的表示。分別采用k近鄰法和softmax回歸監(jiān)督學習方法建立統(tǒng)計模型，實施優(yōu)化參數(shù)決策。給定新的目標程序，kNN和softmax回歸模型在兩種平臺上相對于GCC默認優(yōu)化級別-O3分別實現(xiàn)1.28×和1.36×及1.25×和1.34×平均加速。程序優(yōu)化參數(shù)的選擇是提升程序性能的關鍵技術；此外，程序進行編譯時需要經(jīng)過幾百個優(yōu)化遍以獲取高效的目標代碼，現(xiàn)有編譯器對所有目標程序執(zhí)行固定優(yōu)化遍，然而，研究表明不同的程序需要有針對性地選擇優(yōu)化遍，下一步工作計劃基于機器學習算法進行目標程序優(yōu)化遍選擇，以進一步提升目標程序性能。

[1] Chen Yang, Fang Shuang-de,Huang Yuan-jie,et al.Deconstructing iterative optimization[J].ACM Transactions on Architecture and Code Optimization,2012,9(3):article 21.

[2] Pouchet L N，Bastoul C，Cohen A，et al.Iterative optimization in the polyhedral model:Part I,one-dimensional time[C]∥Proc of International Symposium on Code Generation and Optimization (CGO’07),2007:144-156.

[3] Cooper K D,Schielke P J,Subramanian D.Optimizing for reduced code space using genetic algorithms[C]∥Proc of ACM SIGPLAN 1999 Workshop on Languages,Compilers,and Tools for Embedded Systems,1999:1-9.

[4] Kisuki T,Knijnenburg P M W,Boyle M F P O.Combined selection of tile sizes and unroll factors using iterative compilation[C]∥Proc of the 2000 International Conference on Parallel Architectures and Compilation Techniques (PACT’00),2000:237-248.

[5] Agakov F,Bonilla E,Cavazos J.Using machine learning to focus iterative optimization[C]∥Proc of International Symposium on Code Generation and Optimization(CGO’06),2006:295-305.

[6] Liu Zhang-lin.Compiler optimization adaption research based on machine learning [D].Beijing:Chinese Academy of Sciences,2006.(in Chinese)

[7] Cavazos J,Fursin G,Agakov F,et al.Rapidly selecting good compiler optimizations using performance counters [C]∥Proc of International Symposium on Code Generation and Optimization(CGO’07),2007:185-197.

[8] Fursin G,Kashnikov Y,Memon A W,et al.Milepost gcc:Machine learning enabled self-tuning compiler[J].International Journal of Parallel Programming,2011,39(3):296-327.

[9] Fursin G,Miranda C,Temam O,et al. Milepost Gcc:Machine learning based research compiler[C]∥Proc of GCC Summit,2008:1-10.

[10] Leather H,Bonilla E,Boyle M O.Automatic feature generation for machine learning based optimizing compilation[C]∥Proc of International Symposium on Code Generation and Optimization(CGO’09),2009:81-91.

[11] Ding Yu-fei,Ansel J,Veeramachaneni K,et al.Autotuning algorithmic choice for input sensitivity[C]∥Proc of the 36th ACM Conference on Programming Language Design and Implementation(PLDI’15),2015:379-390.

[12] Martins L G A,Nobre R, Delbem A C B, et al.Clustering-based selection for the exploration of compiler optimization sequences [J].ACM Transactions on Architecture and Code Optimization,2016,13(1):article 8.

[13] Kulkarni P A,Whalley D B,Tyson G S,et al.Practical exhaustive optimization phase order exploration and evaluation[J].ACM Transactions on Architecture and Code Optimization，2009,6(1):article 1.

[14] Ballal P A，Sarojadevi H，Harsha P S,et al.Compiler optimization:A genetic algorithm approach [J].International Journal of Computer Applications,2015,112 (10):9-13.

[15] Kumar T S,Sakthivel S,Kumar S.Optimizing code by selecting compiler flags using parallel genetic algorithm on multicore CPUs [J].International Journal of Engineering and Technology,2014,6 (2):544-551.

[16] Xu Ming-he.Research on multi-object particle swarm optimization algorithm [D].Shanghai:Shanghai Jiao Tong University,2013.(in Chinese)

附中文參考文獻：

[6] 劉章林.基于機器學習的編譯優(yōu)化適應性研究[D].北京：中國科學研究院，2006.

[16] 徐鶴鳴.多目標粒子群優(yōu)化算法的研究[D].上海:上海交通大學，2013.