李 韋 文淵博 孫廣中 陳云霽

(*中國科學技術大學計算機科學與技術學院 合肥 230026) (**計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190) (***上海寒武紀信息科技有限公司 上海 201203)

0 引 言

過去的幾十年，在高性能計算(high-performance computing，HPC)社區(qū)的軟件開發(fā)工作中，誕生了許多廣泛使用的高性能函數(shù)庫，這些函數(shù)庫或針對計算進行優(yōu)化，如基本線性代數(shù)例程(basic linear algebra subprograms，BLAS)[1-3]、高擴展線性代數(shù)庫(scalable LAPACK，ScaLAPACK)[4]、西方最快傅立葉變換(fastest Fourier transforms in the West，F(xiàn)FTW)[5]；或提供等特定場景中的基本原語，如信息傳遞接口(message passing interface，MPI)。同時，使用編譯制導語句進行編程，提高程序并行度也已成為高性能應用開發(fā)中的常用技術，例如開放并行處理(open multi-processing，OpenMP)[6]和開源加速器(open accelerators，OpenACC)[7]。使用標準化的庫函數(shù)以及編譯制導語句的一個重要原因是：使用它們進行編程，可以提高所編寫應用程序的性能可移植性。使用庫函數(shù)和編譯制導語句，程序員不必過分糾結底層實現(xiàn)，而相同的代碼也可以更為輕松移植到新硬件架構上。同時，當標準庫的開發(fā)人員為所需移植的目標架構提供優(yōu)化版本時，應用程序在硬件架構上的性能也會同步得到提高。

盡管在許多應用程序中廣泛使用了高度優(yōu)化的函數(shù)庫，但是將所有的庫“鏈接”到一個應用程序中的過程仍然存在問題。其原因在于不同函數(shù)調用之間通常需要使用手寫代碼(即膠水代碼)，在將應用程序的輸入或者函數(shù)調用的輸出作為輸入傳遞給另一個函數(shù)調用之前，進行一些類似于更改數(shù)據(jù)布局格式或分配存儲空間的額外操作，以實現(xiàn)數(shù)據(jù)預處理。膠水代碼常會阻礙將應用程序代碼移植到新的架構上，原因在于它們大多是針對硬件架構進行編寫的，也同樣需要針對新的硬件架構和應用程序進行特定的優(yōu)化，并且膠水代碼中可能使用了硬件架構特定的指令。例如，如果使用矩陣向量乘法實現(xiàn)定制化矩陣乘法，因為循環(huán)的存在，應用程序有了更多的訪存和指令跳轉，當其被移植到對訪存帶寬更為敏感的硬件平臺上時，性能瓶頸會被進一步放大。再例如，在支持高級向量擴展指令集(advanced vector extensions，AVX)指令的處理器上，會使用單指令流多數(shù)據(jù)流(single instruction multiple data，SIMD)指令進行向量化加速，而這樣的程序無法運行到不支持AVX指令的處理器上。因此，膠水代碼的存在使得高性能計算程序性能可移植性降低。

有許多關注于特定領域內程序性能的優(yōu)化工作。SPIRAL[8]作為面向數(shù)字信號處理領域的調優(yōu)系統(tǒng)，提供了從高層次的數(shù)學算法描述到低層次的代碼實現(xiàn)的映射，能夠自動生成給定硬件平臺的算法的高性能實現(xiàn)。Halide[9]是專為圖像處理領域設計的編程語言，它的核心思路是將算法描述和計算過程分離，程序員可以靈活的使用循環(huán)展開、向量化等方法手動嘗試不同的調度算法來得到最好的性能。Chen等人[10]針對于深度學習應用，提出TVM優(yōu)化框架，通過AutoTVM的方式用機器學習的方法去優(yōu)化程序空間的代價估計函數(shù)，在龐大的參數(shù)空間之中預測最優(yōu)的優(yōu)化方式，從而將深度學習靈活、高效地部署在不同的硬件平臺之上。

本文針對于高性能計算應用，描述了與編譯器優(yōu)化[11，12]相關的工作，對高性能庫函數(shù)調用中存在的語義信息進行了分析，在編譯時對應用程序進行優(yōu)化。對使用了大量膠水代碼的高性能應用程序，本文嘗試用更為高效的庫函數(shù)替代膠水代碼與原始的庫函數(shù)調用，并增加更多的編譯制導語句，使整個應用在不同平臺上的整體性能得到提升。

本文描述了一種抽象的關于高性能函數(shù)庫的領域特定語言，以及支持它的原型編譯器實現(xiàn)。這種源代碼到源代碼的編譯器，首先將庫函數(shù)調用轉換為關于庫函數(shù)的領域特定語言，之后針對生成的領域特定語言進行分析和優(yōu)化，最后將優(yōu)化后的領域特定語言重新翻譯為更為高效的C代碼。這種設計，實現(xiàn)了對原始C代碼的性能優(yōu)化。針對需要移植的應用和目標硬件，優(yōu)化領域特定語言到C代碼的翻譯過程，就可以使高性能計算的應用程序具有更好的性能可移植性。本文以簡單的矩陣乘算法以及復雜的空時自適應處理(space-time adaptive processing，STAP)[13-15]算法為應用示例，展示了移植到不同的硬件平臺的具體實現(xiàn)。實驗結果表明，該領域特定語言以及編譯器可以顯著提高應用程序在不同硬件平臺上的性能表現(xiàn)。

1 研究動機

在調用高性能函數(shù)庫的過程中，需要增加許多膠水代碼，其作用多數(shù)功能為數(shù)據(jù)重排、數(shù)據(jù)補齊等。圖1以一段基于FFTW函數(shù)庫編寫的應用程序為例，展示了需要實際解決的問題和需要完成的優(yōu)化。

圖1中的代碼片段取自一個真實應用，其描述了多次調用FFTW庫函數(shù)執(zhí)行多個一維快速傅里葉變換(FFT)，接著用一段手寫代碼將多個FFT的輸出轉換為不同的布局格式。這里的膠水代碼具體是指外圍調用FFT的循環(huán)(第2個代碼塊)以及執(zhí)行數(shù)據(jù)重排的循環(huán)(第3個代碼塊)。

圖1 快速傅里葉變換原始代碼和膠水代碼

首先，針對第1個代碼塊中的函數(shù)fftw_plan_dft_1d進行分析。該函數(shù)的作用是計算大小為N_DOP的一維FFT。FFT本身是一個原位操作，因為輸入指針和輸出指針都指向相同的內存地址(由第2個和第3個參數(shù)可得)。

圖1中的第2個代碼塊，按照代碼塊1得到的plan_fft進行運算。函數(shù)fftw_execute_dft表示，在不同的輸入/輸出數(shù)組(array)上執(zhí)行多個FFT。輸入/輸出地址使用包圍fftw_execute_dft的兩層循環(huán)進行索引，而這些循環(huán)代碼即上文所述膠水代碼。對開發(fā)以及維護程序員來說，明晰這些膠水代碼實際進行的操作，是能否進行后續(xù)開發(fā)維護的關鍵點。

最后一個代碼塊是膠水代碼的另一個例子。在庫函數(shù)調用后，需要執(zhí)行數(shù)據(jù)重排。更具體的，圖中第3個代碼塊中，循環(huán)包圍著一個簡單數(shù)據(jù)拷貝，即輸入基地址為datacube_pulse_major_padded，輸出基地址為doppler_data_cube的數(shù)據(jù)重排。由于不同硬件架構的基礎內存排列方式可能不同，導致這些循環(huán)必須以高效且不同的方式進行實現(xiàn)(硬件的特點，例如內存交織，對齊方式等)，以在不同平臺上實現(xiàn)良好性能。

針對圖1中的代碼邏輯，實際上可以使用FFTW函數(shù)庫中更為高效的fftwf_plan_guru_dft函數(shù)對其進行優(yōu)化和改寫。如果將循環(huán)和數(shù)據(jù)重排融合到單一的庫函數(shù)調用中，如圖2所示，首先，膠水代碼大量減少，將計算執(zhí)行和訪存處理重疊起來隱藏了部分時間開銷；最后，同樣因為膠水代碼的減少，程序訪存壓力得到緩解，提升程序運行性能、降低應用程序運行能耗(如圖3所示)。圖3為在Haswell架構處理器(Intel Xeon E5-4667V3，40 MB L3 Cache，16核，32線程)的服務器上的測試性能對比，從圖中可以看出，相對于圖1中的代碼，融合優(yōu)化后的圖2中的代碼，在性能、能耗與能耗延遲積3個方面都有顯著的性能優(yōu)化。更重要的是，由于膠水代碼被替換為了對標準庫(此情況下為FFTW guru)的單一庫函數(shù)調用，使得優(yōu)化重構后的代碼具有更好的性能可移植性，即程序員不用再根據(jù)硬件平臺基礎架構做類似于優(yōu)化循環(huán)以及內存拷貝的手動優(yōu)化。

圖2 對膠水代碼融合優(yōu)化后的版本

圖3 融合膠水代碼和庫函數(shù)調用，性能提高、能耗降低、能耗延遲積降低

綜上分析，高性能計算程序中調用的函數(shù)通常來自高性能函數(shù)庫，例如BLAS和FFTW。在調用多個庫函數(shù)編寫高性能計算應用時，需要編寫大量膠水代碼以保證應用程序功能與性能。而膠水代碼的存在，導致應用程序維護困難，程序訪存量增加，最終導致應用程序性能可移植性變差。針對膠水代碼進行優(yōu)化，減少不必要的循環(huán)和內存拷貝，使用更為高效的函數(shù)調用替換原始函數(shù)調用以及膠水代碼以優(yōu)化程序，可以使得應用程序更充分利用高性能函數(shù)庫所提供的優(yōu)化，使應用程序具有更好的性能可移植性。

2 DSL語言和編譯器

針對高性能計算程序在調用高性能計算函數(shù)庫的過程中，需要插入大量進行循環(huán)和數(shù)據(jù)重排的膠水代碼，以至應用程序性能可移植性差的問題，本文構建了一個原型Source-To-Source編譯器。它能將基于高性能函數(shù)庫的程序解析為一種作為中間表示的領域特定語言，然后對中間表示進行分析優(yōu)化，最終得到使用更高效的庫函數(shù)替代循環(huán)、數(shù)據(jù)拷貝和原始的庫函數(shù)調用的C代碼。對于無法通過該方法進行優(yōu)化的循環(huán)，該編譯器嘗試使用OpenMP或OpenACC(取決于目標架構)來插入編譯制導語句。圖4為該編譯器框架圖。

圖4 編譯器架構示意圖

在Source-To-Source 編譯器實現(xiàn)中，本文先定義了一個改編自The Spiral Language[16]的通用的領域特定語言(domain-specific language，DSL)表示。在原始代碼重構和移植的過程中，原有的C代碼被編譯器前端翻譯為關于庫的領域特定語言。隨后使用了一系列在 DSL 之上的循環(huán)展開、循環(huán)交換、循環(huán)自動向量化等的優(yōu)化，從而得到更好的訪存局部性和并行化加速。同時制定了可擴展的模板匹配規(guī)則，用更高效的高性能庫函數(shù)對應的 DSL 原語替換中間DSL表示。在編譯器后端代碼生成模塊中，將優(yōu)化后的DSL翻譯成優(yōu)化后的C代碼。對于不能用高性能計算庫函數(shù)優(yōu)化，但可以進行并行化加速的代碼，插入編譯制導語句，通過OpenMP等并行加速庫優(yōu)化用戶的原始程序。

2.1 DSL語言表示和編譯器前端

DSL 語言的設計目標是盡可能充分的表達原始 C 代碼中的數(shù)據(jù)分布描述與數(shù)學運算表示，同時能夠滿足后續(xù)優(yōu)化的需求。圖5提供了用巴科斯-諾爾范式描述的 DSL 語言的形式化語法。

圖5 DSL 形式化語義描述

DSL 有最基本的數(shù)學運算表示功能。它能表達一些常數(shù)，比如 2、3/7、2.33、π，也能表達一些簡單的數(shù)學函數(shù)運算，如 exp(2) 、sin(π/2)等。特殊的，對于在高性能計算領域中比較常見的向量或者矩陣運算，DSL拓展了一些如vector(a0,…,an-1)之類的原語，從而高效地表示數(shù)學運算。

DSL還包括一些高性能計算庫函數(shù)原語，它們與以FFTW及BLAS為代表的常用高性能庫中的函數(shù)調用存在對應關系，從而方便編譯器后端代碼生成模塊的一對一轉換。例如，圖1中的函數(shù)fftw_plan_dft_1d由如下原語表示：

此外，本文抽象了一些符號與運算符，用來精確表示DSL語言中數(shù)學計算的行為。在如下的符號運算符例子中：

基于上述原語介紹與擴展，實現(xiàn)了基于 GAP 4[17]的編譯器前端，完成從原始C代碼到DSL中間表示的轉換工作。GAP 4是在離散代數(shù)領域中使用廣泛的語言系統(tǒng)，它提供了基本的描述復雜代數(shù)符號、函數(shù)的數(shù)據(jù)結構，且方便擴展。通過上述編譯器前端，能夠將圖1中的代碼片段翻譯為如下的DSL表示：

(1)

2.2 優(yōu)化及代碼生成

基于DSL的代數(shù)表達能力，應用集合基本知識對上面的表達式進行化簡和重排，可以得到下面的表達式：

(IN_CHAN?(IN_RANGE?

(2)

對于重點優(yōu)化路徑，制定了可靈活擴展的模板匹配規(guī)則，完成庫函數(shù)調用之間的優(yōu)化。

例如，通過FFTW guru接口(guru-interface)的模板匹配搜索，式(2)所表示的計算可以被等效替換。這樣能夠在代碼生成時使用單個FFTW guru接口調用優(yōu)化圖1中代碼片段的膠水代碼和FFT函數(shù)調用。

對比圖1和圖3可以看出，化簡和重排后的方案將局部數(shù)據(jù)重排緊接在調用FFT計算之后，不僅可以將計算執(zhí)行和訪存處理重疊起來隱藏部分時間開銷，還可以利用數(shù)據(jù)的局部性來提升訪存效率。

從理論上可以大致獲知，原先算法時間復雜度為O(n3+n2)，即O(n3)，經過表達式優(yōu)化后，算法時間復雜度可以被降低到O(n)。假設原先的運算中，計算時間為tc，訪存時間為tm。在經過計算、訪存優(yōu)化后，訪存時間為tc′，且有tc′<=tc，計算訪存總時間為max(tc′,tm)?？梢缘玫降睦碚摷铀俦葹?tm+tc)/(max(tc′,tm))。當tm=n·tc時，將其代入式(2)，可以獲得的加速比至少為(n+1)/n。

3 應用優(yōu)化示例

為了證明本文所提出解決方法的可行性，本文分別以較為簡單的矩陣乘算法以及一種重要的雷達系統(tǒng)處理算法，space time adaptive processing(STAP)算法作為應用示例來介紹。

3.1 矩陣乘算法優(yōu)化示例

簡單的矩陣乘是科學計算中最為常用的計算。矩陣乘算法有3種可行的實現(xiàn)方式：矢量-矢量運算(Level 1)、矩陣-矢量運算(Level 2)、矩陣-矩陣運算(Level 3)。這3種實現(xiàn)方式會分別調用BLAS、ScaLAPACK中的axpy、gemv以及gemm函數(shù)。使用axpy和gemv運算拼接矩陣運算時，需要使用多重循環(huán)以拼接完整的矩陣乘。圖6展示了最為簡單和典型的算法優(yōu)化思想。

圖6 使用gemm替換用戶編寫的gemv

用戶所編寫的應用程序中，為了實現(xiàn)較為靈活的功能，使用了矩陣-向量乘法，而非矩陣-矩陣乘法。在編譯器將原始C代碼翻譯成中間表示后，會對中間表示進行依賴分析，盡可能使用更為高效的矩陣-矩陣乘法代替原始的矩陣-向量乘法。

3.2 STAP算法優(yōu)化示例

STAP算法由4個階段組成： 多普勒處理(Doppler processing，DP)、協(xié)方差矩陣構造(covariance matrix construction，CMC)、計算自適應權重(computing adaptive weights，CAW)，以及應用自適應加權(applying adaptive weighting，AAW)。在不同階段之間，當進行FFT相關運算，或者BLAS、ScaLAPACK中的線性代數(shù)運算，則需要進行數(shù)據(jù)重排、對齊或數(shù)據(jù)拷貝。

接下來對優(yōu)化過程進行展開描述。圖7以圖示的形式重點表現(xiàn)該編譯器的關鍵優(yōu)化內容和核心思想。整個計算過程主要的3個優(yōu)化點如下。

(1)將數(shù)據(jù)布局與庫函數(shù)調用合并。DP階段如圖7(a)所示，其對應原始代碼如圖1所示。在該階段的原始運算過程中，中間的FFT函數(shù)前后存在大量的膠水代碼(用于數(shù)據(jù)重排和對齊的循環(huán))。嘗試合并一系列一維FFT后的膠水代碼，并替換為圖3中所示的代碼。

(2)用矩陣乘法取代外積。在CMC階段，每個協(xié)方差矩陣是由累加多個外積(outer-products)得到的，如圖7(b)所示，而每個外積均由多個從數(shù)據(jù)立方(datacube)中提出的快照向量(snapshot vectors)計算得到。編譯器將提取快照向量的過程用一個rank為0的FFTW-guru接口替代。除此之外，多個外積也可以被一個單獨的矩陣乘法替代(rank為k)，如圖8所示。

圖7 FFT和BLAS運算后/前存在膠水代碼

圖8 CMC階段優(yōu)化

(3)跨階段優(yōu)化。在AAW階段，該編譯器識別提取了相同的快照矢量。由此，上述快照矢量可被復用，不再進行數(shù)據(jù)提取。

通過上述優(yōu)化，將原先的膠水代碼所執(zhí)行的數(shù)據(jù)重排以及循環(huán)調用等過程進行了一個更高層次的抽象，變?yōu)榱艘粋€高級函數(shù)調用。

4 實驗平臺與性能分析

針對第3節(jié)提到的矩陣乘算法和STAP算法，本文在3種不同平臺上進行了實現(xiàn)。這些平臺包括：

(1) Haswell平臺：通用多核處理器(Intel Haswell)，Intel Xeon E5-4667V3，40 MB L3 Cache，16核，32線程。

(2) Xeon Phi平臺：多核協(xié)處理器(Intel Xeon Phi)，Intel Xeon Phi Processor 7210，32 MB L2 Cache，64核，64線程。

(3) 異構高峰值加速器：一種集成了更多運算器，同時存儲端使用3D堆疊DRAM[18]的研究架構，其結構類似于FFT加速器[19，20]、數(shù)據(jù)重塑單元[21]、Dot Product硬件。相比Haswell平臺和Xeon Phi平臺，其具有更高的硬件峰值算力。

針對Haswell平臺和Xeon Phi平臺，算法實現(xiàn)直接調用了公開實現(xiàn)的高性能函數(shù)庫，例如FFTW、Intel MKL[22]。而在異構高峰值加速器上，實現(xiàn)了可能調用的原始以及優(yōu)化接口以供性能對比，例如FFTW-guru、gemv、gemm等。進行性能對比的3種實現(xiàn)分別為：(1)未優(yōu)化版本，具有顯式循環(huán)、 數(shù)據(jù)拷貝和庫函數(shù)調用的原始C代碼；(2)編譯優(yōu)化版本，使用更高效的庫函數(shù)優(yōu)化循環(huán)、內存拷貝后的C代碼；(3)編譯優(yōu)化+并行優(yōu)化版本，在編譯優(yōu)化版本的基礎上添加供OpenMP/OpenACC識別的編譯制導語句以利用并行加速庫進行優(yōu)化的版本。

4.1 矩陣乘算法性能分析

矩陣乘的原始代碼為一份使用gemv函數(shù)加for循環(huán)的C代碼。經過編譯器優(yōu)化后，自動將原始代碼轉為中間表示，最后再將中間表示翻譯為直接使用gemm函數(shù)實現(xiàn)矩陣乘的C代碼。

圖9展示了在3種硬件平臺上，分別僅進行編譯優(yōu)化性能對比，橫坐標為優(yōu)化方式，縱坐標為優(yōu)化后相比原始版本的加速比。

圖9 矩陣乘應用程序在3個不同平臺上的性能比較

首先，可以看出，3種硬件平臺上，經過編譯優(yōu)化的C代碼執(zhí)行效率相比原始C代碼都有超過20倍的提升。其次，在Xeon Phi平臺和異構高峰值加速器上，使用編譯優(yōu)化后的加速比，相比Haswell要更好，這種現(xiàn)象的原因是3者的訪存帶寬幾乎一致，但后兩者有更高的硬件計算峰值，當減少訪存后，硬件效率提升更為明顯。最后，在Haswell和Xeon Phi平臺上，是否開啟編譯器中的并行優(yōu)化，沒有明顯的性能提升，這種現(xiàn)象的原因是矩陣乘是一個較為簡單的例子，編譯優(yōu)化所作的工作與并行優(yōu)化所做工作基本類似，所以增加并行優(yōu)化效果不佳。

4.2 STAP算法性能分析

針對STAP算法的一種原始實現(xiàn)，使用3組來自PNNL PERFECT Benchmark集合[23]的輸入數(shù)據(jù)，即大(large)、中(medium)、小(small)，分別測試原始代碼，進行編譯優(yōu)化的代碼以及同時進行編譯優(yōu)化、并行優(yōu)化的代碼。

圖10顯示了不同平臺上的性能，橫坐標為3種硬件上不同的數(shù)據(jù)集，縱坐標為優(yōu)化后的性能與未優(yōu)化版本的加速比。首先，在Haswell和Xeon Phi硬件平臺上測試3種數(shù)據(jù)集，僅僅進行編譯優(yōu)化后，優(yōu)化版本相比原始版本有加速，但不夠明顯，最高可以取得的加速比是在Xeon Phi硬件上對小數(shù)據(jù)集進行測試得到的1.39倍加速。這種現(xiàn)象的原因是整個應用中所調用的函數(shù)，可以被編譯器識別優(yōu)化的較少。其次，同時使用編譯優(yōu)化和并行優(yōu)化后，加速效果較為明顯。在Xeon Phi硬件和小數(shù)據(jù)集上可以取得4.89倍加速，而在異構高峰值加速器上，可以取得8.21倍加速。這種現(xiàn)象的出現(xiàn)是因為原始實現(xiàn)中存在較多可以并行的循環(huán)代碼。

綜合在簡單矩陣乘和STAP算法兩種應用上原型編譯器的表現(xiàn)，可以得到的結論是：在簡單應用中，本文所實現(xiàn)的原型編譯器，可以通過優(yōu)化代碼實現(xiàn)的方式，顯著提升應用性能。而在復雜的應用中，該原型編譯器，可以通過優(yōu)化代碼實現(xiàn)和插入編譯制導語句，使復雜應用不再需要進行繁雜的手工優(yōu)化。因此，本文提出的中間表示和編譯器，可以解決因為膠水代碼而產生的高性能計算程序性能可移植性欠佳的問題。

圖10 STAP應用程序在3個不同平臺上的性能比較

5 結 論

許多HPC應用程序是直接基于標準化庫和編譯制導語句實現(xiàn)的。由于將多個不同的庫函數(shù)調用與應用進行鏈接的膠水代碼的存在，高性能計算應用程序性能可移植性(即在不同平臺上保持高性能)依然是一個不小的挑戰(zhàn)。通常，圍繞庫函數(shù)調用的膠水代碼會提供可以進行優(yōu)化的上下文信息。利用這些膠水代碼提供的上下文信息，本文定義和引入了一種作為中間表示的領域特定語言，最終使用更高效的函數(shù)調用替代膠水代碼和原始的庫函數(shù)調用，或根據(jù)并行硬件架構本身，自動插入供OpenMP或OpenACC的識別編譯制導語句，完成對應用程序的優(yōu)化。這種方法使得程序員不再需要針對不同硬件平臺，對應用程序代碼進行復雜的手工優(yōu)化。本文以簡單的矩陣乘算法和較為復雜的STAP算法優(yōu)化過程展示了實際的優(yōu)化效果。實驗結果表明，根據(jù)應用程序原始代碼的編寫以及硬件架構的不同，原型編譯器可以取得不同的優(yōu)化效果。而對于真實應用，在通用處理器硬件架構上，經過優(yōu)化的代碼相比原始代碼可以取得最高4.89倍的加速比；在類似異構高峰值加速器的實驗性硬件架構上，本文所描述的工作可以取得最高加速8.21倍。