面向飛騰邁創數字處理器的內核代碼自動生成框架

趙宵磊 陳照云 時 洋 文 梅 張春元

（國防科技大學計算機學院 長沙 410073）

數字信號處理器（digital signal processor，DSP）通常采用超長指令字（very long instruction word，VLIW）和單指令多數據（single instruction multiple data，SIMD）的體系結構設計[1-3].VLIW 和SIMD 提高了在處理器上執行各種應用程序時的計算性能、實時處理能力和能效比.作為具有該典型架構的通用高性能的DSP之一，飛騰邁創數字處理器（FT-Matrix）利用了靈活的標向量硬件單元協同與多層次并行性挖掘來提高處理器的整體性能與效能[1].

然而，絕大多數處理器上極致性能的釋放依然依賴于高度優化的內核代碼[2]，例如核心算法庫等.由于通用編譯器對于特定的體系結構指令或硬件優勢的支持有限，不能很好地平衡可編程性和能效比，因此極致優化的內核代碼通常采用手工匯編級優化或基于底層匯編級的工具開發.然而，手工編寫優化內核級代碼需要大量的時間和勞動成本，尤其是對于VLIW+SIMD 架構的處理器，如何充分挖掘數據重用與潛在的并行性是一個重大的挑戰.

一般地，一名資深工程師可能會耗費幾個月的時間來對一個新的內核函數進行針對硬件的深度優化.因此，面向以飛騰邁創為代表的VLIW+SIMD 處理器架構，設計一個高性能內核代碼自動生成工具是必要的.這可以將開發人員從繁重的內核代碼優化和函數庫開發的負擔中解放出來.

目前，針對CPU 和GPU 等通用處理器和加速器上的代碼自動優化和生成已是領域的研究熱點.傳統的代碼優化手段（如重復訪存和內聯等）已不是新興的優化手段中的重點，這些手段在現有的DSP 編譯中均已有應用，但不是本文關注的重點.循環優化如多面體[3]，自動向量化如VW-SLP[4]等工作均對代碼優化和生成提供了新思路，但此類優化更加注重代碼的上層優化，如算子級和循環級的代碼優化工作.如果不考慮軟件兼容問題，循環優化如文獻[3-4]中的方法也可直接用于DSP 的代碼優化，且文獻[3-4]中的 工作考慮更多的是SIMD 并行性，并沒有完全發掘出VLIW 架構的特性，除此之外VLIW+SIMD 的體系結構的特異性帶來的底層優化問題需要更加繁雜的移植和適配工作，文獻[3-4]中的方法未有針對硬件后端的指令級優化，優化完成后仍需要工程師對代碼進行指令靜態調度、軟流水等一系列手段以發揮VLIW 架構的最佳性能，這些底層優化手段對于DSP 來說同樣重要.

與用于特定AI 加速器的張量編譯器[3]和用于具有全新SIMT 編程模型GPU 的CUDA/OpenCL 工具包[5]不同，DSP 缺少高級計算調度語言的支持，DSP應用編譯時的核心算子映射邏輯與其硬件參數的匹配對于性能釋放具有很大影響.設計用于通用 DSP的內核代碼自動生成工具時需要同時考慮可編程性和能效比，以釋放VLIW+SIMD 架構的潛力.然而，到目前為止，關于DSP 方向的有關研究大都集中在體系結構設計和極致提高能效比上，而未能詳細考慮其軟件兼容性和面向DSP 的代碼優化[1].文獻[6]提出了一種通過平等性飽和方法[7]來進行自動向量化，從而面向DSP 的內核代碼進行優化的編譯器Diospyros，但是該方法對內核代碼規模有限制，且無法實現端到端的代碼生成支持.因此，實現一個面向VLIW+SIMD 架構的完整的內核代碼生成框架仍然面臨3 點挑戰：

1）考慮到內存層次結構和容量的限制，設計人員通常使用乒乓緩沖機制來拆分和處理大規模的輸入數據.然而，為不同內核找到一組最佳的循環分塊參數以最大限度地提高其在飛騰邁創或其他目標平臺上的數據重用是具有挑戰性的.這需要開發人員深入了解內核代碼執行時硬件的細節和特征.自動循環分塊可以將程序員從手動調節循環分塊參數和重復的迭代優化工作的負擔中解放出來.

2）為了利用處理器執行SIMD 指令時閑置的標量單元，實現標量單元和向量單元的工作負載均衡是必要的.目前大多數研究只關注充分利用硬件上的向量單元的自動向量化技術，而忽略了不同供應商在體系結構中設計的標量單元和向量單元之間進行協作的優化空間.

3）VLIW 體系結構的性能很大程度上受到指令級并行性（instruction-level parallelism，ILP）的影響.現有的通用編譯器雖然提供了部分VLIW 的支持，但對于以飛騰邁創處理器為代表的VLIW+SIMD 架構來說，其后端支持比較有限，尤其是指令級優化和快速代碼生成，這些優化的支持可以提高內核代碼的指令級并行度，增強代碼的可移植性并減輕手工為內核編寫匯編代碼的工作負擔.

為了解決這3 點挑戰，本文提出了一種面向飛騰邁創數字處理器的高性能內核代碼自動生成框架（automatic kernel code-generation framework on FTMatrix）.該框架由3 個不同粒度的優化組件層構成，通過分層編譯優化來提高內核代碼在飛騰邁創上的數據重用和并行性.這些分層優化包括帶反饋的自動循環分塊、標量-向量協同的自動向量化和細粒度指令級優化，其結構如圖1 所示.通過利用自動循環分塊，該框架可以根據硬件的內存層次結構確定最佳循環分塊參數和內核數據布局.對于每個分塊，利用標量-向量協同可以提高自動向量化效率并減少其產生的數據移動.此外，該框架還提供了細粒度的指令級優化，以提高內核代碼執行時的指令級的并行性.

Fig.1 DSP kernel code-generation framework with three layers of optimization structure圖1 具有三層優化結構的DSP 內核代碼生成框架

本文的主要工作是為DSP 平臺提供了一個將內核代碼由高級語言到類匯編的底層指令優化生成過程的框架，框架中實現的循環分塊算法和自動向量化模塊也可以更換為其他算法，用戶完全可以自行進行配置.此框架實現了將多層優化過程進行組合和自動調優，減少了開發人員的額外工作，生成的代碼可以直接在硬件上高效執行.

實驗表明，面向飛騰邁創的內核代碼自動生成框架的編譯性能是人工開發的優化庫函數的3.25 倍，是支持向量Intrinsic 指令的C 代碼編寫的內核函數的20.62 倍.

本文的主要貢獻包括4 個方面：

1）提出了一種面向飛騰邁創數字處理器的內核代碼自動生成框架.該框架具有3 個優化組件層：帶反饋的自動循環分塊、標量-向量協同的自動向量化和細粒度指令級優化.框架通過分層優化生成高度優化的內核代碼，提高了其在飛騰邁創上的數據重用和并行性.

2）本文設計的框架提供了帶自反饋的自動循環分塊算法，可以根據輸入內核程序自動搜索最優的循環分塊參數，能夠減輕人工手動進行代碼調優的負擔，提高內核數據的復用性.

3）為了提高向量化效率，本文提出了一種新的標量單元和向量單元之間協同的自動向量化技術，減少由激進的向量化策略導致的SIMD 體系結構上的數據移動開銷.

4）本文設計的框架自動生成類匯編代碼，能夠支持細粒度的指令級優化.類匯編能夠為生成高效的內核代碼提供諸多便利，擴大了指令級并行優化的探索空間，并可以通過外部指令集描述文件適配其他硬件平臺，使開發人員減少額外的移植工作，為應用開發提供敏捷設計.

1 背 景

1.1 飛騰邁創處理器體系結構

以飛騰邁創處理器為代表的DSP 處理器大多采用VLIW 和SIMD 體系結構.以飛騰邁創架構為例，如圖2 所示，指令派發組件同時向標量單元（SU）和單指令多數據單元（SIMDU）發射指令[1].SU 中的標量存儲單元（SM）支持標量內存訪問.向量處理單元（VPU）由16 個同構的向量處理引擎（VPE）組成[8]，每個VPE 包含3 個浮點乘加器（MAC）和2 個向量數據訪存單元.內核中的陣列存儲器（AM）可實現16 路的向量數據訪問.同時，VLIW 體系結構需要在靜態編譯過程中進行超長指令字的指令并行打包，才能發揮其架構特性.

Fig.2 Architecture of FT-Matrix圖2 FT-Matrix 架構

1.2 向量化

由于通常不會激進地探索極其復雜的數據移動策略，向量化技術（從循環依賴性分析到自動向量化）會錯過一些向量化優化的可能性.平等性飽和利用等價圖（e-graph）來實現先進的由重寫規則驅動的編譯優化[9].文獻[6]利用平等性飽和來避免手工尋找特定的向量化模式，并提供了比自動調優（auto tuning）更大的搜索空間覆蓋范圍.雖然e-graph 是一個強大的自動向量化工具，但它同時也需要高昂的時間和存儲開銷來處理中、大規模的循環輸入代碼，對于通用內核代碼優化不具有普適性.本文也借鑒了egraph 技術手段，但補充了額外的分塊支持與標向量協同技術，彌補了其方法的弱點，進一步提高了并行性挖掘.

2 框架設計

本文提出的內核代碼自動生成框架探索并提高了內核代碼在飛騰邁創上的數據重用和并行性，以充分發揮硬件的利用效率.本節首先介紹了整體框架的結構.然后，分別介紹了框架中的各層結構及其優化方法，包括帶反饋的自動循環分塊、標量-向量協同的自動向量化和細粒度指令級優化.

2.1 框架概述

該內核代碼自動生成框架具有3 層不同粒度的優化層級，其結構如圖3 所示.

Fig.3 Overview of our framework structure and compilation process圖3 本文框架結構和編譯過程總覽

整個框架的輸入是未經任何優化的標量C 程序，這避免了其他代碼生成工具需要用戶將代碼轉換為特定領域語言（domain-specific language，DSL）的過程.基于輸入的標量程序，自動循環分塊算法會分析輸入的循環維度參數的比例，計算出相應的循環分塊參數值，經自動向量化的優化和反饋，進行多次迭代和更新以搜索到循環分塊的最優解.該層也支持其他循環分塊算法的部署與擴展.此優化完成后該框架會將經循環分塊后標量C 程序自動轉換為一種DSL 語言編寫的中間表示（intermediate representation，IR），稱為向量領域特定語言（vector DSL）.

標量-向量協同的自動向量化能夠探索每個分塊的向量化，可優化空間并生成優化后的vector DSL 程序，利用閑置的標量單元以減少內核中的數據移動開銷.該層設置了代價函數來判斷自動向量化的優化效果，該代價函數值也將返回至上一個優化層，以指導自動循環分塊對循環參數進行調整，直到總代價達到收斂狀態.

在循環分塊和向量化之后，該框架將代碼轉換為目標平臺后端特定的IR，如飛騰邁創后端的類匯編語言.基于此IR，該框架可以部署細粒度的指令級優化，如指令調度、軟件流水線等，可以在飛騰邁創上探索更多的指令級并行優化空間.

2.2 帶反饋的自動循環分塊

循環分塊對內核代碼在硬件平臺上的數據重用具有顯著影響.內核的最佳循環分塊參數（通常由專家手動調整）可以提高內核在硬件上執行時的計算效率和內存讀寫效率.

多面體[3]技術是一種統一化的程序變換表示技術，它通過迭代域、仿射調度和訪存函數來表示代碼，有利于表示程序變換的組合，有助于解決包含循環程序的向量化問題.但該技術不適合應用在帶反饋的自動調優框架中，原因有3 點：1）調整的靈活性.本文框架設計要求反饋機制能夠迅速發揮作用，建模的循環分塊可以根據反饋結果快速計算出下一次迭代過程的分塊規模，能夠根據自動向量化的結果進行靈活調整.多面體則需要根據迭代域和仿射關系的調整來進行循環級優化.2）適配所需的工作繁雜.由于DSP 后端支持薄弱，通用的高層次的編譯優化手段需要根據硬件架構特性進行細粒度的適配工作，以保障該手段能夠有效發揮作用.3）架構特性帶來的優化空間.多面體面向通用處理器有較好的優化效果，但對于標向量協同架構特性帶來的并行性發掘有限，如飛騰架構的標向量協同指令帶來的并行性優化.分塊算法和指令選擇是面向DSP 代碼生成的重要一環，通過框架設計，利用樸素的循環分塊算法和平等性飽和工具進行標向量協同的向量化的搜索，可以更好地利用架構中的一些特殊指令，如飛騰的廣播指令來利用標量和向量協同工作，提高硬件的利用效率.

此外，一些關于內核代碼生成的研究，如文獻[6]，由于其優化過程的時間和存儲成本高昂，只能處理小規模的輸入.為了充分利用硬件特性并減輕手動優化的負擔，設計了一種帶有代價反饋的自動循環分塊算法來實現此過程.

本文根據循環中各維度的數據重用率和內存限制條件建立了一個分塊規模選擇（tile size selection，TSS）模型[10].根據TSS 模型，一個維度為i，k，j的二維矩陣乘法在未經任何優化時，初始化Ri：Rk：Rj= 1：2：1（每次計算中，矩陣A和矩陣B的維度K的數據重用了2 次）.循環分塊的大小T= （i，k，j）在滿足內存限制的條件下根據此數據重用比例的反比進行初始化設置.

經過循環分塊后的內核程序段將被轉換為vector DSL 代碼段后進行自動向量化的優化過程.然而，探索SIMD 并行性可能會導致各維度數據重用率發生變化.那么，T需要在向量化后進行更新.如圖4所示，最初，矩陣A第1 行中的一個元素應乘以矩陣B第1 列中的每個元素，數據重用的情況在圖4 中用豎紋塊標記.通過自動向量化優化后，該優化結果將矩陣A中的元素利用標量單元進行廣播操作，以提高數據的復用率.如圖4 中的斜紋塊所示，此時，矩陣A中每一行的每個元素（維度K）被重用4 次.然后，將數據重用比例相應地更新為Ri∶Rk∶Rj= 1∶4∶1，并重新進行循環分塊.自動向量化提供一個代價值函數cost進行反饋，該函數值表示當前循環分塊大小下vector DSL 代碼段在硬件上的執行周期值，反映了此循環分塊代碼段優化的效果.同時，更新后的數據重用比例指導算法進行循環分塊參數T的調整.

Fig.4 Data reuse before and after applying broadcast instruction圖4 應用廣播指令前后的數據重用

自動循環分塊的過程如算法1 所示.算法1 根據初始比例選擇循環各維度的分塊大小，并根據此大小切分循環（行⑤～⑥）.通過標量-向量協同優化，算法得到優化后的vector DSL 代碼的代價值cost和數據復用情況的變化（行⑧）.算法1 根據比例調整分塊大小，并自動返回到分塊階段（行⑥）.自動調優過程將進行迭代，直到總代價值Costtotal收斂（行④）.算法1 的最終結束狀態為向量化的反饋無法改變數據重用情況且向量化后循環分塊的總代價值收斂至最小值.

2.3 標量-向量協同的自動向量化

為了提高內核代碼的數據復用和并行性，采用向量化技術能夠最大限度地提高計算效率和硬件利用率.在內核代碼生成框架中，本文采用了一種vector DSL 作為自動向量化的中間描述[6].

內核代碼生成通常采用的向量化技術，包括循環依賴分析等，僅關注向量單元.類似地，文獻[6]旨在向量單元之間實現靈活地數據移動，卻忽略了閑置的標量單元的作用.另外，其數據移動的實現依賴于硬件提供的混洗（shuffle）指令，然而混洗指令雖然通用靈活，但是通常其硬件執行開銷也較大，因此依賴混洗指令的方法生成的內核代碼性能在該硬件上大打折扣，甚至出現負優化的情況[11].

如何釋放標量單元與向量單元協同的潛力來增強內核代碼中的數據重用和并行性是本節設計基于飛騰邁創處理器的自動向量化策略的主要挑戰.

如圖5 所示，帶有標向量硬件單元的DSP 供應商通常提供的交互指令（包括broadcast，reduce，scatter，gather，allreduce 等）可以顯著提高標量和向量單元之間的數據移動效率[1].為了釋放這部分潛力，在代碼生成過程中支持這些交互指令和重寫規則顯得尤為重要.

Fig.5 Typical ISA-specific scalar-vector cooperation instructions圖5 典型的特定指令集架構中的標量和向量單元協作指令

本文將這些特定指令的重寫規則擴充至平等性飽和[7]工具中進行，以探索標量—向量協同指令為導向的自動向量化空間的搜索.

以圖6（a）中的標量 C 程序為例，它表示一個1×4 的矩陣A乘以4×4 的矩陣B.該程序可以轉換為圖6（b）中的未經優化的vector DSL 代碼段，并以此作為自動向量化的輸入對象.

Fig.6 An example of rewrite rule application with the broadcast instruction圖6 廣播指令重寫規則應用的示例

平等性飽和工具可以依據擴充的等價規則來重寫vector DSL 代碼，通過替換相同操作的不同指令選擇來生成最優的內核代碼.例如，VecMac（）節點的功能與VecAdd（VecMul（））節點的功能相同，均可以表示向量的乘加操作.因此，平等性飽和工具可以在圖6（c）中找到相應的等效表示并生成指令替換后的優化代碼.

但是，Vec（）節點可能包含大量無序數據，這些數據會導致生成的代碼中具有大量的shuffle 指令來進行數據移動，從而導致目標硬件產生高昂的數據移動開銷.這一現象存在可優化的空間，可以利用閑置的標量單位來減少此開銷.

我們補充了特定內置指令的重寫規則，以利用標量—向量的協作來減少數據移動.以廣播指令為例：

廣播只需要一次數據加載，就可以減少冗余的內存訪問并減少訪存開銷.我們根據硬件不同指令的周期在代價函數中調整每個可替換指令的代價函數值.此外，還為用戶提供了一個接口，以根據目標硬件上的指令周期來調整代價函數，為其他硬件實現敏捷開發提供便利.

該過程的搜索效率體現在可通過有限時間得到向量化搜索的結果，具體數據如表1 所示.平等性飽和搜索是指令選擇優化技術中的一種，其根據用戶提供的重寫規則來對等價的指令進行替換而得到新的指令序列，并根據代價函數來評估經指令選擇后代碼序列的性能.我們定義的等價規則包括乘加指令、移位指令、轉置指令、數據拼接指令和體系結構支持的特殊指令等，等價規則包含了結合律和分配律.搜索空間即由這些等價指令及其等價規則組合形成.此外，我們未在等價規則中配置交換律，交換操作數在指令級別沒有優化意義，以此裁剪了平等性飽和搜索的搜索空間.同時，帶性能反饋的自動向量過程也提供了有選擇性的分塊規模參數，此過程也裁剪了大部分搜索迭代過程.

Table 1 Benchmark Programs Adopted in Experimental Evaluation表1 實驗評估中采用的基準程序

代價函數能夠準確反饋平等性飽和工具搜索的指令選擇序列在硬件上的執行周期，從而能夠幫助其確定最佳的代碼重寫和優化方式.代價函數的返回值為指令序列中所有指令的執行周期的總和.我們為各類指令分別預設了周期值，并且提供了接口，支持用戶對特殊指令的周期值進行設置（例如飛騰支持較好的廣播指令等）.對于VLIW 架構的DSP 硬件后端來說，靜態排布后指令序列的執行周期為確定值，用戶可直接對代價函數進行計算.代價函數的返回值也會發回循環分塊算法以指導自動循環分塊過程.在該例中，vector DSL 中的表達式與模式Vec（a，a，a，a）匹配并用Broadcast（a）重寫它.由于廣播指令在飛騰邁創處理器上的執行代價很低，最終的內核代碼通過平等性飽和搜索和標量-向量協同優化，優先選擇廣播指令進行替換，能夠在飛騰邁創上實現最短的執行周期，如圖6（d）所示.

2.4 細粒度指令級優化

由于VLIW 架構在很大程度上依賴于靜態指令級優化，該優化層提供了一個將vector DSL 代碼轉換為類匯編代碼的組件來為飛騰邁創或其他供應商提供敏捷開發的支持.如圖7 所示，類匯編指令參照基本的VLIW 匯編指令格式[12-13]，但省略了需要手工排布的一些繁瑣信息，如并行符號和功能單元信息，并且條件域和操作數列表也可由變量來代替物理寄存器.這樣在編寫代碼時可以不考慮指令延遲時隙、VLIW 打包、寄存器分配等細節優化問題，適合作為細粒度代碼的優化和生成的輸入代碼格式，這些細節優化問題將交由本組件自動完成適配與生成.

Fig.7 Formats of assembly instructions and assembly intrinsic instructions圖7 匯編指令與類匯編指令的格式

該組件的優化方式主要包括指令調度和自適應代碼生成.類匯編的中間描述對于各供應商提供的細粒度指令優化方式具有一定的通用性，用戶可以根據自身需求來對其中具體的優化算法進行替換或優化.本節以飛騰邁創后端支持較好的指令調度和軟件流水優化算法為例來簡要說明該組件的基本結構與優化過程.

1）指令調度

面向VLIW 后端的現代編譯器一般采用列表調度 （LS）算法或其變體進行指令調度，但是指令調度是一個典型的NP 難題[14].LS 算法的局限性在于尋找調度解決方案的效率不佳，得到的是局部最優解決方案而不是全局最優解.本文的指令調度采用了一種基于動態規劃的指令調度策略（DPS）[15]來獲得VLIW 指令級調度的近似最優解，同時兼顧指令排布的并行、功能單元與讀寫端口的沖突等，以探索更多用于目標硬件體系結構的指令級并行優化空間.除了指令調度外，針對VLIW 架構處理器，本文框架還引入了一些循環優化手段，可以對指令級并行進行更加深入的挖掘，例如循環展開、軟件流水等.尤其是以軟件流水為代表的優化手段可以大幅度提升內核代碼的執行效率.圖8 展示了一個經過軟件流水優化后的內核代碼的指令排布示意圖.

Fig.8 An example of instruction arrangement in kernel code after software pipeline optimization圖8 經過軟件流水優化后的內核代碼的指令排布示例

2）快速和自適應的代碼生成

在完成一系列優化之后，本文的代碼生成框架將內核代碼從類匯編代碼轉換為最終硬件支持的匯編代碼.飛騰邁創指令集內部的類匯編指令的一個簡單的代碼段如圖9 所示.

Fig.9 A code segment example of assembly intrinsic instruction圖9 類匯編指令的一個代碼段示例

一般地，代碼生成與供應商各自的指令集架構（ISA）和目標硬件后端緊密耦合.為了打破枷鎖，實現面向不同硬件后端的自適應代碼生成過程，本文提出了一個利用外部ISA 描述文件進行代碼快速生成的方式，為VLIW 后端（包括飛騰邁創）提出了一種敏捷設計.通過分析發現，本文提出的架構和VLIW 架構的指令集具有一定程度的相似性，將其中與最終指令并行排布相關的指令信息進行了抽取，并將之整合到一個外部描述文件（類似于編譯器后端的TD 文件，但是其格式內容相對更加簡潔友好），其格式如圖10 所示.不同的VLIW 處理器后端只需要提供此指令集描述文件，就可以直接嵌入到最終代碼生成的框架中.基于外部 ISA 描述文件，代碼生成框架可以獲取到所有必需的 ISA 信息，并能夠將類匯編代碼自動降低到飛騰邁創或其他VLIW 硬件上的后端固有的指令集，以及能夠支持VLIW 架構的硬件平臺，受限于可獲得的硬件平臺，該框架目前在飛騰邁創系列的兩代DSP 芯片產品上得到性能驗證，兩代產品之間的功能單元數量和指令節拍均有所區別，但本文提出的框架可以快速兼容和適配.同時，本文在4.5 節對硬件參數進行了模擬和性能評估以保證性能的可移植性.

Fig.10 Format of instruction information in external ISA description file圖10 外部ISA 描述文件的指令信息格式

3 本文框架的實現

本文代碼自動生成框架的實現基于以飛騰邁創處理器為代表的VLIW 和SIMD 體系結構.該框架的實現包含500 行以上的Python 代碼，用于自動循環分塊算法和其反饋迭代過程.同時，擴展了文獻[6]中的自動向量化工具，使用了大約1 000 行的Racket和Rust 語言的代碼，用于標量、向量協同的自動向量化模塊的實現.最后，本文實現了一個包含6 000 多行基于C++語言的類匯編優化器，用于細粒度的指令級優化.本文框架可以實現飛騰邁創處理器系列芯片上內核級代碼的自動優化與生成.

4 實驗評估

本節從3 個方面評估本文代碼生成框架的性能：

1）對于小規模數據（＜256 浮點數），本文框架能否實現更好的內核代碼執行性能？

2）對于中等規模的數據（≥256 浮點數），本文框架能否發掘最佳循環分塊大小并生成與硬件廠商提供的DSP 函數庫相媲美的高性能代碼？

3）通過單獨應用該框架中的每個組件，內核代碼能夠分別實現多少性能提升？

4）對于不同的硬件平臺和參數，本文框架能否生成匹配且高效的內核代碼？

4.1 實驗設置

本文在運行 Ubuntu 16.04 的帶有 Intel i7-8700CPU 的機器上運行基于飛騰邁創的代碼生成框架，并將該框架生成的內核程序與文獻[6]生成的程序、樸素標量（Naive scalar）程序、樸素向量（Naive vector）程序和DSP 函數庫（DSPLIB）程序分別部署在飛騰邁創處理器（具有16 個向量處理單元（VPE），每個VPE 中有3 個乘加器（MAC）單元且同時支持2 個向量的訪存操作，寄存器寬度為32b）上進行比較.本文框架也可以支持其他VLIW+SIMD 架構的硬件處理器，但是受限于實驗條件，目前可獲得的真實硬件環境主要以邁創系列處理器為主，但引入額外的模擬環境來驗證本文工作的可擴展性.

因Diospyros[6]處理中等規模的數據的時間過長、所需內存過大，只在小規模內核中對其進行評估.樸素標量程序是具有樸素標量 C 語言循環的標量內核程序，其在執行時只具備編譯器的默認優化.樸素向量程序是DSP 廠商提供的，由C 語言+向量Intrinsic指令編寫而成的程序版本，該樸素向量程序適用于飛騰系列的DSP 芯片，其編寫了內核函數的計算過程，考慮并進行了面向架構的特定優化，在適當節點利用了broadcast 等飛騰支持較好的指令.DSP 函數庫是由供應商提供的高性能函數庫，它以內核程序在硬件上的實際執行周期作為評估標準來反映各個程序的真實性能，此指標由飛騰邁創后端工具鏈提供的性能統計工具來進行反饋.

4.2 內核函數基準測試程序

表1 列出了本文采用的內核基準測試程序，這些基準測試來自于機器學習和信號處理中廣泛應用的內核程序.

自相關（AutoCor）是 DSP 中廣泛使用的信號處理函數.快速傅里葉變換（FFT）被大量用于各種DSP應用.二維卷積（2D Conv）和矩陣乘法（Mat Mul）均是機器學習領域最常用的算子.

對于每種內核函數，我們均采用2 種數據維度.采用小規模數據來評估標量-向量協作的向量化模塊和細粒度指令級優化模塊的優化效果；中等規模的數據用于評估自動循環分塊和整個代碼生成框架對于內核代碼在飛騰邁創上的優化效率.

表1 還列出了每個基準測試程序的總編譯時間.本文提出的代碼生成框架對于小規模的內核編譯只需要進行1 次迭代，時間在2min 以內.

從測試基準程序來看，小規模程序的框架與Diospyros 中向量化所需的時間基本持平，由于循環分塊模塊的處理，小規模框架可以搜索到Diospyros中向量化無法直接處理的數據規模的優化結果，且搜索時間為迭代次數與分塊后小規模程序的搜索時間的乘積.我們也限制了單次搜索的最長時間，超時后此過程所產生的結果是一種次優解，其性能峰值與理論最優解相近，以此策略來保證搜索效率與搜索結果的平衡.實驗結果也證明了在實際應用中，限定時間內的搜索結果可以獲得較好的性能提升.

對于中等規模的AutoCor，FFT 和2D Conv 內核函數，本文框架只需要 約120 min 來搜索最佳的循環分塊參數；此外，由于Mat Mul 的循環具有三維搜索空間，框架在生成代碼時具有最大的開銷，需要大約200 min.另外，將每次迭代的時間限制為 10 min，以避免每次迭代耗時過長的情況.在該限制條件下，本文框架生成的代碼（一種次優解）與最優情況下的代碼在性能差距和耗時差距上的表現處于可接受的范圍[6].

4.3 內核性能結果和分析

中、小規模下4 種內核程序的執行加速比如圖11～15 所示.本文所提到的加速比由真實值以2 為底的對數函數計算得出.本文將樸素標量程序的執行周期設置為對比基準.本文框架實現的平均加速比為14.01，DSPLIB 的平均加速比為4.77，Diospyros 實現的平均加速比為3.57（且僅限小規模內核）.

Fig.11 Speedup ratios of AutoCor kernels圖11 AutoCor 內核的加速比

Fig.12 Speedup ratios of FFT kernels圖12 FFT 內核的加速比

Fig.13 Speedup ratios of 2D Conv kernels圖13 2D Conv 內核的加速比

Fig.14 Speedup ratios of Mat Mul kernels圖14 Mat Mul 內核的加速比

對于小規模內核程序，Diospyros 嚴重依賴shuffle指令，而飛騰邁創對于該指令需要額外的執行周期來進行數據的重排，這反映在Mat Mul 的內核程序測試結果中，由Diospyros 生成的代碼包含許多shuffle指令用以實現向量化，而本文的框架使用飛騰邁創支持更好的廣播指令，并實現了最優的結果.對于小規模內核程序，本文框架的平均性能是Diospyros 的7.33 倍，具體從 FF T 中的1.31 倍到Mat Mul 中的33.39 倍不等.這些增益來自于標量-向量協作的向量化和細粒度的指令級優化.當內核函數的數據規模很小時，樸素向量程序（Naive vector）仍需進行完整的向量指令調用和實現，且無法完全發揮指令級優化的作用（如指令調度和軟流水的空間被縮減），導致其內核函數的性能沒有樸素的標量實現的性能優異.此類現象也體現在4×4 的Mat Mul 內核函數的實驗結果中（4×4 Mat Mul）.DSP 函數庫是基于最佳數據規模（通常是大規模）進行設計，以發揮硬件最優性能.對于小規模的內核函數，也需要調用完整的DSP庫函數來執行，導致其對小規模內核的支持并不友好.本文框架對于小規模內核的平均性能是DSP 函數庫的17.56 倍.本文框架由于充分利用了標量單元和向量單元的協作，并同時進行了細粒度指令級優化，對于小規模內核函數的優化性能在4 者中最佳.

對于中等規模的內核程序，由于繁重的時間和存儲開銷，Diospyros 無法處理這些內核.由于全局優化和專家在某些情況下手動調整部署的數據分塊，DSP 函數庫表現突出，硬件資源的占用率最高.但Diospyros 移植性差，在硬件參數更改時整個函數庫均需要重寫，這需要額外的人工和時間成本.

受搜索空間和時間的限制，本文的框架在某些情況下未能找到最佳循環分塊大小，并且忽略了循環分塊之間的優化空間.但是，該框架生成的內核代碼標量單元和向量單元協作的指令（如 broadcast 和reduce）進行數據整齊的加載來減少存儲和數據移動開銷.該框架仍然可以為中等規模的內核函數實現大約5.06 的平均加速比，這與專家手工調優的DSP函數庫代碼相比十分具有競爭力.本文框架生成的內核代碼在中等規模下與DSP 庫函數代碼相比實現了平均2.34 的加速比，其中AutoCor 實現了2.55 的加速比，并且對FFT 保持了接近1 的加速比.

從深層次的角度來看，本文框架可以克服Diospyros 和DSP 函數庫的弱點.但是它也有其自身的局限性，在某些情況下，為了增強可編程性和可移植性，它減少了尋找最優解的時間代價，但也犧牲了潛在的加速性能.本文框架能夠充分利用DSP 硬件的架構特征，對于DSP 中的典型應用場景，如信號和圖像處理應用，以及卷積和矩陣運算的應用都可通過該框架獲得加速，并在發揮硬件極端性能和提高開發效率之間得到了一種平衡.

4.4 分解評估

為了分析本文框架中每個組件的性能提升效果，本文設置了分解實驗來探索每個組件對于內核基準測試函數的加速比的影響.

表1 最后2 列的編譯時間對比說明了自動循環分塊的效率.如果沒有自動循環分塊算法，本文框架便無法生成中等規模以上的內核函數代碼（規模大于256）.

自動向量化和細粒度的指令級優化的效果如圖15所示.在本文的基準測試中，標量—向量協作的向量化與這些內核函數的原始向量化策略相比可實現3.49 的平均加速比.此外，該框架部署的細粒度的指令級優化策略與未采用指令級優化的后端相比，可以實現4.67 的平均加速比.這充分說明了本文框架中每層優化均對生成的內核代碼起到了加速作用.同時，3 層優化的組合框架，特別是帶反饋的優化過程要優于3 種優化手段的簡單疊加.

Fig.15 Average speedup ratios provided by vectorization and instruction-level optimization in breakdown experiment圖15 分解實驗中向量化和指令級優化分別提供的平均加速比

4.5 擴展性評估

為了證明本文框架對于其他硬件平臺的支持性和擴展性，我們在不同的硬件參數下生成內核代碼，模擬其性能來檢驗其是否可以生成正確的內核代碼和能夠取得優良的執行性能.

表2 列出了該框架在3 組不同硬件參數下生成的內核代碼推算的2 組加速比，向量加速比的基準為向量寬度為1，VPE 中有1 個MAC 單元的抽象硬件環境；標量加速比的基準為原始的標量程序.

Table 2 Hardware Parameters and Speedup Ratios of Generated Kernel Code of Our Framework表2 本文框架的硬件參數以及生成的內核代碼的加速比

與向量和標量基準代碼相比，隨著向量寬度和MAC 單元數量的增加，本文框架生成的內核代碼的加速比逐步提高，呈現出加速比隨硬件資源的增加呈正比上升，驗證了本文框架的可拓展性.在FFT 中，由于計算中的取數過程并不完全與邊界對齊并且存在更多標量操作，硬件參數的增長對其加速效果遠沒有其余3 種計算對齊的應用明顯.另外，向量程序采用向量接口編程，可以直接調用高效的向量指令.相對于標量程序編譯時需要指令選擇的優化，向量寬度和MAC 數量均為1 的硬件環境下向量程序仍可具有一定的加速收益，例如向量乘加指令、各類訪存指令等.

以表2 中的64 b 向量寬度的硬件模擬平臺為例（向量寬度為64 b，每個VPE 中有4 個MAC 單元，寄存器寬度為32 b），對于一個8×512×256 的矩陣乘法應用，該框架生成的內核代碼指令排布如圖16 所示.

Fig.16 An example of instruction arrangement of kernel code after software pipeline optimization圖16 經過軟件流水優化后的內核代碼的指令排布示例

此推算說明本文框架完全可以根據硬件參數的變化生成在不同硬件平臺上的高效內核代碼，具有拓展性，可以為其他自主芯片后端設計提供自動化代碼生成的敏捷設計.

5 相關工作

文獻[16]設計了一種可移植的編譯器，用于以獨立于體系結構的方式自動生成內核代碼，這種方法更側重于單獨的內核計算方式分析，而未能考慮一般應用在通用體系結構下的適配性.文獻[17]為目標DSP 應用提供了一種DSL，但未能探索標量-向量單元協作的優化空間，使VLIW 和SIMD 架構的性能潛力無法完全釋放.文獻[18]專注于優化稀疏算子，并從高級語言出發生成代碼.

文獻[19-20]采用了不規則的數據移動策略進行向量化.它們利用了SIMD 的特性，但不支持針對VLIW 架構的細粒度指令級優化.文獻[3, 21]著眼于在通用硬件（如 CPU 和 GPU）上部署深度神經網絡，采用的方法是將張量表達式語言降低到特殊的DSL以采用激進的優化策略.

文獻[22]可以在異構硬件上進行算子編譯的自動調優，具有良好的可移植性，并且其為各種算子開發了高性能的實現方式.但是其仍然需要程序員手動編寫計算調度模板.

文獻[23]提出了一種使用修剪和機器學習技術為 CPU，GPU 和 FPGA 上的張量計算生成高性能調度方案的自動優化框架，無需考慮硬件平臺細節.但是，對于自主設計的DSP，由于缺少后端的支持，此技術的移植也將是一個繁重的工程.

6 結 論

本文提出了一種具有3 層優化組件層的基于飛騰邁創處理器的內核代碼自動生成框架.通過帶反饋的自動循環分塊、標量-向量協同的自動向量化和細粒度指令級優化，顯著提高了內核代碼在飛騰邁創上的數據復用和并行性.實驗表明，本文框架能夠自動為飛騰邁創處理器生成深度優化、執行高效的內核代碼.同時，本文框架也為其他目標硬件平臺提供了一種代碼生成框架的敏捷設計，通過替換外部ISA 描述文件，能夠生成相應平臺的深度優化的內核匯編代碼.

作者貢獻聲明：趙宵磊提出主要研究思路、完成實驗并撰寫論文；陳照云指導研究進程、修改和審核論文；時洋協助修改論文；文梅和張春元提供研究方向和論文意見.