基于圖神經(jīng)網(wǎng)絡(luò)的OpenCL 程序自動優(yōu)化啟發(fā)式方法

葉貴鑫 張宇翔 張成 趙佳棋 王煥廷

（西北大學(xué)信息科學(xué)與技術(shù)學(xué)院 西安 710127）

（陜西省無源物聯(lián)網(wǎng)國際聯(lián)合研究中心（西北大學(xué)）西安 710127）

近年來，隨著大數(shù)據(jù)、人工智能技術(shù)的應(yīng)用與普及，計算機體系結(jié)構(gòu)朝著異構(gòu)化、并行化的方向發(fā)展，計算能力強、執(zhí)行效率高的異構(gòu)計算平臺是當(dāng)前環(huán)境所迫切需要的[1].為實現(xiàn)異構(gòu)并行計算，開放運算語言[2]（open computing language，OpenCL）框架應(yīng)運而生.因OpenCL 在C99—ISO/IEC 9899:1999 標(biāo)準(zhǔn)上進行了優(yōu)化擴展，因此它能夠在CPU、GPU、數(shù)字信號處理器等處理器上執(zhí)行.然而，由于異構(gòu)平臺軟硬件環(huán)境的差異，OpenCL 性能的可移植性[3]存在較大的差異，即同一個OpenCL 程序在不同異構(gòu)平臺下的執(zhí)行效率有較大差異.

現(xiàn)有的針對OpenCL 的優(yōu)化工作通常圍繞異構(gòu)并行映射及線程粗化因子預(yù)測任務(wù)展開.異構(gòu)并行映射任務(wù)旨在將目標(biāo)程序映射到合適的硬件設(shè)備上（如GPU 或CPU），以實現(xiàn)高效的執(zhí)行.線程粗化因子預(yù)測旨在為即將執(zhí)行的程序分配適當(dāng)?shù)木€程數(shù)，以實現(xiàn)系統(tǒng)開銷與程序并行執(zhí)行效率的最大收益，故需要判斷線程是否會在粗化過程中收益，從而獲得最佳的粗化因子.

針對上述2 種代碼優(yōu)化任務(wù)，現(xiàn)有的解決思路是由專家知識定義優(yōu)化特征，并利用機器學(xué)習(xí)技術(shù)構(gòu)建專家預(yù)測模型，進而推斷出執(zhí)行效率高的異構(gòu)平臺（CPU 或GPU）或最優(yōu)粗化因子[4-5]，但該類方法需要根據(jù)專家知識和經(jīng)驗人工提取特征，不僅需要較高的專家成本，也難以實現(xiàn)端到端的自動優(yōu)化.隨著深度學(xué)習(xí)技術(shù)的發(fā)展，深度學(xué)習(xí)被廣泛應(yīng)用到代碼建模相關(guān)任務(wù)中，如克隆檢測[6]、代碼自動生成[7]、漏洞檢測[8]等.近年來，研究者提出利用深度學(xué)習(xí)技術(shù)構(gòu)建代碼自動優(yōu)化預(yù)測模型[9-10].而現(xiàn)有的基于深度學(xué)習(xí)技術(shù)的優(yōu)化方法[6]，大多利用自然語言處理模型如長短期記憶（long short-term memory，LSTM）神經(jīng)網(wǎng)絡(luò)[11]、循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network,RNN）等，將代碼按照自然語言的格式進行編碼，并輸入到黑盒深度學(xué)習(xí)模型中構(gòu)建代碼優(yōu)化預(yù)測模型.這使得預(yù)測模型僅能夠捕獲代碼的順序依賴關(guān)系，而難以提取代碼所特有的深度結(jié)構(gòu)與語義信息.因此與傳統(tǒng)基于機器學(xué)習(xí)方法相比，預(yù)測效果并無明顯提升.

針對現(xiàn)有方法在上述2 種代碼優(yōu)化任務(wù)上存在的問題，本文提出了ACCEPT（automatic OpenCL code optimization heuristics），一種基于多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的OpenCL 程序自動優(yōu)化啟發(fā)式方法.該方法首先將OpenCL 代碼表示成圖數(shù)據(jù)結(jié)構(gòu)，然后利用圖神經(jīng)網(wǎng)絡(luò)[12]學(xué)習(xí)代碼圖中的深層結(jié)構(gòu)與語義信息，將圖中節(jié)點信息映射到高維的向量空間中以提取代碼的深度特征信息，最后利用全連接神經(jīng)網(wǎng)絡(luò)層構(gòu)建異構(gòu)映射和線程粗化因子預(yù)測模型.本文一方面基于程序的抽象語法樹（abstract syntax tree，AST），結(jié)合數(shù)據(jù)流圖和控制流圖以及程序中變量的傳遞、調(diào)用關(guān)系，在源代碼上構(gòu)建了一種具有多種邊關(guān)系的程序圖結(jié)構(gòu)，以增強變量間的依賴關(guān)系；另一方面，為了豐富圖中節(jié)點的特征信息，最大程度地提取代碼的特征信息，本文基于編譯器框架LLVM[13]（low level virtual machine）的中間表示形式（intermediate representation，IR），添加了順序流、控制流和數(shù)據(jù)流，在IR 代碼上構(gòu)建了一種多關(guān)系程序圖.同時，通過改進現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)[11]，使其能夠處理上述2 種類型的程序圖結(jié)構(gòu).此外，為了解決數(shù)據(jù)不足的問題，本文在線程粗化因子任務(wù)中使用了遷移學(xué)習(xí)技術(shù)[14]，用于從異構(gòu)映射任務(wù)中遷移標(biāo)注數(shù)據(jù)以改進線程粗化任務(wù)的學(xué)習(xí)效果.

為評估方法的有效性，本文在異構(gòu)映射任務(wù)與線程粗化因子預(yù)測任務(wù)上進行實驗.在異構(gòu)映射任務(wù)中，使用7 種標(biāo)準(zhǔn)數(shù)據(jù)集，在3 種平臺下與現(xiàn)有的6種經(jīng)典方法進行對比實驗.在線程粗化因子預(yù)測任務(wù)中，采用17 個OpenCL 內(nèi)核程序，在4 種平臺下與現(xiàn)有的5 種方法進行對比.實驗結(jié)果表明，在異構(gòu)映射任務(wù)中，本文方法的預(yù)測準(zhǔn)確率能夠達到88.7%，且加速比與現(xiàn)有最優(yōu)方法相比提高7.6%.在線程粗化因子的預(yù)測任務(wù)中，加速比與現(xiàn)有最優(yōu)方法相比提高5.2%.

本文的主要貢獻有3 個方面：

1）提出了一種程序圖構(gòu)建方法.該方法既能夠表征代碼的深度結(jié)構(gòu)特征，又能夠捕獲代碼的語法語義信息.

2）提出了一種基于多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的OpenCL程序自動優(yōu)化啟發(fā)式方法ACCEPT.與現(xiàn)有方法不同，該模型能夠自動提取代碼的深層次結(jié)構(gòu)和語義信息，并結(jié)合遷移學(xué)習(xí)技術(shù)進行建模，能夠有效解決訓(xùn)練數(shù)據(jù)不足的問題.

3）進行了充分的對比分析實驗.結(jié)果表明，ACCEPT在異構(gòu)映射與線程粗化任務(wù)上均優(yōu)于當(dāng)前最優(yōu)的方法，加速比相較最優(yōu)方法分別提高7.6%和5.2%.

1 相關(guān)工作

目前，主流的啟發(fā)式優(yōu)化方法均采用了機器學(xué)習(xí)和深度學(xué)習(xí)技術(shù)，機器學(xué)習(xí)的優(yōu)勢是不需要獲取硬件平臺的配置信息，僅需獲得程序的靜態(tài)及動態(tài)特征信息[4,15-16]，通過對特征自動化建模來完成編譯運行時優(yōu)化任務(wù).而現(xiàn)有工作大多數(shù)采用人工的方式篩選特征，由于編譯過程中涉及大量的解析優(yōu)化過程，使得人工挑選出的特征表征能力不強，并且挑選特征的過程耗時耗力，無法實現(xiàn)端到端的自動優(yōu)化.隨著深度學(xué)習(xí)技術(shù)的發(fā)展，研究者提出利用深度學(xué)習(xí)模型來構(gòu)建代碼優(yōu)化預(yù)測模型，即將源代碼類比成自然語言進行處理，使用深度神經(jīng)網(wǎng)絡(luò)自動提取特征，雖然實現(xiàn)了端到端的優(yōu)化，但該方法更多關(guān)注于提取代碼的順序依賴關(guān)系，而忽略了代碼所特有的語法語義與結(jié)構(gòu)信息.本節(jié)接下來分別介紹現(xiàn)有的基于傳統(tǒng)機器學(xué)習(xí)技術(shù)與基于深度學(xué)習(xí)技術(shù)的代碼優(yōu)化方法.

1.1 基于傳統(tǒng)機器學(xué)習(xí)技術(shù)的代碼優(yōu)化

Grewe 等人[4]針對異構(gòu)設(shè)備并行任務(wù)，利用決策樹算法構(gòu)建預(yù)測模型.為此，其通過獲取代碼的靜態(tài)信息如計算操作、全局內(nèi)存和局部內(nèi)存信息，以及程序執(zhí)行的動態(tài)信息如數(shù)據(jù)傳輸大小、內(nèi)核工作項大小作為代碼特征信息.而上述特征的設(shè)計需要特定領(lǐng)域的專家知識，并且僅適用于支持LLVM 的異構(gòu)設(shè)備的代碼優(yōu)化任務(wù).

Magni 等人[15]針對線程粗化因子任務(wù)研發(fā)了一套預(yù)測模型，該模型利用二元決策過程，在6 個粗化因子（1，2，4，8，16，32）中預(yù)測1 個最佳的值.模型將1 個6 分類問題轉(zhuǎn)換成遞歸的二元判斷任務(wù).例如，第1 次判斷能否從粗化中受益，若不能受益，則最佳粗化因子為1；否則進行粗化，之后再判斷是否從中受益，若不能受益，則最佳粗化因子為2；否則進行粗化并進入下一輪的遞歸判斷，直至5 次決策完成為止.文獻[15]的作者手動挑選出17 個代碼相關(guān)的特征，如程序分支語句個數(shù)、指令個數(shù)等.分別計算每個相關(guān)特征的粗化收益率，然后使用主成分分析（principal components analysis，PCA）算法，在保存信息量95%以上的前提下獲得前7 個主成分.

1.2 基于深度學(xué)習(xí)技術(shù)的代碼優(yōu)化

Cummins 等人[9]提出了一種基于文本的預(yù)測模型，該模型可直接輸入源代碼，并可以應(yīng)用于異構(gòu)映射和線程粗化2 種代碼優(yōu)化任務(wù).首先使用自定義的編碼方式為OpenCL 程序構(gòu)建字符表，并通過字符表將每個OpenCL 程序編碼成等長的數(shù)字序列；然后使用詞嵌入技術(shù)和LSTM 神經(jīng)網(wǎng)絡(luò)提取代碼特征；最后使用2 層全連接神經(jīng)網(wǎng)絡(luò)預(yù)測結(jié)果.總之，Cummins等人[9]使用基于深度學(xué)習(xí)技術(shù)的語言模型，將OpenCL程序當(dāng)作文本，從文本的順序關(guān)系中提取特征完成自動優(yōu)化任務(wù).

Cummins 等人[17]提出了一種基于文本上下文的嵌入模型.該模型的改進方法首先使用LLVM 前端將源代碼編譯成IR，從IR 中抽取數(shù)據(jù)流和控制流，為文本嵌入提供上下文信息；然后對LLVM 的 IR 進行預(yù)處理，如過濾注釋和元數(shù)據(jù)，并使用特定的字符代替其中的變量及標(biāo)識符；最后對預(yù)處理的IR 指令構(gòu)建詞匯表，將每條指令映射到嵌入空間以生成指令級的嵌入向量，利用該向量完成程序優(yōu)化任務(wù).

近年來針對OpenCL 程序啟發(fā)式優(yōu)化[6,18]的相關(guān)工作主要從依賴人工定義特征的方法過渡到依靠深度學(xué)習(xí)技術(shù)自動提取特征的方法.針對現(xiàn)有研究方法的不足，為了解決使用深度學(xué)習(xí)技術(shù)的代碼優(yōu)化方法不能夠提取到準(zhǔn)確的代碼所特有的特征信息的問題，本文提出了一種基于多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的Open-CL 程序自動優(yōu)化啟發(fā)式方法，將代碼轉(zhuǎn)換成多關(guān)系代碼圖[19]，不僅能夠獲取程序語法語義信息，還能夠捕獲程序語言的結(jié)構(gòu)信息，然后使用深度學(xué)習(xí)圖網(wǎng)絡(luò)[20]對圖數(shù)據(jù)不同關(guān)系建模，學(xué)習(xí)程序圖的特征表示并進行分類，完成相關(guān)的代碼優(yōu)化任務(wù).

2 系統(tǒng)設(shè)計與實現(xiàn)

本節(jié)主要介紹基于圖網(wǎng)絡(luò)的OpenCL 程序自動優(yōu)化啟發(fā)式方法ACCEPT 及其具體實現(xiàn)，該方法的整體框架如圖1 所示.

Fig.1 ACCEPT framwork圖 1 ACCEPT 框架

ACCEPT 以待優(yōu)化代碼的程序圖作為輸入，輸出待優(yōu)化代碼的優(yōu)化參數(shù)，如異構(gòu)映射平臺或線程粗化因子.為構(gòu)建ACCEPT 模型，需要收集大量的訓(xùn)練數(shù)據(jù)[21]，為此本文借助現(xiàn)有的生成模型CLgen[22]，合成訓(xùn)練所需的OpenCL 內(nèi)核程序.然后，對生成的OpenCL 內(nèi)核程序進行歸一化處理，以消除OpenCL內(nèi)核程序間編程風(fēng)格差異對訓(xùn)練任務(wù)的影響.接下來，使用Clang 編譯器對預(yù)處理后的OpenCL 內(nèi)核程序進行構(gòu)圖，分別在源代碼和IR 代碼層次上構(gòu)建對應(yīng)的AST 增強圖和多關(guān)系IR 圖.最后，利用改進的圖網(wǎng)絡(luò)模型，分別提取AST 增強圖和多關(guān)系IR 圖的高維特征表示，并將2 種特征向量進行拼接，利用決策網(wǎng)絡(luò)對其進行分類，完成代碼優(yōu)化相關(guān)的預(yù)測任務(wù).接下來介紹ACCEPT 的具體實現(xiàn)細節(jié).

2.1 數(shù)據(jù)生成與標(biāo)記

深度學(xué)習(xí)模型需要大量的訓(xùn)練數(shù)據(jù)，但對于代碼優(yōu)化相關(guān)的任務(wù)，當(dāng)前并沒有足夠多的公開可用的數(shù)據(jù)集.為此，本文利用現(xiàn)有的方法CLgen[22]來自動生成OpenCL 數(shù)據(jù).此外，OpenCL 代碼的運行[23]還需要有對應(yīng)的主機端代碼（host code）來驅(qū)動，用于獲取平臺信息和資源.為了構(gòu)建主機端代碼，需要對OpenCL 源代碼進行解析，以獲取主機端代碼所需要的參數(shù)信息，進而驅(qū)動內(nèi)核程序的運行，最后統(tǒng)計運行信息完成對訓(xùn)練數(shù)據(jù)的標(biāo)記.

1）OpenCL 代碼生成.為生成模型所需要的訓(xùn)練數(shù)據(jù)，本文從GitHub 中爬取了12 351 個OpenCL 文件，過濾掉無法靜態(tài)編譯與沒有實際功能的代碼文件后，最終得到5 200 個OpenCL 文件作為訓(xùn)練集，用于構(gòu)建代碼生成模型CLgen.

CLgen 主要由編碼、LSTM 神經(jīng)網(wǎng)絡(luò)、OpenCL生成和過濾器4 個模塊組成.其使用混合編碼方案[24]，對于OpenCL 語言的關(guān)鍵字等使用基于字（token）的編碼方案；對于用戶自定義的標(biāo)識符、函數(shù)名等使用基于字符的編碼方案，其目的是為了平衡詞匯表規(guī)模、保留代碼語義.LSTM 神經(jīng)網(wǎng)絡(luò)模塊的作用是提取代碼的高維抽象特征，LSTM 循環(huán)單元結(jié)構(gòu)能夠有效學(xué)習(xí)代碼token 之間的順序依賴關(guān)系，CLgen 使用2 層LSTM 網(wǎng)絡(luò)，每層網(wǎng)絡(luò)設(shè)置256 個神經(jīng)元，訓(xùn)練過程中循環(huán)迭代20 次，學(xué)習(xí)率設(shè)為0.01.OpenCL 合成模塊通過迭代采樣的方式生成OpenCL 內(nèi)核程序，主要將LSTM 層輸出的向量解碼成對應(yīng)的代碼.本文將生成OpenCL 內(nèi)核程序的最大字符長度設(shè)置為5 000.最后再利用過濾器模塊移除靜態(tài)解析失敗、編譯失敗以及運行超時等無效的OpenCL 內(nèi)核程序，最終得到11 081 條可用的數(shù)據(jù).

2）驅(qū)動代碼生成.為了構(gòu)造主機端代碼，本文首先對OpenCL 源代碼進行解析，獲取驅(qū)動相關(guān)信息如函數(shù)名、參數(shù)、工作組及傳輸值，將其寫入固定的主機端代碼模板.然后獲取設(shè)備信息組成上下文信息，設(shè)置消息隊列存放需要運行的內(nèi)核代碼，因此驅(qū)動代碼定義了內(nèi)核程序執(zhí)行前的通用流程，僅需對運行的內(nèi)核程序提取必要信息寫入驅(qū)動代碼即可.

3）訓(xùn)練數(shù)據(jù)標(biāo)記.為了獲得訓(xùn)練數(shù)據(jù)對應(yīng)的標(biāo)簽，本文數(shù)據(jù)程序分別在CPU 和GPU 上運行，以計算出在OpenCL 內(nèi)核程序上的實際運行時間與置信區(qū)間.為此，首先在主機端代碼模板中設(shè)置宏參數(shù)，以獲取程序執(zhí)行的時間戳、開始執(zhí)行時間與結(jié)束執(zhí)行時間，進而獲取內(nèi)核程序的實際執(zhí)行時間.然后，將OpenCL 內(nèi)核程序分別在CPU 和GPU 上重復(fù)執(zhí)行，統(tǒng)計出程序在CPU 和GPU 上執(zhí)行時間的置信區(qū)間，最終選擇執(zhí)行時間最短的平臺作為內(nèi)核程序的標(biāo)簽.

2.2 代碼預(yù)處理

為了降低不同編碼風(fēng)格對深度學(xué)習(xí)模型的影響，需要對OpenCL 代碼進行歸一化處理.為此，首先應(yīng)用CLgen 對OpenCL 內(nèi)核程序進行標(biāo)準(zhǔn)化處理，去除與優(yōu)化任務(wù)無關(guān)的冗余信息，如刪除宏定義指令、刪除條件編譯與注釋、解析AST 以及統(tǒng)一變量命名風(fēng)格等.標(biāo)準(zhǔn)化簡化了多關(guān)系圖網(wǎng)絡(luò)對源代碼的建模任務(wù)的復(fù)雜性，消除了程序中無關(guān)的語義信息對模型的干擾，進而降低模型復(fù)雜度.圖2 展示了預(yù)處理前后的對比圖.可以看出，注釋、變量或函數(shù)的命名與程序員的編碼習(xí)慣相關(guān)，這可能導(dǎo)致對模型學(xué)習(xí)的干擾.刪除注釋并不會影響代碼的語法語義信息，同時對變量及函數(shù)名進行標(biāo)準(zhǔn)化處理，以減小微小語義差異對模型造成的影響.

Fig.2 Comparison before and after preprocessing圖 2 預(yù)處理前后對比

具體地，首先解析出OpenCL 內(nèi)核程序的AST，遍歷AST 樹，根據(jù)樹中節(jié)點的類型刪除條件編譯、源代碼注釋.對編譯預(yù)處理的宏指令譬如#include 開頭的標(biāo)識符進行逐一替換.對于變量（VarDecl）及函數(shù)聲明（FunDecl）的節(jié)點，順序替換為統(tǒng)一的字符，如用戶自定義的方法名與變量名分別按照先后順序替換為{A,B,…,Z}與{a,b,…,z}.

2.3 多關(guān)系代碼圖構(gòu)建方法

為準(zhǔn)確地表示程序深度語法、語義及結(jié)構(gòu)特征信息，本文在源碼AST 的基礎(chǔ)上設(shè)計了5 種類型的邊關(guān)系，構(gòu)造了AST 增強圖.同時，基于LLVM 的IR設(shè)計了3 種邊關(guān)系，構(gòu)造了多關(guān)系IR 圖.

2.3.1 代碼圖關(guān)系說明

在AST 層面，本文在AST 樹的基礎(chǔ)上構(gòu)建源代碼的語法語義關(guān)系，首先使用Clang 編譯器對OpenCL代碼進行語法分析，得到OpenCL 源碼的AST，程序圖的主體是程序的抽象語法樹，樹中的節(jié)點由語法結(jié)點和語法令牌（Token）組成.其中語法節(jié)點是非葉子節(jié)點，語法Token 是樹中的終端節(jié)點，節(jié)點的屬性字段（字符串）標(biāo)識了節(jié)點的類型.然后由根節(jié)點開始深度搜索AST 樹，在遍歷過程中，根據(jù)節(jié)點的類型構(gòu)建了5 種邊關(guān)系：ASTChild 邊、ComputedFrom 邊、NextToken 邊、GuardedBy 邊、Jump 邊.同樣地，在IR層面，通過LLVM 內(nèi)置函數(shù)可以直接獲得數(shù)據(jù)流和控制流信息，同時為了記錄IR 節(jié)點的順序，構(gòu)建了IR 順序流，如圖3 所示.

表1 列舉了不同的邊類型，接下來將詳細介紹2種圖中各種類型邊的含義.

2.3.2 AST 增強圖邊類型

圖4 展示了AST 增強圖中邊的類型，接下來詳細介紹各種邊的構(gòu)建.

1）ASTChild 邊.ASTChild 邊連接了父節(jié)點和子節(jié)點，用于表征代碼的抽象結(jié)構(gòu)化信息，它代表一個程序圖的基本結(jié)構(gòu).通過Clang 編譯器獲得AST 樹的根節(jié)點，基于根節(jié)點深度遍歷獲得AST 的其他節(jié)點，本文使用ASTChild 邊構(gòu)建OpenCL 代碼的基本圖結(jié)構(gòu).

Fig.3 LLVM IR instruction圖 3 LLVM IR 指令

Table 1 Program Diagram Connection Relationship表 1 程序圖連接關(guān)系

Fig.4 AST augment graph圖 4 AST 增強圖

2）ComputedFrom 邊.ComputedFrom 邊連接了等式左右兩邊變量的賦值關(guān)系，用于記錄代碼的數(shù)據(jù)流，在內(nèi)核程序中存在著較多的賦值語句，變量的賦值使用ComputedFrom 邊進行存儲.

3）Jump 邊.Jump 邊記錄了跳轉(zhuǎn)語句的跳轉(zhuǎn)方向，用于表征代碼的控制流，程序語句的跳轉(zhuǎn)可以控制程序運行的結(jié)果，例如常見的循環(huán)語句、判斷語句等，Jump 邊控制著程序執(zhí)行的路徑，是程序特有的重要特征.

4）NextToken 邊.NextToken 邊連接 了AST 樹 中同一層的葉子節(jié)點，其記錄了節(jié)點之間的順序關(guān)系，進而豐富了代碼的上下文依賴信息.

5）GuardedBy 邊.GuardedBy 邊將條 件語句中的變量與其作用域相同的變量相連，用于表征程序的控制流.對于條件語句而言，條件表達式會影響程序的執(zhí)行流程，同時，表達式中變量的值也會影響程序控制流的跳轉(zhuǎn)方向.因此，為了捕獲復(fù)雜的控制依賴關(guān)系，本文使用GuardedBy 邊記錄條件語句中變量的關(guān)系.例如，對于條件語句if（x＞y）{…x…} else {…y…}，使用GuardedBy 邊將if 域中的x與表達式x＞y相連，將else 域中的y與表達式x＞y相連.

為了進一步捕獲控制依賴信息，Jump 邊用來連接所有的跳轉(zhuǎn)依賴關(guān)系，包含if，switch…case，while，for，do…while 所形成的跳轉(zhuǎn)關(guān)系.在上述跳轉(zhuǎn)指令中，本文將判斷表達式與所有跳轉(zhuǎn)域中的第一個變量相連以捕獲跳轉(zhuǎn)關(guān)系.

2.3.3 IR 多關(guān)系圖邊類型

1）IR 順序流邊.IR 順序流邊連接了當(dāng)前指令與下一條指令，用于記錄LLVM IR 指令的順序關(guān)系，同樣地，這種順序關(guān)系對于圖網(wǎng)絡(luò)而言也是不可或缺的.如圖3 為內(nèi)核程序?qū)?yīng)的IR 指令，IR 順序流邊記錄圖中每條指令的執(zhí)行順序.

2）IR 數(shù)據(jù)流邊.同樣，在IR 層面中，IR 數(shù)據(jù)流邊連接變量的調(diào)用關(guān)系，記錄了寄存器中變量的賦值過程與走向，是IR 指令的重要特征.

3）IR 控制流邊.IR 控制流連接了跳轉(zhuǎn)指令與下一條指令.在遇到br 等跳轉(zhuǎn)指令時會記錄指令的跳轉(zhuǎn)方向，與AST 層面的Jump 邊類似，IR 控制流邊記錄指令的跳轉(zhuǎn)路徑.

同樣地，在IR 層面通過LLVM 內(nèi)置函數(shù)獲得IR 的數(shù)據(jù)流和控制流信息并進行向量存儲，為了記錄IR的執(zhí)行順序，本文增加了順序流邊，該邊有效記錄了指令的執(zhí)行順序.圖5 展示了所構(gòu)建的IR 多關(guān)系圖.

2.3.4 多關(guān)系代碼圖的構(gòu)建

Fig.5 IR multi-relationship graph圖 5 IR 多關(guān)系圖

多關(guān)系代碼圖的構(gòu)建如算法1 所示.該算法以O(shè)penCL 源碼為輸入，通過分析源碼的AST 與IR 中的數(shù)據(jù)控制依賴關(guān)系，輸出二元組（GAST,GIR），分別存儲對應(yīng)的AST 增強圖GAST與多關(guān)系IR 圖GIR.

算法1.多關(guān)系代碼圖生成算法.

具體地，為構(gòu)建GAST，利用Clang 編譯器提取代碼的AST，從根節(jié)點逐層遍歷AST，在遍歷AST 的過程中，利用游標(biāo)（算法1 中變量Cursor）的類型來判斷AST 邊的類型，并在對應(yīng)的AST 節(jié)點位置分別添加ASTChild 邊、NextToken 邊、ComputedFrom 邊、GuardedBy 邊以及Jump 邊（如算法1 中行④～?），進而完成GAST的構(gòu)建.另一方面，為構(gòu)建IR 多關(guān)系圖，使用Clang 編譯器將OpenCL 內(nèi)核程序轉(zhuǎn)換成LLVM的IR，利用程序分析技術(shù)解析IR 并定位到第1 個基本塊，然后順序遍歷基本塊中的指令（如算法1 中行?～?），在遍歷指令過程中，向GIR中依次添加IR 順序流、數(shù)據(jù)流以及控制流（如算法1 中行?～?）.最終，算法返回二元組（GAST,GIR）（如算法1 中行?）.

為將所構(gòu)建的代碼圖表示成深度學(xué)習(xí)模型能夠處理的數(shù)據(jù)形式，ACCEPT 使用鄰接矩陣表示圖的節(jié)點間的連接關(guān)系，即當(dāng)2 個節(jié)點之間存在邊時，則將鄰接矩陣中對應(yīng)位置置為1，否則置為0.由于GAST存在5 種類型的邊，GIR存在3 種類型的邊，每種類型的邊都需要使用1 個鄰接矩陣表示，因此共需要8 個鄰接矩陣表示（GAST,GIR）.同時，為了豐富圖中節(jié)點之間的連接信息，通過轉(zhuǎn)置鄰接矩陣，為圖添加反向邊，增強圖神經(jīng)網(wǎng)絡(luò)對節(jié)點間關(guān)系的學(xué)習(xí)能力.

2.3.5 多關(guān)系代碼圖節(jié)點特征提取

ACCEPT 使用Word2Vec[25]對代碼圖中每個節(jié)點進行編碼，其能夠?qū)蝹€詞映射到連續(xù)向量空間，這有助于學(xué)習(xí)代碼的語法與語義關(guān)系.例如，聲明類的節(jié)點更容易被映射到相近的向量空間中，模型可以學(xué)習(xí)if-else 語句的順序關(guān)系等.為了保存節(jié)點間豐富的信息，本文將每個Token 和單詞映射到100 維固定長度的嵌入向量.

為對代碼圖中的節(jié)點進行編碼，ACCEPT 利用深度優(yōu)先遍歷，首先從根節(jié)點遍歷代碼圖，定位節(jié)點類型，如AST 增強圖中的節(jié)點類型包括根節(jié)點（TranslationUnit）、參數(shù)說明（ParmDecl）等，多關(guān)系IR 圖中節(jié)點類型主要包括call，icmp，load 等.然后利用Skip-Gram 嵌入算法學(xué)習(xí)節(jié)點類型和節(jié)點上下文之間的關(guān)系，該嵌入方法根據(jù)節(jié)點類型出現(xiàn)的頻率構(gòu)建詞匯表，然后根據(jù)詞匯表中節(jié)點類型抽取對應(yīng)的特征向量，以構(gòu)建圖節(jié)點的特征矩陣.此外，為盡可能減小詞匯表大小，本文對變量、函數(shù)名以及常數(shù)采用Token級別的編碼方式.

2.4 多關(guān)系圖神經(jīng)網(wǎng)絡(luò)建模

為了能夠準(zhǔn)確地對多關(guān)系代碼圖建模，并提取OpenCL 代碼的深度結(jié)構(gòu)和語義特征，本文提出了一種多關(guān)系圖深度神經(jīng)網(wǎng)絡(luò)模型，該網(wǎng)絡(luò)在關(guān)系圖卷積網(wǎng)絡(luò)（relational graph convolutional network，RGCN）的基礎(chǔ)上，通過改進其輸入結(jié)構(gòu)、鄰域聚合與節(jié)點信息傳播策略，使其能夠處理具有多種邊類型的多關(guān)系代碼圖，同時可以針對不同類型的邊進行特征提取，以便學(xué)習(xí)更深層的代碼特征，提取OpenCL 代碼的高維抽象特征向量.為此，多關(guān)系圖網(wǎng)絡(luò)模型以鄰接矩陣與節(jié)點特征矩陣為輸入，利用鄰域聚合算法，按照邊類型對圖中節(jié)點信息進行更新，最后使用圖嵌入策略完成一輪特征提取.為實現(xiàn)多跳節(jié)點之間的特征信息交互，需要在圖網(wǎng)絡(luò)中進行多輪迭代特征提取，以完成對多關(guān)系中所有的節(jié)點特征的更新，輸出OpenCL 代碼的高維抽象特征.接下來，將詳細介紹鄰域聚合與圖嵌入的具體實現(xiàn).

2.4.1 鄰域聚合

為了學(xué)習(xí)程序的高維抽象表示，在圖網(wǎng)絡(luò)中需要遞歸更新圖中每個節(jié)點的特征表示，這通過對鄰域節(jié)點的特征進行聚合操作來實現(xiàn)，以學(xué)習(xí)節(jié)點鄰域信息，從而找到每個節(jié)點更加準(zhǔn)確的抽象表示.鄰域聚合表達式為

其中，l為鄰域聚合的結(jié)果，節(jié)點u是當(dāng)前節(jié)點v的鄰域，N(v)是節(jié)點v的鄰域集，是節(jié)點u第t層的更新特征.鄰域信息的聚合能夠有效地傳遞節(jié)點的信息，為后續(xù)的圖嵌入過程提供信息交互的支持.

由2.3.5 節(jié)可知，節(jié)點特征的初始化任務(wù)由Word2-Vec 模型得到.每一次迭代都將更新節(jié)點當(dāng)前狀態(tài)，并將其作為消息發(fā)送給圖中的所有鄰域節(jié)點來交換信息.當(dāng)每個頂點完成消息聚合后，當(dāng)前節(jié)點狀態(tài)將被用于下一次迭代的鄰域聚合過程.重復(fù)此迭代更新步驟直至達到固定的迭代次數(shù).當(dāng)完成固定迭代次數(shù)的更新后，網(wǎng)絡(luò)將輸出學(xué)習(xí)到的節(jié)點特征矩陣.本文將節(jié)點特征矩陣按行展開聚合，組成新的一維特征向量，即為OpenCL 程序的高維抽象特征向量.

2.4.2 圖嵌入

圖嵌入旨在更新節(jié)點的特征信息，完成節(jié)點間的信息傳遞.接下來以AST 增強圖為例，詳細說明圖嵌入具體過程.

假設(shè)OpenCL 程序?qū)?yīng)的AST 增強圖表示為G=〈V,E〉，其中V為節(jié)點的集合，E為邊的集合，E={EAST,ENT,EGB,EJump,ECF}，集合中的邊分別對應(yīng)ASTChild 邊、NextToken 邊、GuardedBy 邊、Jump 邊以及ComputedFrom 邊.首先根據(jù)邊類型進行鄰域聚合，假設(shè)Word2Vec 初始化的節(jié)點特征矩陣為X，更新特征為 μ，則 μ的計算公式為

特征矩陣X與每種邊構(gòu)建的圖進行消息傳遞，生成每種邊獨有的新的節(jié)點特征，最終將5 種特征矩陣進行聚合，完成邊類型的特征提取.類似地，IR 多關(guān)系圖的嵌入同樣經(jīng)過AST 增強圖嵌入流程完成3種邊類型的特征提取.具體的嵌入過程如圖6 所示.

Fig.6 Graph embedding process圖 6 圖嵌入過程圖

首先將節(jié)點特征向量 μ以及二元組（GAST,GIR）輸入嵌入層，假設(shè)當(dāng)前節(jié)點v的特征向量為Xv，節(jié)點u是當(dāng)前節(jié)點v的鄰域，為了學(xué)習(xí)每個節(jié)點的嵌入向量，過程為：設(shè)置當(dāng)前節(jié)點特征向量Xv的初始化權(quán)重矩陣W0，第i輪更新的鄰域節(jié)點集聚合成之后進入n輪嵌入過程，每一輪迭代嵌入使用修正線性單元（rectified linear unit）激活函數(shù)，記為ReLU，用于過濾噪聲，經(jīng)過n輪嵌入后使用tanh 激活函數(shù)，與當(dāng)前節(jié)點特征疊加再使用ReLU激活后獲得當(dāng)前節(jié)點第i+1輪的節(jié)點更新，完成更新后獲得OpenCL 代碼的特征矩陣，最后將特征矩陣逐行展開并聚合為一維的特征向量，該特征向量即為代碼的高維特征表示.上述迭代更新嵌入過程表示為：

2.5 決策網(wǎng)絡(luò)

決策網(wǎng)絡(luò)的目的是預(yù)測代碼優(yōu)化參數(shù)，如異構(gòu)設(shè)備映射或線程粗化因子，其輸入是多關(guān)系圖神經(jīng)網(wǎng)絡(luò).圖7 展示了決策網(wǎng)絡(luò)的架構(gòu)，可以看出，決策網(wǎng)絡(luò)由向量拼接層、批歸一化層以及全連接層組成.

Fig.7 The structure of decision network圖 7 決策網(wǎng)絡(luò)結(jié)構(gòu)

向量拼接層將多關(guān)系圖神經(jīng)網(wǎng)絡(luò)層學(xué)習(xí)到的特征向量（AST 增強圖特征向量與IR 多關(guān)系圖特征向量）以及輔助輸入聚合成固定長度的一維特征向量.輔助輸入是程序的動態(tài)運行特征，如程序運行內(nèi)存大小、棧內(nèi)存大小等.由于輔助輸入的值并不在[0，1]范圍內(nèi)，使得輔助輸入與嵌入向量具有不同的量綱，將導(dǎo)致訓(xùn)練時間過長、模型難以收斂.因此使用歸一化層，將拼接好的特征向量的值標(biāo)準(zhǔn)化在[0，1]范圍內(nèi).標(biāo)準(zhǔn)化的特征向量能夠捕獲代碼的諸多特征，例如語義相似性、控制流、依賴流等.最后標(biāo)準(zhǔn)化的特征向量將被送入全連接層神經(jīng)網(wǎng)絡(luò)進行分類，完成優(yōu)化預(yù)測任務(wù).

2.6 模型訓(xùn)練

ACCEPT 使用反向傳播機制協(xié)同訓(xùn)練圖網(wǎng)絡(luò)和決策網(wǎng)絡(luò).與大多數(shù)機器學(xué)習(xí)訓(xùn)練方法不同，ACCEPT 不必手動從程序中構(gòu)建和提取特征，只需輸入源代碼，就能實現(xiàn)端到端的優(yōu)化預(yù)測.訓(xùn)練過程中，本文使用隨機梯度下降（stochastic gradient descent，SGD）算法，并結(jié)合Adam 優(yōu)化器[26]加速模型的收斂速度，使用標(biāo)準(zhǔn)交叉熵損失函數(shù)作為目標(biāo)函數(shù)，使用常用于分類任務(wù)的Sigmoid 和Softmax 激活函數(shù).目標(biāo)函數(shù)定義為

其中N是分類的數(shù)目，在異構(gòu)設(shè)備映射任務(wù)中N=2，在線程粗化任務(wù)中N=6；yi,c的取值為0 或1，表示標(biāo)簽c是否是訓(xùn)練樣本i的正確分類；pi是樣本i屬于標(biāo)簽c的預(yù)測概率.隨機梯度下降將尋找適合的參數(shù)使得最小化損失函數(shù)，即減小預(yù)測值與期望值的對數(shù)差異進而完成模型的訓(xùn)練.

3 實驗設(shè)置

3.1 實驗平臺

本文采用TensorFlow 深度學(xué)習(xí)框架構(gòu)建多關(guān)系圖神經(jīng)網(wǎng)絡(luò)模型.所有實驗均運行在Ubuntu 16.04 操作系統(tǒng)上，其內(nèi)存為12GB，CPU 處理器為Intel Xeon E5-2 667，編程語言為Python 3.6.

3.2 數(shù)據(jù)集構(gòu)成

異構(gòu)設(shè)備映射任務(wù)采用了DeepTune[9]提供的數(shù)據(jù)集，該數(shù)據(jù)集從7 個benchmark 集（Parboil[27]，NVIDIA CUDA SDK[28]，AMD SDK[29]，SHOC[30]，NPB[31]，Rodinia[32]，PolyBench[33]）中抽取256 個OpenCL 內(nèi)核程序，通過改變輔助輸入將其擴充至680 條數(shù)據(jù).

線程粗化任務(wù)采用了DeepTune[9]給定的標(biāo)記數(shù)據(jù)，該數(shù)據(jù)集從3 個benchmark 集（Parboil[27]，NVIDIA CUDA SDK[28]，AMD SDK[29]）中抽取 了17 個OpenCL內(nèi)核程序.其中Parboil 4 個，NVIDIA CUDA SDK 3 個，AMD SDK 10 個.

3.3 評估指標(biāo)

為評估ACCEPT 對異構(gòu)平臺映射與線程粗化因子預(yù)測的性能，選取準(zhǔn)確率（Accuracy）和加速比（Speedup）作為評估指標(biāo).準(zhǔn)確率指模型預(yù)測正確的個數(shù)與測試數(shù)據(jù)總數(shù)的比值.加速比指同一程序在目標(biāo)設(shè)備上的運行時間與在靜態(tài)映射上的執(zhí)行時間的比值，本文中靜態(tài)映射為AMD 平臺.準(zhǔn)確率計算為

其中m為測試集的個數(shù)，true_labeli為 第i個測試數(shù)據(jù)的預(yù)測結(jié)果.加速比計算為

其中m為測試集的個數(shù)，static_timei為第i個測試數(shù)據(jù)對應(yīng)的靜態(tài)映射時間，predict_timei為模型第i個測試數(shù)據(jù)預(yù)測最優(yōu)設(shè)備上的執(zhí)行時間.加速比的結(jié)果由對所有測試數(shù)據(jù)的靜態(tài)映射時間（在靜態(tài)映射上的執(zhí)行時間）與預(yù)測時間的比值求和再取平均得到，實驗中加速比的值為每種benchmark 下的幾何平均值.

為驗證ACCEPT 的有效性，在所有實驗中本文采用10 折交叉驗證，實驗的準(zhǔn)確率與加速比為10 次實驗的平均值，從而減小噪聲數(shù)據(jù)對實驗結(jié)果的影響.

4 實驗結(jié)果與分析

4.1 實驗概況

本文分別在異構(gòu)設(shè)備映射與線程粗化因子預(yù)測2 個代碼優(yōu)化任務(wù)上評估ACCPET 的有效性.同時，分別與現(xiàn)有的經(jīng)典代碼優(yōu)化方法進行對比實驗，充分驗證ACCEPT 的有效性，如表2 所示.

Table 2 Comparison of Machine Learning Methods表 2 機器學(xué)習(xí)方法對比

為保證對比實驗的公平性，本文使用自動化模型調(diào)優(yōu)工具AutoML（automated machine learning）對所有未公布訓(xùn)練模型參數(shù)（如學(xué)習(xí)率、Batch Size、Epoch等參數(shù)）的待比較代碼優(yōu)化方法進行訓(xùn)練調(diào)優(yōu)，使其均能夠達到最優(yōu)的實驗結(jié)果.在對比實驗?zāi)Ｐ陀?xùn)練過程中，均統(tǒng)一采用10 折交叉驗證，在每一輪交叉驗證中，若損失函數(shù)在連續(xù)20 個訓(xùn)練輪次內(nèi)無下降，或者在驗證集上達到99%以上的準(zhǔn)確率，則終止訓(xùn)練.

4.2 異構(gòu)設(shè)備映射任務(wù)

OpenCL 是一個面向異構(gòu)并行程序編寫代碼的框架，使用OpenCL 編寫的程序可以透明地在多個設(shè)備上運行，例如GPU 或CPU 等異構(gòu)設(shè)備.異構(gòu)設(shè)備映射任務(wù)的目的是預(yù)測OpenCL 程序最佳的執(zhí)行設(shè)備，以提高程序執(zhí)行的加速比.故模型預(yù)測結(jié)果的準(zhǔn)確性是提高程序加速比的前提條件，也是異構(gòu)設(shè)備映射任務(wù)評估的主要指標(biāo).

4.2.1 實驗方法

該實驗所用的異構(gòu)平臺分別為AMD Tahiti 7970，NVIDIA GTX 970.因模型訓(xùn)練需要足夠的訓(xùn)練數(shù)據(jù)，而現(xiàn)有公開可用的數(shù)據(jù)并不充足，因此在準(zhǔn)確率實驗評估中，本文使用OpenCL 程序生成器CLgen 生成了11 081 個有效且可編譯的OpenCL 內(nèi)核程序并在3.2 GHz 6 核 Xeon E5-2667CP U 和NVIDIA Titan XP GPU 的平臺上進行標(biāo)記，將標(biāo)記的數(shù)據(jù)作為訓(xùn)練集，測試集使用DeepTune[7]方法中所公開的680 個標(biāo)準(zhǔn)的OpenCL 內(nèi)核程序.

4.2.2 對比實驗

表2 前6 種代碼優(yōu)化方法為該實驗的對比對象，包括：Grewe 等人[4]，其使用手工特征和決策樹算法構(gòu)建代碼優(yōu)化模型；DeepTune[9]與DeepTune IR[17]分別使用源代碼的Token 序列和LLVM IR 序列做代碼表征，并都使用了LSTM 模型；Inst2Vec[34]使用LLVM IR 生成的圖作為代碼表征和LSTM 模型；GNN-AST與GNN-CDFG 分別使用AST 圖以及CDFG 圖提取代碼特征，這2 種方法使用了基于圖網(wǎng)絡(luò)變體模型.此外，對于異構(gòu)設(shè)備映射任務(wù)，該實驗保留了原有方法的設(shè)置，使用程序執(zhí)行的動態(tài)信息（如工作組大小和數(shù)據(jù)大小）作為模型的輔助輸入.

4.2.3 實驗結(jié)果與分析

圖8 展示了在不同平臺下ACCEPT 與其他方法的加速比對比結(jié)果.由圖8 可知，無論是在早期的GPU 平臺如NVIDIA GTX 970，還是在最新的NV IDIA Titan XP 上，ACCEPT 優(yōu)化后的加速比均優(yōu)于其他經(jīng)典的代碼優(yōu)化方法.在AMD Tahiti 7970 平臺上，ACCEPT 取得了平均3.18×的加速比；在NVIDIA Titan XP 平臺上，ACCEPT 的加速比能夠達到2.6×，比其他方法平均提高至少25%.雖然ACCEPT 在NVIDIA GTX 970 平臺上的性能提升相對較小，為1.31×，但其總體加速比相比其他方法最高.

Fig.8 Comparison results of speedup圖 8 加速比對比結(jié)果

由實驗結(jié)果推斷，ACCEPT 能夠利用構(gòu)建的多關(guān)系圖和改進的多關(guān)系圖神經(jīng)網(wǎng)絡(luò)，有效地提取代碼的深度結(jié)構(gòu)和語義特征.具體表現(xiàn)在：僅通過構(gòu)建OpenCL 代碼的抽象語法特征圖（如GNN-AST 方法），或者僅構(gòu)建代碼數(shù)據(jù)依賴圖（如GNN-CDFG 方法），所取得的加速比都沒有ACCEPT 高.這說明，本文所構(gòu)建的AST 增強圖和IR 多關(guān)系圖更有助于提取代碼的高維抽象特征.

進一步地，為了深入分析ACCEPT 的性能，本文統(tǒng)計了異構(gòu)映射的準(zhǔn)確率.圖9 展示了在不同平臺下準(zhǔn)確率對比評估結(jié)果，與DeepTune 和Inst2Vec 相比，ACCEPT 能夠?qū)?zhǔn)確率從82%提高到88.7%，并且ACCEPT 能夠以最高的概率預(yù)測出最佳的異構(gòu)映射平臺.直觀上，預(yù)測準(zhǔn)確率越高，其相對加速比就越高，因此由圖9 可以看出，準(zhǔn)確率總體趨勢和加速比一致，這也是ACCEPT 能夠取得最高加速比的原因.

Fig.9 Comparison results of accuracy圖 9 準(zhǔn)確率對比結(jié)果

4.3 線程粗化任務(wù)

線程粗化任務(wù)的對象是并行執(zhí)行的程序，其目的是選擇待執(zhí)行程序的最佳線程粗化因子，即需要并行執(zhí)行的線程數(shù)量，從而達到系統(tǒng)開銷與程序并行執(zhí)行效率的最佳平衡點.該實驗具體的量化指標(biāo)是加速比，程序在某個線程粗化因子下的加速比越高，說明其執(zhí)行效率越高.與現(xiàn)有工作相同，該評估實驗中分別設(shè)置6 種粗化因子，分別為1,2,4,8,16,32，其中粗化因子為1 表示不進行線程粗化，其對應(yīng)的加速比值為基準(zhǔn)值.

4.3.1 實驗方法

為驗證ACCEPT 在線程粗化任務(wù)上的有效性，該實驗分別在AMD Radeon HD 5900，AMD Tahiti 7970，NVIDIA GTX 480,NVIDIA Tesla K20c 這4 個平臺上進行.由于線程粗化任務(wù)中僅有公開可用的17個OpenCL 內(nèi)核程序，為了訓(xùn)練ACCEPT，該實驗使用DeepTune[7]公開的680 條OpenCL 內(nèi)核程序數(shù)據(jù)做訓(xùn)練，然后再利用遷移學(xué)習(xí)技術(shù)，使用留一法評估模型.具體地，將17 條數(shù)據(jù)分成17 份，并將每份數(shù)據(jù)按照訓(xùn)練與測試16∶1 的比例進行分割，每次遷移時，使用16 條數(shù)據(jù)作為訓(xùn)練集，剩余1 條作測試，因此在每個平臺上的評估實驗最終會訓(xùn)練出17 個模型，將17 個模型加速比的幾何平均值作為該平臺上的評估結(jié)果.

4.3.2 對比實驗

為充分評估ACCEPT 的有效性，該實驗分別與DeepTune,Inst2Vec,GNN-CDFG,GNN-AST 以及文獻[15]中的方法共計5 種方法進行比較.其中文獻[15]使用人工特征提取的方法，將OpenCL 內(nèi)核程序所占用內(nèi)存及指令數(shù)等靜態(tài)信息作為特征，在特征中使用主成分分析法獲取高維特征表示，然后使用基于二元決策樹的方法預(yù)測線程粗化因子.此外，該實驗還比對了在不同平臺下線程粗化任務(wù)的最優(yōu)加速比，即如圖10 中Oracle.

Fig.10 Comparison of speedup圖 10 加速比對比

4.3.3 實驗結(jié)果與分析

圖10 展示了在不同平臺下各種方法的對比實驗結(jié)果.由圖10 可以看出，ACCEPT 整體上的性能表現(xiàn)優(yōu)于現(xiàn)有的代碼優(yōu)化方法.例如，在AMD Radeon HD 5900 平臺上，ACCEPT 能將加速比提高到1.26×，其提升性能略高于DeepTune 的加速比，并且遠高于其他方 法.在NVIDIA GTX 480 平臺上，ACCEPT 是唯一高于基準(zhǔn)加速比（即基準(zhǔn)為1）的方法，其加速比為1.02×，而其他方法均低于基準(zhǔn)加速比.在其他方法中，DeepTune 與 GNN-CDFG 在 NVIDIA Tesla K20c，NVIDIA GTX 480，AMD Tahiti 7970 這3 個平臺上的加速比均低于基準(zhǔn)值，這說明使用人工定義的特征或使用控制數(shù)據(jù)依賴特征并不能夠提取到代碼的深度特征信息.雖然DeepTune 的性能與ACCEPT 接近，但其微小的差距也說明了利用LSTM 并不能夠有效地對代碼進行特征建模，而ACCEPT 使用多關(guān)系圖網(wǎng)絡(luò)，能夠有效地提取代碼圖中的結(jié)構(gòu)與語義信息.

總的來說，與其他方法相比，ACCEPT 在4 個異構(gòu)平臺上均有性能的提升，尤其在AMD Radeon HD 5900 上的性能提升最顯著.同時從實驗結(jié)果來看，ACCEPT 可以在訓(xùn)練語料庫較小時有效地支持遷移學(xué)習(xí).由此可以看出，ACCEPT 不僅在異構(gòu)映射任務(wù)上取得了最好的結(jié)果，而且在線程粗化任務(wù)上也取得了較好的結(jié)果，充分說明了ACCEPT 對于代碼特征的提取能力，是一種有效的代碼優(yōu)化啟發(fā)式方法.

4.4 數(shù)據(jù)生成質(zhì)量分析

在異構(gòu)映射任務(wù)中，本文使用生成的OpenCL 程序內(nèi)核數(shù)據(jù)訓(xùn)練ACCEPT 模型.程序生成的質(zhì)量將直接影響模型的預(yù)測準(zhǔn)確率，為評估程序生成的質(zhì)量，本實驗分別對所生成的OpenCL 程序的可用性及編碼質(zhì)量進行評估.

4.4.1 OpenCL 程序可用性評估

為驗證所生成OpenCL 內(nèi)核程序的可用性，該評估實驗分別在Intel Xeon E5-2667 和NVIDIA Titan XP這2 個平臺上進行，實驗平臺的具體參數(shù)如表3 所示.對于生成數(shù)據(jù)，通過統(tǒng)計其在編譯過程中出現(xiàn)編譯失敗、編譯異常、編譯超時以及運行過程中出現(xiàn)運行錯誤和超時的內(nèi)核程序的數(shù)量來評估生成的OpenCL 內(nèi)核程序的可用性.該實驗的數(shù)據(jù)為20 000個生成的OpenCL 內(nèi)核程序.

Table 3 Platform Arguments for Evaluation of Program Generation Quality表 3 程序生成質(zhì)量評估平臺具體配置信息

實驗結(jié)果如表4 所示，在Intel Xeon E5-2667 設(shè)備上，編譯階段失敗、異常和超時的內(nèi)核程序數(shù)量分別為234，78，44，運行階段失敗與超時的數(shù)量分別為744 和127，共計有1 227 個低質(zhì)量的OpenCL 內(nèi)核程序，即大約有93.9%的內(nèi)核程序能夠通過編譯及運行；在NVIDIA Titan XP 平臺上，大約有1 381 個內(nèi)核程序沒有通過編譯及運行.這2 個平臺下最終得到的OpenCL 內(nèi)核程序數(shù)量不一致，這是因為不同平臺下所使用的硬件驅(qū)動不同，并且不同平臺的編譯及運行情況也不同.總之，在2 個平臺上，平均能夠生成93%以上的可用的OpenCL 內(nèi)核程序.

Table 4 Results of Program Quality Evaluation表 4 程序質(zhì)量評估結(jié)果

4.4.2 OpenCL 程序雙盲實驗評估

生成數(shù)據(jù)與真實數(shù)據(jù)是否符合同一個概率分布，關(guān)系到訓(xùn)練出的模型是否能夠?qū)嵱?即若生成數(shù)據(jù)與真實數(shù)據(jù)極為相似，那么使用生成數(shù)據(jù)訓(xùn)練出的模型能夠應(yīng)用于真實數(shù)據(jù).為驗證生成與真實OpenCL①真實OpenCL 代碼是從真實項目中收集的完整代碼片段.內(nèi)核程序的相似性，本文設(shè)計了雙盲驗證實驗.該實驗中，選擇了具有OpenCL 編碼經(jīng)驗的30 位程序員作為志愿者，共28 位碩士和2 位博士，其中13 位為女性，17 位為男性.實驗過程中，分別隨機抽取真實與生成的內(nèi)核程序各15 個，并進行隨機打亂，讓每一位志愿者進行人工標(biāo)記.為保證實驗的公平性，實驗前對測試的內(nèi)核程序進行標(biāo)準(zhǔn)化操作，其目的是為了減少注釋以及函數(shù)名所帶來的標(biāo)記干擾；同時，在測試之前，分別給每位志愿者展示30 個標(biāo)準(zhǔn)化后的生成與真實的OpenCL 內(nèi)核程序.實驗過程中不限標(biāo)記時間，直至志愿者將所有的30 個內(nèi)核程序標(biāo)記完成.該實驗分別統(tǒng)計了標(biāo)記正確的生成與真實OpenCL 內(nèi)核程序的志愿者人數(shù)，實驗結(jié)果如表5所示.

Table 5 Results of Double-blind Experiment表 5 雙盲實驗結(jié)果

僅有少數(shù)志愿者能夠正確標(biāo)記出大部分生成與真實的OpenCL 內(nèi)核程序，而大部分志愿者能夠正確標(biāo)記生成與真實OpenCL 內(nèi)核程序的數(shù)量不超過8 個.由此可以看出，標(biāo)記生成代碼的準(zhǔn)確率為46.6%，而標(biāo)記真實代碼的準(zhǔn)確率為53.4%，平均準(zhǔn)確率接近50%，這意味著人工標(biāo)記過程中，其準(zhǔn)確率與隨機猜測的概率基本相同，說明了生成與真實的OpenCL 內(nèi)核程序相似度比較高，這也是使用生成數(shù)據(jù)訓(xùn)練模型能夠以較高的準(zhǔn)確率預(yù)測出真實OpenCL 代碼適合的異構(gòu)平臺的原因.

4.5 模型分析評估實驗

為進一步驗證本文所提出的模型與構(gòu)圖方法的有效性，構(gòu)建最優(yōu)的模型與構(gòu)圖方法，本文分別評估了神經(jīng)網(wǎng)絡(luò)層數(shù)、不同構(gòu)圖方法以及不同圖神經(jīng)網(wǎng)絡(luò)對實驗結(jié)果的影響.該評估實驗以異構(gòu)映射任務(wù)為例，使用DeepTune[9]提供的數(shù)據(jù)集②需要說明的是，該實驗僅在680 條數(shù)據(jù)集上進行，因此ACCEPT 的準(zhǔn)確率與4.2 節(jié)中的數(shù)值不同.，在AMD Tahiti 7970 平臺上進行.

4.5.1 網(wǎng)絡(luò)層數(shù)的影響

神經(jīng)網(wǎng)絡(luò)的層數(shù)是網(wǎng)絡(luò)模型的重要參數(shù)，設(shè)置合理數(shù)量的中間層，能夠增強模型的表征與特征抽取能力.相反，若設(shè)置的中間層數(shù)太少，將使網(wǎng)絡(luò)難以模擬出具有復(fù)雜分類空間的模型；而中間層過多，將使模型太過復(fù)雜導(dǎo)致難以收斂.

為選取合適的網(wǎng)絡(luò)層數(shù)，實驗中除構(gòu)建不同層數(shù)的多關(guān)系圖神經(jīng)網(wǎng)絡(luò)外，其他實驗設(shè)置均與4.2 節(jié)中保持一致.實驗結(jié)果如表6 所示，可以看出，該實驗結(jié)果符合深度學(xué)習(xí)模型的一般規(guī)律，即隨著網(wǎng)絡(luò)層數(shù)的增加，模型的表征能力與特征提取能力不斷增強，預(yù)測準(zhǔn)確率由79.4%增長到82.0%，而隨著層數(shù)的繼續(xù)增加，模型變得越來越復(fù)雜，極易導(dǎo)致過擬合，準(zhǔn)確率逐漸降低.該實驗表明，在異構(gòu)映射任務(wù)中，當(dāng)網(wǎng)絡(luò)層數(shù)設(shè)置為5 時，模型表現(xiàn)最優(yōu).同樣地，因不同的任務(wù)具有不同的復(fù)雜度與分類空間，本文使用上述方法確定線程粗化因子預(yù)測任務(wù)的最佳網(wǎng)絡(luò)層數(shù).

Table 6 Comparison of Accuracy with Different Numbers of Network Layers表 6 不同網(wǎng)絡(luò)層數(shù)的準(zhǔn)確率對比

4.5.2 構(gòu)圖方式的影響

ACCEPT 不僅依靠表征能力強的多關(guān)系圖網(wǎng)絡(luò)模型，還需要正確的、能夠表征代碼深度結(jié)構(gòu)與語義特征的構(gòu)圖方式將OpenCL 代碼轉(zhuǎn)換成多關(guān)系程序圖.為驗證構(gòu)圖方式對ACCEPT 的影響，該實驗保持多關(guān)系圖網(wǎng)絡(luò)結(jié)構(gòu)不變，通過改變構(gòu)圖方式進行評估.為此，本文分別在源碼與IR 代碼的基礎(chǔ)上，向AST中加入不同類型的邊，構(gòu)建出4 種程序圖，分別為：ACCEPT-vanilla-AST，表示僅構(gòu)建源代碼的AST 圖；ACCEPT-AST 與ACCEPT-CDFG，分別表示僅構(gòu)建AST增強圖與IR 多關(guān)系圖；ACCEPT-8，表示將AST 增強圖與IR 多關(guān)系圖中的每種邊類型單獨構(gòu)圖，然后將所構(gòu)建的8 種圖的特征向量進行拼接.圖11 展示了不同構(gòu)圖方式之間的對比關(guān)系圖.

Fig.11 Accuracy of different graph construction圖 11 不同構(gòu)圖方法的準(zhǔn)確率

由圖11 可知，在除SHOC 外的7 個數(shù)據(jù)集上，ACCEPT-AST 的平均準(zhǔn)確率比ACCEPT-vanilla-AST準(zhǔn)確率高，這說明給AST 增加額外的5 種數(shù)據(jù)控制依賴關(guān)系邊，能夠更加精準(zhǔn)地提取代碼的語法語義信息.ACCEPT-8 雖然包含了所有的8 種邊類型，但其在每個benchmark 上的準(zhǔn)確率均不高于75%，這說明僅僅將8 種圖的特征進行簡單地拼接，而不考慮不同邊類型所攜帶的特征信息，并不能將節(jié)點的信息傳遞給其他的鄰居節(jié)點，導(dǎo)致模型表征能力并不強.此外，從ACCEPT-AST 與ACCEPT-CDFG 比較結(jié)果來看，ACCEPT-CDFG在大部分數(shù)據(jù)集上實現(xiàn)的準(zhǔn)確率高于ACCEPT-AST，這很大程度上是因為CDFG在IR 代碼上進行構(gòu)圖，IR指令更加簡潔，并且能夠突出底層的執(zhí)行邏輯.需要說明的是，在Parboil[29]數(shù)據(jù)集上，ACCEPT-CDFG 的準(zhǔn)確率接近80%，大于ACCEPT 的74%的準(zhǔn)確率，分析發(fā)現(xiàn)，Parboil 數(shù)據(jù)集中的算法具有豐富的控制流信息，使得ACCEPT-CDFG 更能聚焦代碼特征信息.

從圖11 的實驗結(jié)果來看，與其他5 種不同的構(gòu)圖方法比，ACCEPT 取得了最高的準(zhǔn)確率，這表明通過將源代碼的增強AST 與IR 代碼的多關(guān)系控制依賴圖相結(jié)合，能夠更加精準(zhǔn)地提取到代碼的深度結(jié)構(gòu)和語義特征.

4.5.3 圖網(wǎng)絡(luò)模型的影響

為驗證本文所構(gòu)建的多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的有效性，該實驗中將ACCEPT 分別與現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)模型進行比較.本文分別選擇利用門控信息來傳遞信息的GGNN[36]（gated graph sequence neural networks）、基于線性特征調(diào)制的GNN_FILM[37]（graph neural networks with feature-wise linear modulation）、基于多邊關(guān)系建模的圖卷積神經(jīng)網(wǎng)絡(luò)RGCN[38]（relational graph convolutional networks），及其RGCN 的變體網(wǎng)絡(luò)GNN_Edge_MLP[39].實驗過程中，由于不同的網(wǎng)絡(luò)模型需要輸入不同的圖結(jié)構(gòu)，因此本文將AST 增強圖與IR 多關(guān)系圖轉(zhuǎn)換成每個圖網(wǎng)絡(luò)模型適合處理的格式.對比實驗結(jié)果如圖12 所示，其中GeoMean 為5 種模型在7 種數(shù)據(jù)集的幾何平均值.

Fig.12 Accuracy of different graph neural networks圖 12 不同圖神經(jīng)網(wǎng)絡(luò)的準(zhǔn)確率

總體上，與其他4 種經(jīng)典的圖網(wǎng)絡(luò)模型相比，ACCEPT 取得了最好的結(jié)果，其平均準(zhǔn)確率達到了77.5%，其次為RGCN 與GNN_Edge_MLP，平均準(zhǔn)確率均為74%.盡管RGCN 及GNN_Edge_MLP 支持對多邊建模，但并不適合對異構(gòu)代碼圖進行建模，而AST 和CDFG 是2 種具有不同特征信息的異構(gòu)圖，這將在很大程度上降低RGCN 與GNN_Edge_MLP 這2種模型的特征提取與建模能力.由于GGNN 與GNN_FILM 更適合使用門控信息或線性調(diào)制來提取特征，因此對關(guān)系程序圖的建模能力較弱，所取得的準(zhǔn)確率最低.

5 總結(jié)

當(dāng)前針對OpenCL 程序的優(yōu)化方法需要過多的人為參與，難以有效提取程序的深度結(jié)構(gòu)與語法語義特征信息，進而無法對代碼進行有效地建模，使得程序優(yōu)化效果并不明顯.針對上述問題，本文提出了ACCEPT，一種基于多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的OpenCL 程序自動優(yōu)化啟發(fā)式方法，旨在無需手工提取特征的情況下，實現(xiàn)端到端的自動化優(yōu)化，提高程序的執(zhí)行效率.與傳統(tǒng)的基于深度學(xué)習(xí)的優(yōu)化方法相比，ACCEPT 將源代碼轉(zhuǎn)換為代碼特有的多關(guān)系程序圖，以表征代碼的深度結(jié)構(gòu)與語義特征信息.為此，ACCEPT 分別在源代碼和IR 代碼上對目標(biāo)程序進行構(gòu)圖，通過添加8 種類型的數(shù)據(jù)控制依賴邊，保留了代碼的語法及語義信息.同時，為了處理所構(gòu)建的多關(guān)系程序圖，ACCEPT 改進了現(xiàn)有的圖形神經(jīng)網(wǎng)絡(luò)模型，通過融合程序的控制流、數(shù)據(jù)流以及抽象語法樹所表征的代碼的結(jié)構(gòu)與語義特征信息，進而生成高維特征向量，最終輸入到?jīng)Q策網(wǎng)絡(luò)中進行分類，完成預(yù)測優(yōu)化因子任務(wù).

為驗證模型性能，本文分別在異構(gòu)映射與線程粗化因子預(yù)測2 個代碼優(yōu)化任務(wù)上，進行了詳細的對比分析實驗，與現(xiàn)有的經(jīng)典代碼優(yōu)化方法相比，ACCEPT 在準(zhǔn)確率、加速比上均提升明顯，在異構(gòu)設(shè)備映射任務(wù)中，加速比可提高7.6%.在線程粗化任務(wù)中，加速比可提高5.2%.為充分地說明本文所提多關(guān)系程序圖與多關(guān)系圖神經(jīng)網(wǎng)絡(luò)的有效性，分別在神經(jīng)網(wǎng)絡(luò)層數(shù)、構(gòu)圖方式以及網(wǎng)絡(luò)模型上進行了詳細的模型分析及對比實驗，實驗結(jié)果進一步表明了ACCEPT 的有效性，說明ACCEPT 在代碼優(yōu)化領(lǐng)域具有一定的學(xué)術(shù)價值和應(yīng)用前景.

作者貢獻聲明：葉貴鑫提出了文章思路和實現(xiàn)方案并負責(zé)撰寫與修改論文；張宇翔負責(zé)系統(tǒng)設(shè)計與實現(xiàn)；張成負責(zé)數(shù)據(jù)收集與模型調(diào)優(yōu)、數(shù)據(jù)分析；趙佳棋負責(zé)數(shù)據(jù)預(yù)處理；王煥廷負責(zé)代碼圖多種邊關(guān)系的構(gòu)建.葉貴鑫和張宇翔為共同第一作者.