面向深度學(xué)習(xí)算子的循環(huán)不變式外提算法

梁佳利，華保健，呂雅帥，蘇振宇

1.中國(guó)科學(xué)技術(shù)大學(xué)軟件學(xué)院，合肥230000

2.中科寒武紀(jì)科技股份有限公司，北京100000

TVM（tensor virtual machine）[1]是一個(gè)開源深度學(xué)習(xí)編譯器[2-5]，通過提供圖級(jí)別的優(yōu)化[6]和算子級(jí)別的優(yōu)化，生成多硬件后端代碼。在算子實(shí)現(xiàn)時(shí)，不同的計(jì)算方法卻導(dǎo)致了生成代碼的局部性、并行性的差異[7-8]。TVM 的領(lǐng)域?qū)Ｓ谜Z(yǔ)言——張量表達(dá)式支持用簡(jiǎn)潔的方式定義算子，并提供一系列調(diào)度原語(yǔ)對(duì)算子代碼做循環(huán)變換。用張量表達(dá)式描述的算子會(huì)被TVM翻譯為TVM IR（TVM intermediate representation）——一種樹狀的、易于描述循環(huán)計(jì)算的高級(jí)中間表示。TVM 在TVM IR 上實(shí)現(xiàn)了一系列分析和變換的優(yōu)化遍，來(lái)對(duì)算子的中間表示進(jìn)行調(diào)整和優(yōu)化，最終生成目標(biāo)硬件平臺(tái)上的高效代碼。

深度學(xué)習(xí)應(yīng)用[9-12]中的重要算子，如卷積、矩陣乘和向量加等，都會(huì)被TVM 編譯生成TVM IR 上的多層嵌套循環(huán)[13]，經(jīng)過循環(huán)變換后會(huì)產(chǎn)生與循環(huán)迭代變量相關(guān)的復(fù)雜表達(dá)式計(jì)算。例如，以下的代碼示例是向量加算子的TVM IR 表示：

1.for(i.outer:int32,0,4){

2.for(i.inner:int32,0,32){

3.C[(i.outer*32)+i.inner]=

4.A[(i.outer*32)+i.inner]+

5.B[(i.outer*32)+i.inner]}}

注意到在內(nèi)層循環(huán)中存在被重復(fù)計(jì)算的表達(dá)式i.outer * 32，它應(yīng)該被循環(huán)不變量外提優(yōu)化[14]提取到第一層和第二層循環(huán)之間，從而消除冗余計(jì)算。

然而，在深度學(xué)習(xí)編譯器中實(shí)現(xiàn)循環(huán)不變式外提優(yōu)化，存在以下研究挑戰(zhàn)：

首先，傳統(tǒng)編譯器中的循環(huán)不變量外提優(yōu)化算法，將計(jì)算結(jié)果保存在物理寄存器中，避免每次使用時(shí)都重復(fù)計(jì)算。但是TVM 等深度學(xué)習(xí)編譯器的高級(jí)中間表示無(wú)法感知物理寄存器的存在，盲目地外提所有循環(huán)不變量會(huì)帶來(lái)不必要的寄存器壓力，甚至降低算子的性能[15]；因此直接將傳統(tǒng)編譯器中的循環(huán)不變式外提算法應(yīng)用到TVM 等深度學(xué)習(xí)編譯器中，并不能得到理想的優(yōu)化效果。

其次，表達(dá)式中操作數(shù)的順序會(huì)影響不變式的發(fā)現(xiàn)[16]；傳統(tǒng)的循環(huán)不變式外提算法，對(duì)深度學(xué)習(xí)算子中經(jīng)常出現(xiàn)的、復(fù)雜嵌套條件表達(dá)式的檢測(cè)能力有限，無(wú)法檢測(cè)、合并、變換生成新的循環(huán)不變式。

最后，深度學(xué)習(xí)編譯器生成的算子，會(huì)被目標(biāo)平臺(tái)編譯器進(jìn)一步編譯優(yōu)化。目標(biāo)平臺(tái)編譯器在一個(gè)更低級(jí)的中間表示上進(jìn)行優(yōu)化[17]，而在兩個(gè)不同級(jí)別上的優(yōu)化常常存在沖突[18]，導(dǎo)致降低了循環(huán)不變式外提算法的有效性。Halide 開源編譯器[19]中實(shí)現(xiàn)了一個(gè)保守的循環(huán)不變式外提算法，但該算法只考慮循環(huán)內(nèi)的表達(dá)式，而不對(duì)語(yǔ)句做處理；且在做循環(huán)不變式外提之前只對(duì)包含加減法的表達(dá)式做了重結(jié)合，沒有對(duì)條件表達(dá)式做優(yōu)化；因此，這些簡(jiǎn)單的處理并不能完全解決上述研究挑戰(zhàn)。

本文提出了一種面向深度學(xué)習(xí)編譯器高級(jí)中間表示的、采用啟發(fā)式策略的循環(huán)不變式外提算法。首先，針對(duì)第一個(gè)研究挑戰(zhàn)，本文借鑒Halide 編譯器循環(huán)不變量外提優(yōu)化的代價(jià)模型，設(shè)計(jì)了衡量表達(dá)式計(jì)算代價(jià)的函數(shù)，來(lái)指導(dǎo)是否外提循環(huán)不變式，以一種簡(jiǎn)單且易于實(shí)現(xiàn)的方式對(duì)消除冗余計(jì)算和寄存器分配之間的矛盾做了權(quán)衡。其次，針對(duì)第二個(gè)研究挑戰(zhàn)，本文算法在檢測(cè)循環(huán)不變量之前，先調(diào)整操作數(shù)結(jié)合順序和變換條件表達(dá)式的形式來(lái)對(duì)表達(dá)式做規(guī)范化，為循環(huán)不變量外提優(yōu)化以及后續(xù)的其他優(yōu)化提供更好的時(shí)機(jī)。最后，針對(duì)第三個(gè)研究挑戰(zhàn)，本文結(jié)合TVM IR 和目標(biāo)平臺(tái)編譯器的具體特點(diǎn)，對(duì)分支和迭代數(shù)目比較小的內(nèi)層循環(huán)做了特殊處理，解決了在不同級(jí)別的中間表示上的優(yōu)化沖突。

為驗(yàn)證本文算法的有效性，在開源編譯器TVM的0.7 版本上實(shí)現(xiàn)了本文算法，并進(jìn)行了實(shí)驗(yàn)和結(jié)果分析。實(shí)驗(yàn)選擇TVM 的TOPI測(cè)試集作為測(cè)試集合，對(duì)其包含的27 個(gè)算子對(duì)應(yīng)的511 個(gè)測(cè)例進(jìn)行了測(cè)試，這些算子都是TVM 框架頻繁用到的算子，其中包含了多種實(shí)現(xiàn)策略的卷積和激活等算子，測(cè)例都是典型的多層嵌套循環(huán)的數(shù)組計(jì)算，同時(shí)一些算子內(nèi)的補(bǔ)零和邊界檢查操作在循環(huán)內(nèi)產(chǎn)生了條件表達(dá)式和分支。這些算子測(cè)例描繪了常見深度學(xué)習(xí)領(lǐng)域算子特點(diǎn)，并且每一個(gè)算子都提供了大量在常見神經(jīng)網(wǎng)絡(luò)中不同參數(shù)規(guī)模的測(cè)例，因此具有一定的代表性。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在排除那些優(yōu)化前后代碼沒有發(fā)生變化的測(cè)例后，與未進(jìn)行循環(huán)不變量外提優(yōu)化的測(cè)例相比，有47.6%的算子性能得到了顯著提升，最大加速比大于40.0%；所有測(cè)例的總時(shí)間加速比平均為22.7%。實(shí)驗(yàn)結(jié)果證明，本算法對(duì)TVM 生成算子的性能產(chǎn)生了積極影響，加速了含有大量冗余計(jì)算的算子的執(zhí)行，完善了TVM 的算子優(yōu)化。

總結(jié)起來(lái)，本文的主要貢獻(xiàn)如下：

（1）提出了一個(gè)新的融合深度學(xué)習(xí)代價(jià)函數(shù)和啟發(fā)式策略的循環(huán)不變量外提算法；

（2）基于TVM 開源深度學(xué)習(xí)編譯器（0.7 版本），給出了原型系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)；

（3）選取深度學(xué)習(xí)領(lǐng)域典型的27 個(gè)算子及其511個(gè)測(cè)例，對(duì)原型系統(tǒng)進(jìn)行了系統(tǒng)測(cè)試；實(shí)驗(yàn)結(jié)果分析表明，該算法對(duì)提升TVM 的性能產(chǎn)生了積極作用。

1 背景與研究動(dòng)機(jī)

本章介紹關(guān)于TVM 中間表示的相關(guān)背景，以給出本文工作的研究動(dòng)機(jī)。

1.1 張量表達(dá)式和TVM IR

張量表達(dá)式是TVM 基于Halide 的算子描述和調(diào)度優(yōu)化分離的思想[7-8]，而設(shè)計(jì)實(shí)現(xiàn)的描述張量運(yùn)算的領(lǐng)域?qū)Ｓ谜Z(yǔ)言。該語(yǔ)言定義張量間的輸入輸出關(guān)系，同時(shí)提供循環(huán)拆分、循環(huán)合并和循環(huán)分塊等一系列調(diào)度原語(yǔ)，這些調(diào)度原語(yǔ)的組合指定了計(jì)算輸出張量的具體策略[20]。

張量表達(dá)式首先被翻譯為TVM IR，TVM IR 是一種樹狀的中間表示，主要包含兩種類型的節(jié)點(diǎn)：（1）表達(dá)式節(jié)點(diǎn)；（2）語(yǔ)句節(jié)點(diǎn)。表達(dá)式節(jié)點(diǎn)主要包含：有名字的變量和常數(shù)、數(shù)組數(shù)據(jù)的加載、函數(shù)調(diào)用、算術(shù)邏輯表達(dá)式、條件表達(dá)式等；語(yǔ)句節(jié)點(diǎn)包含順序、循環(huán)、分支、賦值等。

下面實(shí)例定義了一個(gè)描述固定規(guī)模矩陣乘法算子的張量表達(dá)式：

變量A、B為規(guī)模為（1 024，1 024）的二維矩陣，k為求和歸約的那個(gè)循環(huán)“軸”。矩陣C由矩陣A和B計(jì)算得到。上述算子被翻譯為以下TVM IR：

為了高效實(shí)現(xiàn)上述代碼中的最內(nèi)側(cè)循環(huán)，TVM使用了tile、split和reorder等操作，對(duì)矩陣乘法算子進(jìn)行循環(huán)分塊、循環(huán)拆分和循環(huán)重排序：

1.2 研究動(dòng)機(jī)

算子經(jīng)過循環(huán)變換后有更好的并行性和數(shù)據(jù)局部性，且能夠充分利用底層硬件特性，加速計(jì)算[7,13,20-22]。但是算子經(jīng)過循環(huán)變換后，數(shù)組下標(biāo)表達(dá)式變?yōu)榱苏Z(yǔ)義等價(jià)，但更復(fù)雜的表達(dá)式，增加了額外標(biāo)量運(yùn)算。例如上述矩陣乘算子最后生成的TVM IR，對(duì)于最內(nèi)層循環(huán)，其循環(huán)迭代變量是yi，下標(biāo)表達(dá)式xo*32768+xi*1024+yo*32 在最內(nèi)層循環(huán)迭代時(shí)，計(jì)算結(jié)果不變，在第一次迭代后的計(jì)算都屬于冗余計(jì)算。本算法的設(shè)計(jì)目標(biāo)，是通過把循環(huán)中多次迭代結(jié)果保持不變的計(jì)算移動(dòng)到循環(huán)外，從而減少冗余計(jì)算。另外，TVM 編譯生成的算子會(huì)經(jīng)過目標(biāo)平臺(tái)編譯器的編譯優(yōu)化，才能在常用深度學(xué)習(xí)硬件，如英偉達(dá)的GPU 和寒武紀(jì)的MLU 硬件上[23]，高效運(yùn)行。這類硬件的典型特征是很多部件都為了運(yùn)行計(jì)算密集的程序而設(shè)計(jì)。為了充分利用這些硬件特性，目標(biāo)平臺(tái)編譯器會(huì)選擇展開內(nèi)層循環(huán)，一些計(jì)算的延時(shí)通常被指令流水線所掩蓋，因此一些冗余計(jì)算并不影響運(yùn)行時(shí)間，反而會(huì)降低物理寄存器壓力。而由于硬件更專注于計(jì)算，對(duì)于分支優(yōu)化處理的任務(wù)需要由編譯器優(yōu)化完成[24-25]。因此對(duì)布爾表達(dá)式、條件分支語(yǔ)句進(jìn)行外提時(shí)需要謹(jǐn)慎處理，有時(shí)還需要變換條件表達(dá)式的形式，使得生成的代碼更利于底層編譯器的優(yōu)化。綜合以上討論，本文面向深度學(xué)習(xí)編譯器，提出了一種新的循環(huán)不變量外提算法，該算法考慮了TVM IR 和目標(biāo)平臺(tái)編譯器的特點(diǎn)，通過外提循環(huán)不變量減少冗余計(jì)算，提高TVM 生成算子的性能。

2 相關(guān)工作

作為優(yōu)化循環(huán)內(nèi)冗余計(jì)算的一種有效技術(shù)，循環(huán)不變式外提已經(jīng)被廣泛研究和應(yīng)用，很多編譯器都使用消除冗余計(jì)算的方法，優(yōu)化生成代碼性能。Aho 等[14]系統(tǒng)討論了循環(huán)不變量外提的概念。TVM[1]在圖級(jí)別的中間表示RELAY 上[6]，使用公共子表達(dá)式消除算法，在算子的層級(jí)上減少了相同輸入規(guī)模算子的重復(fù)計(jì)算；LLVM（low level virtual machine）[26]在LLVM IR 上使用了循環(huán)不變量外提技術(shù)，在基于基本塊的控制流圖上對(duì)循環(huán)內(nèi)不變量指令外提；Steffen 等[27]提出了一種代碼移動(dòng)和代數(shù)優(yōu)化的算法；Rosen 等[28]使用全局值編號(hào)來(lái)做冗余消除優(yōu)化。但是，這些研究都是做語(yǔ)義更高的計(jì)算圖級(jí)別中間表示，或是語(yǔ)義更低的底層中間表示上進(jìn)行，缺失了在像TVM IR 這種源代碼級(jí)別的樹狀中間表示上的優(yōu)化算法。如RELAY 中間表示上沒有循環(huán)的概念，對(duì)于RELAY 的冗余消除優(yōu)化都是以整個(gè)算子為單位，優(yōu)化的粒度過大，并不能很好地對(duì)算子內(nèi)的計(jì)算進(jìn)行優(yōu)化。如在LLVM IR 上的循環(huán)不變量外提技術(shù)在一個(gè)更低級(jí)別的中間表示上進(jìn)行，并沒有對(duì)于高語(yǔ)義的表達(dá)式形式如嵌套的條件表達(dá)式提供優(yōu)化方案。因此這些方法無(wú)法直接應(yīng)用在深度學(xué)習(xí)編譯器的優(yōu)化場(chǎng)景中。不少的研究對(duì)于源代碼級(jí)別的優(yōu)化做了討論和實(shí)踐。Halide 編譯器[19]在把算子計(jì)算描述翻譯為Halide IR 后，針對(duì)循環(huán)內(nèi)的表達(dá)式使用了公共子表達(dá)式刪除和循環(huán)不變量外提技術(shù)。Rawat等[15]提出了一個(gè)寄存器優(yōu)化框架，在源代碼級(jí)別對(duì)含有多層嵌套循環(huán)的高階模板計(jì)算進(jìn)行了寄存器的優(yōu)化，提高指令并行性；akg 框架[29]研究了在華為mindspore后端的算子自動(dòng)生成器akg 上，實(shí)現(xiàn)公共子表示消除算法，優(yōu)化了特定指令的重復(fù)計(jì)算；Vasilev等[30]提出了一種在遞歸函數(shù)上的循環(huán)不變量外提算法；Song 等[31]通過展開循環(huán)的前幾次迭代，來(lái)優(yōu)化循環(huán)不變量外提的效果；Bacon 等[32]全面總結(jié)了在高級(jí)語(yǔ)言上的高性能計(jì)算的優(yōu)化方法。但是，這些研究提供的消除冗余計(jì)算的方法沒有考慮到TVM 算子程序特點(diǎn)和深度學(xué)習(xí)加速硬件的特性。如akg 的公共子表達(dá)式消除只是針對(duì)特殊的張量指令進(jìn)行，并沒有對(duì)于TVM 算子調(diào)度優(yōu)化產(chǎn)生的復(fù)雜下標(biāo)表達(dá)式和條件表達(dá)式做優(yōu)化。深度學(xué)習(xí)領(lǐng)域的處理器雖然有很好的指令集并行架構(gòu)，卻不擅長(zhǎng)分支的處理。如Halide 編譯器實(shí)現(xiàn)的循環(huán)不變式外提算法，在分支的處理上忽略了對(duì)條件表達(dá)式的優(yōu)化。因此這些方法對(duì)于深度學(xué)習(xí)編譯器的優(yōu)化，還存在不足之處。

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

本章討論系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。在給出系統(tǒng)架構(gòu)后，重點(diǎn)討論循環(huán)不變式外提算法，并給出規(guī)范化和代價(jià)函數(shù)。

3.1 系統(tǒng)架構(gòu)

本文設(shè)計(jì)和實(shí)現(xiàn)的系統(tǒng)基于開源深度學(xué)習(xí)編譯器TVM 的0.7 版本。TVM 優(yōu)化[1]可以分為圖級(jí)別優(yōu)化和算子級(jí)別優(yōu)化兩個(gè)獨(dú)立的模塊，算子級(jí)別的優(yōu)化又可分為在張量表達(dá)式級(jí)別的基于機(jī)器學(xué)習(xí)的自動(dòng)調(diào)度優(yōu)化和在TVM IR 級(jí)別的優(yōu)化。本算法針對(duì)算子生成的TVM IR 進(jìn)行優(yōu)化，涉及對(duì)算子級(jí)別優(yōu)化模塊的修改。循環(huán)不變量外提算法在TVM 中的整體架構(gòu)圖和關(guān)鍵編譯流程如圖1 所示。

圖1 TVM 中實(shí)現(xiàn)循環(huán)不變量外提算法的架構(gòu)圖Fig.1 Architecture of loop invariant code motion algorithm in TVM

從整體架構(gòu)上看，循環(huán)不變量外提算法由兩個(gè)關(guān)鍵部分組成：第一個(gè)是前處理部分規(guī)范化，該部分對(duì)表達(dá)式進(jìn)行規(guī)范化處理，使得變化后的表達(dá)式更利于循環(huán)不變量的識(shí)別；第二個(gè)是不變量外提部分，對(duì)循環(huán)保持不變的表達(dá)式和語(yǔ)句進(jìn)行識(shí)別和外提。TVM 通過優(yōu)化遍管理器組織一系列優(yōu)化遍在TVM IR 上進(jìn)行優(yōu)化，向TVM 的優(yōu)化遍管理器注冊(cè)本算法的優(yōu)化遍，并安排新增的優(yōu)化遍到原生TVM 優(yōu)化遍序列的合適的位置（如圖1 中加粗邊框的遍所示）。同時(shí)使用了原生TVM 的循環(huán)判斷外提的優(yōu)化遍，對(duì)分支條件為循環(huán)不變量的分支語(yǔ)句做提升；修改原生TVM 的化簡(jiǎn)優(yōu)化遍，禁止了原本對(duì)整數(shù)類型的賦值變量進(jìn)行前向替換的操作。

大量研究表明，父母的信念是兒童信念發(fā)展的錨定起點(diǎn)(Ozorak, 1989; Boyatzis et al., 2006)。不同信仰的父母有著不同的觀念和行為方式，這些不同借助親子談話等方式，影響著兒童各種觀念的形成(Boyatzis et al., 2006)。 例如， Rosengren(2004)等人發(fā)現(xiàn)， 父母(天主教徒)被問及如何回答3～6歲的兒童的死亡問題時(shí)，大部分父母是用宗教相關(guān)的字眼來(lái)回應(yīng)的，例如，天堂、靈魂、上帝等。有宗教信仰的父母的信念更加與眾不同，對(duì)兒童信念的影響也顯得尤為突出。

3.2 循環(huán)不變代碼外提算法

深度學(xué)習(xí)編譯器中的循環(huán)不變量實(shí)例中，典型的是訪問數(shù)組元素的地址表達(dá)式的計(jì)算和條件表達(dá)式的計(jì)算，表達(dá)式中包含了循環(huán)迭代變量、程序參數(shù)和立即數(shù)。TVM IR 中的循環(huán)節(jié)點(diǎn)包含了循環(huán)嵌套關(guān)系以及對(duì)應(yīng)的迭代變量，因此遞歸地判斷某個(gè)表達(dá)式是否是循環(huán)不變的，只需要構(gòu)成表達(dá)式的值滿足以下判定條件：

（1）是常數(shù)（不可變的程序參數(shù)或立即數(shù)）；

（2）該變量的賦值在循環(huán)之外，或者；

（3）到達(dá)該變量的使用只有一個(gè)定值，且該定值的表達(dá)式也是循環(huán)不變的。

實(shí)際上，識(shí)別在一個(gè)循環(huán)中的不變表達(dá)式，只需要標(biāo)記出，在循環(huán)的多次迭代中計(jì)算結(jié)果可能發(fā)生變化的表達(dá)式，那么剩下未標(biāo)記的表達(dá)式都是該循環(huán)的不變式。因此，可按照以下計(jì)算步驟識(shí)別并提升循環(huán)不變式：

（1）標(biāo)記循環(huán)迭代變量為“不可提升”；

（2）標(biāo)記循環(huán)迭代變量到達(dá)的定值變量都是“不可提升”；

（4）將（3）中新的變量的賦值語(yǔ)句插入循環(huán)之前。

雖然單個(gè)常數(shù)是循環(huán)不變的，但是提升它沒有意義，因此算法不對(duì)單個(gè)常數(shù)做提升。

另外對(duì)于表達(dá)式中循環(huán)不變式的識(shí)別，表達(dá)式中操作數(shù)的順序非常關(guān)鍵；不同的操作數(shù)順序不但影響了某些循環(huán)不變的表達(dá)式能否被發(fā)現(xiàn)，還決定了目標(biāo)編譯器中某些對(duì)于分支的優(yōu)化能否被觸發(fā)。因此，在發(fā)現(xiàn)循環(huán)不變量之前需要先對(duì)表達(dá)式進(jìn)行規(guī)范化，利用運(yùn)算符的結(jié)合律對(duì)表達(dá)式進(jìn)行重結(jié)合等變換。

算法1循環(huán)不變量外提算法

算法1 給出了循環(huán)不變式外提算法LICM(T)的偽代碼。該算法接受原始程序T作為輸入?yún)?shù)，并返回優(yōu)化后的程序。算法首先調(diào)用規(guī)范化函數(shù)Normalize(T)對(duì)程序T中的語(yǔ)句和表達(dá)式做規(guī)范化。然后算法按照一定的順序，遍歷程序T中的語(yǔ)句S，并按語(yǔ)句S的可能語(yǔ)法形式進(jìn)行分類討論：若S為賦值語(yǔ)句x=e，并且賦值右側(cè)表達(dá)式e被標(biāo)記為“不可提升”，那么算法標(biāo)記被該賦值語(yǔ)句定義的變量x為“不可提升”；注意到，算法中使用映射Promote[e]來(lái)記錄給定的表達(dá)式e是否可提升，特定的常量值⊥代表不可提升。若S為循環(huán)語(yǔ)句loop(x,e)，其中x是循環(huán)遍歷，e是循環(huán)體，則算法標(biāo)記S的循環(huán)變量x為“不可提升”。對(duì)于語(yǔ)句S中那些沒有被標(biāo)記為“不可提升”的表達(dá)式e，都可認(rèn)為是循環(huán)不變量，因此，算法生成一個(gè)新變量z，將S中的表達(dá)式e用變量z改寫，并將識(shí)別的循環(huán)不變式的候選z←e添加到循環(huán)不變式集合R中供后續(xù)處理。

算法接著對(duì)循環(huán)不變式集合R中的每個(gè)循環(huán)不變式z←e進(jìn)行分析。算法調(diào)用代價(jià)函數(shù)cost(e)計(jì)算外提表達(dá)式e的代價(jià)，當(dāng)且僅當(dāng)該代價(jià)大于等于給定的閾值K，并且表達(dá)式e沒有副作用時(shí)，算法才真正將不變式z←e外提；否則，算法放棄對(duì)不變式z←e的外提嘗試，并恢復(fù)被替換的表達(dá)式。代價(jià)常數(shù)K的取值與目標(biāo)平臺(tái)硬件和編譯器密切相關(guān)，在通常情況下可取K為1。

LICM 算法的輸入T是一棵樹，設(shè)樹中的語(yǔ)句節(jié)點(diǎn)和表達(dá)式節(jié)點(diǎn)數(shù)量為n，Normalize 函數(shù)時(shí)間復(fù)雜度和空間復(fù)雜度為O(n)，具體分析在下節(jié)給出。LICM 算法在規(guī)范化之后，第一個(gè)循環(huán)遍歷T中的語(yǔ)句節(jié)點(diǎn)，該循環(huán)內(nèi)的第一個(gè)內(nèi)層循環(huán)遍歷語(yǔ)句節(jié)點(diǎn)內(nèi)的表達(dá)式節(jié)點(diǎn)，并記錄對(duì)合法的表達(dá)式的賦值語(yǔ)句，第二個(gè)內(nèi)存循環(huán)處理記錄的合法表達(dá)式的賦值，cost 函數(shù)的計(jì)算雖然是遞歸的，但是在計(jì)算過程中存儲(chǔ)每個(gè)表達(dá)式對(duì)應(yīng)代價(jià)值，因此每個(gè)表達(dá)式只會(huì)被計(jì)算一次，所有cost的執(zhí)行時(shí)間和表達(dá)式節(jié)點(diǎn)數(shù)量線性相關(guān)。因此整個(gè)算法的時(shí)間復(fù)雜度和輸入T中語(yǔ)句節(jié)點(diǎn)和表達(dá)式節(jié)點(diǎn)數(shù)量線性相關(guān)，LICM 算法的時(shí)間復(fù)雜度為O(n)。整個(gè)LICM 算法除T外所涉及的存儲(chǔ)結(jié)構(gòu)為R，Promote 和cost 記錄表達(dá)式的代價(jià)值所需的存儲(chǔ)。以上三個(gè)存儲(chǔ)結(jié)構(gòu)的任意一個(gè)的大小最多為表達(dá)式節(jié)點(diǎn)數(shù)量，因此空間復(fù)雜度為O(n)。Halide 編譯器中的循環(huán)不變量外提算法也是在樹結(jié)構(gòu)的中間表示上進(jìn)行，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。本文算法的時(shí)間和空間復(fù)雜度都不差于Halide編譯器的循環(huán)不變量外提算法。

傳統(tǒng)編譯器中的循環(huán)不變量外提算法，如LLVM中的外提算法，都是在基于基本塊的流圖上設(shè)計(jì)和實(shí)現(xiàn)的。這種實(shí)現(xiàn)方式主要的缺點(diǎn)是程序在下降的過程中丟失了如循環(huán)、作用域以及條件表達(dá)式等高層程序信息，因此在執(zhí)行循環(huán)不變量外提算法前這些必要信息都要通過額外的操作來(lái)恢復(fù)。另外，在編譯器低層次的中間表示中，表達(dá)式或語(yǔ)句的表示形式發(fā)生了改變，這導(dǎo)致原本在高級(jí)表示上顯而易見的優(yōu)化時(shí)機(jī)在后面的優(yōu)化中很難被發(fā)現(xiàn)。而本算法充分利用了深度學(xué)習(xí)編譯器的主要特點(diǎn)，面向其高級(jí)中間表示實(shí)現(xiàn)循環(huán)不變式外提，彌補(bǔ)了傳統(tǒng)循環(huán)不變量外提算法的不足。另外，該算法和已有的類似循環(huán)不變式算法也很不相同，如本算法使用的新的前置處理方式對(duì)表達(dá)式做變換，而不僅僅是像Halide 那樣只對(duì)加法減法表達(dá)式做重結(jié)合；這使得本算法對(duì)冗余消除得更為徹底，避免了需要對(duì)外提的不變量做公共子表達(dá)式消除的額外工作，讓目標(biāo)平臺(tái)編譯器更加簡(jiǎn)化。

3.3 規(guī)范化

規(guī)范化指的是通過對(duì)語(yǔ)句和表達(dá)式進(jìn)行保語(yǔ)義的變換，使得變換后的程序更利于后續(xù)循環(huán)不變量外提，或目標(biāo)平臺(tái)編譯器的優(yōu)化。規(guī)范化最主要的操作包括：調(diào)整表達(dá)式中操作數(shù)的順序和對(duì)條件表達(dá)式和分支的合并操作。調(diào)整操作數(shù)順序是指利用特定的代數(shù)性質(zhì)，如結(jié)合律、交換律和分配律等，對(duì)表達(dá)式進(jìn)行重結(jié)合優(yōu)化，將其劃分成常數(shù)部分、循環(huán)不變部分和變量部分。盡管這本身并不能改進(jìn)性能，但由于某個(gè)表達(dá)式的子表達(dá)式是否為循環(huán)不變表達(dá)式，很大程度上取決于操作數(shù)的運(yùn)算順序和結(jié)合關(guān)系[16]，因此，調(diào)整表達(dá)式操作數(shù)順序能夠給循環(huán)不變式外提優(yōu)化帶來(lái)明顯的提升效果。例如，假設(shè)下面給定的兩個(gè)表達(dá)式中，只有i是循環(huán)迭代變量，j為外層循環(huán)的迭代變量：

表達(dá)式（1）對(duì)應(yīng)的抽象語(yǔ)法樹如圖2 所示，算法會(huì)計(jì)算得到兩個(gè)候選的循環(huán)不變式：(3 ＜j)和(j＜56)。而表達(dá)式（1）在規(guī)范化過程中，把(3 ＜j)和(j＜56)放到了一起，得到表達(dá)式（2），其對(duì)應(yīng)的抽象語(yǔ)法樹如圖3 所示，表達(dá)式順序調(diào)整后的作用如下：變換之前的兩個(gè)循環(huán)不變式(3 ＜j)和(j＜56)在調(diào)整順序后形成了新的循環(huán)不變式((3 ＜j)&&(j＜56))，比原先的多外提了一個(gè)取并的運(yùn)算操作。根據(jù)以上的觀察，調(diào)整表達(dá)式的操作數(shù)結(jié)合順序的思路為：對(duì)于某個(gè)滿足結(jié)合律的運(yùn)算，把操作數(shù)按照所包含循環(huán)迭代變量對(duì)應(yīng)循環(huán)的嵌套深度，以遞增或遞減進(jìn)行排序后結(jié)合到一起，這樣的操作能夠?qū)⒎稚⒌难h(huán)不變式結(jié)合到一起，利于循環(huán)不變量表達(dá)式的發(fā)現(xiàn)?；谝陨咸攸c(diǎn)，可按如下步驟把循環(huán)不變的表達(dá)式結(jié)合到一起：

圖2 表達(dá)式（1）的抽象語(yǔ)法樹Fig.2 Abstract syntax tree of expression(1)

圖3 表達(dá)式（2）的抽象語(yǔ)法樹Fig.3 Abstract syntax tree of expression（2）

（1）為每一個(gè)表達(dá)式e綁定一個(gè)整數(shù)rank：

（2）若表達(dá)式e為常數(shù)，則為其綁定rank為0；

（3）若表達(dá)式e為循環(huán)迭代變量，則為其綁定rank為嵌套循環(huán)的深度，否則：

①綁定定義該變量的操作數(shù)的最大rank值。

②對(duì)于滿足結(jié)合律的運(yùn)算，按照rank值遞增為每個(gè)表達(dá)式排序后，重新結(jié)合為新的表達(dá)式。

條件表達(dá)式對(duì)應(yīng)判斷條件的成立和不成立，都有對(duì)應(yīng)的返回值，而在嵌套的條件表達(dá)式中，多個(gè)判斷條件成立與否可能對(duì)應(yīng)于同一個(gè)返回值，對(duì)此，可以合并這些具有相同返回值的判斷條件，使得變換后的表達(dá)式中的循環(huán)不變量更完整。例如，假設(shè)下面的表達(dá)式中只有i是循環(huán)迭代變量：

表達(dá)式（3）對(duì)應(yīng)的語(yǔ)法樹如圖4 所示，算法確定的候選循環(huán)不變式為3 ＜j和j＜56。表達(dá)式（3）經(jīng)過化簡(jiǎn)后得到條件表達(dá)式：

圖4 表達(dá)式（3）的抽象語(yǔ)法樹Fig.4 Abstract syntax tree of expression（3）

其對(duì)應(yīng)的語(yǔ)法樹如圖5 所示，算法發(fā)現(xiàn)了更好的候選循環(huán)不變表達(dá)式((3 ＜j)&&(j＜56))，并且((3 ＜i)&&(i＜56))和((3 ＜j)&&(j＜56))這兩個(gè)表達(dá)式的形式更利于實(shí)現(xiàn)與布爾表達(dá)式相關(guān)的窺孔優(yōu)化。最后，對(duì)于相鄰的具有相同跳轉(zhuǎn)條件的分支，算法可以合并這些分支語(yǔ)句。算法2 給出了規(guī)范化算法Normalize(T)的偽代碼實(shí)現(xiàn)。

圖5 表達(dá)式（4）的抽象語(yǔ)法樹Fig.5 Abstract syntax tree of expression（4）

算法2表達(dá)式規(guī)范化算法

該算法接受原始程序T作為輸入，并輸出優(yōu)化后的程序。算法遍歷程序T中的表達(dá)式e，并根據(jù)表達(dá)式e的語(yǔ)法形式對(duì)其進(jìn)行處理：如果表達(dá)式e為條件表達(dá)式if(e1,e2,e3)，則算法調(diào)用函數(shù)condCollapse(e)，對(duì)可以進(jìn)行判斷條件合并的表達(dá)式e進(jìn)行優(yōu)化，并返回優(yōu)化后的結(jié)果。接下來(lái)，算法按照前面討論的步驟，計(jì)算表達(dá)式e中的所有變量和子表達(dá)式的rank值。對(duì)于完成rank值計(jì)算的表達(dá)式e，算法遍歷其所有滿足結(jié)合律的操作符⊕，調(diào)用deconstruct(e,⊕)將由操作符⊕連接的子表達(dá)式轉(zhuǎn)換為有序子表達(dá)式序列L；然后，算法調(diào)用函數(shù)stableSort(L)使用穩(wěn)定排序算法將L按照rank值從小到大排序并返回排序后的序列L；最后，算法調(diào)用函數(shù)groupExpressions(L,⊕)將L中相同rank值的子表達(dá)式用操作符⊕連接為新的表達(dá)式并返回變換后的序列L，并調(diào)用函數(shù)construct(L,⊕)用操作符⊕依序?qū)中的所有子表達(dá)式連接，并返回變換后的最終結(jié)果e。算法對(duì)程序T中的所有表達(dá)式遍歷結(jié)束后，調(diào)用函數(shù)ifconcat(T)合并T中相鄰的具有相同分支條件的分支語(yǔ)句，并返回變換后的程序T。函數(shù)ifconcat(T)本質(zhì)上完成控制流優(yōu)化，通過對(duì)分支語(yǔ)句進(jìn)行合并優(yōu)化，可有效減少語(yǔ)句和表達(dá)式的數(shù)量，減少優(yōu)化算法的執(zhí)行時(shí)間。Normalize 算法的輸入T是一棵樹，設(shè)樹中的語(yǔ)句節(jié)點(diǎn)和表達(dá)式的數(shù)量為n，外層循環(huán)遍歷T中的表達(dá)式節(jié)點(diǎn)，condCollapse 所需時(shí)間和判斷條件數(shù)量線性相關(guān)；loopDepth 函數(shù)遞歸求每個(gè)變量的嵌套深度，在遞歸過程中保存遇到的變量的嵌套深度，因此每個(gè)變量的深度只會(huì)被求一次，所需時(shí)間和表達(dá)式數(shù)量線性相關(guān)。最后一個(gè)內(nèi)層循環(huán)對(duì)表達(dá)式重結(jié)合，deconstruct、groupExpressions 和construct 都是和表達(dá)式數(shù)量相關(guān)的線性時(shí)間；stableSort 排序算法根據(jù)rank值進(jìn)行排序，因?yàn)槊總€(gè)表達(dá)式的rank值都是0 到嵌套深度之間的整數(shù)值，可以使用計(jì)數(shù)排序，該排序算法為線性時(shí)間復(fù)雜度，ifconcat 和T的語(yǔ)句數(shù)線性相關(guān)，因此Normalize 算法時(shí)間復(fù)雜度為O(n)?？臻g復(fù)雜度的分析和LICM 的思路相同，也為O(n)。

傳統(tǒng)的標(biāo)量編譯器在進(jìn)行循環(huán)不變式外提前，也都會(huì)執(zhí)行代數(shù)化簡(jiǎn)和表達(dá)式重結(jié)合等優(yōu)化遍，來(lái)完成前置的處理和準(zhǔn)備工作。而在深度學(xué)習(xí)編譯器中，和內(nèi)存讀寫相關(guān)操作的優(yōu)化應(yīng)該在更加低級(jí)的中間表示上進(jìn)行，代數(shù)化簡(jiǎn)和常量傳播等優(yōu)化由TVM 原生的simplify 優(yōu)化遍完成，因此，規(guī)范化算法可以更專注于對(duì)下標(biāo)和條件表達(dá)式進(jìn)行特定變換，以有利于循環(huán)不變量外提優(yōu)化和控制流優(yōu)化的實(shí)現(xiàn)。

3.4 代價(jià)函數(shù)

代價(jià)函數(shù)cost(e)接受表達(dá)式e作為輸入，計(jì)算并返回e的外提代價(jià)值。當(dāng)且僅當(dāng)該函數(shù)的返回值大于等于給定的閾值K時(shí)，編譯器才認(rèn)為有足夠的收益，并將該表達(dá)式e進(jìn)行外提。需要計(jì)算代價(jià)函數(shù)cost(e)的原因是TVM 生成的高層算子代碼，還要經(jīng)過目標(biāo)平臺(tái)編譯器的編譯，才能生成真正目標(biāo)硬件上的可執(zhí)行程序。由于目標(biāo)平臺(tái)編譯器會(huì)在更低層次的中間表示上對(duì)程序做一系列優(yōu)化，兩個(gè)不同層次的優(yōu)化之間可能產(chǎn)生矛盾，比如外提循環(huán)不變量和后端寄存器分配優(yōu)化存在矛盾，當(dāng)循環(huán)內(nèi)的一條指令的執(zhí)行需要一個(gè)不變表達(dá)式的執(zhí)行結(jié)果時(shí)，有兩種方法可以獲取這個(gè)結(jié)果：（1）每次指令執(zhí)行前重新計(jì)算；（2）將計(jì)算結(jié)果保存在變量中，每次指令執(zhí)行前使用該變量。方法（1）中重復(fù)計(jì)算相同的表達(dá)式增加了冗余計(jì)算，但是減少了變量聲明周期，降低了寄存器壓力，利于有序寄存器分配優(yōu)化。方法（2）消除了多次計(jì)算不變表達(dá)式的冗余計(jì)算，但是增加了變量生命周期，增加寄存器壓力，可能導(dǎo)致后續(xù)寄存器分配優(yōu)化效果下降。為了權(quán)衡消除冗余計(jì)算和寄存器分配優(yōu)化之間的矛盾，避免兩個(gè)不同層次的優(yōu)化相互干擾，設(shè)計(jì)了一個(gè)代價(jià)函數(shù)cost(e)來(lái)計(jì)算表達(dá)式的代價(jià)，指導(dǎo)算法外提循環(huán)不變式。表達(dá)式代價(jià)值代表了計(jì)算表達(dá)式所需開銷，也就是外提表達(dá)式的收益，因此僅當(dāng)代價(jià)值大于某一閾值K時(shí)，算法才對(duì)該表達(dá)式做外提。對(duì)表達(dá)式e的代價(jià)函數(shù)cost(e)定義為：

當(dāng)e是常數(shù)或變量時(shí)，其代價(jià)定義為0；當(dāng)e是復(fù)合表達(dá)式時(shí)，其代價(jià)遞歸定義在其子表達(dá)式a上，另外加上其運(yùn)算符⊕的代價(jià)。下面以一個(gè)具體的表達(dá)式x/1024+y為例，詳細(xì)說明代價(jià)值的計(jì)算方式。根據(jù)定義有：

不同的運(yùn)算⊕根據(jù)其需要的時(shí)鐘周期的不同定義了不同的代價(jià)，其中加法指令需要的時(shí)鐘周期較少，設(shè)置cost(+)=1，除法指令需要的時(shí)鐘周期較多，設(shè)置cost(/)=3。因此有cost(x/1 024+y)=1+3+0+0+0=4。這個(gè)基礎(chǔ)的代價(jià)函數(shù)cost(e)可以修改為適合于不同硬件平臺(tái)的代價(jià)函數(shù)，例如，對(duì)于GPU 平臺(tái)，其平臺(tái)上的編譯器NVCC 通常選擇展開迭代范圍很小的循環(huán)，并在此基礎(chǔ)上執(zhí)行其他的優(yōu)化。因此，可以設(shè)置循環(huán)迭代范圍很小的循環(huán)中的表達(dá)式代價(jià)值為0，避免兩個(gè)不同層次的優(yōu)化互相干擾。

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

4.1 研究問題

實(shí)驗(yàn)主要回答以下兩個(gè)研究問題：

（1）性能。本文提出的新的循環(huán)不變式外提算法是否能夠提升實(shí)際TVM 生成算子的性能？以及對(duì)哪些算子會(huì)造成一些特殊情況性能下降？如果有下降，原因是什么？

（2）正確性。本文算法改變了操作數(shù)的順序，對(duì)于優(yōu)化后生成的算子的正確性（即計(jì)算精度）是否會(huì)造成影響？

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

實(shí)驗(yàn)使用英偉達(dá)的NVCC 編譯器的10.0 版本作為GPU 平臺(tái)的編譯器。所有實(shí)驗(yàn)數(shù)據(jù)都在表1 所示配置的服務(wù)器上收集得到。

表1 實(shí)驗(yàn)環(huán)境Table 1 Setup of experiment

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

實(shí)驗(yàn)選擇了TVM 的TOPI 算子庫(kù)中的部分算子在不同輸入規(guī)模下的實(shí)現(xiàn)，作為本次實(shí)驗(yàn)的基準(zhǔn)測(cè)試集，本次測(cè)試涉及27 個(gè)算子和511 個(gè)測(cè)例。表2 列出了本次實(shí)現(xiàn)選擇的所有算子及其測(cè)例數(shù)量。這些算子屬于深度學(xué)習(xí)框架和TVM 常用的算子，并且實(shí)驗(yàn)對(duì)每一個(gè)算子都提供了大量在常見神經(jīng)網(wǎng)絡(luò)中不同輸入規(guī)模的測(cè)例，在這些測(cè)例上的實(shí)驗(yàn)結(jié)果具有一定的代表性。

表2 算子測(cè)試集Table 2 Benchmark of operators

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

在研究算法對(duì)性能的影響時(shí)，為了減少實(shí)驗(yàn)誤差，認(rèn)為那些優(yōu)化前后生成代碼相同和運(yùn)行時(shí)間小于50 μs 的測(cè)例為無(wú)效測(cè)例，且不考慮運(yùn)行時(shí)間波動(dòng)低于1%的測(cè)例。表2 給出了每個(gè)算子的有效測(cè)例數(shù)量，稱有效測(cè)例數(shù)量大于0 的算子為有效算子。定義算子運(yùn)行加速比S為：

其中，T0為原生TVM 生成算子的運(yùn)行時(shí)間，T1為本次實(shí)驗(yàn)的原型系統(tǒng)生成算子的運(yùn)行時(shí)間（即經(jīng)循環(huán)不變式外提優(yōu)化后算子運(yùn)行時(shí)間）。定義算子平均加速比A為所有測(cè)例的加速比的算術(shù)平均值：

圖6（a）給出了有效算子的平均加速比，圖6（b）給出了有效算子運(yùn)行時(shí)間加速比。圖中的綠色虛線代表加速比為101%，橙色實(shí)線代表加速比為99%。從算子平均加速比的角度來(lái)看，相比原生TVM 編譯得到的算子，本文算法編譯得到的算子中有10 個(gè)算子性能得到了提升，占有效算子的47.6%，性能提升最明顯的算子為conv3d_winograd，其加速比達(dá)到141.46%；只有1 個(gè)算子性能下降，占有效算子的4.7%，該性能下降的算子為conv2d_hwcn，其加速比為97.60%；其余算子性能不變。從算子總時(shí)間加速比的角度來(lái)看，相比原生TVM 編譯得到的算子，本文算法編譯得到的算子中有10 個(gè)算子性能得到了提升，占有效算子的47.6%，性能提升最明顯的算子為conv3d_transpose_ncdhw，加速比為142.91%；只有1個(gè)算子性能下降，占有效算子的4.7%，該性能下降的算子為conv2d_hwcn，加速比為97.10%；其余算子性能不變。所有算子的總時(shí)間加速比為122.7%。對(duì)性能得到提升的測(cè)例，進(jìn)一步分析了其優(yōu)化前后生成的代碼，發(fā)現(xiàn)表達(dá)式中的循環(huán)不變式被提出了循環(huán)外，分支和條件表達(dá)式也得到了相應(yīng)的優(yōu)化。首先，循環(huán)內(nèi)的指令數(shù)目減少了，一部分循環(huán)不變的指令被移到了循環(huán)外；其次，計(jì)算謂詞的指令得到了優(yōu)化，一些有公共操作數(shù)的比較指令被減法或其他指令替換；再次，分支指令也用謂詞執(zhí)行來(lái)替換，減少了分支指令的數(shù)量；最后，因?yàn)檠h(huán)內(nèi)指令減少或者簡(jiǎn)化，nvcc 編譯器對(duì)內(nèi)層循環(huán)進(jìn)行了更大范圍的循環(huán)展開，同時(shí)其他的優(yōu)化遍對(duì)展開后的循環(huán)體進(jìn)行了更好的優(yōu)化。對(duì)優(yōu)化后性能下降的一個(gè)測(cè)例，進(jìn)一步分析發(fā)現(xiàn)只有少量的簡(jiǎn)單表達(dá)式被提出了循環(huán)外，循環(huán)內(nèi)的控制流結(jié)構(gòu)和指令數(shù)基本沒有發(fā)生變化，這些簡(jiǎn)單指令的延遲原本就會(huì)被流水線隱藏；另外，一些指令和同步指令的相對(duì)位置發(fā)生了變化，一些原本在同步指令后的計(jì)算被移動(dòng)到了同步指令之前，可能改變后指令調(diào)度時(shí)的優(yōu)化效果。需要特別注意的是，盡管這個(gè)特定算子的性能出現(xiàn)下降，但其2.9%的小幅下降仍然在可接受的范圍內(nèi)。

圖6 算子加速比Fig.6 Operator speedups

另外，根據(jù)本算法對(duì)于不同類型的算子性能提升幅度不同，具體分析了本文循環(huán)不變式外提算法的使用場(chǎng)景。對(duì)于conv3d_winograd、conv3d_transpose_ncdhw 這類實(shí)現(xiàn)復(fù)雜的算子，經(jīng)過前端調(diào)度優(yōu)化后得到的中間表示包含大量的嵌套循環(huán)和嵌套條件表達(dá)式，本文算法對(duì)這類使用場(chǎng)景能夠減少循環(huán)內(nèi)的計(jì)算和分支，利于后端編譯器優(yōu)化的進(jìn)行。在這類使用場(chǎng)景下本文算法能夠起到顯著的性能提升效果。對(duì)于像conv2d_hwcn、depthwise_conv2d_back_input 等這類算子代碼中循環(huán)和條件表達(dá)式嵌套數(shù)較少，表達(dá)式形式較為簡(jiǎn)單，部分簡(jiǎn)單形式的冗余計(jì)算在底層編譯器優(yōu)化中也能被消除。且由于外提計(jì)算導(dǎo)致其中同步指令的相對(duì)位置發(fā)生變化，可能改變后續(xù)指令調(diào)度優(yōu)化的效果。在這類使用場(chǎng)景下本文算法對(duì)于算子性能的提升可能得不到令人滿意的效果。

為了進(jìn)一步證明算法改進(jìn)的有效性，選擇Halide編譯器的循環(huán)不變量外提優(yōu)化與本文算法的優(yōu)化效果進(jìn)行比較，實(shí)驗(yàn)將Halide 編譯器的循環(huán)不變量外提優(yōu)化遍經(jīng)過適配移植到了TVM 上。在原生優(yōu)化遍的基礎(chǔ)上，添加了對(duì)于條件表達(dá)式和其他符合運(yùn)算結(jié)合律的運(yùn)算的外提支持。實(shí)驗(yàn)結(jié)果如圖7 所示，本次實(shí)驗(yàn)中最小的加速比為90%，因此將加速比減去89%后以2 為底取對(duì)數(shù)，以上操作是為了直觀地對(duì)比兩個(gè)算法的優(yōu)劣，每個(gè)縱坐標(biāo)計(jì)算方式為lb((s-89%)×100)，其中，s表示算子加速比。紅色的柱形表示Halide 編譯器的循環(huán)不變量外提算法的優(yōu)化效果。本次實(shí)驗(yàn)的有效算子測(cè)例中，忽略性能波動(dòng)小于1%的測(cè)例。同時(shí)本文認(rèn)為兩個(gè)算法優(yōu)化算子性能差異小于1%時(shí)為實(shí)驗(yàn)誤差。實(shí)驗(yàn)結(jié)果顯示，本文算法相比于另一比較算法，在5 個(gè)算子的性能提升效果上明顯更優(yōu)，占有效測(cè)試算子的23.81%；僅在1 個(gè)算子的性能提升效果上較差。其余71.42%的算子測(cè)例的性能提升效果差別不大。從優(yōu)化效果明顯提升的例子，如conv3d_transpose_ncdhw、depthwise_conv2d_back_weight 和conv3d_winograd 等復(fù)雜算子測(cè)例的生成代碼中觀察到，相比比較算法，本文算法在對(duì)于嵌套條件表達(dá)式、不變式的重結(jié)合方面表現(xiàn)都更好，外提了一部分沒有被比較算法發(fā)現(xiàn)的不變式，減少了跳轉(zhuǎn)指令數(shù)量。而觀察性能下降的例子conv2d_hwcn，經(jīng)過Halide 循環(huán)不變量外提算法優(yōu)化后算子性能沒有發(fā)生變化，而本算法的變化導(dǎo)致了性能的輕微下降，大約為2.9%。生成代碼中控制流結(jié)構(gòu)和指令數(shù)基本不變，但有一部分計(jì)算和同步指令的相對(duì)位置發(fā)生了變化，可能導(dǎo)致底層編譯優(yōu)化效果的下降。從總體效果來(lái)看，本文算法對(duì)算子性能提升效果明顯優(yōu)于比較算法，進(jìn)一步證明了本文對(duì)于循環(huán)不變量外提算法改進(jìn)的有效性。

圖7 本文算法與Halide編譯器的LICM 算法對(duì)比Fig.7 Comparison between proposed algorithm and Halide’s LICM

本次實(shí)驗(yàn)研究的第二個(gè)問題為算子的準(zhǔn)確性，算子的準(zhǔn)確性主要由算子計(jì)算結(jié)果的精度來(lái)衡量。影響算子計(jì)算準(zhǔn)確性的主要因素有硬件計(jì)算單元本身精度和數(shù)據(jù)計(jì)算順序。硬件計(jì)算單元精度和實(shí)驗(yàn)硬件平臺(tái)緊密相關(guān)，本次實(shí)驗(yàn)選擇NVIDIA Tesla P4圖形處理器。數(shù)據(jù)計(jì)算順序主要依賴于前端的調(diào)度，另外優(yōu)化遍對(duì)于中間表示的變換也會(huì)改變計(jì)算順序，本文算法實(shí)現(xiàn)的優(yōu)化遍只對(duì)于滿足運(yùn)算結(jié)合律的運(yùn)算改變計(jì)算順序，不會(huì)改變運(yùn)算結(jié)果。為研究本文算法的正確性，對(duì)所有測(cè)例在GPU 上的運(yùn)行結(jié)果與Python 實(shí)現(xiàn)的等價(jià)測(cè)例在CPU 上的運(yùn)行結(jié)果進(jìn)行了比較，由于浮點(diǎn)數(shù)的相等測(cè)試的約束，本實(shí)驗(yàn)設(shè)置誤差容忍度為1E-5。實(shí)驗(yàn)結(jié)果表明100%的測(cè)例實(shí)驗(yàn)結(jié)果誤差小于1E-5，這證實(shí)了本文算法的正確性。

4.5 結(jié)論

本文以TVM（0.7 版本）為基礎(chǔ)，實(shí)現(xiàn)了添加循環(huán)不變式外提優(yōu)化算法的原型系統(tǒng)，并在TVM 的TOPI算子測(cè)試集上針對(duì)27 個(gè)算子的511 個(gè)測(cè)例進(jìn)行測(cè)試，并收集實(shí)驗(yàn)結(jié)果。對(duì)實(shí)驗(yàn)結(jié)果的分析表明，本文提出的循環(huán)不變式外提算法，彌補(bǔ)了閉源編譯器NVCC在對(duì)復(fù)雜表達(dá)式的冗余刪除和控制流優(yōu)化存在的不足，完善了TVM 生成算子的優(yōu)化過程，對(duì)算子性能提升產(chǎn)生了積極的作用。

5 結(jié)語(yǔ)

本文針對(duì)深度學(xué)習(xí)編譯器，提出了一種新的循環(huán)不變式外提優(yōu)化算法，并基于開源TVM 的0.7 版本實(shí)現(xiàn)了原型系統(tǒng)。對(duì)TVM 中的TOPI 算子庫(kù)中的27個(gè)算子和511 個(gè)測(cè)例進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該新優(yōu)化算法在保證正確性的情況下有效提升了算子性能。本文工作為TVM 或者其他深度學(xué)習(xí)編譯器移植傳統(tǒng)循環(huán)不變式外提算法提供了有益參考。