李嘉楠，韓 林，柴赟達(dá)

（1.鄭州大學(xué)信息工程學(xué)院，鄭州 450000；2.國(guó)家超級(jí)計(jì)算鄭州中心，鄭州 450000）

0 概述

高性能計(jì)算可用于開發(fā)解決全球性問題的科學(xué)應(yīng)用程序，如疫苗研制、氣候建模等。如今，提高處理器的性能變得越來越重要，而電子器件的更新已不能滿足日益增長(zhǎng)的計(jì)算需求，在此情況下，微型的向量并行部件SIMD（Single Instruction Multiple Data）擴(kuò)展得到迅速發(fā)展，并被廣泛應(yīng)用于各種科學(xué)計(jì)算類程序的加速優(yōu)化任務(wù)。

基于SIMD 擴(kuò)展部件的向量化已成為程序并行的重要手段，其向量寄存器和SIMD 指令是程序員以及處理器廠商的研究重點(diǎn)［1］。目前，ICC、GCC、LLVM（Low Level Virtual Machine）等編譯器已相繼支持了SIMD 的自動(dòng)向量化編譯，面向SIMD 擴(kuò)展部件的自動(dòng)向量化編譯已逐漸成為程序向量化變換的主要方式。

LLVM 是對(duì)任意編程語言提供一種基于SSA（Static Single Assignment）［2］的靜態(tài)與動(dòng)態(tài)編譯的現(xiàn)代編譯技術(shù)，與其他主流編譯器相比，LLVM 具有如下優(yōu)勢(shì)：統(tǒng)一的IR（Intermediate Representation）與模塊化［3］，能夠以庫的形式抽取其組件并用于其他領(lǐng)域；編譯器中的優(yōu)化和分析被組織成遍（Pass）結(jié)構(gòu)，通過不同遍完成不同的優(yōu)化算法［4］；開源License 的優(yōu)勢(shì)使其被各大公司廣泛采用。在LLVM 編譯器中，已實(shí)現(xiàn)了循環(huán)級(jí)與基本塊級(jí)的自動(dòng)向量化方法［5］。

申威系列處理器是我國(guó)自主研發(fā)、面向高性能計(jì)算的通用微處理器，該處理器主要針對(duì)計(jì)算密集型程序，如科學(xué)計(jì)算、數(shù)字信號(hào)分析、多媒體處理等。申威系列處理器包含豐富的向量運(yùn)算指令和完善的向量重組指令，為程序的向量化提供了良好的硬件基礎(chǔ)。

LLVM 編譯器中自動(dòng)向量化部分主要由Intel 團(tuán)隊(duì)開發(fā)推進(jìn)，算法以及向量指令的應(yīng)用更適用于X86 平臺(tái)［6］。目前，LLVM 編譯器還未支持面向國(guó)產(chǎn)平臺(tái)的自動(dòng)向量化。由于指令集的差別，申威處理器與X86 處理器的自動(dòng)向量化實(shí)現(xiàn)方法有所不同，如AVX 指令集兼容256 位與128 位的向量長(zhǎng)度，而國(guó)產(chǎn)處理器一般只支持單一的向量長(zhǎng)度，導(dǎo)致向量化后生成不支持的向量類型，從而產(chǎn)生段錯(cuò)誤、結(jié)果錯(cuò)誤等問題。

本文針對(duì)申威1621 處理器平臺(tái)進(jìn)行自動(dòng)向量化移植研究，從循環(huán)級(jí)與基本塊級(jí)2 個(gè)方面提高自動(dòng)向量化適配能力，以完善向量化所需的指令代價(jià)信息，并在精準(zhǔn)代價(jià)模型的指導(dǎo)下生成后端支持的向量指令。同時(shí)，針對(duì)循環(huán)級(jí)向量化中控制流向量化進(jìn)行算法改進(jìn)，以解決后端不支持掩碼訪存指令的問題。

1 LLVM 自動(dòng)向量化框架

1.1 循環(huán)級(jí)向量化

循環(huán)級(jí)向量化主要是在迭代間尋找并行機(jī)會(huì)以進(jìn)行向量化，其主要流程如圖1 所示。

圖1 循環(huán)級(jí)向量化流程Fig.1 Procedure of cyclic vectorization

合法性分析步驟為：首先檢查是否為嵌套循環(huán)，排除不能向量化的循環(huán)形式，如多出口多回邊結(jié)構(gòu)；然后對(duì)包含控制流的循環(huán)進(jìn)行分析，收集分支掩碼以用于后續(xù)向量代碼生成［7］；接著對(duì)phi 指令以及調(diào)用指令進(jìn)行分析，判斷其是否符合向量化格式要求；最后調(diào)用循環(huán)訪存信息，分析訪存指令是否具有阻止向量化的依賴關(guān)系。依賴分析就是根據(jù)循環(huán)內(nèi)的數(shù)據(jù)依賴關(guān)系構(gòu)造語句依賴圖，在語句依賴圖上求解強(qiáng)連通分量，不具有強(qiáng)連通分量的語句就是可以進(jìn)行向量執(zhí)行的語句［8-9］。

通過調(diào)用代價(jià)模型，首先對(duì)基本塊中訪存指令進(jìn)行分析，連續(xù)訪存可直接獲取指令代價(jià)，非連續(xù)訪存需要對(duì)比不同策略下的收益，選出訪存指令向量化的最佳執(zhí)行方案［10-11］；然后將該指令與基本塊內(nèi)其他指令一起，以2 的整數(shù)冪在［2，IMaxVF］范圍內(nèi)進(jìn)行收益比較；最終將其與標(biāo)量代價(jià)進(jìn)行對(duì)比，選出最優(yōu)的向量化因子。

向量代碼生成是在原始標(biāo)量循環(huán)結(jié)構(gòu)之前創(chuàng)建一個(gè)新的循環(huán)，使其成為向量指令的載體。標(biāo)量循環(huán)中不同類型的指令分別調(diào)用不同的轉(zhuǎn)換函數(shù)以進(jìn)行向量指令生成，最后將生成的向量指令逐一添加到新的循環(huán)中，更新支配關(guān)系，原始的標(biāo)量循環(huán)將作為新向量循環(huán)的“標(biāo)量尾循環(huán)”處理［12］。

1.2 基本塊級(jí)向量化

緊跟在循環(huán)級(jí)向量化后的是基本塊級(jí)向量化，其主要在基本塊內(nèi)尋找同構(gòu)語句以發(fā)掘并行機(jī)會(huì)?；緣K級(jí)向量化流程如圖2 所示。

圖2 基本塊級(jí)向量化流程Fig.2 Procedure of basic-block level vectorization

在基本塊級(jí)向量化中，首先找到函數(shù)中所有的內(nèi)存引用，收集指令并進(jìn)行打包［13］，包是一個(gè)同構(gòu)語句的集合，將多個(gè)同構(gòu)語句組成包的過程稱作打包，相反則稱為拆包［14］；然后SLP 利用相鄰地址的存儲(chǔ)指令作為種子進(jìn)行打包，通過“定義-使用鏈”和“使用-定義鏈”啟發(fā)式地?cái)U(kuò)展包［15］，若循環(huán)中的每一個(gè)操作都可以被目標(biāo)平臺(tái)以向量形式支持，則進(jìn)行語法樹的代價(jià)分析，在有收益的情況下構(gòu)建向量化樹，從上到下掃描基本塊的所有語句，在需要向量化的標(biāo)量語句前插入向量語句，以完成向量代碼生成［16］；最后移至下一組指令重復(fù)以上分析，直至完成基本塊內(nèi)所有指令的向量發(fā)掘。

2 自動(dòng)向量化移植

近年來，作為編譯優(yōu)化領(lǐng)域的研究熱點(diǎn)，SIMD擴(kuò)展部件不斷發(fā)展。申威系列處理器的SIMD 向量長(zhǎng)度在持續(xù)增長(zhǎng)，指令集功能也越來越豐富，因此，需要針對(duì)每一種處理器實(shí)現(xiàn)其自動(dòng)向量化功能移植。移植主要包含自動(dòng)向量化優(yōu)化遍、后端相關(guān)轉(zhuǎn)換信息2 個(gè)方面。自動(dòng)向量化可分為識(shí)別、優(yōu)化、指令生成3 個(gè)部分。識(shí)別方法在循環(huán)級(jí)向量化與基本塊級(jí)向量化中通用，最重要的是考慮SIMD 部件差異與指令集特征，其中，寄存器信息、跨幅因子、基本指令代價(jià)的精確描述是自動(dòng)向量化的基礎(chǔ)條件。另外，本文提出一種掩碼指令轉(zhuǎn)換方法，使得申威平臺(tái)支持包含控制流結(jié)構(gòu)的向量化。

2.1 寄存器信息

完善SIMD 向量化的寄存器基礎(chǔ)信息包含RegisterInfo 文件中向量寄存器數(shù)量、特征信息以及TargetTransformInfo 文件中寄存器寬度描述，必要時(shí)數(shù)據(jù)類型長(zhǎng)度也需要根據(jù)指令集信息進(jìn)行修改［17］，否則會(huì)生成后端不支持的向量長(zhǎng)度或向量類型，增加后端指令降級(jí)工作從而導(dǎo)致向量代碼生成效率降低。

2.2 跨幅因子

跨幅因子即循環(huán)級(jí)向量化中的“Interleave Count”，為基本塊中單條語句的展開數(shù)，默認(rèn)值為1。結(jié)合向量指令特征，將TargetTransformInfo 中最大跨幅因子設(shè)置為4，向量化階段調(diào)用代價(jià)模型從［1，4］范圍內(nèi)分析出最佳跨幅因子，與原始默認(rèn)值1 相比，提升了向量化性能。以TSVC（Test Suit for Vectorizing Compilers）測(cè)試集中的vpvts 函數(shù)為例，移植后進(jìn)行收益分析，選擇出最佳跨幅因子為4，以此進(jìn)行向量代碼的局部展開，相比原始向量化其性能提升了70%。

2.3 基本指令延遲信息

基本指令包含邏輯運(yùn)算指令、類型轉(zhuǎn)換指令、比較指令、內(nèi)建函數(shù)指令、訪存指令等。根據(jù)硬件提供的指令延遲表，在后端TargetTransformInfo 文件中對(duì)指令代價(jià)進(jìn)行精確描述，包含數(shù)據(jù)類型、操作碼識(shí)別、指令延遲數(shù)補(bǔ)充。將后端不支持的向量指令代價(jià)調(diào)高，防止向量化后產(chǎn)生倒加速問題。對(duì)于復(fù)雜指令如混洗指令，結(jié)合后端指令降級(jí)中自定義的指令拆分組合情況進(jìn)行精確描述。

X86 平臺(tái)支持128 位的向量寄存器［18］，在自動(dòng)向量化中最小向量化因子限制為2，但這在申威平臺(tái)不適用，原因是會(huì)造成數(shù)據(jù)處理過程中讀取錯(cuò)誤信息，在程序運(yùn)行時(shí)引發(fā)段錯(cuò)誤?；谏鲜鲈?，本文分別在循環(huán)級(jí)向量化與基本塊級(jí)向量化中修改最小向量化因子。

2.4 掩碼內(nèi)建指令

掩碼內(nèi)建函數(shù)是對(duì)LLVM 基本指令集的補(bǔ)充，由特定目標(biāo)平臺(tái)的特殊指令組合而成，但并不是所有目標(biāo)架構(gòu)指令集都具備全面的掩碼指令［18-19］。在申威平臺(tái)下進(jìn)行SIMD 編譯時(shí)，自動(dòng)向量化并不支持掩碼訪存指令，導(dǎo)致大量包含控制流的循環(huán)錯(cuò)失向量化機(jī)會(huì)。在循環(huán)級(jí)向量化時(shí)將掩碼訪存指令替換為select 向量指令，可解決目標(biāo)平臺(tái)不支持掩碼訪存指令的問題，核心轉(zhuǎn)換算法描述如算法1 所示。

算法1掩碼指令轉(zhuǎn)換算法

3 收益評(píng)估模型

循環(huán)或函數(shù)被向量化后的基本收益就是基本塊中減少的指令周期數(shù)，收益評(píng)估用于衡量向量化是否有利于提高程序效率［7］。自動(dòng)向量化移植使得收益評(píng)估更加精準(zhǔn)與完善，可以在收益評(píng)估的指導(dǎo)下判斷是否需要進(jìn)行向量化以及如何進(jìn)行向量化，從而生成最符合申威后端需求的向量或標(biāo)量代碼。

3.1 面向循環(huán)級(jí)向量化的收益評(píng)估

循環(huán)級(jí)向量化收益分析流程如圖3 所示。

圖3 循環(huán)級(jí)向量化收益分析流程Fig.3 Procedure of cost analysis in cyclic vectorization

收益分析主要集中在2 個(gè)部分：針對(duì)訪存指令的最佳加寬決策；針對(duì)循環(huán)基本塊的最佳向量化因子選擇。具體步驟如下：

1）計(jì)算可行的最大向量化因子IMaxVF，獲取后端向量寄存器長(zhǎng)度DWidthRegister以及數(shù)據(jù)寬度DWidthType信息，對(duì)于只支持單一向量長(zhǎng)度的后端：

2）訪存指令對(duì)程序的向量化或性能提升起決定性作用，對(duì)于訪存指令，循環(huán)級(jí)向量化具有專屬的決策分析以求得最大收益。對(duì)于連續(xù)訪存代價(jià)，直接從后端指令延遲表獲取；對(duì)于不連續(xù)訪存，比較跨幅訪存、聚合訪存、標(biāo)量化訪存3 種方案下的收益以選取最佳方案進(jìn)行執(zhí)行。

額外代價(jià)來源于從<8 x i32>向量中的0、2、4、6 位抽取數(shù)據(jù)并插入到<4 x i32>向量過程中的插入抽取指令，設(shè)GGroupNums為跨幅訪存組指令數(shù)量，其額外代價(jià)為：

跨幅store 指令是從子向量中提取所有元素，并將它們插入到目的向量中，例如：

額外代價(jià)來源于從2 個(gè)<4 x i32>向量中抽取8 個(gè)元素插入到<8 x i32>向量過程中的插入抽取指令代價(jià)，設(shè)跨步為SSteps，其額外代價(jià)為：

（3）標(biāo)量化訪存代價(jià)首先獲取標(biāo)量存儲(chǔ)指令和地址計(jì)算：

包含控制流的循環(huán)屬于不連續(xù)訪存，掩碼指令轉(zhuǎn)換算法將包含控制流的循環(huán)進(jìn)行select 指令轉(zhuǎn)換，改變包含控制流訪存收益分析的計(jì)算方式，如下：

在更新包含控制流的代價(jià)計(jì)算后，根據(jù)基本塊執(zhí)行的概率來擴(kuò)展代價(jià)［20］，循環(huán)級(jí)向量化認(rèn)為每個(gè)基本塊執(zhí)行的概率均為50%，因此，分支基本塊的代價(jià)為CCost=CCost/2。

3）將循環(huán)中所有指令進(jìn)行累加，對(duì)比以上3 種不連續(xù)訪存的收益，選擇最優(yōu)收益方案進(jìn)行下一步向量因子的收益分析。

最后對(duì)比標(biāo)量與向量形式下的收益，選擇進(jìn)行向量代碼生成或保持原有的標(biāo)量執(zhí)行。

3.2 面向基本塊級(jí)向量化的收益評(píng)估

SLP 向量化收益開銷計(jì)算算法以抽象語法樹為基礎(chǔ)，滿足E≥VVF條件后以存儲(chǔ)指令為根節(jié)點(diǎn)遍歷樹形結(jié)構(gòu)，通過“使用-定義鏈”自下而上進(jìn)行打包，其中，每個(gè)節(jié)點(diǎn)都包含可并行處理且數(shù)目相同的同構(gòu)語句［21-22］。

代價(jià)模型獲取寄存器信息計(jì)算向量化所需的同構(gòu)語句數(shù)，根據(jù)指令代價(jià)選擇收益最大的進(jìn)行向量化。首先確定同構(gòu)語句長(zhǎng)度（即同構(gòu)語句數(shù)量）與向量化因子：設(shè)同構(gòu)語句長(zhǎng)度為E，向量化因子為VVF（設(shè)向量寄存器長(zhǎng)度為256 位，標(biāo)量元素double 為64 bit，則向量化因子VVF等于4）。假設(shè)標(biāo)量指令代價(jià)為Si，向量指令代價(jià)為VCost，則每條向量指令的收益為：

該基本塊向量的收益總和為：

考慮寄存器溢出與指令重組對(duì)向量化性能存在影響，因此，自底向上遍歷語法樹以計(jì)算額外開銷，其值在理想狀態(tài)下為0，則總體收益為：

另外一些計(jì)算如標(biāo)量的規(guī)約計(jì)算、向量化指針指令的索引計(jì)算，沒有被基于同構(gòu)store 組的自底向上的遍歷過程所捕獲，因?yàn)樗鼈儾话@樣的存儲(chǔ)指令，此類收益分析需考慮插入/抽取指令以及索引信息的代價(jià)（從后端相關(guān)指令延遲表中獲取，默認(rèn)值為0），則總體收益為：

4 測(cè)試分析

本文采用申威1621 處理器為測(cè)試平臺(tái)，進(jìn)行LLVM 編譯器自動(dòng)向量化移植功能測(cè)試，編譯器版本為7.0。分別采用SPEC2006 與TSVC 測(cè)試集以及向量化應(yīng)用測(cè)試，從正確性與向量化性能2 個(gè)方面進(jìn)行對(duì)比分析。

4.1 功能測(cè)試與分析

SPEC2006 標(biāo)準(zhǔn)測(cè)試集是SPEC 組織推出的CPU 子系統(tǒng)評(píng)估軟件。為驗(yàn)證本文方法改進(jìn)下編譯器的健壯性，對(duì)SPEC2006 標(biāo)準(zhǔn)測(cè)試集中的29 道題進(jìn)行測(cè)試，結(jié)果如表1 所示。

表1 SPEC 測(cè)試結(jié)果Table 1 SPEC test results

移植前中間表示代碼在自動(dòng)向量化階段生成了后端不支持的向量類型，在后端指令降級(jí)過程中找不到匹配的降級(jí)方法與指令模板，導(dǎo)致測(cè)試題出現(xiàn)段錯(cuò)誤以及結(jié)果錯(cuò)誤的問題。從表1 可以看出，移植優(yōu)化后410、416、454 等測(cè)試題依靠后端信息的精準(zhǔn)描述以及收益分析的正確引導(dǎo)，向量化程序在test、train、ref 規(guī)模下正確運(yùn)行。

4.2 精準(zhǔn)代價(jià)指導(dǎo)下的測(cè)試分析

基本運(yùn)算指令代價(jià)的精準(zhǔn)描述，可以使得自動(dòng)向量化做出符合后端要求的向量化決策，生成簡(jiǎn)潔高效的向量匯編指令。本文采用TSVC 測(cè)試集中的典型例題，對(duì)比移植優(yōu)化前后的加速性能，結(jié)果如圖4 所示，從圖4 可以看出，相對(duì)移植前，移植優(yōu)化后平均加速比提升42%。

圖4 精準(zhǔn)代價(jià)指導(dǎo)下的加速性能Fig.4 Accelerated performance under precise cost guidance

當(dāng)后端對(duì)不支持的向量指令進(jìn)行降級(jí)處理時(shí)，會(huì)生成冗余標(biāo)量指令導(dǎo)致倒加速。精準(zhǔn)代價(jià)模型指導(dǎo)下的自動(dòng)向量化可排除后端不支持的向量類型，防止向量化倒加速產(chǎn)生。從圖5 可以看出，使用精準(zhǔn)代價(jià)指導(dǎo)后，選擇與后端匹配的向量化因子以及向量化方法，可以使倒加速情況得到明顯改善，在原有移植的基礎(chǔ)上平均加速比提升28%。

圖5 精準(zhǔn)代價(jià)指導(dǎo)下的倒加速改善結(jié)果Fig.5 Reverse acceleration improvement results under precise cost guidance

4.3 性能測(cè)試與分析

本文分別采用SPEC CPU2006 測(cè)試題、TSVC 測(cè)試集以及被廣泛應(yīng)用的矩陣運(yùn)算測(cè)試題進(jìn)行性能測(cè)試。

4.3.1 SPEC 測(cè)試分析

本次實(shí)驗(yàn)對(duì)SPEC 測(cè)試集的29 道題進(jìn)行性能測(cè)試分析，編譯優(yōu)化選擇-O3-static，ref 規(guī)模，單進(jìn)程運(yùn)行。選取代表性測(cè)試題進(jìn)行分析，對(duì)比X86 平臺(tái)與國(guó)產(chǎn)平臺(tái)的向量化能力，從而驗(yàn)證移植的有效性。測(cè)試結(jié)果如圖6 所示，其中，X86 選用與申威SIMD長(zhǎng)度相同的AVX 指令集。

圖6 SPEC 測(cè)試分析結(jié)果Fig.6 SPEC test analysis results

前端將測(cè)試題解析為中間表示代碼，自動(dòng)向量化在此基礎(chǔ)上進(jìn)行向量代碼優(yōu)化生成，然后由后端進(jìn)行降級(jí)處理，生成特定指令集的匯編碼。從圖6 可以看出，移植優(yōu)化后的向量代碼簡(jiǎn)潔高效且符合后端指令集特征需求，移植后SPEC 整體性能提升10.8%，國(guó)產(chǎn)平臺(tái)的向量化能力優(yōu)于X86，其中，436 加速效果最為明顯，提升了97%，437 加速比提升52%，434、470、482 加速比平均提升21%。由于指令集存在差異，國(guó)產(chǎn)處理器不支持一些特殊的向量指令，導(dǎo)致其對(duì)456 與482 的加速性能低于X86。

4.3.2 TSVC 測(cè)試分析

TSVC 測(cè)試集主要用來對(duì)編譯器的自動(dòng)向量化能力進(jìn)行性能測(cè)試，本文采用TSVC 測(cè)試集對(duì)比移植優(yōu)化前后的加速性能，測(cè)試結(jié)果表明，移植優(yōu)化后整體加速比提升16%。對(duì)掩碼內(nèi)建指令進(jìn)行相關(guān)修改，可以使得后端兼容原本不支持的向量化實(shí)現(xiàn)方法，從而充分利用申威后端的向量指令。從圖7 可以看出，在控制流優(yōu)化下，循環(huán)識(shí)別率提升48%，平均加速比提升51%。

圖7 控制流優(yōu)化下的加速比結(jié)果Fig.7 Acceleration ratio results under control flow optimization

4.3.3 應(yīng)用測(cè)試分析

快速傅立葉變換被廣泛應(yīng)用于信號(hào)分析任務(wù)，其性能提升離不開矩陣運(yùn)算優(yōu)化，另外，圖形處理、游戲開發(fā)、科學(xué)計(jì)算中包含了大量的矩陣運(yùn)算，因此，本次實(shí)驗(yàn)以矩陣乘為代表，進(jìn)行應(yīng)用程序測(cè)試分析。實(shí)驗(yàn)采用3 層循環(huán)，以3 種N×N規(guī)模的矩陣進(jìn)行測(cè)試，每個(gè)規(guī)模運(yùn)行3 次并取平均值，以對(duì)比移植優(yōu)化前后的運(yùn)算性能，結(jié)果如圖8 所示。從圖8 可以看出，矩陣乘運(yùn)算總體性能提升了72%，矩陣規(guī)模為1 024×1 024、2 048×2 048、4 096×4 096 時(shí)，加速比分別提升了77%、79%、59%。矩陣乘性能收益主要來源于合適的跨幅因子與向量化因子，其能夠最大程度地發(fā)揮SIMD 向量指令的優(yōu)勢(shì)。

圖8 矩陣乘運(yùn)算性能分析Fig.8 Performance analysis of matrix multiplication operation

5 結(jié)束語

本文針對(duì)申威1621 處理器進(jìn)行LLVM 自動(dòng)向量化功能移植，以解決自動(dòng)向量化過程中后端信息不匹配和向量化實(shí)現(xiàn)方法不兼容的問題。實(shí)驗(yàn)結(jié)果表明，移植優(yōu)化后不再生成后端不支持的向量類型以及不合法的向量指令，控制流向量化程度顯著提升，在TSVC 測(cè)試集中，相對(duì)自動(dòng)向量化移植前，移植優(yōu)化后平均加速比提升16%。通過對(duì)自動(dòng)向量化移植進(jìn)行研究可以看出，在申威后端存在不支持某些相對(duì)重要的向量指令的情況，這將嚴(yán)重影響向量化的效果。因此，下一步將綜合考慮申威指令集與自動(dòng)向量化后代碼生成的關(guān)系，將申威指令集中的基本向量指令進(jìn)行拼接與重組，從而提高向量指令的適用性。