領域編譯器發展的前世今生

本文分為兩個部分，第一部分為綜述，第二部分重點討論AI編譯技術。

近年來，隨著GPU和DSA架構在不同領域的廣泛應用，特別是AI系統相關技術的飛速發展，對于編譯器的需求越來越強烈。編譯器已經從一個相對小眾的研究領域，變為學界和業界都高度關注并大量投入的方向。與此同時，編譯器的開發人員也從芯片研發團隊開始延伸到更上層的軟件層面。在很多領域的軟件系統中，都開始引入編譯技術來實現提升開發效率或運行效率等目標。本文從領域編譯器的角色著眼，來討論領域編譯器發展的前世今生。

通用編譯器 vs. 領域編譯器

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

結合領域編程語言的領域編譯器

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

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

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

01面向圖像處理領域的Halide

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

02面向Stencil計算的領域編程語言

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

Stencil計算常見模板[6]

03面向矩陣計算的領域編程語言HTA

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

HTA的tiling描述[8]

04面向圖計算的領域編程語言GraphIt

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

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

05面向張量的領域編譯器TACO

張量代數編譯器 (Tensor Algebra COmpiler：TACO)[11] 是一個用于計算稀疏和密集張量上的張量代數表達式的代碼生成工具，特別針對稀疏張量做了大量優化。TACO通過簡單的format描述做稀疏張量存儲的自動生成，通過迭代圖中間表示描述復合張量表達式中稀疏操作數的多級索引數據結構，通過用戶指定循環生成的代碼可以直接做并行化，并且支持自動算子融合。TACO在廣泛使用的稀疏張量代數和稀疏線性代數庫中獲得與手動優化內核相當的性能。

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

06面向AI領域的編譯技術

隨著人工智能時代的來臨，AI領域應用的大量出現也促進著領域編譯的發展，最突出的表現就是多種AI編譯器的普及和應用。AI領域有幾個重要的特征使得AI編譯器面臨很多新的機遇和挑戰：一是AI領域中編程框架對計算圖與算子分離的設計機制為編譯優化提供了更多的機會和更廣闊的空間；二是AI領域中對張量的抽象為編譯優化提供了具有鮮明領域特征的語義信息；三是以Python為主的動態解釋器語言前端為其與AI編譯器的銜接帶了挑戰；四是面向AI的領域專用架構為應用的可移植性帶來了挑戰。在這些因素的驅動下，近年來學術界和工業界在AI編譯方面提出了一系列創新性的方法，也為編譯這一基礎學科的發展注入了新的活力。

本文下一篇將重點介紹面向AI領域的編譯技術。

審核編輯：湯梓紅