李居垚，何先波

（西華師范大學(xué)電子信息工程學(xué)院，四川 南充 637009）

0 引 言

當(dāng)下新架構(gòu)芯片問(wèn)世的頻率遠(yuǎn)超以往，這需要縮短芯片編譯的開(kāi)發(fā)周期來(lái)進(jìn)行適配。 在編譯器中許多關(guān)鍵決策是由抽象模型來(lái)決定的，雖然這些模型能夠有效地解決問(wèn)題，但是開(kāi)發(fā)編寫(xiě)一個(gè)精確的抽象模型需要耗費(fèi)大量的人力物力；所以使用新技術(shù)來(lái)縮短編譯器開(kāi)發(fā)的成本和周期是有必要的。

編譯優(yōu)化中的循環(huán)展開(kāi)有著承上啟下的作用，因?yàn)檠h(huán)展開(kāi)從多維度間接影響了系統(tǒng)性能，同時(shí)也會(huì)為其他優(yōu)化（如SLP）帶來(lái)契機(jī)，所以開(kāi)發(fā)一種有別于傳統(tǒng)的新技術(shù)來(lái)對(duì)編譯器循環(huán)展開(kāi)進(jìn)行自動(dòng)化是必要的。 本文將使用人工智能技術(shù)提出一個(gè)模型來(lái)對(duì)編譯器循環(huán)展開(kāi)工作中的至關(guān)重要的展開(kāi)因子（Unroll Factor，UF）進(jìn)行自動(dòng)生成，已達(dá)到循環(huán)展開(kāi)工作自動(dòng)化減少編譯器開(kāi)發(fā)工作量和成本的目的。

1 相關(guān)理論及方法

1.1 循環(huán)展開(kāi)

循環(huán)展開(kāi)是一種常用的編譯優(yōu)化策略，開(kāi)啟后編譯器會(huì)通過(guò)既定的抽象模型啟發(fā)式地將目標(biāo)循環(huán)進(jìn)行多次復(fù)制。 循環(huán)展開(kāi)主要用于為其他優(yōu)化提供機(jī)會(huì)，例如，展開(kāi)會(huì)創(chuàng)建與動(dòng)態(tài)執(zhí)行相對(duì)應(yīng)的多個(gè)靜態(tài)內(nèi)存單一操作指令，可以重新安排這些指令以利用內(nèi)存局部性［1］。 如果循環(huán)訪問(wèn)連續(xù)迭代中的相同內(nèi)存位置，引用還可以用標(biāo)量進(jìn)行消除。 循環(huán)展開(kāi)是暴露相鄰內(nèi)存引用的關(guān)鍵，展開(kāi)完成后后續(xù)的優(yōu)化可識(shí)別到這些引用并將其合并為一個(gè)寬引用［2］。

由于循環(huán)展開(kāi)的主要影響集中在次級(jí)效應(yīng)上，所以選取最優(yōu)的展開(kāi)因子進(jìn)行循環(huán)展開(kāi)是困難的。循環(huán)展開(kāi)也可以被歸納為空間換時(shí)間的一種手段，這很容易造成一種循環(huán)展開(kāi)總能提升性能的誤解。不合適的循環(huán)展開(kāi)都會(huì)造成以下性能損失：會(huì)降低指令緩存的性能，會(huì)造成內(nèi)存的溢出和重新加載，如果編譯器選擇推測(cè)性的訪問(wèn)展開(kāi)內(nèi)存會(huì)造成動(dòng)態(tài)沖突［3］。 循環(huán)展開(kāi)會(huì)增加編譯時(shí)間，所以通過(guò)暴力搜索等手段獲取循環(huán)展開(kāi)因子是低效的，圖1 展示了不同循環(huán)展開(kāi)因子選擇對(duì)編譯耗時(shí)的影響。

圖1 TSVC 中s3111.c 設(shè)置不同循環(huán)展開(kāi)次數(shù)的編譯耗時(shí)比Fig. 1 Compilation time ratio of s3111. c with different loop unwinding times in TSVC

使用暴力搜索的方式來(lái)尋找最優(yōu)的展開(kāi)因子是效率低下的，如圖1 所示。 圖1 中，以不進(jìn)行展開(kāi)的耗時(shí)為基準(zhǔn)。 近年來(lái)，隨著機(jī)器學(xué)習(xí)技術(shù)不斷發(fā)展成熟，許多學(xué)者希望利用機(jī)器學(xué)習(xí)來(lái)解決復(fù)雜的編譯器優(yōu)化問(wèn)題，即構(gòu)建一個(gè)機(jī)器學(xué)習(xí)模型去預(yù)測(cè)編譯器優(yōu)化參數(shù)和編譯選項(xiàng)等［4］。 本文將會(huì)嘗試使用強(qiáng)化學(xué)習(xí)來(lái)預(yù)測(cè)的循環(huán)展開(kāi)因子。

1.2 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)通過(guò)和環(huán)境動(dòng)態(tài)交互不斷試錯(cuò)來(lái)得到較優(yōu)解的方法。 在這種方法中智能體通過(guò)不斷和環(huán)境交互來(lái)進(jìn)行學(xué)習(xí)［5］，強(qiáng)化學(xué)習(xí)想要直接訓(xùn)練得到策略函數(shù)或者價(jià)值函數(shù)是比較困難的，對(duì)此引入神經(jīng)網(wǎng)絡(luò)來(lái)近似目標(biāo)函數(shù)是一種常用的策略。

在強(qiáng)化學(xué)習(xí)中智能體通過(guò)對(duì)環(huán)境的“觀察”來(lái)采取行為動(dòng)作，行為會(huì)產(chǎn)生新的環(huán)境并根據(jù)當(dāng)前環(huán)境得到一個(gè)獎(jiǎng)勵(lì)的分值作為行為好壞的評(píng)判，整個(gè)學(xué)習(xí)過(guò)程的目的是獎(jiǎng)勵(lì)達(dá)到數(shù)學(xué)期望的最大化并得到相映的決策函數(shù)（π?）：

強(qiáng)化學(xué)習(xí)有很多巧妙的算法，本文選用PPO（Proximal Policy Optimization）算法［6］。 PPO 算法的優(yōu)勢(shì)在于每次進(jìn)行梯度更新時(shí)能夠使得成本最小化，并且能夠很好地消除和上一次梯度更新的偏差。

1.3 代碼嵌入

使用代碼詞嵌入能夠使輸入的源程序更好地通過(guò)強(qiáng)化學(xué)習(xí)進(jìn)行訓(xùn)練，代碼詞嵌入的最終目標(biāo)是有效地將源程序和強(qiáng)化學(xué)習(xí)所需要的向量進(jìn)行映射。在本文中，選擇IR2Vec 作為代碼嵌入。

IR2Vec［4］是一種基于源碼中間表示形式（LLVM IR）的代碼嵌入，這種代碼嵌入的方法具有簡(jiǎn)明和可伸縮的特點(diǎn)，IR2Vec 通過(guò)表征學(xué)習(xí)和流信息相結(jié)合的方式捕獲程序的語(yǔ)法和語(yǔ)義將程序表示為連續(xù)空間中的分布式嵌入。 IR 的表示被轉(zhuǎn)化為一個(gè)種子嵌入詞匯表，并且有2 種編碼模式：符號(hào)編碼和流感知編碼。 由于本文主要針對(duì)的是源代碼中循環(huán)部分的工作，控制流的信息至關(guān)重要，所以本文使用IR2Vec 的流感知編碼模式。

2 相關(guān)工作

2.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)平臺(tái)信息見(jiàn)表1。

表1 實(shí)驗(yàn)平臺(tái)信息Tab. 1 Experimental platform information

2.2 實(shí)驗(yàn)內(nèi)容

本次實(shí)驗(yàn)所使用的模型如圖2 所示，源程序作為初始的輸入會(huì)通過(guò)腳本識(shí)別代碼中的循環(huán)并插入循環(huán)展開(kāi)指令設(shè)置循環(huán)展開(kāi)因子，然后使用Clang＼LLVM 將源代碼轉(zhuǎn)為中間表示形式（IR），而后將IR輸入到IR2Vec 中生產(chǎn)長(zhǎng)度為300 的向量嵌入到強(qiáng)化學(xué)習(xí)的智能體中，同時(shí)編譯運(yùn)行使用LLVM 基準(zhǔn)（LLVM－O3）的可執(zhí)行文件并收集運(yùn)行時(shí)間。 下一階段使用策略函數(shù)輸出的新因子作為參數(shù)，再次進(jìn)行編譯并運(yùn)行，2 次運(yùn)行的性能差異將作為模型的獎(jiǎng)勵(lì)，這意味著本模型的獎(jiǎng)勵(lì)不需要手動(dòng)進(jìn)行設(shè)置，獎(jiǎng)勵(lì)的值也不是固定不變的。 模型中一輪迭代后會(huì)將預(yù)測(cè)出的循環(huán)展開(kāi)因子作為下一輪的學(xué)習(xí)所需要的編譯選項(xiàng)參數(shù)，獲得新的IR、新的向量嵌入智能體，以此往復(fù)訓(xùn)練出預(yù)測(cè)循環(huán)展開(kāi)因子的模型。

圖2 本文提出的自動(dòng)循環(huán)展開(kāi)框架Fig. 2 The automatic loop unrolling framework proposed in this article

本次實(shí)驗(yàn)將會(huì)采取上述的模型和方法進(jìn)行，代碼嵌入使用的IR2Vec 開(kāi)源工具并根據(jù)設(shè)定的任務(wù)要求進(jìn)行改造，研究中選用其流感知模式來(lái)更好地識(shí)別循環(huán)中的控制流信息。 在搭建強(qiáng)化學(xué)習(xí)模型的過(guò)程中，使用了RLlib［6］和Tune［7］，RLlib 和Tune 都能在強(qiáng)化學(xué)習(xí)的開(kāi)源庫(kù)里找到。 這樣一來(lái)，研究所搭建的模型會(huì)更加規(guī)范，便于進(jìn)行參數(shù)的調(diào)整和對(duì)模型的擴(kuò)展。

在實(shí)驗(yàn)中使用Ray［8］框架，因此對(duì)于提前設(shè)置好的3 種不同的學(xué)習(xí)率可以同時(shí)進(jìn)行，這極大地縮短了訓(xùn)練所需的時(shí)間。 同時(shí)，為了與本次研究搭建的強(qiáng)化學(xué)習(xí)模型進(jìn)行對(duì)比，還準(zhǔn)備了暴力搜索來(lái)鎖定最優(yōu)循環(huán)展開(kāi)因子。

2.3 參數(shù)設(shè)置

實(shí)驗(yàn)選用PPO 算法，設(shè)置了3 個(gè)學(xué)習(xí)率：5－e3、5－e4、5－e5。 本模型的獎(jiǎng)勵(lì)將以LLVM11 －O3 編譯后的運(yùn)行時(shí)間作為基準(zhǔn)，將其進(jìn)行如下定義：

對(duì)于循環(huán)展開(kāi)因子的取值，本文設(shè)立一個(gè)數(shù)組array［1、2、4、…、8］，此后隨機(jī)從中取值作為強(qiáng)化學(xué)習(xí)的動(dòng)作。

表2 是本文構(gòu)建的強(qiáng)化學(xué)習(xí)模型具體的參數(shù)設(shè)置。

表2 強(qiáng)化學(xué)習(xí)模型參數(shù)Tab. 2 Parameters of reinforcement learning model

2.4 數(shù)據(jù)集

實(shí)驗(yàn)所使用的訓(xùn)練集是在向量化測(cè)試套件（TSVC）的基礎(chǔ)上進(jìn)行篩選和拓展組成的訓(xùn)練集。TSVC 最初由Callahan 等人開(kāi)發(fā)后由Maleki 等學(xué)者［9］將其從Fortran 轉(zhuǎn)換為C 進(jìn)行了擴(kuò)展。 擴(kuò)展版本有151 個(gè)內(nèi)核。 本次研究選擇這個(gè)基準(zhǔn)測(cè)試是因?yàn)槠渲刑峁┝艘恍┫鄬?duì)簡(jiǎn)單的循環(huán)的集合，這些循環(huán)可以在許多科學(xué)用途的C 語(yǔ)言代碼中找到，同時(shí)TSVC 中的循環(huán)能夠根據(jù)其測(cè)試的用途進(jìn)行適當(dāng)分類(lèi)，對(duì)結(jié)果分析有很大的幫助。 通過(guò)腳本將TSVC中每個(gè)函數(shù)提取出去生成獨(dú)立的C＋＋文件；TSVC的數(shù)據(jù)量對(duì)強(qiáng)化學(xué)習(xí)來(lái)說(shuō)還是偏小了，本實(shí)驗(yàn)將會(huì)在TSVC 原有的循環(huán)上進(jìn)行增加，手段主要是改變變量名稱(chēng)使得數(shù)據(jù)的總量倍增；同時(shí)，對(duì)不同分類(lèi)的TSVC 函數(shù)進(jìn)行隨機(jī)抽取用來(lái)構(gòu)建測(cè)試集。 構(gòu)建訓(xùn)練集和其中一個(gè)測(cè)試集如圖3 所示。

圖3 TSVC 訓(xùn)練集和測(cè)試集構(gòu)建流程Fig. 3 TSVC training and testing set construction process

為了測(cè)試本文構(gòu)建的強(qiáng)化學(xué)習(xí)循環(huán)展開(kāi)化器能否很好地推廣到新代碼，并且測(cè)試其對(duì)于循環(huán)復(fù)雜程度的敏感程度，選擇使用Ameer 等學(xué)者［10］構(gòu)建的循環(huán)結(jié)構(gòu)簡(jiǎn)單的數(shù)據(jù)集Tests、分離出的TSVC 內(nèi)核和PloyBench［11］三個(gè)測(cè)試集進(jìn)行推廣性能的測(cè)試。這3 個(gè)測(cè)試集中，Tests 的循環(huán)結(jié)構(gòu)最簡(jiǎn)單，其次是TSVC，PloyBench 的循環(huán)結(jié)構(gòu)最為復(fù)雜其主要由循環(huán)構(gòu)成，即由多個(gè)benchmark 組成。 本次研究選用其中的2mm、bicg、atax、gemm、gemver、choleshy 來(lái)進(jìn)行測(cè)試。

3 實(shí)驗(yàn)結(jié)果

強(qiáng)化學(xué)習(xí)循環(huán)展開(kāi)器、LLVM 基準(zhǔn)模型和暴力搜索的性能對(duì)比如圖4 所示。 在Tests 基準(zhǔn)上本文提出的循環(huán)展開(kāi)器比LLVM 基準(zhǔn)模型有1.19x 的性能提升；在TSVC 基準(zhǔn)上，有1.13x 的性能提升；在Polybench 基準(zhǔn)上，有1.09x 的性能提升。 可以看到，隨著循環(huán)復(fù)雜度的提升，循環(huán)展開(kāi)器的性能也隨之下降，可見(jiàn)在面對(duì)復(fù)雜循環(huán)時(shí)本文提出的循環(huán)展開(kāi)器還有進(jìn)一步的優(yōu)化空間。

圖4 歸一化后強(qiáng)化學(xué)習(xí)循環(huán)展開(kāi)器、LLVM 基準(zhǔn)模型和暴力搜索的性能比Fig. 4 The performance ratio of reinforcement learning loop unroller，LLVM benchmark model and brute force search after normalization

雖然本文提出的循環(huán)展開(kāi)器性能上要弱于暴力搜索的結(jié)果，但是在運(yùn)行速度上大幅領(lǐng)先暴力搜索，如圖5 所示：在Tests 基準(zhǔn)上，本文提出的循環(huán)展開(kāi)器比暴力搜索快5.97x；在TSVC 基準(zhǔn)上，快6.23x 的性能提升；在Polybench 基準(zhǔn)上快5.61x 的性能提升。

圖5 歸一化后強(qiáng)化學(xué)習(xí)向量器和暴力搜索編譯所需時(shí)間比Fig. 5 Time ratio between reinforcement learning vector machineand brute force search compilation after normalization

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

針對(duì)編譯開(kāi)發(fā)成本急需縮減的問(wèn)題，本文提出了一個(gè)基于強(qiáng)化學(xué)習(xí)的循環(huán)展開(kāi)器來(lái)對(duì)編譯開(kāi)發(fā)中循環(huán)展開(kāi)進(jìn)行自動(dòng)化。 通過(guò)代碼嵌入的方式來(lái)表征循環(huán)代碼，然后使用強(qiáng)化學(xué)習(xí)模型來(lái)對(duì)展開(kāi)因子進(jìn)行預(yù)測(cè)以達(dá)到輸入新代碼能快速自動(dòng)地進(jìn)行循環(huán)展開(kāi)的目的。 實(shí)驗(yàn)表明，本文提出的循環(huán)展開(kāi)器相比于LLVM －O3 的基準(zhǔn)模型有更好的效果，同時(shí)有比暴力搜索更快的編譯速度。 但根據(jù)本文選取的3 個(gè)測(cè)試集的實(shí)驗(yàn)結(jié)果，本文提出的向量化器在復(fù)雜場(chǎng)景中會(huì)效果下降，在未來(lái)的工作中會(huì)考慮更多復(fù)雜應(yīng)用場(chǎng)景，將謂詞加入到控制流的識(shí)別當(dāng)中、將多面體模型和強(qiáng)化學(xué)習(xí)進(jìn)行結(jié)合以提升循環(huán)展開(kāi)器的性能。