自動向量化：近期進展與展望

馮競舸，賀也平，3，陶秋銘

（1.中國科學院軟件研究所基礎軟件國家工程研究中心，北京 100190；2.中國科學院大學研究生院，北京 100049；3.中國科學院軟件研究所計算機科學國家重點實驗室，北京 100090）

0 引言

芯片和基礎軟件的發展，不僅影響國家信息安全[1]，也影響產業供應鏈安全。編譯器作為基礎軟件之一，對發揮芯片特性、提升程序性能至關重要，國內越來越多的企業和科研機構高度重視編譯技術研發，例如華為、阿里巴巴、騰訊、中國科學院、國防科學技術大學、清華大學、中國科學技術大學、上海交通大學、武漢大學，等等。

自動向量化是一種重要的編譯優化方法，它利用單指令流多數據流（SIMD，single-instruction stream multiple-data stream）系統擴展部件[2]提供的數據并行處理能力，有效提升程序性能，在數字信號處理[3]、大數據[4]、人工智能[5]、高性能計算[6]等眾多應用場景[7-10]中發揮著重要的作用。

自動向量化不僅可顯著提升程序性能[11-12]，也能降低程序功耗[13]。與程序員以手動方式編寫SIMD 向量程序（如利用內嵌匯編[14]、內部函數[15]、SIMD 函數庫等）相比，自動向量化能將程序員編寫的標量程序自動轉換為SIMD 向量程序，不需要程序員深入理解SIMD 擴展部件的功能和特性，從而減少程序員的負擔。

人們對計算性能的不懈追求和SIMD 擴展部件的迅速發展推動著自動向量化技術的進步。SIMD 擴展部件的應用并不局限于多媒體應用[16]中，還大量應用于大數據、人工智能、云計算等科學計算領域和訪存密集型應用領域。處理器對SIMD 擴展部件的支持是自動向量化的硬件基礎。目前絕大部分處理器都支持SIMD 擴展部件，例如Intel 推出的x86 AVX512 指令集，ARM 推出的SVE[17]指令集和美國加州大學推出的RISC-V[7]指令集等。隨著硬件處理器技術的快速發展，SIMD 擴展部件支持的并行長度越來越長，功能越來越豐富[18]。如何充分利用這些功能日漸強大的SIMD 擴展部件，給自動向量化帶來新的挑戰，并推動著自動向量化技術的進步。然而，盡管目前主流編譯器如GCC、LLVM和ICC 等都初步實現了自動向量化功能，但仍存在較大的提升空間。國內外研究人員對ICC和GCC 的自動向量化功能評測后發現，自動向量化獲得的性能與手工向量化相比，依然存在較大的差距[11，19]。

近年來，大量的自動向量化研究成果被公布。為了對該研究問題的進展進行系統梳理和歸納總結，本文搜集和分析了2011—2021 年關于自動向量化的重要文獻。

早在2007 年，張為華等[20]針對自動向量化的研究進展進行了綜述。2015 年，高偉等[2]也對相關研究進行了成果綜述。2015 年以來，自動向量化領域出現了一系列新的問題和研究成果，例如運算類型語句的自動向量化[21]（CGO2015），基于特殊SIMD 指令的自動向量化[22]（ASPLOS 2021）等，以及新的解決方法，例如利用機器學習方法解決自動向量化問題[23]（CGO2020），利用部分線性化技術解決分支判定語句的自動向量化問題（PLDI2018）[24]等。本文旨在對近年的自動向量化技術研究成果進行更加全面的分析和歸納總結。基于目前該領域的研究現狀，展望了該領域的發展趨勢，總結了可能的研究方向，為未來的研究提供參考。

鑒于已有的綜述論文，本文對部分較早期的成果不做贅述，更聚焦于2015 年之后的研究成果。當然由于個別類型的自動向量化方法是基于早期研究成果（2015 年之前），為了完整性和便于讀者理解，本文對部分相關研究也會做適當的介紹和分析。

1 自動向量化問題概述

1.1 自動向量化問題抽象描述

自動向量化問題可描述為：在保證轉換前后語義具有可觀察等價性[25]，滿足處理器支持SIMD 擴展部件的限定下，評估有性能收益時，利用編譯器將標量程序轉換為向量程序，有效提升程序性能，其具體解釋如下。

1)保持程序轉換前后語義“可觀察等價性”是保證自動向量化正確性的前提條件。Plotkin[25]給出了可觀察等價性的定義，即對于2 個表達式M和N，當且僅當在M和N均為封閉（即沒有自由變量）的上下文C中，對C[M]和C[N]求值，兩者或者產生相同的結果或者均不停止時，那么M和N是可觀察等價的。

2)自動向量化要在處理器支持特性的限制條件下生成SIMD 擴展指令，不能生成處理器不支持的SIMD 擴展指令。

3)自動向量化目標是提升程序運行的性能。只有當編譯器判定自動向量化有收益時，才進行向量化。

自動向量化問題描述如圖1 所示，限制條件1中的Origin_Semantics和Sem分別是向量化轉換前后的程序語義，它們必須是可觀察等價的。限制條件2中SimdInst 是向量化后生成的向量指令集合，Support_SimdInst 是SIMD 擴展部件支持的指令集合。SimdInst 必須包含于Support_SimdInst。限制條件3中，性能評估自動向量化有收益，自動向量化的目標就是在保證限制條件1～3 下，生成向量指令，以有效提升程序性能。

圖1 自動向量化問題描述

下面用一個示例說明上述描述。如圖2 所示，圖2(c)中的向量加載指令（vload）、向量存儲指令（vstore）和向量加法指令（vadd）在多數處理器中都支持。圖2(a)程序執行時需4 個加載訪存指令（load)、2 個加法指令（add）和2 個存儲訪存指令（store)，圖2(b)程序執行時（如圖2(c)匯編代碼）只需要2 個vload、一個vadd和一個vstore，比圖2(a)程序的代價低。并且，圖2(b)與圖2(a)程序語義一致，處理器支持所有生成的SIMD 指令，且可有效提升性能。因此，圖2(a)標量程序可轉換為圖2(b)向量程序。

圖2 自動向量化示例

1.2 自動向量化關鍵問題分類描述

基于自動向量化問題的“語義可觀察等價性”和“性能有收益”等限制條件分析，自動向量化的關鍵問題可分類歸納為以下4 個方面。

1)自動向量化與編譯器的保義分析和變換能力相關，保義分析和變換能力越強，向量化的適用范圍越大。向量化從程序執行順序角度講，本質上是將原始串行程序轉換為局部并行程序，在同一SIMD 向量指令中運行的操作不能有依賴關系，否則將改變原始程序語義。面向向量化的保義分析的核心是依賴關系分析。依賴關系分析與別名關系分析緊密相關，別名關系分析能力的不足有時會阻礙依賴關系的判定。

2)自動向量化與其自身的分組方法有關。將多個標量數據轉為一個向量數據的過程稱為分組。分組直接影響向量化的收益。根據程序分析粒度，向量化分組分析和變換問題可分為基本塊級、循環級、函數級[2]和混合級向量化分組問題?；緣K級分組問題旨在尋找基本塊內向量化分組，循環級分組問題旨在尋找包含循環的程序中迭代間語句分組，函數級分組問題旨在尋找不同函數之間的語句分組，混合級分組問題是前面3 種分組方式的擴展及融合問題。

3)向量化與處理器特性相關。向量化從使用指令角度講，本質是利用SIMD 擴展部件的運算并行和訪存并行特性提升程序性能。在運算并行特性方面，目前大多處理器只支持相同類型運算并行的向量指令。在訪存并行特性方面，大多處理器只支持對齊/連續訪問指令[26]，或者盡管支持非對齊/非連續指令，但其指令時延較大。在并行度支持特性方面，大多處理器只支持處理長度為2 的整數次冪[27]的向量。由于上述限制因素，編譯器不能直接使用SIMD 擴展指令，對不滿足上述特征的程序進行向量化。本文將面向處理器支持特性的分析和變換問題分為運算并行相關問題、內存訪問并行相關問題和并行長度相關問題。

4)向量化與性能評估分析相關。性能評估最終決定編譯器是否進行向量化。性能與處理器支持的指令時延、訪存模型和寄存器相關特性緊密相關。設計精確的向量化代價評估模型，能夠有效指導向量化的程序變換，并減少因不恰當的程序變換導致程序性能下降的情形。圖3 展示了自動向量化流程與上述4 個關鍵問題的關系。

圖3 自動向量化流程

根據上述分析，向量化問題可歸納為4 類：保義分析和變換問題、分組分析和變換問題、處理器相關分析和變換問題以及性能評估分析問題。本文從這4 個角度，對近幾年自動向量化的研究成果進行分析和總結。

2 保義分析和變換問題及方法

保義分析和變換是編譯優化的基礎和前提。幾乎所有的編譯器優化方法都涉及保義分析和變換問題。本文只關注自動向量化的保義分析和變換問題。目前面向自動向量化的保義分析和變換的研究集中于依賴和別名的分析和變換。

2.1 依賴分析和變換

2.1.1 數據依賴分析和變換

數據的訪問和重用常引入數據依賴，如圖4 所示，當兩條語句訪問相同的存儲單元，且其中有一個寫數據，則發生數據依賴。

圖4 數據依賴說明

近幾年對于數據依賴分析，學術界有三方面的主要突破。在研究對象方面，從原始的簡單依賴關系的判定，逐漸轉向多層嵌套復雜依賴關系的判定；在理論方法方面，從傳統靜態分析方法，轉向動態投機執行的方法，從軟件表達式等價變換的方法，轉向基于特殊硬件處理的方法；在分析和轉換流程方面，從傳統的“分析-判定”流程模式，轉向“分析-轉換-判定”迭代模式。

起初，向量化主要采用編譯器中通用的依賴分析和變換方法，例如GCD 測試[28]和Banerjee 測試[29]等，這些方法沒有考慮SIMD 的特點，如SIMD 擴展部件的并行長度有限，在循環中，當操作的依賴距離大于其并行長度時，把這些操作存放到SIMD 寄存器中，不改變原始程序語義。Buli? 等[30]基于Banerjee 方法將SIMD 擴展部件并行長度信息應用于依賴測試中，擴展面向向量化的依賴測試識別范圍，有效解決在循環中依賴距離大于SIMD 并行化長度的數據依賴分析問題。

傳統編譯器的依賴測試主要基于靜態分析的方法，然而有時候該方法不能準確判定語句的依賴關系。2017 年，Jensen 等[31]首次提出根據原始程序中已有的OpenMP 并行編譯指示信息，指導面向向量化的依賴分析，基于標識信息的依賴判定方法一定程度上彌補了單純靜態分析本身程序特征方法的不足，該方法實質是利用了原始程序中指導多線程并行的信息指導向量化。還有研究者采用動靜態分析結合的方法解決依賴判定問題。例如2017 年，Sampaio 等[32]提出了基于動靜態結合的依賴分析及變換方法，對于不能完全由靜態分析確定依賴關系的程序，建立多個可能的執行處理版本，在實際運行中確定具體執行的版本，該方法能夠解決因靜態分析信息不全導致的依賴分析失敗的問題。

當編譯器判定存在阻礙向量化的依賴時，傳統的向量化方法不進行程序轉換。然而，有的數據依賴關系可通過程序變換改變，從而使向量化成為可能。2017 年，趙捷等[33]根據SIMD 特征及等價變換關系式，提出并論證了7 個依賴分析及轉換的定理，為利用等價關系式解除依賴奠定理論基礎，并基于數組依賴圖構建包含數組和語句依賴信息的有向圖，在此基礎上，利用語句重排和節點分裂等技術在數組依賴圖中改變程序中阻礙向量化的依賴關系，增強了向量化能力。

2.1.2 控制依賴分析和變換

程序中分支判定和循環語句經常引入控制依賴，如圖5 所示，語句C 是否執行依賴于語句B 的判定條件?？刂埔蕾嚱o程序分析及優化帶來復雜性和不確定性，增加了向量化難度。

圖5 控制依賴說明

近幾年對于面向向量化的控制依賴問題，學術界在研究對象方面，從原始的簡單分支判定語句的向量化，逐漸轉向多層嵌套分支判定語句的向量化；在向量并行化方面，從原始迭代間的分支判定語句的向量化，轉向多角度綜合考慮迭代內和迭代間的語句自動向量化；在理論方法方面，從先前的基于控制流轉換數據流的全分支轉換法，轉向更加激進的分支判斷轉換方法，如部分線性化和投機執行等方法。

Smith 等[34]將控制依賴轉換成數據依賴（If-conversion），然后利用傳統向量化方法處理[35]。基于If-conversion 的向量化方法示例如圖6 所示，圖6(a)是原始程序，圖6(b)是通過If-conversion并利用選擇指令（select）實現對控制流程序的向量化。

圖6 基于If-conversion 的向量化方法示例

基于If-conversion 的向量化方法在沒有代價模型指導的情況下，轉換所有分支判定語句，生成較多額外的選擇指令。Shin[36]利用謂詞判定是否會真正執行，繞過一些不實際執行的語句，減少了在包含多層嵌套分支程序中產生的冗余指令。還有基于分支分類處理的方法，例如2015年，孫回回等[37]解決嵌套分支的向量化問題，根據控制流分支控制條件與循環迭代之間的關系將控制流條件變量分為循環變量和循環不變量兩類，外提循環不變量，將循環變量轉換為數據流形式，并利用遞歸方法解決包含嵌套分支程序的向量化問題。利用分支逆轉方法將向量化沒有收益的分支退回為控制流，該方法能夠有效減少包含嵌套分支程序向量化的指令代價。近幾年，分支線性化選擇方面的研究有了新的突破。Moll等[24]在PLDI 2018 會議中首次提出了用部分分支線性化技術及基于控制流及數據流分析技術，來減少條件分支轉換的數量，與先前的所有分支都進行線性化不同，該研究根據程序分支的特點，并結合不同迭代的一致性分析，來選擇向量化收益更大的分支進行線性化處理。該方法有效減少了分支依賴引入的冗余重組指令，顯著提高了向量化對分支依賴程序的性能，該方法對SPEC CPU 2017和NAB Benchmark 的測試程序平均性能提升了146%。

傳統控制依賴分析主要采用靜態分析方法，沒有考慮動態運行時信息，忽略了一些優化機會。Sujon 等[38]利用投機執行的方法，解決包含控制依賴程序的向量化問題，根據運行時程序執行的路徑判定是否向量化，該方法能夠有效處理靜態分析中不可知依賴信息的程序，適用于總是執行可向量化特定分支的程序。類似地，Baghsorkhi 等[39]采用投機執行法，對包含控制依賴且運行執行次數少的程序進行部分向量化?；谶\行時統計的方法也應用于分支判定語句的向量中，例如，Sun 等[40]利用靜態仿射分析和動態統計控制流運行比例的方法，探測一致性運行分支，插入運行時檢查分支語句，該方法基于運行程序，根據統計的分支運行狀態進行動態調優，能夠有效減少因控制流向量化引入的冗余分支和掩碼向量指令，該方法使Rodinia 測試程序平均性能提升1.14 倍。

此外，除了上述從控制依賴關系角度出發解決向量化問題，還出現了從分支判定語句內部挖掘向量化并行性的研究。2017 年，高偉等[41]分析分支語句輸出的基本塊內蘊含的向量并行性，首次提出考慮基本塊間向量重用的直接控制流向量化方法，向量化包含同構語句條數較多的循環，然后利用代價模型指導向量指令生成。

2.2 別名分析和變換

別名分析是指判定2 個變量是否訪問同一地址空間的分析過程[42]。別名分析的局限，會限制編譯器對依賴關系的判定和對優化機會的識別，進而限制向量化。對于如圖7 所示的示例程序，在考慮指針別名引起的依賴時，指針a和b作為形式參數傳入函數體，在無法取得a和b的內存地址信息時，指針a可能存在循環攜帶的真依賴，該循環無法進行向量化。

圖7 別名分析示例程序

針對別名分析，近幾年學術界逐漸從研究傳統的靜態的別名分析法轉為動靜態結合的分析方法。如侯永生[43]利用動靜態結合的方法，解決別名和非線性表達式的動態檢測條件構建問題，該方法插入動態監測代碼，運行時判定是否進行向量化。類似地，2015 年，劉鵬等[44]通過動態插樁和試運行提取指針別名信息，并反饋到向量化階段指導向量化代碼生成。

除了動靜結合的方法外，近幾年還出現了挖掘程序別名相關過程間的特征信息的突破性方法。例如，2016 年，Sui 等[45]發現在自動向量化中應用的別名分析方法較保守，例如編譯器沒有將過程間分析方法應用于自動向量化的別名分析中。別名分析方法的局限阻礙了依賴關系的判定，丟失了一些自動向量化的機會。對于包含指針、數組訪問和結構體訪問循環的程序，文獻[45]根據訪存基地址，結合循環特征及訪存的范圍，進行過程間別名分析，該方法能夠有效處理包含數組和結構體等程序的向量化的別名分析問題，可有效提升SPEC CPU 2000 基準測試的177.mesa程序7.18%的性能收益。

3 分組分析和變換問題及方法

自動向量化分組策略直接影響能否向量化及其收益[46]。近幾年對于分組問題，在研究對象方面，從原始單一形式的分組方法研究，逐漸轉向多級融合的分組方法研究；在程序信息分析粒度方面，從先前單一基本塊或循環特征信息分析，轉向跨基本塊以及多層嵌套循環的特征分析；在理論方法方面，從先前的啟發式貪心方法轉向更加高級的組合優化方法，如人工智能、動態規劃和整數線性規劃，等等。

3.1 基本塊級分組問題及方法

基本塊級分組旨在尋找基本塊內語句的向量并行性，如圖8 所示，將同一個基本塊中的4條語句，分組轉換為一個向量語句。Larsen 等[47]于2000 年首次提出了奠基性的基本塊級向量化方法，即超字并行（SLP，superword level parallelism）方法，基于連續內存訪問，利用基本塊內數據的復用信息，尋找多條可并行執行的同構語句，并將其向量化。

圖8 分組轉換示例

學術界對SLP 進一步展開研究，提出了許多新的改進方法，其分組策略主要包括局部貪心和全局的分組策略。貪心策略和全局策略互有優劣。貪心策略編譯速度快，但分析信息較局部，無法有效向量化不規則的內存訪問。全局策略分析信息較全局，能夠向量化不規則的內存訪問，但編譯時間較長。

局部貪心分組指基于“定義/使用”和“使用/定義”關系對向量進行分組。近幾年出現了許多相關的擴展優化工作[48-51]。例如，2015 年，Porpodas 等[49]在建立“定義/使用”或“使用/定義”依賴圖時，實時計算代價，找到最小生成指令代價，去除生成破壞代價的指令。2017 年，Porpodas 等[52]同時利用“定義/使用”和“使用/定義”關系信息擴展同構語句，首次在向量分組中利用了不同構建同構鏈間的重用信息，來減少向量化中重組指令的生成。2019 年，Mendis等[53]將啟發式SLP 方法擴展應用于嵌套匯編形式的向量程序，分析向量程序的并行度結合處理器所支持的SIMD 功能，并利用混洗指令進一步提升程序的向量并行度，其實質是將向量化的范疇從“多對一轉換”擴展到了“多對多轉換”。

全局分組指在程序中進行全局搜索可向量化的指令。例如，Barik 等[54]在基本塊中進行全局搜索，利用動態規劃方法綜合考慮標量和向量指令代價對程序進行分組。Liu 等[55]擴展了初始對象選擇范圍，除了連續內存訪問外，將具有相同類型的運算也作為初始向量對象，以減少重組指令為目標，基于依賴圖全局搜索，并啟發式選擇相對最優的分組方法。Huh 等[56]在 MICRO 2017 會議上首次提出了將分級處理的思路應用到全局SLP 分組中，先局部選擇收益較高的向量化對象，再全局將它們重組構建向量化程度更高的向量對象集合。該方法適用于包含尺寸較大的基本塊，平均提升SPEC CPU 2006和NAS 測試程序的性能8.6%。值得一提的是，Mendis 等[57]在OOPSLA 2018 會議上提出將整數線性規劃方法應用于全局SLP 向量化分組中，并利用IBM CPLEX 商用的整數線性規劃調度器，能夠找到在函數中相對最優分組的向量化策略，該方法使SPEC CPU 2017 的浮點測試程序平均提升了7.58%。此外，近幾年出現了基于人工智能技術的分組方法，代表性工作如Mendis 等[58]在Neur IPS2019 提出的利用圖網絡學習方法模擬SLP 方法的分組打包過程。

3.2 循環級分組問題及方法

循環級向量化分組旨在尋找循環中迭代間的向量化并行。Allen 等[59]首次提出基于循環的（Loop-based）自動向量化方法，如圖9 所示。Loop-based 自動向量化方法針對內層循環的迭代空間，將整個數組作為一個向量單元進行操作，基于依賴關系分析將在不同迭代間且相互間不會形成依賴環的多條語句轉換為向量形式。

圖9 Loop-based 自動向量化方法示例

學術界在Loop-based 方法的基礎上進一步改進優化，集中于外層循環向量化及多層嵌套循環向量化。其中大多數研究集中于多層嵌套循環向量化。

對于外層循環向量化，Nuzman 等[60]利用循環展開實現外層循環向量化，該方法能夠有效提升包含多層嵌套循環且外層循環包含較多并行性的程序性能。

對于多層嵌套循環向量化，魏帥等[61]發現對于多層嵌套循環而言，有時會有多種向量化分組方法，如何進行分組選擇影響向量化的收益，綜合考慮多層嵌套循環的內存訪問和依賴等信息，確定相對最優的自動向量化方案，該方法可有效選擇包含多層嵌套循環程序的分組向量化方案。研究者也將多面體技術[62]應用于多層嵌套循環的分組選擇中。多面體技術是一種統一化的程序變換表示技術，它通過迭代域、仿射調度和訪存函數表示代碼，有利于表示程序變換的組合，有助于解決包含循環程序的向量化問題。Trifunovic等[63]建立一種考慮對齊、連續和類型轉換等因素的代價模型指導多面體變換，選擇收益最大的向量化方案。Kong 等[64]基于多面體模型，結合向量化、并行化和局部性因素分步驟進行程序變換；基于依賴和局部訪問信息，利用循環分塊和循環融合等方法進行空間局部性優化，選擇相對最優的向量化方案。

3.3 函數級分組問題及方法

函數級向量化從函數粒度[65]識別程序中的數據級并行，發展到過程間分析。函數包含的程序類型復雜多變，程序的復雜性和過程間的分析給函數級向量化分組分析和變換帶來挑戰。

起初，編譯器通過基于模式匹配的內建函數（build-in function）[66]實現函數級向量化，如基礎數學向量函數已在編譯器中廣泛使用。近幾年，相關研究者深入研究函數級向量化分析和變換方法。2015 年，Karrenberg 等[67]在靜態單賦值表示形式（SSA，static single assignment form）下，基于數據流分析和變換利用掩碼和選擇指令解決函數向量化中運行操作不一致的問題。2017 年，Reiche 等[68]對Karrenberg 的方法進一步擴展，針對圖像處理專用語言，結合領域語言的相關信息，實現了高級語言程序到高級語言程序的函數級向量化。

3.4 多級向量化分組擴展及融合

學術界近期關注如何綜合利用上述不同級別的分組方法，主要包括多種轉換方法的融合及多模式分組的選擇。多種轉換方法的融合指同時利用多種轉換方法來提升向量化的適用范圍。例如，If-conversion 與SLP 結合實現跨基本塊語句的向量化[69-70]；循環展開與SLP 的結合實現循環的向量化[71-72]。

多模式分組的選擇指對多種分組模式進行選擇來提升向量化的收益。2017 年，高偉等[46]提到程序蘊含的并行性是固有的，根據程序的特征分析向量化的并行度，來選擇具體的分組方法，分組方法包括 Loop-based 方法、SLP 方法和Loop-aware 方法。該方法平均提升SPEC CPU 2006、SPEC CPU 2000和NPB中部分測試程序的12.1%的性能。Zhou 等[73]根據語句重用及并行相關信息，同時綜合考慮基本塊級和循環級分組方法，該方法能夠有效減少包含循環結構的程序在自動向量化中產生的重組指令負載。

4 處理器相關分析和變換問題及方法

目前絕大部分處理器都支持SIMD 擴展部件，如Intel、AMD和ARM 等，如表1 所示。SIMD 擴展部件支持的向量寄存器長度越來越長[74]，功能也越來越豐富，Intel SIMD 擴展部件的指令集統計如表2 所示。

表1 支持帶有SIMD 擴展部件的處理器

表2 Intel SIMD 擴展部件的指令集統計

SIMD 擴展部件的發展推動著向量化方法的不斷改進。1)向量寄存器長度的增長增加了向量化的并行度。2)SIMD 擴展部件功能越來越豐富，使編譯器能夠向量化更多的程序。例如，AVX512 指令集的沖突探測指令有助于編譯器實現對包含間接數組訪問程序的自動向量化。

然而，SIMD 相關處理器在運算并行、訪存并行及并行度支持方面依然存在以下局限。

1)在運算并行特性支持方面，大部分處理器只支持相同類型運算并行的向量指令，不支持不同類型運算并行的向量指令，或者盡管支持不同類型運算并行的向量指令，但是其指令的時延較大。

2)在訪存并行特性支持方面，大部分處理器只支持連續向量內存訪問指令，或者盡管支持非連續內存訪問指令，但指令時延較大。大部分處理器只支持對齊訪問指令，或者盡管支持非對齊訪問指令，但指令時延較大。

3)在并行度支持特性方面，SIMD 擴展部件支持的并行長度有限，且只支持向量處理長度為2 的整數次冪。

由于上述局限，對于有些程序，編譯器不能直接使用SIMD 擴展指令進行向量化，進而限制了向量化的適用范圍。為此，本節分別從以上三方面介紹面向處理器支持特性的向量化分析和變換問題及方法。

4.1 運算相關分析和變換問題及方法

如前文所述，編譯器不能直接使用SIMD 擴展部件支持的指令實現對運算類型不相同程序向量化。然而，現實中存在大量包含不相同類型運算的程序，且有些實際上運算類型相同的程序語句在編譯過程中由于某些標量優化（如常量折疊和強度削弱[75]等）的實施，會被轉換為運算類型不同的程序，這類情形廣泛存在于SPEC CPU 測試程序中。如果能夠對這類程序實現自動向量化，可有效提升這些程序的性能。

運算類型不相同程序的向量化問題是Porpodas等[21]在2015 年CGO 會議中首次提出的，近年來有多篇論文對該問題從不同角度提出了解決方法，主要包括基于硬件特殊指令的方法和基于表達式等價變換的方法。

1)基于硬件特殊指令的方法。其主要利用SIMD 特殊指令實現運算類型不同語句的向量化，例如，PSLP 方法[21]將運算類型不同的語句中差異的部分相互參照并分別通過添加選擇指令進行擴充，從而將運算類型不同的語句轉換成運算類型相同的形式；VeGen 方法[22]實現了一個編譯框架，利用Non-SIMD 指令實現對運算類型不同語句的向量化。基于硬件特殊指令的方法一般會受到處理器平臺的限制，且會引入額外的運行代價。

2)基于表達式等價變換的方法。其主要利用表達式等價變換將滿足特定條件的運算類型不同的語句轉換為運算類型相同的語句，從而為實施SLP 創造條件。例如，LSLP[50]（look-ahead SLP）方法針對運算順序存在差異的多條語句分析和處理，當條件合適時基于交換律對可交換運算操作和操作數進行重排，從而獲得運算順序相同的語句。SN-SLP[76]（super-node SL）方法與LSLP 方法類似，當條件合適時基于減法或者除法的等價關系式（如a-b-c=a-c-b）對不同語句中的運算進行重排。基于表達式等價變換的方法一般對處理器硬件沒有特殊要求，不會引入額外的運行代價。

4.2 訪存相關分析和變換問題及方法

訪存并行特性主要包括連續和對齊2 個方面，下面分別介紹相關問題及方法。

4.2.1 連續訪存相關分析和變換問題及方法

非連續內存訪問在程序中大量存在，例如間接數組[77]和結構體等。對于非連續內存訪問的向量化，學術界有了新的突破。在分析方法方面，從傳統的靜態分析方法，擴展到基于動態投機執行的方法、基于特殊硬件指令的方法以及針對特定類型程序的訪存排布方法；在研究對象方面，從傳統的固定步長的非連續內存訪問的向量化研究，擴展到不固定步長[78]的非規則連續內存訪問的向量化研究。

在訪存信息的分析方面，在編譯器中對于連續內存訪問的判定主要基于連續內存訪問定義的靜態分析法。單純通過靜態分析法有時難以判定訪存是否連續，有研究者利用動靜分析結合的方法解決該問題，例如，姚遠[79]記錄指針引用信息，進而確定指針引用對齊和連續信息，根據循環迭代信息推出運行時指針地址信息判斷對齊和連續性信息指導自動向量化，該方法利用動態運行時信息指導對齊和連續訪存指令生成，減少了非對齊和非連續內存訪問。

在分析對象方面，近期研究集中于規則步長的內存訪問、結構體、間接數組和非規則內存訪問方面的向量化研究。

對于規則步長的內存訪問，Nuzman 等[80]發現循環中包含數組訪問步長為2 的整數次冪內存訪問程序大量存在，為了實現此類程序的向量化，基于線性數組訪問的基地址和步長信息，給出了循環中訪問步長為常量操作的識別方法，抽象定義了交錯操作和提取操作，如圖10 所示，利用該操作實現循環中包含數組訪問步長為2 的整數次冪內存訪問程序的向量化。此后，Anderson 等[81]利用混洗指令實現基于循環的數組訪問步長為任意長度的向量化，該研究也利用了數據流分析，改變不同迭代的執行順序以減少不必要的混洗指令生成，能有效減少重組指令的數量。

圖10 交錯和提取操作

結構體在程序中很常見，由于其數據的非連續和非對齊訪問特性[82]，導致對其向量化[83]較困難。近幾年，研究者關注對結構體的向量化。2015年，Li 等[84]提出一種轉換結構體中數據重組的方法，利用矩陣轉置運算，使結構體中相同類型的訪問變量數據排布連續，進而減少了非連續內存訪問。2016 年，于海寧等[85]提出利用結構體中訪問的數據相似性信息指導結構體拆分，將引用的結構體數組的非數組域映射到二維數組來滿足結構體數組向量化時的訪存連續和對齊要求，以降低緩存失效的次數。

有些包含間接數組訪問的程序[86]由于在編譯階段不知是否訪問連續、對齊或依賴關系信息，導致很難向量化[87]。2018 年，姚金陽等[88]利用局部數據重組方法解決間接數組索引向量化問題，首先將間接數組賦值到臨時數組中，然后將臨時數組中的數據加載到SIMD 向量寄存器，進而實現向量化，運算結束后根據需求判斷是否將其存入間接數組。

非規則內存訪問形式的代碼在人工智能和大數據等應用領域廣泛存在，近幾年對該類型程序的向量化研究越來越引起學術界的關注。非規則內存訪問的隨機性和不確定性，給向量化的依賴、連續和對齊相關分析及變換增加了難度[2]。近幾年，關于非規則內存訪問的向量化研究出現了新的研究方法，包括排布內存訪問的方法和基于硬件特殊指令的方法。其中訪存排布代表性的工作有：Chen等[89]在CGO2016 會議上將不規則的內存訪問抽象為稀疏矩陣的計算，通過排布內存訪問的結構，增強內存訪問的時間和空間局部性，進而有效提升了非規則內存訪問的性能收益，對于一些包含不規則的圖計算的應用平均提升了2.81 倍的性能?；谔厥庥布噶畹拇硇苑椒ㄓ校篔iang 等[90]在CGO2018 會議中利用AVX512中的沖突探測指令，并結合運算的結合律進行對reduction 型非規則內存訪問的向量化，在部分圖計算的應用中可提升1.4～11.8 倍的性能。

4.2.2 對齊訪存相關分析和變換問題及方法

目前針對非對齊內存訪問的研究問題主要包括靜態分析訪存的對齊信息方法[26，91]、基于OpenMP 的編譯指示方法[92]、基于硬件特殊指令的方法[93]、基于動態運行時分析的方法[94]以及訪存排布方法[28]，等等。由于近幾年并未發現有新的相關研究工作，因此本文不做詳述。傳統的非對齊內存訪問的向量化研究可詳見文獻[2]。

4.3 并行度相關分析和變換問題及方法

并行度選擇直接影響向量化能否實施及其收益。并行度越大，通常向量化的收益越高，可向量化的條件越嚴格。選擇適合的并行度并不是顯而易見的，與程序本身蘊含的并行特性以及處理器支持特性都有關系。

近幾年，并行度的選擇研究在分析粒度方面越來越精細，從傳統循環級的分析[59]，到后來的語句級的分析[56]，再到近幾年新出現指令級的分析[27]。其中代表性的工作是VW-SLP（PACT2018），根據程序蘊含的并行特性；在指令級別調整向量的并行度，當可并行語句較多時候，增大向量并行度，充分利用SIMD 的并行特性；當可并行語句較少時，減少并行度，避免向量分組過早停止。除了傳統的并行度分析和轉換方法外，近幾年也出現了面向并行度調節的機器學習方法[95-96]。例如，2019 年，Haj-Ali 等[23]將端到端的深度學習方法應用到循環向量化并行度選擇中，與原有的方法相比，性能提升了1.29～4.73 倍的性能提升。

并行度的選擇除了與程序特征有關系，也受限于處理器的特性。如前文所述，目前大部分處理器SIMD 擴展部件只支持向量處理的長度為2 的整數次冪。因此編譯器無法直接利用SIMD 指令實現非2 的整數次冪并行度的向量化。然而，這類程序在現實中普遍存在，如基于紅綠藍顏色標準表示的多媒體應用中經常出現并行語句數量為3 的程序。

非2 的整數次冪并行度向量化是近幾年出現的新問題，目前的解決方法主要是基于指令生成優化的方法。例如，2016 年，Zhou 等[97]在把向量寄存器數據存儲到內存時，先把不需要處理的數據拿出來，等待計算完成后把數據存放回去，該方法能夠處理并行度為非2 整數次冪程序的向量化，并減少了重組指令的數量。類似地，2017 年，高偉等[46]部分利用SIMD 擴展指令，實現包含循環次數或者基本塊內可并行語句較少程序的向量化，區分向量寄存器中的有效部分和無效部分，把有效部分的數據經過計算傳進內存，無效部分的數據不傳送到內存，該方法能夠處理并行度為非2 的整數次冪程序的向量化。

5 性能評估分析問題及方法

編譯器利用代價評估模型輔助判定是否實施向量化。代價評估模型需要精確且評估時間復雜度不能太高。然而，這兩方面往往是矛盾的。代價評估模型越精確，需考慮處理器的因素越多，導致代價評估模型算法復雜度越大。如何找到有效的代價評估算法是個挑戰。

近幾年，關于向量化性能評估分析問題，學術界出現了較多新的方法，從傳統的基于指令計數的評估方法，轉向基于人工智能的方法。在評估模式使用方面，從傳統的應用于判定是否向量化，轉向利用評估模型指導面向向量化相關的程序變換。

在評估方法方面，出現了較多基于機器學習的方法。例如，Stock 等[98]等針對向量化代價模型不精確的問題，利用機器學習方法提取匯編代碼特征，結合循環重排、循環展開以及向量化的方案選擇，輔助向量指令生成。2020 年，Pohl 等[99]分析程序的中間表示特征以及內存訪問特征，采用基于線性回歸技術的機器學習方法訓練評估模型。

在評估模型的應用方面，Trifunovic 等[63]設計性能代價評估模型，指導多層嵌套循環的相對最優向量化方案選擇，該模型結合了向量化因子、訪存步長寬度和對齊訪存等因素。類似地，張媛媛等[100]結合內存訪問的非連續和非對齊等因素，利用基于多面體指導循環變換的向量化代價模型，指導向量化分組方案。

自動向量化代價評估模型可從功能設計上進一步擴展。從性能評估模型的功能角度講，傳統編譯器的代價評估模型只指導最終是否進行向量化，其實代價評估模型還可以指導與向量化相關的程序變換方法。從代價評估模型自身考慮的因素角度講，傳統代價評估模型只考慮指令時延因素，其實處理器運行程序的性能與多方面因素有關系，如指令時延、訪存對齊等，如圖11 所示。如何考量多種影響性能的因素[12]，如何設計性能衡量權重，以及如何結合程序自身的邏輯特征設計快速精確的向量化評估模型都是值得進一步研究的。

圖11 改進自動向量化評估模型

6 自動向量化的展望

自動向量化領域還存在眾多的挑戰需要突破，基于近年來相關關鍵問題突破及暴露出來的不足之處，本節梳理出一些值得進一步關注和探索的研究問題。

6.1 保義分析和變換相關問題

1)一些程序的依賴關系比較復雜，只有在動態運行時才能夠確定。目前的研究工作主要是利用基于動靜態結合的多版本技術處理方法，但是這類方法額外增加了運行時判定代碼，當實際運行時存在較多依賴時，反而可能會降低程序性能。如何進一步減少動態運行時不必要的判定語句是值得進一步研究的問題。

2)當編譯器確定程序依賴關系時，可通過一些程序變換方法應用于向量化中，改變依賴關系，進而提高向量化的適用范圍。

6.2 分組分析和變換相關問題

程序尺寸越來越大，語句形式越來越復雜。有時一些語句同時存在多種向量化的分組方案。向量化分組直接決定能否實現向量化及是否有收益。

1)運算類型不同語句的向量化問題是近幾年出現的新問題，由于運算類型不同語句比運算類型相同語句在程序中的占比更高，若能對運算類型不同語句進行向量化，可有效提升程序的性能，因而該問題近幾年得到廣泛的關注。如何利用更多類型的等價表達式變換來對運算類型不同語句進行轉換以及多種變換如何進行選擇是未來值得研究的重要方向。對于上述研究問題，應用端到端的深度學習等[101]方法值得關注。

此外，編譯指令融合優化和強度消減優化也會影響運算排布，目前少有研究將這些優化與向量化進行有機綜合考慮，該問題是值得結合應用場景進一步深入研究的。

2)并行度選擇直接影響向量化的性能收益，目前的研究深入到指令級別的自適應并行度選擇，但僅采用基于遍歷搜索啟發式策略進行選擇。可引入組合優化方法進行并行度的選擇，例如，引入動態規劃、整數線性規劃等方法是值得深入探索的可能解決思路。

3)函數級向量化研究近幾年越來越得到研究者的關注，可取得任務級并行的效果[2]。然而，其受限于向量化分組方法、編譯過程間分析和別名分析。當函數運行路徑不一致時，很有可能其操作的數據類型長度也不一致，為了向量化這些操作，需要額外添加重組指令。如果能減少因為函數執行路徑不一致而引入的重組指令，則有利于提高向量化的收益，該問題有可能是引導打破函數執行路徑差異限制的向量化方法的研究方向。

4)自動向量化可描述為邏輯約束求解問題，因而可嘗試利用SMT 等理論方法解決向量化分組問題，同時結合向量化相關的限制因素，以加快求解速度，這方面的研究較少，值得嘗試。

6.3 處理器支持特性相關問題

自動向量化實質就是利用SIMD 擴展部件提供的運算并行和訪存并行特性提升程序性能。隨著處理器對SIMD 擴展部件支持能力的提高，出現了一些新的向量化方法。

1)處理器不僅支持基于SIMD 擴展的數據級并行，還支持基于多發射的指令級并行和基于多核多線程的任務級并行。目前向量化研究集中于發掘程序的數據級并行，可綜合考慮指令級并行和任務級并行，這樣更有助于充分利用處理器的多層次并行能力。

2)非規則內存訪問廣泛存在于科學計算領域和信號處理領域[78]。然而，對該類型程序的自動向量化研究并不充分。非規則內存訪問的隨機性和不確定性，給自動向量化的依賴、連續和對齊相關分析及變換增加了難度。如何克服上述困難，對該類型程序的自動向量化是值得研究的。

3)大部分處理器SIMD 擴展部件支持的并行長度有限，如能提高向量化的并行度，有助于提升程序性能。對于一些特定應用領域，并不需要高精度的計算，只需“夠用”就好，因此可適當減少數據類型長度，來提高程序的并行度。

4)如何充分利用功能日益豐富的SIMD 指令，給編譯器帶來新的挑戰。如 Intel 推出的AVX512 包含內存沖突檢測、擴展壓縮和掩膜操作指令等，利用這些指令有利于向量化更多類型程序。盡管目前很多編譯器已經支持這些新的指令，但是目前采用的方法大多是模板匹配法，并未深入分析程序特征、指令特性并與向量化有機結合起來，不具備通用性和可擴展性。如何改進向量化方法并利用這些指令提升向量化的能力是值得進一步研究的。

另外，指令集發展給向量化提供了更多選擇，如實現向量化非連續訪存，既可以通過連續內存訪問結合重組指令的方式優化，也可直接通過非連續的內存訪問指令優化。不同優化方案帶來的收益與具體的硬件平臺和程序特征都相關，如何選擇更優的指令生成方案是值得結合應用場景深入研究的。

6.4 性能評估分析相關問題

處理器技術快速發展有效提升了處理器的性能，如超標量和亂序執行等。傳統編譯器通過基于指令計數的評估方法早已不能準確評估處理器的性能。不精確的評估方法會嚴重影響編譯器程序變換的具體實施方法和收益。向量化性能與處理器的指令時延和執行單元等多方面因素都有關系，要精確評估比較困難，通過引入機器學習等新方法可能解決該問題。

7 結束語

自動向量化能夠利用SIMD 并行特性有效提升程序性能，受到越來越多的關注，眾多向量化技術先后被提出。本文針對自動向量化相關的文獻進行了系統整理，尤其對近些年的一些研究成果和技術突破進行了分析和總結。本文基于自動向量化問題的抽象描述識別出自動向量化領域4 個方面的關鍵問題，即保義分析和變換、分組分析和變換、處理器相關分析和變換以及性能評估分析，從以上4 個方面對研究成果和技術突破進行了全面分析和梳理，展望了該領域未來可能的研究方向，為該領域研究人員提供有益的參考。