馮競(jìng)舸，賀也平，3，陶秋銘

（1.中國科學(xué)院軟件研究所基礎(chǔ)軟件國家工程研究中心，北京 100190；2.中國科學(xué)院大學(xué)研究生院，北京 100049；3.中國科學(xué)院軟件研究所計(jì)算機(jī)科學(xué)國家重點(diǎn)實(shí)驗(yàn)室，北京 100090）

0 引言

芯片和基礎(chǔ)軟件的發(fā)展，不僅影響國家信息安全[1]，也影響產(chǎn)業(yè)供應(yīng)鏈安全。編譯器作為基礎(chǔ)軟件之一，對(duì)發(fā)揮芯片特性、提升程序性能至關(guān)重要，國內(nèi)越來越多的企業(yè)和科研機(jī)構(gòu)高度重視編譯技術(shù)研發(fā)，例如華為、阿里巴巴、騰訊、中國科學(xué)院、國防科學(xué)技術(shù)大學(xué)、清華大學(xué)、中國科學(xué)技術(shù)大學(xué)、上海交通大學(xué)、武漢大學(xué)，等等。

自動(dòng)向量化是一種重要的編譯優(yōu)化方法，它利用單指令流多數(shù)據(jù)流（SIMD，single-instruction stream multiple-data stream）系統(tǒng)擴(kuò)展部件[2]提供的數(shù)據(jù)并行處理能力，有效提升程序性能，在數(shù)字信號(hào)處理[3]、大數(shù)據(jù)[4]、人工智能[5]、高性能計(jì)算[6]等眾多應(yīng)用場(chǎng)景[7-10]中發(fā)揮著重要的作用。

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

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

近年來，大量的自動(dòng)向量化研究成果被公布。為了對(duì)該研究問題的進(jìn)展進(jìn)行系統(tǒng)梳理和歸納總結(jié)，本文搜集和分析了2011—2021 年關(guān)于自動(dòng)向量化的重要文獻(xiàn)。

早在2007 年，張為華等[20]針對(duì)自動(dòng)向量化的研究進(jìn)展進(jìn)行了綜述。2015 年，高偉等[2]也對(duì)相關(guān)研究進(jìn)行了成果綜述。2015 年以來，自動(dòng)向量化領(lǐng)域出現(xiàn)了一系列新的問題和研究成果，例如運(yùn)算類型語句的自動(dòng)向量化[21]（CGO2015），基于特殊SIMD 指令的自動(dòng)向量化[22]（ASPLOS 2021）等，以及新的解決方法，例如利用機(jī)器學(xué)習(xí)方法解決自動(dòng)向量化問題[23]（CGO2020），利用部分線性化技術(shù)解決分支判定語句的自動(dòng)向量化問題（PLDI2018）[24]等。本文旨在對(duì)近年的自動(dòng)向量化技術(shù)研究成果進(jìn)行更加全面的分析和歸納總結(jié)?；谀壳霸擃I(lǐng)域的研究現(xiàn)狀，展望了該領(lǐng)域的發(fā)展趨勢(shì)，總結(jié)了可能的研究方向，為未來的研究提供參考。

鑒于已有的綜述論文，本文對(duì)部分較早期的成果不做贅述，更聚焦于2015 年之后的研究成果。當(dāng)然由于個(gè)別類型的自動(dòng)向量化方法是基于早期研究成果（2015 年之前），為了完整性和便于讀者理解，本文對(duì)部分相關(guān)研究也會(huì)做適當(dāng)?shù)慕榻B和分析。

1 自動(dòng)向量化問題概述

1.1 自動(dòng)向量化問題抽象描述

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

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

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

3)自動(dòng)向量化目標(biāo)是提升程序運(yùn)行的性能。只有當(dāng)編譯器判定自動(dòng)向量化有收益時(shí)，才進(jìn)行向量化。

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

圖1 自動(dòng)向量化問題描述

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

圖2 自動(dòng)向量化示例

1.2 自動(dòng)向量化關(guān)鍵問題分類描述

基于自動(dòng)向量化問題的“語義可觀察等價(jià)性”和“性能有收益”等限制條件分析，自動(dòng)向量化的關(guān)鍵問題可分類歸納為以下4 個(gè)方面。

1)自動(dòng)向量化與編譯器的保義分析和變換能力相關(guān)，保義分析和變換能力越強(qiáng)，向量化的適用范圍越大。向量化從程序執(zhí)行順序角度講，本質(zhì)上是將原始串行程序轉(zhuǎn)換為局部并行程序，在同一SIMD 向量指令中運(yùn)行的操作不能有依賴關(guān)系，否則將改變?cè)汲绦蛘Z義。面向向量化的保義分析的核心是依賴關(guān)系分析。依賴關(guān)系分析與別名關(guān)系分析緊密相關(guān)，別名關(guān)系分析能力的不足有時(shí)會(huì)阻礙依賴關(guān)系的判定。

2)自動(dòng)向量化與其自身的分組方法有關(guān)。將多個(gè)標(biāo)量數(shù)據(jù)轉(zhuǎn)為一個(gè)向量數(shù)據(jù)的過程稱為分組。分組直接影響向量化的收益。根據(jù)程序分析粒度，向量化分組分析和變換問題可分為基本塊級(jí)、循環(huán)級(jí)、函數(shù)級(jí)[2]和混合級(jí)向量化分組問題。基本塊級(jí)分組問題旨在尋找基本塊內(nèi)向量化分組，循環(huán)級(jí)分組問題旨在尋找包含循環(huán)的程序中迭代間語句分組，函數(shù)級(jí)分組問題旨在尋找不同函數(shù)之間的語句分組，混合級(jí)分組問題是前面3 種分組方式的擴(kuò)展及融合問題。

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

4)向量化與性能評(píng)估分析相關(guān)。性能評(píng)估最終決定編譯器是否進(jìn)行向量化。性能與處理器支持的指令時(shí)延、訪存模型和寄存器相關(guān)特性緊密相關(guān)。設(shè)計(jì)精確的向量化代價(jià)評(píng)估模型，能夠有效指導(dǎo)向量化的程序變換，并減少因不恰當(dāng)?shù)某绦蜃儞Q導(dǎo)致程序性能下降的情形。圖3 展示了自動(dòng)向量化流程與上述4 個(gè)關(guān)鍵問題的關(guān)系。

圖3 自動(dòng)向量化流程

根據(jù)上述分析，向量化問題可歸納為4 類：保義分析和變換問題、分組分析和變換問題、處理器相關(guān)分析和變換問題以及性能評(píng)估分析問題。本文從這4 個(gè)角度，對(duì)近幾年自動(dòng)向量化的研究成果進(jìn)行分析和總結(jié)。

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

保義分析和變換是編譯優(yōu)化的基礎(chǔ)和前提。幾乎所有的編譯器優(yōu)化方法都涉及保義分析和變換問題。本文只關(guān)注自動(dòng)向量化的保義分析和變換問題。目前面向自動(dòng)向量化的保義分析和變換的研究集中于依賴和別名的分析和變換。

2.1 依賴分析和變換

2.1.1 數(shù)據(jù)依賴分析和變換

數(shù)據(jù)的訪問和重用常引入數(shù)據(jù)依賴，如圖4 所示，當(dāng)兩條語句訪問相同的存儲(chǔ)單元，且其中有一個(gè)寫數(shù)據(jù)，則發(fā)生數(shù)據(jù)依賴。

圖4 數(shù)據(jù)依賴說明

近幾年對(duì)于數(shù)據(jù)依賴分析，學(xué)術(shù)界有三方面的主要突破。在研究對(duì)象方面，從原始的簡(jiǎn)單依賴關(guān)系的判定，逐漸轉(zhuǎn)向多層嵌套復(fù)雜依賴關(guān)系的判定；在理論方法方面，從傳統(tǒng)靜態(tài)分析方法，轉(zhuǎn)向動(dòng)態(tài)投機(jī)執(zhí)行的方法，從軟件表達(dá)式等價(jià)變換的方法，轉(zhuǎn)向基于特殊硬件處理的方法；在分析和轉(zhuǎn)換流程方面，從傳統(tǒng)的“分析-判定”流程模式，轉(zhuǎn)向“分析-轉(zhuǎn)換-判定”迭代模式。

起初，向量化主要采用編譯器中通用的依賴分析和變換方法，例如GCD 測(cè)試[28]和Banerjee 測(cè)試[29]等，這些方法沒有考慮SIMD 的特點(diǎn)，如SIMD 擴(kuò)展部件的并行長(zhǎng)度有限，在循環(huán)中，當(dāng)操作的依賴距離大于其并行長(zhǎng)度時(shí)，把這些操作存放到SIMD 寄存器中，不改變?cè)汲绦蛘Z義。Buli? 等[30]基于Banerjee 方法將SIMD 擴(kuò)展部件并行長(zhǎng)度信息應(yīng)用于依賴測(cè)試中，擴(kuò)展面向向量化的依賴測(cè)試識(shí)別范圍，有效解決在循環(huán)中依賴距離大于SIMD 并行化長(zhǎng)度的數(shù)據(jù)依賴分析問題。

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

當(dāng)編譯器判定存在阻礙向量化的依賴時(shí)，傳統(tǒng)的向量化方法不進(jìn)行程序轉(zhuǎn)換。然而，有的數(shù)據(jù)依賴關(guān)系可通過程序變換改變，從而使向量化成為可能。2017 年，趙捷等[33]根據(jù)SIMD 特征及等價(jià)變換關(guān)系式，提出并論證了7 個(gè)依賴分析及轉(zhuǎn)換的定理，為利用等價(jià)關(guān)系式解除依賴奠定理論基礎(chǔ)，并基于數(shù)組依賴圖構(gòu)建包含數(shù)組和語句依賴信息的有向圖，在此基礎(chǔ)上，利用語句重排和節(jié)點(diǎn)分裂等技術(shù)在數(shù)組依賴圖中改變程序中阻礙向量化的依賴關(guān)系，增強(qiáng)了向量化能力。

2.1.2 控制依賴分析和變換

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

圖5 控制依賴說明

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

Smith 等[34]將控制依賴轉(zhuǎn)換成數(shù)據(jù)依賴（If-conversion），然后利用傳統(tǒng)向量化方法處理[35]?；贗f-conversion 的向量化方法示例如圖6 所示，圖6(a)是原始程序，圖6(b)是通過If-conversion并利用選擇指令（select）實(shí)現(xiàn)對(duì)控制流程序的向量化。

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

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

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

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

2.2 別名分析和變換

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

圖7 別名分析示例程序

針對(duì)別名分析，近幾年學(xué)術(shù)界逐漸從研究傳統(tǒng)的靜態(tài)的別名分析法轉(zhuǎn)為動(dòng)靜態(tài)結(jié)合的分析方法。如侯永生[43]利用動(dòng)靜態(tài)結(jié)合的方法，解決別名和非線性表達(dá)式的動(dòng)態(tài)檢測(cè)條件構(gòu)建問題，該方法插入動(dòng)態(tài)監(jiān)測(cè)代碼，運(yùn)行時(shí)判定是否進(jìn)行向量化。類似地，2015 年，劉鵬等[44]通過動(dòng)態(tài)插樁和試運(yùn)行提取指針別名信息，并反饋到向量化階段指導(dǎo)向量化代碼生成。

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

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

自動(dòng)向量化分組策略直接影響能否向量化及其收益[46]。近幾年對(duì)于分組問題，在研究對(duì)象方面，從原始單一形式的分組方法研究，逐漸轉(zhuǎn)向多級(jí)融合的分組方法研究；在程序信息分析粒度方面，從先前單一基本塊或循環(huán)特征信息分析，轉(zhuǎn)向跨基本塊以及多層嵌套循環(huán)的特征分析；在理論方法方面，從先前的啟發(fā)式貪心方法轉(zhuǎn)向更加高級(jí)的組合優(yōu)化方法，如人工智能、動(dòng)態(tài)規(guī)劃和整數(shù)線性規(guī)劃，等等。

3.1 基本塊級(jí)分組問題及方法

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

圖8 分組轉(zhuǎn)換示例

學(xué)術(shù)界對(duì)SLP 進(jìn)一步展開研究，提出了許多新的改進(jìn)方法，其分組策略主要包括局部貪心和全局的分組策略。貪心策略和全局策略互有優(yōu)劣。貪心策略編譯速度快，但分析信息較局部，無法有效向量化不規(guī)則的內(nèi)存訪問。全局策略分析信息較全局，能夠向量化不規(guī)則的內(nèi)存訪問，但編譯時(shí)間較長(zhǎng)。

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

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

3.2 循環(huán)級(jí)分組問題及方法

循環(huán)級(jí)向量化分組旨在尋找循環(huán)中迭代間的向量化并行。Allen 等[59]首次提出基于循環(huán)的（Loop-based）自動(dòng)向量化方法，如圖9 所示。Loop-based 自動(dòng)向量化方法針對(duì)內(nèi)層循環(huán)的迭代空間，將整個(gè)數(shù)組作為一個(gè)向量單元進(jìn)行操作，基于依賴關(guān)系分析將在不同迭代間且相互間不會(huì)形成依賴環(huán)的多條語句轉(zhuǎn)換為向量形式。

圖9 Loop-based 自動(dòng)向量化方法示例

學(xué)術(shù)界在Loop-based 方法的基礎(chǔ)上進(jìn)一步改進(jìn)優(yōu)化，集中于外層循環(huán)向量化及多層嵌套循環(huán)向量化。其中大多數(shù)研究集中于多層嵌套循環(huán)向量化。

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

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

3.3 函數(shù)級(jí)分組問題及方法

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

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

3.4 多級(jí)向量化分組擴(kuò)展及融合

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

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

4 處理器相關(guān)分析和變換問題及方法

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

表1 支持帶有SIMD 擴(kuò)展部件的處理器

表2 Intel SIMD 擴(kuò)展部件的指令集統(tǒng)計(jì)

SIMD 擴(kuò)展部件的發(fā)展推動(dòng)著向量化方法的不斷改進(jìn)。1)向量寄存器長(zhǎng)度的增長(zhǎng)增加了向量化的并行度。2)SIMD 擴(kuò)展部件功能越來越豐富，使編譯器能夠向量化更多的程序。例如，AVX512 指令集的沖突探測(cè)指令有助于編譯器實(shí)現(xiàn)對(duì)包含間接數(shù)組訪問程序的自動(dòng)向量化。

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

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

2)在訪存并行特性支持方面，大部分處理器只支持連續(xù)向量?jī)?nèi)存訪問指令，或者盡管支持非連續(xù)內(nèi)存訪問指令，但指令時(shí)延較大。大部分處理器只支持對(duì)齊訪問指令，或者盡管支持非對(duì)齊訪問指令，但指令時(shí)延較大。

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

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

4.1 運(yùn)算相關(guān)分析和變換問題及方法

如前文所述，編譯器不能直接使用SIMD 擴(kuò)展部件支持的指令實(shí)現(xiàn)對(duì)運(yùn)算類型不相同程序向量化。然而，現(xiàn)實(shí)中存在大量包含不相同類型運(yùn)算的程序，且有些實(shí)際上運(yùn)算類型相同的程序語句在編譯過程中由于某些標(biāo)量?jī)?yōu)化（如常量折疊和強(qiáng)度削弱[75]等）的實(shí)施，會(huì)被轉(zhuǎn)換為運(yùn)算類型不同的程序，這類情形廣泛存在于SPEC CPU 測(cè)試程序中。如果能夠?qū)@類程序?qū)崿F(xiàn)自動(dòng)向量化，可有效提升這些程序的性能。

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

1)基于硬件特殊指令的方法。其主要利用SIMD 特殊指令實(shí)現(xiàn)運(yùn)算類型不同語句的向量化，例如，PSLP 方法[21]將運(yùn)算類型不同的語句中差異的部分相互參照并分別通過添加選擇指令進(jìn)行擴(kuò)充，從而將運(yùn)算類型不同的語句轉(zhuǎn)換成運(yùn)算類型相同的形式；VeGen 方法[22]實(shí)現(xiàn)了一個(gè)編譯框架，利用Non-SIMD 指令實(shí)現(xiàn)對(duì)運(yùn)算類型不同語句的向量化?；谟布厥庵噶畹姆椒ㄒ话銜?huì)受到處理器平臺(tái)的限制，且會(huì)引入額外的運(yùn)行代價(jià)。

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

4.2 訪存相關(guān)分析和變換問題及方法

訪存并行特性主要包括連續(xù)和對(duì)齊2 個(gè)方面，下面分別介紹相關(guān)問題及方法。

4.2.1 連續(xù)訪存相關(guān)分析和變換問題及方法

非連續(xù)內(nèi)存訪問在程序中大量存在，例如間接數(shù)組[77]和結(jié)構(gòu)體等。對(duì)于非連續(xù)內(nèi)存訪問的向量化，學(xué)術(shù)界有了新的突破。在分析方法方面，從傳統(tǒng)的靜態(tài)分析方法，擴(kuò)展到基于動(dòng)態(tài)投機(jī)執(zhí)行的方法、基于特殊硬件指令的方法以及針對(duì)特定類型程序的訪存排布方法；在研究對(duì)象方面，從傳統(tǒng)的固定步長(zhǎng)的非連續(xù)內(nèi)存訪問的向量化研究，擴(kuò)展到不固定步長(zhǎng)[78]的非規(guī)則連續(xù)內(nèi)存訪問的向量化研究。

在訪存信息的分析方面，在編譯器中對(duì)于連續(xù)內(nèi)存訪問的判定主要基于連續(xù)內(nèi)存訪問定義的靜態(tài)分析法。單純通過靜態(tài)分析法有時(shí)難以判定訪存是否連續(xù)，有研究者利用動(dòng)靜分析結(jié)合的方法解決該問題，例如，姚遠(yuǎn)[79]記錄指針引用信息，進(jìn)而確定指針引用對(duì)齊和連續(xù)信息，根據(jù)循環(huán)迭代信息推出運(yùn)行時(shí)指針地址信息判斷對(duì)齊和連續(xù)性信息指導(dǎo)自動(dòng)向量化，該方法利用動(dòng)態(tài)運(yùn)行時(shí)信息指導(dǎo)對(duì)齊和連續(xù)訪存指令生成，減少了非對(duì)齊和非連續(xù)內(nèi)存訪問。

在分析對(duì)象方面，近期研究集中于規(guī)則步長(zhǎng)的內(nèi)存訪問、結(jié)構(gòu)體、間接數(shù)組和非規(guī)則內(nèi)存訪問方面的向量化研究。

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

圖10 交錯(cuò)和提取操作

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

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

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

4.2.2 對(duì)齊訪存相關(guān)分析和變換問題及方法

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

4.3 并行度相關(guān)分析和變換問題及方法

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

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

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

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

5 性能評(píng)估分析問題及方法

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

近幾年，關(guān)于向量化性能評(píng)估分析問題，學(xué)術(shù)界出現(xiàn)了較多新的方法，從傳統(tǒng)的基于指令計(jì)數(shù)的評(píng)估方法，轉(zhuǎn)向基于人工智能的方法。在評(píng)估模式使用方面，從傳統(tǒng)的應(yīng)用于判定是否向量化，轉(zhuǎn)向利用評(píng)估模型指導(dǎo)面向向量化相關(guān)的程序變換。

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

在評(píng)估模型的應(yīng)用方面，Trifunovic 等[63]設(shè)計(jì)性能代價(jià)評(píng)估模型，指導(dǎo)多層嵌套循環(huán)的相對(duì)最優(yōu)向量化方案選擇，該模型結(jié)合了向量化因子、訪存步長(zhǎng)寬度和對(duì)齊訪存等因素。類似地，張媛媛等[100]結(jié)合內(nèi)存訪問的非連續(xù)和非對(duì)齊等因素，利用基于多面體指導(dǎo)循環(huán)變換的向量化代價(jià)模型，指導(dǎo)向量化分組方案。

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

圖11 改進(jìn)自動(dòng)向量化評(píng)估模型

6 自動(dòng)向量化的展望

自動(dòng)向量化領(lǐng)域還存在眾多的挑戰(zhàn)需要突破，基于近年來相關(guān)關(guān)鍵問題突破及暴露出來的不足之處，本節(jié)梳理出一些值得進(jìn)一步關(guān)注和探索的研究問題。

6.1 保義分析和變換相關(guān)問題

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

2)當(dāng)編譯器確定程序依賴關(guān)系時(shí)，可通過一些程序變換方法應(yīng)用于向量化中，改變依賴關(guān)系，進(jìn)而提高向量化的適用范圍。

6.2 分組分析和變換相關(guān)問題

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

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

此外，編譯指令融合優(yōu)化和強(qiáng)度消減優(yōu)化也會(huì)影響運(yùn)算排布，目前少有研究將這些優(yōu)化與向量化進(jìn)行有機(jī)綜合考慮，該問題是值得結(jié)合應(yīng)用場(chǎng)景進(jìn)一步深入研究的。

2)并行度選擇直接影響向量化的性能收益，目前的研究深入到指令級(jí)別的自適應(yīng)并行度選擇，但僅采用基于遍歷搜索啟發(fā)式策略進(jìn)行選擇。可引入組合優(yōu)化方法進(jìn)行并行度的選擇，例如，引入動(dòng)態(tài)規(guī)劃、整數(shù)線性規(guī)劃等方法是值得深入探索的可能解決思路。

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

4)自動(dòng)向量化可描述為邏輯約束求解問題，因而可嘗試?yán)肧MT 等理論方法解決向量化分組問題，同時(shí)結(jié)合向量化相關(guān)的限制因素，以加快求解速度，這方面的研究較少，值得嘗試。

6.3 處理器支持特性相關(guān)問題

自動(dòng)向量化實(shí)質(zhì)就是利用SIMD 擴(kuò)展部件提供的運(yùn)算并行和訪存并行特性提升程序性能。隨著處理器對(duì)SIMD 擴(kuò)展部件支持能力的提高，出現(xiàn)了一些新的向量化方法。

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

2)非規(guī)則內(nèi)存訪問廣泛存在于科學(xué)計(jì)算領(lǐng)域和信號(hào)處理領(lǐng)域[78]。然而，對(duì)該類型程序的自動(dòng)向量化研究并不充分。非規(guī)則內(nèi)存訪問的隨機(jī)性和不確定性，給自動(dòng)向量化的依賴、連續(xù)和對(duì)齊相關(guān)分析及變換增加了難度。如何克服上述困難，對(duì)該類型程序的自動(dòng)向量化是值得研究的。

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

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

另外，指令集發(fā)展給向量化提供了更多選擇，如實(shí)現(xiàn)向量化非連續(xù)訪存，既可以通過連續(xù)內(nèi)存訪問結(jié)合重組指令的方式優(yōu)化，也可直接通過非連續(xù)的內(nèi)存訪問指令優(yōu)化。不同優(yōu)化方案帶來的收益與具體的硬件平臺(tái)和程序特征都相關(guān)，如何選擇更優(yōu)的指令生成方案是值得結(jié)合應(yīng)用場(chǎng)景深入研究的。

6.4 性能評(píng)估分析相關(guān)問題

處理器技術(shù)快速發(fā)展有效提升了處理器的性能，如超標(biāo)量和亂序執(zhí)行等。傳統(tǒng)編譯器通過基于指令計(jì)數(shù)的評(píng)估方法早已不能準(zhǔn)確評(píng)估處理器的性能。不精確的評(píng)估方法會(huì)嚴(yán)重影響編譯器程序變換的具體實(shí)施方法和收益。向量化性能與處理器的指令時(shí)延和執(zhí)行單元等多方面因素都有關(guān)系，要精確評(píng)估比較困難，通過引入機(jī)器學(xué)習(xí)等新方法可能解決該問題。

7 結(jié)束語

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