學習模型指導的編譯器優(yōu)化順序選擇方法

劉 慧 徐金龍 趙榮彩 姚金陽

1(河南師范大學計算機與信息工程學院 河南新鄉(xiāng) 453007)2(數(shù)學工程與先進計算國家重點實驗室(戰(zhàn)略支援部隊信息工程大學) 鄭州 450002)3(河南省高?！坝嬎阒悄芘c數(shù)據(jù)挖掘”工程技術(shù)研究中心(河南師范大學) 河南新鄉(xiāng) 453007)

為應用程序選擇最佳編譯優(yōu)化順序是編譯優(yōu)化領(lǐng)域歷久彌新的問題，而且是NP完全問題，編譯器研究人員依靠他們對編譯器后端的理解提出一些預定義的優(yōu)化順序.大型應用程序編譯優(yōu)化方案的提出需要研究人員花費很長的時間運行程序的不同優(yōu)化版本，遠不及體系結(jié)構(gòu)和應用軟件的更新速度.GCC(GNU compiler collection)編譯器有超過200個的編譯優(yōu)化遍(pass)，LLVM(low level virtual machine)編譯器有超過100個的編譯優(yōu)化遍，并且這些優(yōu)化在不同的應用層上工作，如分析遍、循環(huán)嵌套遍等.通常情況下，大多數(shù)編譯優(yōu)化是默認關(guān)閉的，編譯器開發(fā)人員期望軟件開發(fā)人員知道哪些優(yōu)化對其代碼是有益的，而軟件開發(fā)人員可能并不熟悉編譯優(yōu)化相關(guān)知識.目前，大多商用編譯器使用標準優(yōu)化級別-O1，-O2，-O3等為應用程序執(zhí)行固定順序的優(yōu)化，對于大多數(shù)應用程序可以帶來“平均良好性能”.然而，由于應用程序具有不同程序特征，為產(chǎn)生最佳性能提升，必須采用更有程序針對性的編譯優(yōu)化順序[1].特別是針對嵌入式系統(tǒng)的編譯器更加依賴于代碼優(yōu)化，因為使用的體系結(jié)構(gòu)更加受限于內(nèi)存大小、處理器速度等.如何為目標程序?qū)嵤└嗅槍π缘膬?yōu)化順序，最大化程序性能仍然是一個亟需解決的關(guān)鍵問題.

在高性能計算領(lǐng)域中，并行計算機系統(tǒng)日益復雜.為了降低系統(tǒng)功耗，開發(fā)人員應用了不同的硬件和軟件技術(shù).目前主流的P級高性能計算機系統(tǒng)大多使用了GPU[2]和MIC(many integrated core architecture)[3]等眾核處理器作為加速器或協(xié)處理器.在2017年6月的TOP榜單中，排名前十的機器中有5臺使用了GPU或者MIC處理器作為加速器和協(xié)處理器[4].計算密集型應用程序?qū)⒋蟛糠值膱?zhí)行時間花費在適合于高級編譯優(yōu)化的循環(huán)嵌套中，例如稠密線性代數(shù)代碼等.近年來提出的多面體編譯優(yōu)化技術(shù)亦致力于將數(shù)學表示集中在多面體模型的循環(huán)嵌套中[5-6].因此，復雜體系結(jié)構(gòu)下為應用程序特定循環(huán)結(jié)構(gòu)選擇更有針對應的優(yōu)化順序，對程序性能提升至關(guān)重要.目前，通常使用迭代編譯方法和基于機器學習的方法解決編譯器優(yōu)化順序的選擇問題.

迭代編譯(iterative compilation)是一種針對通用程序的優(yōu)化方法，該方法可有效集成不同的優(yōu)化技術(shù)，適用于不同的體系結(jié)構(gòu)[7].Chen等人[8]提出基于數(shù)據(jù)中心的迭代編譯方法，通過在主服務(wù)器上收集性能統(tǒng)計數(shù)據(jù)，選擇最佳編譯優(yōu)化及進行收益分析.Purini等人[9]使用下采樣技術(shù)減少優(yōu)化搜索空間，為應用程序選擇最佳編譯器優(yōu)化順序.Nobre等人[10]提出將編譯器優(yōu)化遍之間的變換用圖形進行表示，然后通過圖形采樣的方式確定目標程序的優(yōu)化順序，能夠有效減小搜索空間和提升收斂速度.Martins等人[11]基于遺傳算法，采用聚類技術(shù)實施應用程序特定的優(yōu)化順序選擇.在面向FPGAs的硬件編譯環(huán)境下，Huang等人[12]分析了2種基于順序插入的迭代方法，用于可變序列長度的編譯優(yōu)化順序選擇.采用迭代編譯獲取的程序性能加速明顯好于靜態(tài)編譯，但在程序的迭代編譯過程中會產(chǎn)生龐大的編譯優(yōu)化空間.此外，迭代編譯是一種“無記憶”的優(yōu)化搜索方法，不能利用已經(jīng)獲取的編譯優(yōu)化經(jīng)驗.

因此，編譯優(yōu)化人員提出將機器學習技術(shù)加入傳統(tǒng)迭代編譯優(yōu)化過程，逐步形成基于機器學習的迭代編譯方法[13-15].優(yōu)化預測模型的輸入為程序特征，輸出為特定性能目標，如程序運行時間、優(yōu)化選擇和優(yōu)化順序等.理想情況下，預測模型獨立于應用程序，能對不同程序版本進行快速評估，顯著減少迭代編譯代價[16].Agakov等人[17]提出2種優(yōu)化順序預測模型：獨立同分布模型和馬爾可夫模型，以提升應用程序性能.預測模型在迭代編譯過程中利用機器學習算法尋找更好的優(yōu)化順序，取得了一定的程序性能提升.但Agakov等人[17]提出的模型僅使用源代碼程序特征，不能體現(xiàn)程序的當前版本優(yōu)化狀態(tài)，而程序的當前優(yōu)化狀態(tài)對接下來將使用的優(yōu)化具有重要的影響.

Fursin等人[18]提出基于GCC編譯器的Milepost GCC，將機器學習算法集成于GCC編譯框架.Milepost GCC基于源代碼及程序中間表示抽取程序特征，統(tǒng)計不同指令和函數(shù)控制流圖信息，使用機器學習技術(shù)自動調(diào)整程序優(yōu)化變換.但Milepost GCC主要解決的是優(yōu)化選擇問題，基于固定的優(yōu)化順序從中選擇能最有效提升代碼性能的優(yōu)化，而且其使用的是固定長度的特征向量.Cavazos等人[19]提出一種基于機器學習的編譯優(yōu)化順序預測方法，該方法使用性能計數(shù)器構(gòu)建程序特征向量，并用于預測編譯優(yōu)化順序.Dubach等人[20]提出使用機器學習在嵌入式程序和微體系結(jié)構(gòu)之間進行可移植的編譯器優(yōu)化.Hoste等人[21]提出使用多目標進化算法為程序選擇最佳編譯優(yōu)化.Kumar[22]提出通過在多核CPU上使用并行遺傳算法選擇最佳編譯優(yōu)化.Jantz等人[23]采用修剪設(shè)計空間搜索技術(shù)，在較小的非聯(lián)合優(yōu)化子集上進行多階段的優(yōu)化順序搜索.Ashouri等人[24]提出優(yōu)化順序預測模型COBAYN，基于貝葉斯網(wǎng)絡(luò)將程序特征表示與編譯優(yōu)化遍相關(guān)聯(lián)，以最大化程序性能.Park等人[25]將基于多面體模型的迭代編譯與機器學習相結(jié)合用以解決編譯優(yōu)化順序問題，取得了較好的預測效果.現(xiàn)有基于機器學習的迭代編譯方法大多數(shù)使用單獨的靜態(tài)程序特征或單獨的動態(tài)程序特征進行優(yōu)化預測模型的構(gòu)建，如何采用更有效的程序特征表示方法需要進一步進行研究.此外，為了進一步降低編譯器優(yōu)化順序選擇過程中的迭代編譯開銷，如何構(gòu)建更有效的優(yōu)化預測模型，也亟需進行更深入的研究.

人工神經(jīng)網(wǎng)絡(luò)(artificial neural network， ANN)是一種模擬人腦功能對數(shù)據(jù)信息進行加工處理的系統(tǒng)化方法.本文提出基于機器學習的編譯器優(yōu)化順序選擇方法Features ANN,通過ANN基于監(jiān)督學習模型進行編譯器優(yōu)化順序選擇.主要貢獻有3個方面：

1) 使用動靜結(jié)合的程序特征表示方法，通過主成分分析技術(shù)將高維程序特征降維為低維程序特征，在不降低程序表示性的基礎(chǔ)上，為優(yōu)化順序預測模型選擇最佳程序特征表示.

2) 優(yōu)化順序選擇模型Features ANN的樣本為由降維后的程序特征和當前最佳優(yōu)化構(gòu)成的二元組，利用人工神經(jīng)網(wǎng)絡(luò)建立統(tǒng)計模型并集成于編譯器框架，為目標程序選擇當前優(yōu)化狀態(tài)下的最佳優(yōu)化及進行編譯過程驅(qū)動.面對新的應用程序，F(xiàn)eatures ANN將新程序特征作為其輸入，并預測最佳優(yōu)化，從而生成新程序的最佳優(yōu)化順序.

3) 在2種平臺上采用動靜結(jié)合特征作為Features ANN預測模型輸入時，相對于GCC 8.1.0編譯器標準優(yōu)化級別-O3分別獲得1.49x和1.41x的程序執(zhí)行時間加速.此外，與現(xiàn)有迭代編譯方法和非迭代編譯方法相比時，均獲得了最佳的程序性能提升.

1 學習模型指導的優(yōu)化順序選擇模型

1.1 優(yōu)化順序問題的形式化描述

為了對優(yōu)化順序選擇問題有更直觀的認識，我們首先對編譯優(yōu)化的選擇空間進行形式化描述.定義布爾向量o，元素oi表示不同的編譯優(yōu)化，每個優(yōu)化可以被啟用(oi=1)或禁用(oi=0).編譯優(yōu)化的選擇空間屬于n維布爾空間，由向量空間oselection表示為

oselection=(0，1)n.

(1)

當對應用程序ai進行優(yōu)化時，n表示編譯優(yōu)化總數(shù)，由一個指數(shù)空間作為其上限.例如，當n=10時，目標應用程序ai有1 024種可選擇的優(yōu)化方式.當應用程序有N個不同的優(yōu)化版本A={a0,a1,…,an}時，將產(chǎn)生更大的優(yōu)化空間.

當使用固定優(yōu)化序列長度且不重復使用優(yōu)化時，定義編譯優(yōu)化順序為n維向量空間為ophase=n!,其中，n表示編譯優(yōu)化總數(shù).當使用動態(tài)優(yōu)化序列長度且可重復使用優(yōu)化時，優(yōu)化順序空間擴展為

(2)

其中，m表示優(yōu)化序列最大期望長度.假設(shè)n和m均為10，將產(chǎn)生高達110億種不同的編譯優(yōu)化順序.當優(yōu)化序列最大期望長度m沒有固定值時，編譯優(yōu)化順序問題沒有上界.

1.2 監(jiān)督學習模型指導的優(yōu)化順序選擇模型

監(jiān)督學習模型指導的編譯器優(yōu)化順序預測模型框架如圖1所示，包括數(shù)據(jù)收集、模型訓練和模型預測階段.在數(shù)據(jù)采集階段，首先根據(jù)程序特征表示方法，使用設(shè)計空間探索引擎(design space exploration, DSE)抽取程序特征{F1,F2,…,Fn}，提取目標程序特征值{f1,f2,…,fn}.然后，使用DSE將優(yōu)化集合{o1,o2,…,om}中的優(yōu)化oi分別應用于目標程序.DSE通過啟用和禁用優(yōu)化實施不同的優(yōu)化、優(yōu)化順序及測試應用程序運行時間.由于程序在每應用一次優(yōu)化后，特征值將會發(fā)生相應的改變，需要根據(jù)更新后的特征值確定下一階段應使用的優(yōu)化.因此，我們設(shè)定DSE在每應用一次優(yōu)化后重新提取特征值{f1,f2,…,fn}，以表示程序的當前優(yōu)化狀態(tài).并根據(jù)程序的當前優(yōu)化狀態(tài)再次選擇優(yōu)化集合{o1,o2,…,om}中的優(yōu)化oi和測試運行時間.數(shù)據(jù)收集階段收集的訓練數(shù)據(jù)由{oi,f1,f2,…,fn,si}構(gòu)成.其中，oi表示優(yōu)化變換，{f1,f2,…,fn}表示程序特征值，si表示特征值為{f1,f2,…,fn}時程序?qū)嵤﹥?yōu)化oi可獲得的加速比.當產(chǎn)生最大加速比smax時，對應的優(yōu)化oi即為程序當前狀態(tài)下可使用的最佳優(yōu)化.

Fig. 1 Compile optimization sequence prediction model圖1 編譯優(yōu)化順序預測模型

在模型訓練階段，基于收集到的訓練數(shù)據(jù)，采用ANN進行模型訓練，構(gòu)建程序優(yōu)化及優(yōu)化順序預測模型Features ANN.在模型預測即使用階段，基于程序在當前優(yōu)化狀態(tài)下的特征值，通過存儲在預測模型中的知識為新程序預測當前狀態(tài)下應用不同優(yōu)化時的加速比，實現(xiàn)最大加速比對應的優(yōu)化即為程序在當前狀態(tài)下應使用的最佳優(yōu)化，從而生成新程序的最佳優(yōu)化順序.優(yōu)化終止條件為達到預先設(shè)定的最大優(yōu)化序列長度，或連續(xù)為程序當前狀態(tài)預測相同的優(yōu)化.

2 程序特征表示

2.1 程序特征

現(xiàn)有程序特征表示方法包括：

1) 靜態(tài)程序特征表示.靜態(tài)特征通常在語法分析過程中、編譯過程中提取.

2) 動態(tài)程序特征表示.動態(tài)特征在程序運行過程中提取，通常具有更好的程序表示性，但為獲取動態(tài)特征往往需要反復執(zhí)行程序的運行.

Features ANN優(yōu)化順序預測模型使用動靜結(jié)合的特征表示方法(dynamic static features combination, DSFC)，為預測模型提供更細粒度的輸入.靜態(tài)和動態(tài)特征列表如表1和表2所示[14].

Table 1 List of Static Features表1 靜態(tài)特征列表

Table 2 List of Dynamic Features表2 動態(tài)特征列表

2.2 特征降維技術(shù)

程序特征的選擇是構(gòu)建優(yōu)化順序預測模型的關(guān)鍵，本文采用主成分分析法(principal component analysis， PCA)為目標程序選擇最主要的靜態(tài)特征和動態(tài)特征.當數(shù)據(jù)空間維度大于3維時，將無法在空間坐標系下用圖形(如點、線、面)表示樣本點.程序特征高維空間的多變量數(shù)據(jù)不能以圖形化方式直觀展示其空間特征分布規(guī)律，如樣本相似度、樣本中的異常點等信息.PCA的核心思想是通過正交變換，將一個變量維數(shù)較高而且變量之間存在相互關(guān)聯(lián)的數(shù)據(jù)矩陣映射到一個較低維數(shù)的主成分空間.程序特征的PCA計算過程為：

Step1. 假定程序特征中有p個樣本，每個樣本共有n個變量，樣本數(shù)據(jù)可構(gòu)成一個p×n階矩陣：

(3)

對樣本矩陣進行標準化變換，得到標準化陣Z：

(4)

其中，

(5)

(6)

Step2. 對標準化陣Z求相關(guān)系數(shù)矩陣：

(7)

Step3. 解樣本相關(guān)陣R的特征方程|λI-R|=0，求出n個特征根，按照特征值的大小倒序排列.對于每一個特征值λi求出其所對應的特征向量ei(i=1,2,…,n).

Step4. 主成分的選取規(guī)則：

(8)

(9)

其中，統(tǒng)計量Ii代表某一主成分λi的貢獻率，統(tǒng)計量Si代表某一主成分λi的累積貢獻率.k的選擇原則是取累計貢獻率90%，保證主成分變量包括原始數(shù)據(jù)的大多數(shù)信息，即求得Si≈0.9的所有λi所對應的主成分fi.

Step5. 載荷系數(shù)的計算.觀測值xi(i=1,2,…,n)在主成分fi上的得分為

(10)

Step6. 根據(jù)程序特征，對程序特征主成分進行命名，對主成分及其荷載進行相關(guān)解釋.

主成分提取原則一般選取主成分累計貢獻率超過90%的前m個主成分，經(jīng)過實驗分析表明，由于程序特征值的冗余和協(xié)方差，程序特征可以降維至5維特征向量，此時仍能保持99%的數(shù)據(jù)差異性.

3 ANN構(gòu)建

3.1 基于ANN的優(yōu)化順序預測

在編譯器中確定合適的優(yōu)化順序是一個十分復雜的問題，我們可以將優(yōu)化順序問題定義為馬爾可夫過程(Markov process, MP)，即基于當前程序版本狀態(tài)做出接下來應用何種優(yōu)化的決定.本文以ANN為基礎(chǔ)構(gòu)造程序變換優(yōu)化順序預測模型Features ANN.Features ANN的基本思想是持續(xù)詢問ANN預計使用何種優(yōu)化可為當前狀態(tài)下的程序產(chǎn)生最佳性能.ANN使用當前狀態(tài)下的代碼特征作為輸入，利用網(wǎng)絡(luò)層次表示特征之間復雜的非線性關(guān)系，并與優(yōu)化過程中特定點的最佳優(yōu)化相關(guān)聯(lián).Features ANN模型框架如圖2所示：

Fig. 2 Process of Features ANN compile optimization selection圖2 Features ANN編譯優(yōu)化選擇過程

在模型訓練階段，采用擴張拓撲的神經(jīng)進化算法(neuro-evolution for augmenting topologies, NEAT)生成用來控制優(yōu)化順序的ANN，通過對每個函數(shù)應用不同的優(yōu)化，并記錄程序運行時間進行ANN評估.Features ANN迭代輸出優(yōu)化oi的過程如圖3所示.ANN的輸入為當前狀態(tài)下的代碼特征{f1,f2,…,fn}，輸出為應用不同優(yōu)化oi后的收益概率P，選擇最大概率P對應的優(yōu)化obest作為當前狀態(tài)下應使用的優(yōu)化.應用優(yōu)化obest后將形成一個新的程序版本，特征值發(fā)生改變，將更新后的特征值重新輸入Features ANN，使其輸出下一個要應用的優(yōu)化oi+1.當ANN達到最大代數(shù)或連續(xù)若干代性能沒有變化時，停止使用優(yōu)化，生成目標程序優(yōu)化順序{o1,o2,…,om}.模型預測階段將ANN集成于編譯器，并作為新程序優(yōu)化順序的啟發(fā)式規(guī)則進行使用.Features ANN優(yōu)化順序選擇算法如算法1所示.

Fig. 3 Process of Features ANN output optimization oi iteratively圖3 Features ANN迭代輸出優(yōu)化oi過程

算法1.基于ANN的優(yōu)化順序選擇算法.

輸入：程序特征值f1,f2,…,fn,優(yōu)化{o1,o2,…,om}；

輸出：最佳優(yōu)化序o*={o1,o2,…,om}及其對應的程序運行時間T*.

Step1. 初始化：設(shè)置每代神經(jīng)網(wǎng)絡(luò)個數(shù)N、網(wǎng)絡(luò)代數(shù)M，并隨機生成第1代網(wǎng)絡(luò).

Step2. 輸入程序C當前狀態(tài)特征值f1,f2,…,fn作為當前代網(wǎng)絡(luò)輸入層神經(jīng)元的輸入.

Step3. 計算每個網(wǎng)絡(luò)的適應度Fitness(T)，選擇前10個具有最大適應度值的網(wǎng)絡(luò)傳播到下一代產(chǎn)生新的網(wǎng)絡(luò)

Step4. 交叉和變異產(chǎn)生新一代網(wǎng)絡(luò).變異包括在網(wǎng)絡(luò)隱藏層現(xiàn)有邊上增加一個神經(jīng)元(概率設(shè)置為0.1%)、增加一個新邊(概率設(shè)置為0.5%)或刪除一個現(xiàn)有邊(概率設(shè)置為0.9%).

Step5. 當網(wǎng)絡(luò)到達最大代數(shù)M或連續(xù)若干代性能沒有變化，將具有最大適應度的優(yōu)化作為當前程序版本狀態(tài)下的最佳優(yōu)化obest.

Step6. 算法終止條件：當達到最大優(yōu)化個數(shù)或重復使用優(yōu)化沒有性能提升時，算法終止，轉(zhuǎn)至Step7，否則更新函數(shù)特征，轉(zhuǎn)至Step2.

Step7. 輸出最佳優(yōu)化序o*={o1,o2,…,om}及其對應的函數(shù)執(zhí)行時間T*.

3.2 NEAT

由于優(yōu)化順序預測模型Features ANN處于動態(tài)編譯環(huán)境中，因此ANN及特征抽取過程的開銷要小，否則應用該網(wǎng)絡(luò)進行優(yōu)化順序選擇的代價會高于調(diào)整優(yōu)化順序帶來的收益.本文采用NEAT算法[26]為程序變換優(yōu)化順序選擇模型構(gòu)建ANN.NEAT算法開始于若干沒有隱結(jié)點的最小網(wǎng)絡(luò)，在進化的實施過程中通過變異引入新結(jié)構(gòu)，從而進行網(wǎng)絡(luò)擴張.并通過適應度評估網(wǎng)絡(luò)優(yōu)劣，淘汰適應度較低的個體.由于種群從最小結(jié)構(gòu)開始，優(yōu)化搜索空間的維度也將是最小的.因此，NEAT算法總是搜索比其他進化神經(jīng)網(wǎng)絡(luò)算法更低的維度空間，網(wǎng)絡(luò)構(gòu)建開銷小于其他同類算法.

NEAT進化神經(jīng)網(wǎng)絡(luò)的過程是從只有輸入輸出結(jié)點的簡單網(wǎng)絡(luò)開始逐步增加網(wǎng)絡(luò)復雜程度，具有較大的結(jié)點連接自由度.如圖4所示，NEAT采用結(jié)點基因編碼進行網(wǎng)絡(luò)結(jié)構(gòu)和連接權(quán)值的描述.當創(chuàng)建新的結(jié)點和連接時，借助于所產(chǎn)生的歷史標記，從而避免競爭約定問題.NEAT嘗試將構(gòu)成的網(wǎng)絡(luò)尺寸最小化，在進化開始時讓群體中每個神經(jīng)網(wǎng)絡(luò)都具有最小的拓撲結(jié)構(gòu)，在進化過程中始終保持在網(wǎng)絡(luò)中隨機逐個添加神經(jīng)元和連接.該過程和自然界生物體的生長過程一樣，隨著時間的推移，不斷進化、不斷增加復雜性，從而試圖構(gòu)建最小化的最優(yōu)網(wǎng)絡(luò).

Fig. 4 NEAT gene mapping圖4 NEAT基因映射

NEAT算法的適應度值為訓練集中測試集性能的幾何平均值：

(11)

其中，|S| 表示訓練集個數(shù)，Speedup(s)表示程序運行時間加速比：

(12)

其中，Runtime(sdef)表示測試集s使用默認優(yōu)化順序時的運行時間，Runtime(s)表示使用預測模型預測的優(yōu)化順序時測試集s的運行時間.

4 實 驗

我們在2種平臺上進行Features ANN優(yōu)化順序預測模型的訓練和評估，模型輸入為程序熱點函數(shù)特征，輸出為相應的最佳優(yōu)化順序.

1) 平臺1. 實驗編譯環(huán)境為Linux操作系統(tǒng)，版本為Readhat Enterprise AS 5.0，實驗平臺為國產(chǎn)處理器申威26 010，CPU主頻為 2.5 GHz，L1數(shù)據(jù)cache為 32 KB，L2 cache為256 KB，向量寄存器寬度為256 b，可同時處理4個浮點型數(shù)據(jù)或8個整型數(shù)據(jù).

2) 平臺2.實驗編譯環(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，二級Smart cache 8 MB.

實驗中訓練集測試用例為SPEC CPU2006測試集中的2 000個熱點循環(huán)，測試集用例為NPB測試集和表3所示大型科學計算程序中的熱點函數(shù).實驗將標準優(yōu)化級別-O2及圖5所示優(yōu)化作為優(yōu)化空間，將新的優(yōu)化順序與標準優(yōu)化級別-O3的默認優(yōu)化順序進行性能對比，優(yōu)化的啟用禁用通過使用GCC8.1.0編譯優(yōu)化選項完成.對程序熱點函數(shù)特征采用動靜結(jié)合特征表示方法DSFC，將抽取的特征作為PCA過程的輸入.我們分別比較了采用Features ANN和現(xiàn)有迭代編譯方法、非迭代編譯方法時測試集用例的程序性能.當現(xiàn)有方法使用的優(yōu)化和測試集與本文不同時，我們采用本文的優(yōu)化和測試集重新進行實驗.對抽取的每個熱點函數(shù)采用添加時間戳的方式進行運行時間計時，為減少噪聲影響，每個樣本運行10次，取執(zhí)行時間平均值.

Table 3 Large Scientific Calculation Programs表3 大型科學計算程序

-fauto-inc-dec-falign-jumps-ftree-tail-merge-fstrict-overflow-fcombine-stack-adjustments-fcompare-elim-fcprop-registers-ftree-forwprop-ftree-pre-finline-functions-called-once-ftree-dce-fcaller-saves-fgcse-after-reload-ftree-vrp-fmove-loop-invariants-fipa-profile-fif-conversion-fssa-backprop-funswitch-loops-frerun-cse-after-loop-ftree-ccp-fif-conversion2-fstrict-aliasing-fpartial-inlining-fdce -fdefer-pop-fpeel-loops-fsplit-paths-fbranch-count-reg-fssa-phiopt-ftree-dominator-opts-fshrink-wrap-ftree-phiprop-ftree-partial-pre-finline-functions-fguess-branch-probability-ftree-sink-ftree-slsr-fipa-cp-clone-fschedule-insns2-ftree-loop-distribute-patterns-fthread-jumps-falign-functions-fipa-bit-cp-fsplit-wide-types-fisolate-erroneous-paths-dereference-falign-loops-falign-labels-findirect-inlining-ftree-coalesce-vars-foptimize-sibling-calls-fcrossjumping-ftree-vectorize-ftree-bit-ccp-foptimize-strlen-freorder-blocks-algorithm=stc-ftree-pta-fipa-pure-const-ftree-copy-prop-fschedule-insns-freorder-blocks-and-partition-ftree-ter-fdevirtualize-funit-at-a-time-fsched-interblock-fdelete-null-pointer-checks-ftree-sra-fipa-reference-fcse-follow-jumps-freorder-functions-fdevirtualize-speculatively-ftree-fre-freorder-blocks-fcse-skip-blocks-fhoist-adjacent-loads-fexpensive-optimizations-ftree-dse-fpeephole2-fipa-cp-alignment-fpredictive-commoning-ftree-loop-distribution-fgcse-flra-remat-fforward-propagate-fdelayed-branch -fdse-finline-small-functions-fgcse-lm-fsched-spec-fmerge-constants-ftree-switch-conversion-ftree-builtin-call-dce-fipa-cp-fipa-sra-fipa-icf-fcode-hoisting-ffast-math

Fig. 5 List of Optimization(GCC8.1.0)圖5 優(yōu)化列表(GCC8.1.0)

本文實驗主要從4個方面進行：1)Features ANN采用不同特征時的性能比較.分別采用靜態(tài)程序特征表示、動態(tài)程序特征表示和動靜結(jié)合程序特征表示作為優(yōu)化順序預測模型Features ANN的輸入，對比分析模型的預測性能.2)Features ANN與迭代編譯方法的性能比較.比較測試集程序采用Features ANN與2種現(xiàn)有迭代編譯方法時的程序性能.3)Features ANN與非迭代編譯方法的性能比較.比較測試集程序采用Features ANN和3種現(xiàn)有非迭代編譯方法時的程序性能.4)離線學習和在線預測時間開銷比較.對比分析Features ANN和現(xiàn)有迭代編譯、非迭代編譯方法在訓練數(shù)據(jù)收集、模型構(gòu)建、特征抽取和模型預測上的時間開銷.

5 實驗結(jié)果分析

5.1 采用不同特征時的預測模型性能

基于現(xiàn)有程序特征表示技術(shù)，我們對比分析3類程序特征表示方法對優(yōu)化順序預測模型的影響：靜態(tài)程序特征表示、動態(tài)程序特征表示和動靜結(jié)合程序特征表示.其中，靜態(tài)程序特征采用Milepost GCC靜態(tài)程序，包括以固定長度特征向量表示的靜態(tài)源代碼及中間表示特征[18].動態(tài)程序特征采用基于性能計數(shù)器的動態(tài)特征表示(performance counter， PC)，PC能實時采集、分析系統(tǒng)內(nèi)的應用程序、服務(wù)等性能數(shù)據(jù)，以此來分析系統(tǒng)瓶頸、監(jiān)視組件表現(xiàn)[19].動靜結(jié)合特征表示我們的程序特征表示方法DSFC.

Features ANN分別采用不同特征表示方法，為NPB測試集和表3所示科學計算程序在平臺1和平臺2上預測優(yōu)化順序時，預測模型性能如圖6和圖7所示.其中，Milepost GCC表示靜態(tài)程序特征，PC表示動態(tài)程序特征，DSFC表示本文提出的動靜結(jié)合程序特征表示.Speedup表示相對于GCC 8.1.0標準優(yōu)化級別-O3產(chǎn)生的性能加速比.

Fig. 6 Speedup on platform 1 when adapting different features圖6 采用不同特征時平臺1上測試程序加速比

Fig. 7 Speedup on platform 2 when adapting different features圖7 采用不同特征時平臺2上測試程序加速比

實驗結(jié)果表明，平臺1上基于Milepost GCC靜態(tài)程序特征、PC動態(tài)特征和DSFC動靜結(jié)合特征為NPB測試集和大型科學計算程序預測優(yōu)化順序時，F(xiàn)eatures ANN相對于GCC標準優(yōu)化級別-O3產(chǎn)生的平均加速比分別為1.19，1.23，1.49.平臺2上產(chǎn)生的平均加速比分別為1.16，1.20，1.41.總體來說，對當前測試用例而言，采用DSFC動靜結(jié)合特征可以產(chǎn)生最好的預測性能，PC動態(tài)特征次之，Milepost GCC靜態(tài)特征具有相對較低的預測性能.

經(jīng)程序分析可知，測試集LU的主要熱點函數(shù)為rhs，占程序執(zhí)行時間的24.98%.采用DSFC動靜結(jié)合特征時，F(xiàn)eatures ANN為rhs預測的優(yōu)化順序為{-O2,-fpeel-loops,-funroll-loops,-fprefetch-loop-arrays,-fgcse-after-reload,-ffast-math}.采用Milepost GCC靜態(tài)特征時，F(xiàn)eatures ANN為rhs預測的優(yōu)化順序為{-O2,-fpeel-loops,-funroll-loops,-fprefetch-loop-arrays,-fgcse-after-reload,-ftree-vectorize,-ffast-math}.采用PC動態(tài)特征時，F(xiàn)eatures ANN為rhs預測優(yōu)化順序為{-O2,-fpeel-loops,-fprefetch-loop-arrays,-funroll-loops,-ffast-math}.采用GCC-O3默認優(yōu)化、DSFC動靜結(jié)合特征、Milepost GCC靜態(tài)程序特征和PC動態(tài)特征時對應的函數(shù)執(zhí)行時間分別為：45.975 s，37.364 s，41.864 s，40.376 s.采用DSFC動靜結(jié)合特征預測的優(yōu)化順序除使用標準優(yōu)化級別-O2外，首先對該熱點循環(huán)進行循環(huán)剝離，然后進行循環(huán)展開，循環(huán)展開可以將迭代次數(shù)少的循環(huán)進行展開以充分利用寄存器.循環(huán)中含有大量的3維數(shù)組和4維數(shù)組引用，使用-fprefetch-loop-arrays可以對數(shù)據(jù)預取，對含有大數(shù)組的程序可以產(chǎn)生較好的性能提升.此外，由于循環(huán)中含有大量的變量引用，在計算時會被重復使用，使用-fgcse-after-reload優(yōu)化可以消除重復性的訪存.采用Milepost GCC靜態(tài)特征預測的優(yōu)化順序會對rhs 函數(shù)進行向量化處理，但該程序含有間接訪存，且語句間含有阻止向量化的依賴環(huán)，內(nèi)層循環(huán)迭代次數(shù)小，循環(huán)多為不完美循環(huán)嵌套，若對其進行向量化，將會引入一些數(shù)據(jù)整理指令，增大開銷，性能反而會下降.采用PC動態(tài)特征預測的優(yōu)化順序在數(shù)據(jù)預取之后進行循環(huán)展開，會增加預取次數(shù)，且預測的優(yōu)化中沒有使用-fgcse-after-reload，獲得的程序執(zhí)行時間加速比小于采用DSFC動靜結(jié)合特征產(chǎn)生的加速比.

DSFC動靜結(jié)合特征表示優(yōu)于Milepost GCC靜態(tài)特征表示，原因在于Milepost GCC特征主要包括基本塊和邊的信息，這些信息是以整個程序為單位的固定長度的特征表示，而DSFC采用動靜結(jié)合特征表示方法，而且程序特征是采用PCA方法選擇的，不是固定不變的，更能表示出不同程序的主要信息.但是有一些程序如MG采用Milepost GCC特征時性能優(yōu)于DSFC，原因是Milepost GCC有一些靜態(tài)特征沒有包括在在基于DSFC的特征中，這可能對特定程序有影響.DSFC動靜結(jié)合特征表示也優(yōu)于單獨使用PC動態(tài)特征表示獲得的性能.因此，在Features ANN預測模型中使用動靜結(jié)合程序特征DSFC有利于進一步提升模型的優(yōu)化順序預測性能.

5.2 Features ANN與迭代編譯方法的比較

為將Features ANN與現(xiàn)有迭代編譯方法進行比較，我們選擇與Nobre[10]和Martins[11]的研究進行對比分析.Nobre等人[10]提出一種基于迭代編譯的優(yōu)化順序搜索方法，該方法首先將編譯優(yōu)化變換用圖形方式進行表示，然后通過圖形采樣確定程序的優(yōu)化順序，能夠有效減小優(yōu)化搜索空間和提升收斂速度.Martins等人[11]基于聚類方法，采用遺傳算法指導的設(shè)計空間探索技術(shù)選擇應用特定的優(yōu)化順序，該方法是最近的基于迭代編譯方法進行優(yōu)化順序搜索的典型代表.采用Features ANN和現(xiàn)有迭代編譯方法為NPB測試集、大型科學計算程序在平臺1和平臺2上預測優(yōu)化順序時，預測模型性能如圖8和圖9所示.其中，GraphDSE表示Nobre等人[10]提出的基于圖形的優(yōu)化順序預測模型，ClusterDSE表示Martins等人[11]提出的基于聚類的預測模型，F(xiàn)eatures ANN表示本文提出的預測模型.

Fig. 8 Comparison with iterative compilation (platform 1)圖8 Features ANN與迭代編譯方法的性能比較(平臺1)

Fig. 9 Comparison with iterative compilation (platform 2)圖9 Features ANN與迭代編譯方法的性能比較(平臺2)

從圖8可以看出，平臺1上基于迭代編譯方法為測試集預測優(yōu)化順序時，F(xiàn)eatures ANN，GraphDSE，ClusterDSE相對于GCC標準優(yōu)化級別-O3的平均加速比分別為1.49，1.25，1.38.對當前測試用例而言，F(xiàn)eatures ANN具有最好的預測性能，ClusterDSE次之，GraphDSE具有相對較低的預測性能.經(jīng)程序分析可知，測試集UA的主要熱點函數(shù)為laplacian，占程序執(zhí)行時間的40%.Features ANN為laplacian函數(shù)預測的優(yōu)化順序為{O2,-fpredictive-commoning,-funswitch-loops,-fpeel-loops,-ftree-loop-distribution,-ftree-vectorize,-ffast-math}.GraphDSE為laplacian預測的優(yōu)化順序為{-O2,-fpredictive-commoning,-funswitch-loops,-ftree-loop-distribution,-ftree-vectorize,-fpeel-loops}.ClusterDSE為laplacian預測的優(yōu)化順序為{-O2,-fpredictive-commoning,-funswitch-loops,-fpeel-loop,-ftree-loop-distribution,-ftree-vectorize}.采用GCC-O3默認優(yōu)化、Features ANN、GraphDSE、ClusterDSE時對應的函數(shù)執(zhí)行時間分別為43.87 s，38.57 s，43.19 s，42.50 s.由于函數(shù)laplacian中含有多個完美嵌套循環(huán)，且不含阻止向量化的依賴環(huán)，適合做向量化處理.Features ANN預測的優(yōu)化順序除使用標準優(yōu)化級別-O2外，在為函數(shù)進行向量化處理前使用預測常見優(yōu)化、分支外提，循環(huán)剝離與分布等優(yōu)化.在進行向量化處理后調(diào)用快速數(shù)學庫優(yōu)化，打開-ffast-math，實驗表明在精度要求不苛刻的情況下使用這種激進的優(yōu)化方式可以獲得較大的性能提升.而ClusterDSE預測的優(yōu)化順序沒有使用-ffast-math，程序性能略差于Features ANN.GraphDSE預測的優(yōu)化順序在優(yōu)化選擇上與ClusterDSE相同，但優(yōu)化順序不同，即在向量化后進行循環(huán)剝離，從而導致一些可以使用循環(huán)剝離的循環(huán)體失去了向量化的機會.

從圖9可以看出，平臺2 Features ANN，GraphDSE，ClusterDSE相對于GCC標準優(yōu)化級別-O3的平均加速比分別為1.41，1.16，1.22.Features ANN獲得了最好的預測性能.因此，F(xiàn)eatures ANN優(yōu)化順序預測模型在2種平臺上都獲得了平均最佳的預測性能.Features ANN能夠獲得較好程序性能的原因在于模型基于機器學習算法構(gòu)建，能在較短的時間內(nèi)生成新程序的最佳優(yōu)化順序.而使用現(xiàn)有迭代編譯方法為新程序搜索最佳優(yōu)化順序時，雖然現(xiàn)有方法在優(yōu)化搜索性能和搜索時間上具有較大的改進，但仍需要進行多次迭代才能獲得局部最佳程序性能.

5.3 Features ANN與非迭代編譯方法的比較

非迭代編譯方法的典型代表是基于機器學習的編譯優(yōu)化方法和基于多面體模型的編譯優(yōu)化方法，本文選擇與Ashouri等人[24]和Park等人[25]的研究進行對比分析.Ashouri等人[24]提出COBAYN優(yōu)化順序預測模型，COBAYN是基于貝葉斯網(wǎng)絡(luò)構(gòu)建的優(yōu)化順序預測模型.Park等人[25]基于多面體編譯框架，采用靜態(tài)程序特征和幾種不同的機器學習算法構(gòu)建優(yōu)化順序預測模型.采用Features ANN和現(xiàn)有非迭代編譯方法預測優(yōu)化順序時，預測模型性能如圖10和圖11所示.其中，COBAYN表示Ashouri等人[24]提出的優(yōu)化順序預測模型，LR和SVM表示Park等人[25]基于多面體框架通過邏輯回歸和支持向量機構(gòu)建的預測模型，F(xiàn)eatures ANN表示本文提出的優(yōu)化順序預測模型.

Fig. 10 Comparison with non-iterative compilation (platform 1)圖10 Features ANN與非迭代編譯方法的性能比較(平臺1)

Fig.11 Comparison with non-iterative compilation (platform 2)圖11 Features ANN與非迭代編譯方法的性能比較(平臺2)

從圖10可以看出，平臺1上基于非迭代編譯方法為NPB測試集和大型科學計算程序預測優(yōu)化順序時，F(xiàn)eatures ANN相對于GCC標準優(yōu)化級別-O3的平均加速比分別為1.51和1.45，COBAYN的平均加速比分別為1.40和1.34，LR的平均加速比分別為1.11和1.06，SVM的平均加速比分別為1.32和1.28.從圖11可以看出，平臺2上基于非迭代編譯方法為NPB測試集和大型科學計算程序預測優(yōu)化順序時，F(xiàn)eatures ANN相對于GCC標準優(yōu)化級別-O3的平均加速比分別為1.39和1.43，COBAYN的平均加速比分別為1.30和1.32，LR的平均加速比分別為1.03和1.05，SVM的平均加速比分別為1.24和1.23.對當前測試用例而言，F(xiàn)eatures ANN具有最好的預測性能，COBAYN次之，SVM的預測性能低于COBAYN，LR具有相對較低的預測性能.Features ANN能夠獲得較好預測性能的原因在于模型采用PCA特征降維技術(shù)，選擇最主要的程序特征作為預測模型的輸入.COBAYN采用探索性因子分析法選擇程序特征，然而在實際應用中探索性因子分析必須和驗證性因子分析結(jié)合使用，才能更好地進行因子分析.LR和SVM均采用固定的程序特征，缺乏程序特定性.此外，F(xiàn)eatures ANN基于ANN根據(jù)當前狀態(tài)下的程序特征選擇最佳優(yōu)化，而現(xiàn)有方法對整個程序優(yōu)化前的特征進行抽取和預測優(yōu)化，F(xiàn)eatures ANN的預測精度更高.

5.4 離線學習和在線預測時間開銷比較

使用Features ANN預測模型為新程序預測優(yōu)化順序時的細粒度時間，分為訓練階段(離線完成)和預測階段(在線完成).訓練階段一次性完成，收集訓練數(shù)據(jù)所需時間，取決于訓練集中應用程序數(shù)量.表4和表5分別表示平臺1和平臺2上SPEC CPU作為訓練集、WRF作為目標應用程序時不同預測模型每個特定階段所需時間.采用本文提出的方法雖然需要若干天時間進行數(shù)據(jù)收集和模型訓練，但對于新的目標程序需要很短的時間就可以完成較好的優(yōu)化參數(shù)預測.

實驗結(jié)果表明，F(xiàn)eatures ANN預測模型的離線學習時間略高于現(xiàn)有方法，但在線預測時間低于現(xiàn)有方法.而且從5.1節(jié)和5.3節(jié)的分析中可以看到，F(xiàn)eatures ANN在特征選擇、預測性能等方面均優(yōu)于現(xiàn)有方法.因此，F(xiàn)eatures ANN在特征選擇、預測性能和在線預測時間開銷等方面均取得了較好的效果.

Table 4 Learning and Prediction Time of WRF (Platform 1)表4 WRF離線學習和在線預測時間(平臺1) s

Table 5 Learning and Prediction Time of WRF (Platform 2) 表5 WRF離線學習和在線預測時間(平臺2) s

6 結(jié)束語

本文提出一種選擇編譯器優(yōu)化順序的新方法：Features ANN，以最大化目標應用程序性能.該方法通過使用動靜結(jié)合的特征表示方法進行程序表示，在最小均方誤差意義下獲取對原始特征數(shù)據(jù)的表示.基于程序特征和當前狀態(tài)最佳優(yōu)化構(gòu)成優(yōu)化順序預測模型的樣本數(shù)據(jù)，采用人工神經(jīng)網(wǎng)絡(luò)建立統(tǒng)計模型并集成于編譯器框架，實施優(yōu)化順序選擇及進行編譯過程驅(qū)動.在2種平臺上采用動靜結(jié)合特征作為Features ANN預測模型輸入時，相對于GCC 5.4編譯器默認標準優(yōu)化級別-O3分別獲得1.49x和1.41x的程序執(zhí)行時間加速.與現(xiàn)有迭代編譯方法GraphDSE和ClusterDSE，及非迭代編譯方法COBAYN，LR，SVM比較時，均獲得了最佳的性能提升.

程序優(yōu)化順序選擇是提升程序性能的關(guān)鍵技術(shù)，目前仍有一些后續(xù)工作值得研究，具體來說包括：1)我們將考慮增加更多的訓練數(shù)據(jù)集、測試數(shù)據(jù)集和目標平臺，以進一步提升預測準確率和通用性.2)由于不同的程序優(yōu)化可能需要不同的目標代碼特征，我們將研究更多優(yōu)化變換的相關(guān)性特征，進一步提升程序性能.3)嘗試人工添加噪聲的方法增加預測方法的魯棒性，研究在負載嚴重的多用戶環(huán)境下提升預測性能.