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

（西北大學信息科學與技術學院 西安 710127）

（陜西省無源物聯網國際聯合研究中心（西北大學）西安 710127）

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

1.2 基于深度學習技術的代碼優(yōu)化

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

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

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

2 系統(tǒng)設計與實現

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

Fig.1 ACCEPT framwork圖 1 ACCEPT 框架

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

2.1 數據生成與標記

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

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

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

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

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

2.2 代碼預處理

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

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

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

2.3 多關系代碼圖構建方法

為準確地表示程序深度語法、語義及結構特征信息，本文在源碼AST 的基礎上設計了5 種類型的邊關系，構造了AST 增強圖.同時，基于LLVM 的IR設計了3 種邊關系，構造了多關系IR 圖.

2.3.1 代碼圖關系說明

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

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

2.3.2 AST 增強圖邊類型

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

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

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

Table 1 Program Diagram Connection Relationship表 1 程序圖連接關系

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

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

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

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

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

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

2.3.3 IR 多關系圖邊類型

1）IR 順序流邊.IR 順序流邊連接了當前指令與下一條指令，用于記錄LLVM IR 指令的順序關系，同樣地，這種順序關系對于圖網絡而言也是不可或缺的.如圖3 為內核程序對應的IR 指令，IR 順序流邊記錄圖中每條指令的執(zhí)行順序.

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

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

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

2.3.4 多關系代碼圖的構建

Fig.5 IR multi-relationship graph圖 5 IR 多關系圖

多關系代碼圖的構建如算法1 所示.該算法以OpenCL 源碼為輸入，通過分析源碼的AST 與IR 中的數據控制依賴關系，輸出二元組（GAST,GIR），分別存儲對應的AST 增強圖GAST與多關系IR 圖GIR.

算法1.多關系代碼圖生成算法.

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

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

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

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

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

2.4 多關系圖神經網絡建模

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

2.4.1 鄰域聚合

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

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

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

2.4.2 圖嵌入

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

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

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

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

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

2.5 決策網絡

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

Fig.7 The structure of decision network圖 7 決策網絡結構

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

2.6 模型訓練

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

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

3 實驗設置

3.1 實驗平臺

本文采用TensorFlow 深度學習框架構建多關系圖神經網絡模型.所有實驗均運行在Ubuntu 16.04 操作系統(tǒng)上，其內存為12GB，CPU 處理器為Intel Xeon E5-2 667，編程語言為Python 3.6.

3.2 數據集構成

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

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

3.3 評估指標

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

其中m為測試集的個數，true_labeli為 第i個測試數據的預測結果.加速比計算為

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

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

4 實驗結果與分析

4.1 實驗概況

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

Table 2 Comparison of Machine Learning Methods表 2 機器學習方法對比

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

4.2 異構設備映射任務

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

4.2.1 實驗方法

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

4.2.2 對比實驗

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

4.2.3 實驗結果與分析

圖8 展示了在不同平臺下ACCEPT 與其他方法的加速比對比結果.由圖8 可知，無論是在早期的GPU 平臺如NVIDIA GTX 970，還是在最新的NV IDIA Titan XP 上，ACCEPT 優(yōu)化后的加速比均優(yōu)于其他經典的代碼優(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 加速比對比結果

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

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

Fig.9 Comparison results of accuracy圖 9 準確率對比結果

4.3 線程粗化任務

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

4.3.1 實驗方法

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

4.3.2 對比實驗

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

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

4.3.3 實驗結果與分析

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

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

4.4 數據生成質量分析

在異構映射任務中，本文使用生成的OpenCL 程序內核數據訓練ACCEPT 模型.程序生成的質量將直接影響模型的預測準確率，為評估程序生成的質量，本實驗分別對所生成的OpenCL 程序的可用性及編碼質量進行評估.

4.4.1 OpenCL 程序可用性評估

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

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

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

Table 4 Results of Program Quality Evaluation表 4 程序質量評估結果

4.4.2 OpenCL 程序雙盲實驗評估

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

Table 5 Results of Double-blind Experiment表 5 雙盲實驗結果

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

4.5 模型分析評估實驗

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

4.5.1 網絡層數的影響

神經網絡的層數是網絡模型的重要參數，設置合理數量的中間層，能夠增強模型的表征與特征抽取能力.相反，若設置的中間層數太少，將使網絡難以模擬出具有復雜分類空間的模型；而中間層過多，將使模型太過復雜導致難以收斂.

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

Table 6 Comparison of Accuracy with Different Numbers of Network Layers表 6 不同網絡層數的準確率對比

4.5.2 構圖方式的影響

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

Fig.11 Accuracy of different graph construction圖 11 不同構圖方法的準確率

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

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

4.5.3 圖網絡模型的影響

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

Fig.12 Accuracy of different graph neural networks圖 12 不同圖神經網絡的準確率

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

5 總結

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

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

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