監(jiān)督學(xué)習(xí)模型指導(dǎo)的函數(shù)級(jí)編譯優(yōu)化參數(shù)選擇方法研究*

劉 慧，趙榮彩，王 琦

(1.解放軍信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001;2.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007)

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

定義1變換(Transformation)是一個(gè)部分函數(shù)f，其輸入是代碼C，輸出是等價(jià)語(yǔ)義的代碼，即f對(duì)代碼C中的一部分進(jìn)行重寫(xiě)變換生成語(yǔ)義等價(jià)的代碼。

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

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

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ù)對(duì)程序變換優(yōu)化參數(shù)的認(rèn)識(shí)，最行之有效的參數(shù)化變換為循環(huán)展開(kāi)(Loop Unrolling)、數(shù)組填充(Array Padding)、循環(huán)分塊(Loop Tiling)。下面首先對(duì)其進(jìn)行介紹。

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

(2)

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

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

(3)循環(huán)分塊因子。循環(huán)分塊技術(shù)利用仿射變換改變循環(huán)迭代訪存順序，充分利用分塊數(shù)據(jù)重用，減少數(shù)據(jù)移動(dòng)和Cache 失效，實(shí)現(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，當(dāng)Li的分塊因子bi≠0時(shí)，數(shù)組第j維的分塊因子Ti=bi，否則，該維不分塊，Ti=ti，ti表示數(shù)組第j維的元素個(gè)數(shù);x(k,j)=1表示數(shù)組第j維分塊，x(k,j)=0表示第j維不分塊。

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

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

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

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個(gè)粒子的速度信息；xid=(xi1,xi2,…,xiD)，1≤i≤N表示第i個(gè)粒子的位置信息。Pid表示粒子的個(gè)體最優(yōu)位置，Pgd表示種群獲得的全局最優(yōu)位置。k為迭代次數(shù)；c1、c2為決定速度變化向量值的學(xué)習(xí)因子；r1∈[0,1]、r2∈[0,1]表示兩個(gè)隨機(jī)系數(shù)，是為了避免粒子在搜索過(guò)程中飛出搜索空間而增加的。標(biāo)準(zhǔn)PSO算法只能求解無(wú)約束的單目標(biāo)優(yōu)化問(wèn)題，對(duì)于有約束的多目標(biāo)優(yōu)化問(wèn)題，需要考慮約束處理方法以及Pareto最優(yōu)解形成的邊界，即Pareto前端。

3.2 自適應(yīng)多目標(biāo)粒子群算法

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

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

(6)

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

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

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

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

(9)

(10)

(11)

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

算法1基于自適應(yīng)進(jìn)化多目標(biāo)粒子群算法的優(yōu)化參數(shù)選擇算法

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

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

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

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

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

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

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

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

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

4 程序特征表示

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

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

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

5.1 kNN

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

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

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

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

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

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

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

(12)

涵蓋這k個(gè)點(diǎn)的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)最多的標(biāo)簽指派給t，作為新程序f的優(yōu)化參數(shù)類t。

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

5.2 softmax回歸

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

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

(14)

(15)

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

(16)

對(duì)于J(θ)的最小化問(wèn)題，目前沒(méi)有閉式解法，本文使用梯度下降迭代優(yōu)化算法，求導(dǎo)得到梯度公式：

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

(17)

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

θj=θj-α▽?duì)萰J(θ)，j=1,2,…,k

(18)

(19)

對(duì)于任意λ>0，J(θ)變?yōu)閲?yán)格凸函數(shù)，得到唯一解。此時(shí)Hessian矩陣變?yōu)榭赡婢仃?，采用梯度下降法可保證收斂到全局最優(yōu)解，對(duì)J(θ)求導(dǎo)得：

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

(20)

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

6 實(shí)驗(yàn)分析

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

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

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

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

訓(xùn)練集：SPEC CPU2006基準(zhǔn)程序測(cè)試集是由標(biāo)準(zhǔn)性能評(píng)價(jià)組織開(kāi)發(fā)的用于評(píng)測(cè)通用型CPU性能的基準(zhǔn)程序測(cè)試集，輸入規(guī)模由小到大分為test、train和reference規(guī)模，本文采用reference規(guī)模進(jìn)行測(cè)試。

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

Table 3 Large scale scientific calculation programs表3 大型科學(xué)計(jì)算程序

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

6.2.1 遺傳算法與AMPSO性能比較

我們通過(guò)對(duì)比遺傳算法GA(Genetic Algorithm)和AMPSO方法，分析本文提出的AMPSO方法的有效性。對(duì)測(cè)試集的熱點(diǎn)函數(shù)使用GA進(jìn)行優(yōu)化參數(shù)搜索的過(guò)程是從優(yōu)化空間中選擇最優(yōu)解的過(guò)程，為GA創(chuàng)建一組染色體(稱為初始種群)，每個(gè)染色體對(duì)應(yīng)一個(gè)優(yōu)化參數(shù)向量，染色體中的每個(gè)基因?qū)?yīng)一個(gè)優(yōu)化參數(shù)。采用GA和AMPSO進(jìn)行程序優(yōu)化參數(shù)搜索時(shí)，GA控制參數(shù)設(shè)置為：群體規(guī)模大小40，交叉概率0.6，變異概率0.3，最大遺傳代數(shù)50；AMPSO參數(shù)設(shè)置為：群體規(guī)模大小20，最大進(jìn)化代數(shù)30。此時(shí)，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最佳適應(yīng)度比較

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

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

Table 4 SPEC CPU2006 benchmark speedup表4 SPEC CPU2006 測(cè)試集加速比

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

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

Figure 3 Test program speedup on platform I圖3 平臺(tái)I測(cè)試程序加速比

Figure 4 Test program speedup on platform II圖4 平臺(tái)II測(cè)試程序加速比

6.2.2 kNN與softmax性能比較

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

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

Table 5 Prediction accuracy on different platforms表5 不同平臺(tái)預(yù)測(cè)準(zhǔn)確率

Figure 5 Speedup using different features on platform I圖5 采用不同特征時(shí)平臺(tái)I測(cè)試程序加速比

Figure 6 Speedup using different features on platform II圖6 采用不同特征時(shí)平臺(tái)II測(cè)試程序加速比

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

6.2.3 采用不同特征時(shí)的性能比較

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

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

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

6.2.4 離線學(xué)習(xí)和在線預(yù)測(cè)時(shí)間

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

Table 6 WRF offline learning and online prediction time表6 WRF離線學(xué)習(xí)和在線預(yù)測(cè)時(shí)間

7 結(jié)束語(yǔ)

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

[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)

附中文參考文獻(xiàn)：

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

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