領(lǐng)域編譯器發(fā)展的前世今生

本文分為兩個部分，第一部分為綜述，第二部分重點(diǎn)討論AI編譯技術(shù)。

近年來，隨著GPU和DSA架構(gòu)在不同領(lǐng)域的廣泛應(yīng)用，特別是AI系統(tǒng)相關(guān)技術(shù)的飛速發(fā)展，對于編譯器的需求越來越強(qiáng)烈。編譯器已經(jīng)從一個相對小眾的研究領(lǐng)域，變?yōu)閷W(xué)界和業(yè)界都高度關(guān)注并大量投入的方向。與此同時，編譯器的開發(fā)人員也從芯片研發(fā)團(tuán)隊(duì)開始延伸到更上層的軟件層面。在很多領(lǐng)域的軟件系統(tǒng)中，都開始引入編譯技術(shù)來實(shí)現(xiàn)提升開發(fā)效率或運(yùn)行效率等目標(biāo)。本文從領(lǐng)域編譯器的角色著眼，來討論領(lǐng)域編譯器發(fā)展的前世今生。

通用編譯器 vs. 領(lǐng)域編譯器

編譯器作為芯片配套的重要基礎(chǔ)軟件，它向上封裝高級語言從而提高應(yīng)用軟件的開發(fā)效率和兼容性，向下適應(yīng)體系結(jié)構(gòu)而生成高效的可執(zhí)行代碼，是溝通軟硬件之間的橋梁。一方面，通用編譯器負(fù)責(zé)將某種編程語言映射到某種特定的芯片，例如Intel平臺的C語言編譯器負(fù)責(zé)將C語言的程序映射為Intel的X86指令集。通用編譯器在設(shè)計(jì)編譯優(yōu)化時，會將通用性作為最重要的出發(fā)點(diǎn)之一。為了更便捷高效的支持更多語言（前端）以及更多目標(biāo)芯片（后端），GCC、LLVM等框架逐漸成為重要的編譯基礎(chǔ)設(shè)施，它們都集成了非常多的通用編譯優(yōu)化組件，如循環(huán)優(yōu)化、指令級優(yōu)化、存儲層次優(yōu)化等。另一方面，領(lǐng)域編譯器面向某些特定的領(lǐng)域應(yīng)用程序而設(shè)計(jì)，旨在大幅提升該領(lǐng)域研發(fā)人員的編程效率或程序的運(yùn)行性能。因此領(lǐng)域編譯器在設(shè)計(jì)編譯優(yōu)化時，會將該領(lǐng)域的應(yīng)用特征進(jìn)行一定的總結(jié)抽象，形成領(lǐng)域特定的一些計(jì)算模式，并根據(jù)這些模式來設(shè)計(jì)針對性的優(yōu)化，例如面向Stencil計(jì)算特征的優(yōu)化等。

結(jié)合領(lǐng)域編程語言的領(lǐng)域編譯器

早期的領(lǐng)域編譯技術(shù)伴隨領(lǐng)域編程語言（DSL）開始發(fā)展，作為解決通用編譯技術(shù)難以在特定領(lǐng)域生成高性能代碼的解決方案出現(xiàn)。DSL會針對領(lǐng)域的特征設(shè)計(jì)易于描述領(lǐng)域問題的編程語言（創(chuàng)建新語言或從現(xiàn)有語言擴(kuò)展），通常使用專用的IR中間表示（一層或多層）來對領(lǐng)域知識進(jìn)行表示，這些領(lǐng)域知識的引入可以極大的方便編譯器的分析和優(yōu)化。領(lǐng)域編程語言的提出有兩個目標(biāo)：一是為了大大的簡化領(lǐng)域開發(fā)用戶的編程復(fù)雜性，這方面的代表性語言是數(shù)據(jù)庫查詢語言SQL[1]，它通過對數(shù)據(jù)庫常用操作進(jìn)行抽象為用戶提供了非常便捷的編程接口，然后利用編譯器將其映射到底層數(shù)據(jù)庫引擎所提供的操作接口；二是為了大幅提升領(lǐng)域應(yīng)用的運(yùn)行性能，這方面的代表性語言是Halide[2]，它為圖像處理領(lǐng)域提供了一種抽象層面的編程語言，基于這一語言編譯器以調(diào)度的形式來抽象底層優(yōu)化，從而避免了傳統(tǒng)編譯器中為了通用程序的正確性而引入的復(fù)雜的分析機(jī)制，使其可以非常便捷的在調(diào)度空間中通過搜索從而得到一個性能很高的目標(biāo)代碼。

領(lǐng)域編譯器相比較于通用編譯器，它仍然是一個解析高級語言，生成中間表示并優(yōu)化，最后代碼生成的系統(tǒng)。它在設(shè)計(jì)上會有更多的選擇理念，除去領(lǐng)域無關(guān)的通用優(yōu)化外，它還需要增加領(lǐng)域知識的專用表示，面向領(lǐng)域特定特征的專門優(yōu)化等等。在系統(tǒng)實(shí)現(xiàn)上，有的是將領(lǐng)域編譯實(shí)現(xiàn)在通用編譯器中，有的是在通用編譯器的前端增加一個高層次的領(lǐng)域編譯器。前者以LLDB[3]為例，LLDB是clang/llvm架構(gòu)的調(diào)試器，使用類似GDB的調(diào)試語句來調(diào)試程序運(yùn)行，調(diào)試的需求主要在動態(tài)調(diào)控程序運(yùn)行，獲得調(diào)試信息，而這些都是通用clang/llvm架構(gòu)中包含的，因而LLDB的實(shí)現(xiàn)上套用了clang/llvm的基礎(chǔ)設(shè)施。像LLDB這樣能夠緊密結(jié)合在通用編譯器基礎(chǔ)設(shè)施的領(lǐng)域編譯器還是比較少的，更多的DSL編譯器的做法則是采用了將高層次的領(lǐng)域編譯器作為前端插在通用編譯器，如LLVM之前。DSL程序通過領(lǐng)域編譯器的前端將DSL做詞法語法解析生成高層次IR（一層或多層），該IR包含領(lǐng)域知識的數(shù)據(jù)結(jié)構(gòu)，在高層IR上可以做專用的領(lǐng)域知識優(yōu)化，也可以做通用的編譯優(yōu)化，然后生成通用編程語言的輸出，如C/CUDA/OpenCL/ LLVM IR等。之后交由通用編譯器完成匯編生成，鏈接最終生成可執(zhí)行程序。這一設(shè)計(jì)不需要關(guān)注編譯的后端部分，因而可以把重點(diǎn)放在利用領(lǐng)域?qū)Ｓ兄R對程序的優(yōu)化上，通用優(yōu)化則可以交給通用編譯器來完成。

在過去幾十年中，很多領(lǐng)域都提出了代表性的領(lǐng)域編程語言及編譯器，這里我們對幾個代表性的工作進(jìn)行簡單的介紹。

01面向圖像處理領(lǐng)域的Halide

Halide是MIT計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室的研究人員開發(fā)的一門新的編程語言，旨在改變圖像處理領(lǐng)域編程的現(xiàn)狀。Halide語言將算法描述與算法中數(shù)據(jù)存儲與計(jì)算執(zhí)行等調(diào)度方面的內(nèi)容解耦合。從而算法的描述和性能的優(yōu)化可以分開進(jìn)行，可以在不改動算法的情況下對算法進(jìn)行調(diào)優(yōu)。它將代碼分為Algorithm和Schedule兩個部分，Algorithm部分僅僅描述算法的功能，不進(jìn)行實(shí)際的實(shí)現(xiàn)；Schedule部分指定算法在何時何處進(jìn)行計(jì)算。使得比起用傳統(tǒng)語言編寫的代碼，用Halide編寫的程序不僅更容易閱讀、編寫和修改，而且 Halide能夠自動優(yōu)化代碼，而人工對代碼進(jìn)行優(yōu)化加速，這個過程需要花費(fèi)數(shù)小時來完成。針對幾種常用的圖像處理算法，將Halide的版本與人工優(yōu)化的版本進(jìn)行比較，在不同平臺上的運(yùn)行結(jié)果如圖所示?？梢?，在前3個算法中Halide版本的算法不僅簡化了代碼量，同時性能有著極大的提升。

02面向Stencil計(jì)算的領(lǐng)域編程語言

Stencil計(jì)算是數(shù)值模擬程序中常見的循環(huán)運(yùn)算模式，其特點(diǎn)是遍歷計(jì)算區(qū)域，每個位置均執(zhí)行相同的計(jì)算操作指令模板（stencil），所以將這種計(jì)算稱作stencil計(jì)算。stencil計(jì)算大量出現(xiàn)在科學(xué)計(jì)算領(lǐng)域，并且通常負(fù)載延時敏感應(yīng)用。因而使用者通常希望將其卸載到高性能設(shè)備如GPU上，以提升端到端性能，但在GPU上，片外內(nèi)存訪問和GPU計(jì)算單元的調(diào)度是不同于CPU的，這是編譯stencil計(jì)算程序到GPU執(zhí)行不可忽略的問題。俄亥俄州大的團(tuán)隊(duì)設(shè)計(jì)了一款面向stencil計(jì)算的DSL[5]，用戶只需要簡單的高層stencil操作描述，通過DSL編譯器分析stencil操作類型，訪存模式，根據(jù)GPU編程模型，自動生成tile size，shared memory優(yōu)化，block間同步等優(yōu)化。這些優(yōu)化減少了訪存帶寬瓶頸，增加了處理單元utility，最終生成了在GPU上運(yùn)行性能更高的stencil程序。

Stencil計(jì)算常見模板[6]

03面向矩陣計(jì)算的領(lǐng)域編程語言HTA

Tiling算法是挖掘并行性，優(yōu)化數(shù)據(jù)局部性重要的方法。HTA(HierarchicallyTiled Arrays)[7]是一個在現(xiàn)代OOP語言上擴(kuò)展的面向數(shù)組tiling描述的數(shù)據(jù)結(jié)構(gòu)。通過HTA，許多科學(xué)計(jì)算算法，如LU分解，分塊矩陣計(jì)算，stencil計(jì)算等，都容易通過tile來表示，而HTA的數(shù)據(jù)布局，tile管理都可以自動進(jìn)行，而無需涉及到最底層每個元素的計(jì)算，從而大大減少了下標(biāo)計(jì)算的描述，簡化了函數(shù)接口，極大地降低了描述并行程序的復(fù)雜性，同時仍然達(dá)到了庫級別的高性能。HTA還引入了dynamic partitioning和overlapped tiling的語言特性，進(jìn)一步增強(qiáng)了tiling描述的靈活性和普適性。

HTA的tiling描述[8]

04面向圖計(jì)算的領(lǐng)域編程語言GraphIt

GraphIt [9]是一種用于圖計(jì)算的新 DSL，它可以為在具有不同大小和結(jié)構(gòu)的圖上運(yùn)行的具有不同性能特征的算法生成快速實(shí)現(xiàn)。GraphIt 將計(jì)算的內(nèi)容（算法）與計(jì)算的方式（調(diào)度）分開。程序員使用算法語言指定算法，而性能優(yōu)化使用單獨(dú)的調(diào)度語言指定。調(diào)度語言使程序員能夠通過將大量邊遍歷和頂點(diǎn)數(shù)據(jù)布局優(yōu)化組合在一起，輕松地搜索這個復(fù)雜的權(quán)衡空間。GraphIt 的性能比當(dāng)時最先進(jìn)的共享內(nèi)存框架（包括Ligra、Green-Marl、GraphMat、Galois、Gemini 和 Grazelle）快最多4.8 倍，同時代碼行數(shù)最多減少了一個數(shù)量級。

Graphlt與多種框架的圖計(jì)算性能比較[10]

05面向張量的領(lǐng)域編譯器TACO

張量代數(shù)編譯器 (Tensor Algebra COmpiler：TACO)[11] 是一個用于計(jì)算稀疏和密集張量上的張量代數(shù)表達(dá)式的代碼生成工具，特別針對稀疏張量做了大量優(yōu)化。TACO通過簡單的format描述做稀疏張量存儲的自動生成，通過迭代圖中間表示描述復(fù)合張量表達(dá)式中稀疏操作數(shù)的多級索引數(shù)據(jù)結(jié)構(gòu)，通過用戶指定循環(huán)生成的代碼可以直接做并行化，并且支持自動算子融合。TACO在廣泛使用的稀疏張量代數(shù)和稀疏線性代數(shù)庫中獲得與手動優(yōu)化內(nèi)核相當(dāng)?shù)男阅堋?/p>

TACO的張量向量乘法示例與生成的C代碼[12]

06面向AI領(lǐng)域的編譯技術(shù)

隨著人工智能時代的來臨，AI領(lǐng)域應(yīng)用的大量出現(xiàn)也促進(jìn)著領(lǐng)域編譯的發(fā)展，最突出的表現(xiàn)就是多種AI編譯器的普及和應(yīng)用。AI領(lǐng)域有幾個重要的特征使得AI編譯器面臨很多新的機(jī)遇和挑戰(zhàn)：一是AI領(lǐng)域中編程框架對計(jì)算圖與算子分離的設(shè)計(jì)機(jī)制為編譯優(yōu)化提供了更多的機(jī)會和更廣闊的空間；二是AI領(lǐng)域中對張量的抽象為編譯優(yōu)化提供了具有鮮明領(lǐng)域特征的語義信息；三是以Python為主的動態(tài)解釋器語言前端為其與AI編譯器的銜接帶了挑戰(zhàn)；四是面向AI的領(lǐng)域?qū)Ｓ眉軜?gòu)為應(yīng)用的可移植性帶來了挑戰(zhàn)。在這些因素的驅(qū)動下，近年來學(xué)術(shù)界和工業(yè)界在AI編譯方面提出了一系列創(chuàng)新性的方法，也為編譯這一基礎(chǔ)學(xué)科的發(fā)展注入了新的活力。

本文下一篇將重點(diǎn)介紹面向AI領(lǐng)域的編譯技術(shù)。

審核編輯：湯梓紅