發(fā)掘函數(shù)級單指令多數(shù)據(jù)向量化的方法

李穎穎，高 偉，高雨辰，翟勝偉，李朋遠(yuǎn)

(1.數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室，鄭州 450002； 2.信息工程大學(xué)，鄭州 450002；3.中國電子科技集團(tuán)公司 第二十七研究所，鄭州 450047； 4.北京跟蹤與通信技術(shù)研究所，北京 100094)

(*通信作者電子郵箱xdsy213@163.com)

發(fā)掘函數(shù)級單指令多數(shù)據(jù)向量化的方法

李穎穎1,2，高 偉1,2，高雨辰1,2*，翟勝偉3，李朋遠(yuǎn)4

(1.數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室，鄭州 450002； 2.信息工程大學(xué)，鄭州 450002；3.中國電子科技集團(tuán)公司 第二十七研究所，鄭州 450047； 4.北京跟蹤與通信技術(shù)研究所，北京 100094)

(*通信作者電子郵箱xdsy213@163.com)

當(dāng)前面向單指令多數(shù)據(jù)(SIMD)擴(kuò)展部件的兩類向量化方法分別是循環(huán)級向量化方法和超字級并行(SLP)方法。針對當(dāng)前編譯器不能實現(xiàn)函數(shù)級向量化的問題，提出一種基于靜態(tài)單賦值的函數(shù)級向量化方法。該方法首先分析程序的變量屬性，然后利用一組包括向量函數(shù)子句、一致子句、線性子句等編譯指示子句指導(dǎo)編譯器實現(xiàn)函數(shù)級向量化，最后利用變量屬性結(jié)果對向量化代碼進(jìn)行了優(yōu)化。從多媒體和圖像處理領(lǐng)域選擇部分測試用例對所提的函數(shù)級向量化的功能和性能在國產(chǎn)申威平臺上進(jìn)行測試,與程序串行執(zhí)行相比，采用函數(shù)級向量化后程序的執(zhí)行效率更高。實驗結(jié)果表明函數(shù)級向量化可以取得類似任務(wù)級并行的加速效果，該方法可以指導(dǎo)自動函數(shù)級向量化的實現(xiàn)。

單指令多數(shù)據(jù)擴(kuò)展；并行性；函數(shù)級向量化；編譯指示；靜態(tài)單賦值

0 引言

單指令多數(shù)據(jù)(Simple Instruction Multiple Data, SIMD)擴(kuò)展部件通過一條SIMD擴(kuò)展指令實現(xiàn)對SIMD向量寄存器中所有數(shù)據(jù)元素的并行處理，SIMD擴(kuò)展指令集包括AltiVec、流媒體單指令多數(shù)據(jù)擴(kuò)展(Streaming SIMD Extension, SSE)部件、先進(jìn)的向量擴(kuò)展(Advanced Vector Extension, AVX)部件、AVX- 512和NEON(ARM架構(gòu)處理器擴(kuò)展結(jié)構(gòu))等[1]，國產(chǎn)處理器中龍芯[2]、飛騰[3]、申威以及魂芯[4]也都含有SIMD擴(kuò)展部件，SIMD擴(kuò)展部件現(xiàn)已廣泛應(yīng)用于多媒體和科學(xué)計算等領(lǐng)域[5]。

雖然手工向量化理論上能夠?qū)崿F(xiàn)最高程度的SIMD向量化[6]，但程序員不僅要掌握程序的結(jié)構(gòu)特征和數(shù)據(jù)布局，還要熟悉目標(biāo)處理器底層結(jié)構(gòu)和指令集的特點。SIMD自動向量化通過編譯器實現(xiàn)程序中可向量執(zhí)行部分的挖掘，并自動生成面向目標(biāo)處理器SIMD擴(kuò)展的向量程序，極大減輕了程序員的工作負(fù)擔(dān)[7]。由于受到編譯技術(shù)的限制，當(dāng)前編譯器僅從循環(huán)和基本塊兩個粒度挖掘程序中的向量并行性，編譯器還不能從函數(shù)這個粒度識別程序中的數(shù)據(jù)級并行[8]。當(dāng)前的SIMD自動向量化方法主要從循環(huán)和基本塊兩個粒度發(fā)掘程序的向量并行性，循環(huán)級向量化方法與面向向量機(jī)的傳統(tǒng)向量化方法相似[9]，對其的改進(jìn)包括外層循環(huán)向量化[10]和多面體指導(dǎo)的多重循環(huán)向量化[11-12]。超字級并行(Super-word Level Parallel, SLP)是第一個發(fā)掘基本塊內(nèi)向量并行性的方法[13]。

目前編譯器更多地是發(fā)掘循環(huán)中蘊(yùn)含的數(shù)據(jù)級并行，但為保證正確性，一些情況下編譯器并不能把所有的循環(huán)都轉(zhuǎn)為向量執(zhí)行，如：當(dāng)循環(huán)內(nèi)含有間接數(shù)組訪問和指針時編譯器不能將依賴關(guān)系分析清楚；此外當(dāng)循環(huán)內(nèi)含有函數(shù)調(diào)用時編譯器也可能向量化失敗[14]。

函數(shù)調(diào)用是循環(huán)向量化時的一個重大障礙。如下所示的數(shù)學(xué)庫自有函數(shù)代碼段的循環(huán)內(nèi)含有一個函數(shù)調(diào)用sin，編譯器提供短向量數(shù)學(xué)庫可以對數(shù)學(xué)函數(shù)進(jìn)行向量化，編譯器在作自動向量化時直接調(diào)用短向量數(shù)學(xué)庫中的向量版本sin，因此編譯器可以對帶有sin函數(shù)調(diào)用的循環(huán)成功地進(jìn)行自動向量化。

#include

#include

#define N 128

double a[N]={0};

double b[N]={1,2,3};

double c;

int main(){

int i;

for(i=0;i

a[i]=sin(c);

}

[swvec@cn09 test]MYM tswocc -O3 sin.c -simd=1

(sin.c:10)LOOP WAS VECTORIZED

然而當(dāng)循環(huán)內(nèi)含有一個用戶定義的函數(shù)調(diào)用時編譯器則不能成功地自動向量化。如下所示自定義函數(shù)代碼段的循環(huán)內(nèi)含有一個用戶自定義的函數(shù)調(diào)用foo_sin，自動向量化時編譯器不容易分析清楚函數(shù)調(diào)用foo_sin會引用和修改哪些變量，除非在調(diào)用點上設(shè)置內(nèi)聯(lián)，否則編譯器會保守地不實施自動向量化。

#include

#include

#define N 128

double a[N]={0};

double b[N]={1,2,3};

double c;

double foo_sin(double p){

return sin(p);

}

int main(){

int i;

for(i=0;i

a[i]=foo_sin(c);

}

[swvec@cn09 test]MYM tswocc -O3 sin.c -simd=1

(sin.c:14)LOOP WAS NOT VECTORIZED,LOOP HAS CALLS

為了實現(xiàn)函數(shù)foo_sin的向量化，程序員可通過添加編譯指示指導(dǎo)編譯器完成函數(shù)級向量化，編譯器會根據(jù)標(biāo)量函數(shù)foo_sin生成一個向量函數(shù)vfoo_sin，向量化后的循環(huán)內(nèi)調(diào)用向量函數(shù)vfoo_sin代替原來的標(biāo)量函數(shù)foo_sin，轉(zhuǎn)換過程的示意圖如圖1所示，假設(shè)SIMD擴(kuò)展部件一次可以處理4個double數(shù)據(jù)，那么在向量化后的函數(shù)調(diào)用點處，每4個標(biāo)量函數(shù)調(diào)用(foo_sin(x0), foo_sin(x1), foo_sin(x2), foo_sin(x3))由一個向量函數(shù)調(diào)用vfoo_sin()代替，函數(shù)vfoo_sin的參數(shù)為向量，返回值為向量。

圖1 標(biāo)量函數(shù)轉(zhuǎn)為向量函數(shù)并在SIMD擴(kuò)展部件上執(zhí)行Fig. 1 Transfering scalar function into vector function and executing on SIMD extensions

本文提出了一種面向SIMD擴(kuò)展部件的函數(shù)級向量化方法，與現(xiàn)有的面向循環(huán)和基本塊的SIMD向量化方法相比，本文的主要工作如下：

1)分析了函數(shù)級向量化的優(yōu)點、合法性問題和變量屬性；

2)基于靜態(tài)單賦值形式實現(xiàn)了函數(shù)級向量化，并對生成的向量代碼進(jìn)行了優(yōu)化；

3)給出了一組SIMD擴(kuò)展編譯指示，輔助編譯器發(fā)掘程序的函數(shù)級向量并行性。

1 函數(shù)級向量化分析

1.1 函數(shù)級向量化的概念

函數(shù)級向量化是將幾個相鄰的計算實例合并為一個向量操作，實際上是一種單程序多數(shù)據(jù)模型(Single Program Multiple Data, SPMD)，關(guān)于SPMD程序當(dāng)前的研究大都基于統(tǒng)一計算設(shè)備架構(gòu)(Compute Unified Device Architecture, CUDA) 或者開放運(yùn)算語言(Open Computing Language, OpenCL)等編程模型，并且在圖形處理器(Graphics Processing Unit, GPU)上有硬件支持分歧等問題的處理。本文提出的函數(shù)級向量化是研究在SIMD擴(kuò)展部件上運(yùn)行SPMD程序，由于SIMD擴(kuò)展部件上沒有硬件支持分歧的處理，因而加大了編譯的難度。

1.2 函數(shù)級向量化的優(yōu)點

雖然內(nèi)聯(lián)替換可以消除函數(shù)調(diào)用，但是過度的內(nèi)聯(lián)替換不僅導(dǎo)致代碼膨脹同時也增加了編譯時間，因此完全利用內(nèi)聯(lián)替換解決含有函數(shù)調(diào)用循環(huán)的向量化問題是不可行的，研究函數(shù)級向量化是必要的。當(dāng)前的SIMD向量化方法是面向循環(huán)和基本塊發(fā)掘程序內(nèi)蘊(yùn)含的數(shù)據(jù)級并行，函數(shù)級向量化是從一個更大的粒度識別程序中的數(shù)據(jù)級并行，并可取得任務(wù)級并行的執(zhí)行效果。循環(huán)級向量化方法有很多限制條件，如循環(huán)的迭代次數(shù)、非正規(guī)化的循環(huán)、依賴關(guān)系等，而這些可能不是函數(shù)級向量化的限制條件，函數(shù)級向量化相當(dāng)于從另一個角度重新考慮程序向量執(zhí)行。此外，函數(shù)級向量化還能處理任意復(fù)雜的控制流，因此循環(huán)級向量化方法不能成功向量化的代碼段，或許可利用函數(shù)級向量化實現(xiàn)向量執(zhí)行。

1.3 函數(shù)級向量化的難題

候選函數(shù)的確定、合法性分析和分歧管理是函數(shù)級向量化時的三個難題。

1.3.1 候選函數(shù)的確定

判斷函數(shù)被調(diào)用次數(shù)是否足夠多，如果連續(xù)被調(diào)用的次數(shù)不足夠多則不能將其轉(zhuǎn)為向量執(zhí)行，連續(xù)多次函數(shù)調(diào)用一般僅出現(xiàn)在循環(huán)體內(nèi)。當(dāng)程序中存在多個函數(shù)時，需要根據(jù)函數(shù)調(diào)用圖確定函數(shù)級向量化的順序。如果一個函數(shù)已經(jīng)被發(fā)掘循環(huán)級或基本塊級向量并行性，那么進(jìn)一步實施函數(shù)級向量化是困難的。

1.3.2 合法性分析

在對程序中的函數(shù)向量化時，保證向量化結(jié)果的正確性是困難的，因為需要考慮多個實例對應(yīng)的函數(shù)體之間是否存在阻礙向量執(zhí)行的依賴，這與編譯器中實現(xiàn)循環(huán)級向量化時考慮循環(huán)內(nèi)的語句間是否含有依賴環(huán)類似，但是判斷循環(huán)內(nèi)語句間是否存在依賴環(huán)在依賴關(guān)系分析中已經(jīng)有很好的理論基礎(chǔ)，并且在編譯器中也有實現(xiàn)，而判斷多次函數(shù)調(diào)用之間是否有阻礙向量化的依賴是困難的，因為這涉及到編譯中過程間分析和別名分析兩大難題。

1.3.3 分歧管理

每一個實例不都是執(zhí)行完全相同的指令，如圖2所示，控制流圖(Control Flow Graph, CFG)在4個輸入并行執(zhí)行的情況下，產(chǎn)生執(zhí)行軌跡。如實例1的執(zhí)行軌跡為ade，而實例3執(zhí)行的執(zhí)行軌跡為abcde，這樣產(chǎn)生分歧的控制流使向量執(zhí)行更為復(fù)雜。GPU的分歧管理是有硬件支持的，每一個實例都映射到多核處理器的一個標(biāo)量核心，由一個中央控制單元控制不活躍實例的結(jié)果消除，而在SIMD擴(kuò)展部件上要求顯式的向量執(zhí)行，編譯時需要通過if轉(zhuǎn)換將控制流轉(zhuǎn)為數(shù)據(jù)流，然后借助SIMD擴(kuò)展部件中提供的超字選擇指令實現(xiàn)謂詞執(zhí)行，進(jìn)而消除不活躍實例的結(jié)果。

圖2 不同實例執(zhí)行的軌跡Fig. 2 Execution path of different instances

1.4 向量屬性分析

程序中的變量屬性分析包括一致(uniform)、連續(xù)(consecutive)、對齊(aligned)、保守(guarded)和不可向量化(nonvectorizable)等。基本塊的屬性包括全活躍(by_all)、混合(blend)、重連(rewire)、分歧(div_causing)屬性。

一個變量是一致的，當(dāng)且僅當(dāng)所有的實例中持有相同的值。變量的一致性可以對訪存和控制流進(jìn)行優(yōu)化。當(dāng)控制流的判斷條件是一致標(biāo)量時，編譯器可以意識到所有的執(zhí)行代碼指令都會經(jīng)過同一個路徑，這樣就可以減少分歧控制流帶來的掩碼執(zhí)行開銷，只需生成超字條件跳轉(zhuǎn)指令即可；如果為一個直接尋址變量則直接利用廣播指令生成向量，而不需要利用插入指令逐個值插入到目標(biāo)向量寄存器中以形成向量。

一個變量是連續(xù)的，當(dāng)且僅當(dāng)對于所有實例相鄰標(biāo)識符的偏移量是連續(xù)的，當(dāng)基址是一致的，偏移地址是線性連續(xù)單元時，編譯器可以生成更高效的連續(xù)向量訪存指令而不需要生成不連續(xù)的向量訪存如gather/scatter等指令。

一個變量是對齊的，當(dāng)且僅當(dāng)所有實例中的第一個實例的地址是SIMD擴(kuò)展部件寬度 S的倍數(shù)。對齊的內(nèi)存位置SIMD硬件通常提供更高效的向量內(nèi)存操作，而不對齊的位置則可能需要兩次對齊訪存和一個拼湊操作，或者直接利用代價更大的不對齊訪存指令。

一個基本塊具有全活躍屬性，當(dāng)且僅當(dāng)該基本塊被所有的實例執(zhí)行。如果基本塊具有by_all屬性，那么它不需要保守執(zhí)行，因此將生成更高效的代碼?；旌匣緣K是指所有實例在這個基本塊內(nèi)匯聚，分歧基本塊是指所有實例在這個基本塊內(nèi)產(chǎn)生分歧。重連基本塊是指分歧基本塊的直接后繼或者與之不相交路徑的結(jié)束塊。分歧循環(huán)(divergent loop)是指實例在不同的迭代或一次迭代內(nèi)的不同位置退出循環(huán)。

2 基于靜態(tài)單賦值形式的函數(shù)級向量化

靜態(tài)單賦值形式(Static Single Assignment, SSA)是一種中間表示，它的單賦值特性表現(xiàn)在每個變量在這種中間表示中僅被賦值一次，SSA使得每個變量都有唯一的定義，因此數(shù)據(jù)流分析和優(yōu)化算法可以更加簡單。若一個變量有M個定義和N個使用，若不采用SSA，則存在M×N個定義-使用關(guān)系，采用SSA則變?yōu)镸+N。對同一個變量的不相關(guān)的若干次使用，在SSA形式中會轉(zhuǎn)變成對不同變量的使用，因此能消除很多不必要的依賴關(guān)系，如可消除多數(shù)輸出依賴和反依賴。由于SSA的中間表示有以上優(yōu)點，因此本文基于SSA實現(xiàn)函數(shù)級向量化。

2.1 函數(shù)級向量化轉(zhuǎn)換

函數(shù)級向量化轉(zhuǎn)換算法包含四個步驟，分別是掩碼生成、選擇生成、控制流圖線性化和向量指令生成，算法的偽代碼如以下所示。

1)掩碼生成：

Function CreateMasks(Block B)

begin

if B already has masks then

return;

end

if B is loop header then

createMasks(preheader);

else

foreach P∈predecessors do

createMasks(P);

end

end

createEntryMask(B);

createExitMask(B);

if B is loop header then

createMasks(latch)

if loop is divergent then

Mask latchMask ←ExitMasks[latch→header]

EntryMasks[B].blocks.push(latch);

EntryMasks[B].values.push(latchMask);

end

end

end

2)選擇生成：

Function GenerateSelectFromPhi(Phi P,Block B)

Begin

S←P.values[0];

foreach i=1→P.values.size()-1 do

Value V←P.values[i];

Block P←P.blocks[i];

Mask M←ExitMasks[P→B];

S←Select(M,V,S) in B;

end

replace all uses of P with S;

delete P;

end

3)控制流圖線性化：

Function Linearize(Function F)

Begin

foreach B∈ F do

foreach S∈ successors do

if NewTargets[B→S].empty() then

remove edge B→S;

continue;

end

X←new Blocks;

rewire edge B→S to B→X;

foreach T ∈NewTargets[B→S]do

P←NewTargetDivCausingBlocks[B→S][T];

create edge X→T under condition P;

end

end

end

end

4)向量指令生成：

Function GenerateCode(Function F)

begin

foreach op∈function do

if op is uniform then

generate broadcast;

else if op is consectuive then

generate unit-stride memory access;

else if op is nonvectorizable then

generate sequential code;

else if op is guarded then

generate guarded code;

else

replace one by one

end

end

end

2.1.1 掩碼生成

不同的實例執(zhí)行時會在一些條件分支發(fā)生分歧，而SIMD擴(kuò)展部件要求所有代碼都要執(zhí)行，所以需要用掩碼顯式地指出哪些實例執(zhí)行而哪些實例丟棄執(zhí)行結(jié)果。在控制流圖中掩碼體現(xiàn)在基本塊之間的邊上。如果實例i的掩碼在控制流圖的邊A→B為真，那么表示實例i將會執(zhí)行該分支，因此掩碼標(biāo)志著向量化后向量中的相應(yīng)元素是有效的數(shù)據(jù)，這種掩碼稱為邊掩碼，用A→B表示基本塊A到基本塊B的邊掩碼。邊掩碼隱含地定義了基本塊的入口掩碼。若是一個循環(huán)頭的基本塊，那么它的入口掩碼是一個來自進(jìn)入循環(huán)的基本塊和循環(huán)尾部跳轉(zhuǎn)回來的基本塊的phi函數(shù)。

2.1.2 選擇生成

通過在控制流圖的匯聚點插入選擇操作，以丟棄不活躍實例產(chǎn)生的結(jié)果。將原控制流圖中的phi函數(shù)用選擇指令替換，具有n個值的phi函數(shù)可以替換成n-1個選擇指令。每一個循環(huán)要求一個結(jié)果向量保留離開循環(huán)的實例的循環(huán)活躍值，循環(huán)活躍值是跨越循環(huán)邊界的值，即在后續(xù)迭代中或循環(huán)外使用，可以認(rèn)為是循環(huán)尾基本塊的活躍輸出變量。對每一個循環(huán)活躍值，結(jié)果向量通過一個phi函數(shù)和一個選擇操作兩條指令維持，這對于每個循環(huán)活躍值僅需插入一個選擇指令，而不需要考慮循環(huán)出口的個數(shù)。結(jié)果phi函數(shù)被放置在每個嵌套循環(huán)的前面，并且有兩個輸入值，來自循環(huán)頭的輸入值被頂級循環(huán)定義。對于嵌套循環(huán)，輸入值是父循環(huán)的結(jié)果phi函數(shù)，來自循環(huán)尾部的輸入值是結(jié)果更新操作。采用結(jié)果向量可以向量化所有循環(huán)，包括含有多層嵌套的控制流和多出口的循環(huán)。

2.1.3 控制流圖線性化

在所有的掩碼和選擇操作生成之后，控制流已經(jīng)全部轉(zhuǎn)換為數(shù)據(jù)流，因此可以將控制依賴邊刪除。最終在保留原控制流圖執(zhí)行順序的前提下將所有的基本塊線性執(zhí)行。在原來的控制流圖中，如果基本塊A在基本塊B之前執(zhí)行，那么在線性化后的控制流圖中，基本塊A也要放在基本塊B之前。如果控制流圖分裂為兩個分支，那么一條分支的所有基本塊必須完整地放在另一分支前面。控制流圖線性化的過程有很多策略，不同策略產(chǎn)生代碼的效率也不相同，實際中啟發(fā)式的方法可以考慮代碼規(guī)?；蛘呒拇嫫鞯膲毫ΑＭㄟ^拓?fù)渑判蜻f歸地決定基本塊的順序，最后控制流圖僅有一個入口和一個出口。

2.1.4 向量指令生成

控制流圖線性化后進(jìn)入到向量指令生成階段，向量指令生成基本上是一對一的轉(zhuǎn)換，即將標(biāo)量指令轉(zhuǎn)為向量指令，但是在向量指令生成過程中也需要考慮變量和操作的屬性。當(dāng)變量具有一致屬性時，利用廣播指令將其轉(zhuǎn)為向量；當(dāng)變量具有連續(xù)屬性時，可生成連續(xù)的向量訪存指令；當(dāng)變量具有對齊屬性時，可生成對齊的向量訪存指令；對于不可向量化的操作如存儲指令和函數(shù)調(diào)用等需要復(fù)制多次。如果一個塊具有全活躍點屬性，它會被所有實例執(zhí)行，因此不需要保守執(zhí)行。

對于具有保守屬性的存操作，需要防止掩碼為假時將結(jié)果寫入內(nèi)存。為防止實例為假時寫入內(nèi)存，第一種代碼生成方法是構(gòu)建if語句標(biāo)量執(zhí)行，但是這種實現(xiàn)方法引入了許多提取、插入和分支操作，降低了向量化收益。第二種代碼生成方法是利用“取-拼湊-存”組合操作，取出內(nèi)存中的數(shù)據(jù)拼湊后直接存入內(nèi)存中，對于連續(xù)存時此種方法比第一種向量化方法更高效。當(dāng)不連續(xù)存時，如硬件支持生成聚集、分散操作會更高效，最后一種實現(xiàn)方法就是利用硬件支持的掩碼內(nèi)存訪問。

2.2 函數(shù)級向量化優(yōu)化

2.2.1 插入超字跳轉(zhuǎn)指令

在進(jìn)入控制流圖線性化階段時，所有基本塊的入口掩碼和選擇操作select已經(jīng)設(shè)置。此時，基本塊入口掩碼的值決定著整個基本塊指令是否執(zhí)行。如果入口掩碼中所有實例的掩碼值均為假，那么可以跳過該基本塊的執(zhí)行而直接執(zhí)行下個基本塊。超字條件跳轉(zhuǎn)指令(Branches-On-Superword-Condition-Codes, BOSCCs) 分為兩類：一類是BOA(Branch-On-All)，指所有分支都為真時跳轉(zhuǎn)；一類是BON(Branch-On-None)，指所有分支都為假時跳轉(zhuǎn)。BOA指令發(fā)掘和BON指令發(fā)掘過程相似。BOA指令生成算法關(guān)鍵在于識別出一個超字條件所控制的指令區(qū)域，而經(jīng)過掩碼生成和控制流圖線性化后，基本塊的入口掩碼已經(jīng)確定并且基本塊已經(jīng)按照線性順序組織在一起，因此，采用了線性掃描的方法將識別謂詞區(qū)域與增加條件跳轉(zhuǎn)操作一起進(jìn)行。

2.2.2 轉(zhuǎn)為標(biāo)量執(zhí)行

如果函數(shù)中頻繁地有一個或者多個活躍的實例執(zhí)行而其他實例的結(jié)果都被丟掉，那么可以利用實例多版本將其轉(zhuǎn)為串行執(zhí)行收益可能更大。首先計算出活躍實例的索引，然后將該實例所有需要的值都提到標(biāo)量寄存器中，最后將結(jié)果再更新到結(jié)果向量中。雖然標(biāo)量執(zhí)行時引入了插入和提取指令，但當(dāng)向量代碼的開銷很大時實例多版本是有收益的。此外還可以對標(biāo)量代碼使用SLP方法進(jìn)行向量化，將同構(gòu)操作繼續(xù)轉(zhuǎn)為向量操作。函數(shù)級向量化屬于水平向量化方法，而SLP方法屬于垂直向量化方法，首先需要將活躍實例中的值從原來的向量中提取出來，然后再繼續(xù)利用打包算法，但這個變換可能涉及到由于數(shù)據(jù)重組帶來的開銷。

下面的程序中顯示，對兩個活躍的實例，首先利用多版本技術(shù)將其轉(zhuǎn)為標(biāo)量執(zhí)行后再利用SLP方法發(fā)掘結(jié)果。原代碼中的兩個操作是相互獨(dú)立的，如while循環(huán)內(nèi)的else分支所示。函數(shù)級向量化后如果僅有兩個實例是活躍的，首先計算得到索引的idx0和idx1，將兩個實例重新打包成向量，經(jīng)過加法、減法和乘法等運(yùn)算后將結(jié)果從向量中提取出來，更新到索引idx0和idx1中。

2.2.3 實例重組

假設(shè)函數(shù)被調(diào)用W次，向量化因子為V，函數(shù)被向量化后執(zhí)行的次數(shù)為S，那么W、V和S之間的關(guān)系為W=V*S。與循環(huán)展開類似，S次向量函數(shù)調(diào)用可以放到一起，相當(dāng)于向量函數(shù)體被執(zhí)行S次，實例重組就可以在此情況下應(yīng)用。實例重組就是將所有實例按照真值重新分為真假兩組，這樣在S次調(diào)用中僅有一次需要考慮分歧，而其余S-1次調(diào)用在重組后已經(jīng)確認(rèn)。實例重組的目標(biāo)是改進(jìn)代碼的一致性，包括控制流和訪存模式。假設(shè)程序的控制流圖如圖3(a)所示，函數(shù)級向量化的控制流圖如圖3(b)所示。如果W=16，V=4，那么S=4，在不實施實例重組的情況下控制流圖如圖3(c)所示。圖3(d)表示實例重組后的控制流圖，其中僅有1次調(diào)用需要考慮執(zhí)行塊b還是塊c這個分歧，而其余3次調(diào)用時已經(jīng)確定或者執(zhí)行塊b或者執(zhí)行塊c，其中塊ra和re表示重組代碼。

圖3 實例重組示意圖Fig. 3 Instance restructuring schematic diagram

3 編譯器中實現(xiàn)

編譯器自動地發(fā)掘程序內(nèi)蘊(yùn)含的函數(shù)級向量并行性是困難的，為了保證函數(shù)級向量化的正確性，本文提供一套編譯指示幫助編譯器實現(xiàn)函數(shù)級向量化。這套編譯指示不僅包括實現(xiàn)函數(shù)級向量化的子句，也包括對向量代碼優(yōu)化的子句如一致子句、連續(xù)子句和對齊子句等。

3.1 向量函數(shù)子句

在選擇向量化哪個函數(shù)時，需要判斷其被調(diào)用的次數(shù)是否足夠多，如果被調(diào)用的次數(shù)不是足夠多，那么就是因為并行度不夠而不能被向量化，連續(xù)多次函數(shù)調(diào)用一般僅出現(xiàn)在循環(huán)體內(nèi)。程序員在發(fā)掘函數(shù)級向量并行時，首先在循環(huán)外加一條指示#pragma simd vec-function，標(biāo)記該循環(huán)雖然存在函數(shù)調(diào)用但是可以實現(xiàn)函數(shù)級向量化。編譯指示__decl-vec-function標(biāo)記后面緊跟著待向量化的函數(shù)，編譯指示__decl-vec-function的格式如下：

_ _decl-vec-function([(vector-clauses)])

vector-clause:

uniform-clause

linear-clause

alignment-clause

mask-clause

其中：uniform-clause表示一致子句；linear-clause表示線性之句；alignment clause表示對齊子句；mask-clause表示掩碼子句。下面的代碼中實現(xiàn)了函數(shù)mandel的向量化，首先利用編譯指示子句標(biāo)記函數(shù)mandel是一個可向量化函數(shù)，同時在出現(xiàn)函數(shù)mandel的循環(huán)前面添加向量化編譯指示，實現(xiàn)了函數(shù)mandel的向量化。

_ _decl-vec-function(uniform(max_iter))

unsigned int mandel(complex c,unsigned max_iter);

…

for(int y=0; y< imageheight;++y){

#pragma simd vec-function

for(int x=0; x< imageheight;++x){

count[y][x]=mandel(in_vals[y][x],max_iter);

}

}

編譯器通過識別函數(shù)和循環(huán)的向量指示子句實現(xiàn)函數(shù)的向量化，將函數(shù)由標(biāo)量形式轉(zhuǎn)為向量形式，同時做好過程克隆。編譯器中也實現(xiàn)了變量的屬性分析，能夠識別出變量的一致性、連續(xù)性和對齊性等屬性，當(dāng)指示子句給出的屬性和編譯器自動識別的屬性不一致時，根據(jù)指示子句給出的屬性生成向量代碼。

3.2 一致子句

一致子句表示向量寄存器中所有槽位的值相同，相反默認(rèn)情況下認(rèn)為所有實例對應(yīng)的向量寄存器槽位的變量值不同。利用關(guān)鍵字uniform標(biāo)記一致子句，一致子句格式如下：

uniform-clause:

uniform(uniform-param-list)

uniform-param-list:

parameter-name

uniform-param-list, parameter-name

parameter-name:

identifier

3.3 線性子句

線性子句表示變量對應(yīng)多個實例在內(nèi)存中引用是連續(xù)的，用關(guān)鍵字linear表示。線性子句格式如下：

linear-clause:

linear(linear-variable-list)

linear-variable-list:

linear-variable

linear-variable-list, linear-variable

linear-variable:

id-expression

id-expression: linear-step

linear-step:

constant-expression

linear-variable中的id-expression應(yīng)該指派一個標(biāo)量；linear-step中的constant-expression應(yīng)該滿足或者是一個整數(shù)常數(shù)表達(dá)式，或者是整數(shù)類型的變量。如果一個linear-variable沒有對應(yīng)的linear-step，則linear-step的值為1。如果linear-step為一個變量，并且這個變量在循環(huán)執(zhí)行過程中被修改，這樣的行為被認(rèn)為是未定義的。在向量屬性的上下文下，linear-step中的constant-expression也應(yīng)該是整常數(shù)表達(dá)式，引用linear-step的參數(shù)是一致的。

3.4 對齊子句

對齊子句表示變量在內(nèi)存中引用是對齊的，默認(rèn)情況下認(rèn)為變量是不對齊的，利用關(guān)鍵字alignment標(biāo)記對齊子句，其格式如下：

alignment-clause:

alignment(uniform-param-list)

alignment-param-list:

parameter-name

alignment-param-list, parameter-name

parameter-name:

identifier

對齊優(yōu)化對于發(fā)揮SIMD硬件的性能也非常重要，編譯器生成更多的向量對齊訪問指令對于提升生成的向量程序執(zhí)行效率有很大幫助，本文的編譯器中提出了向量對齊子句，為程序員提供一系列表達(dá)對齊的信息。

3.5 掩碼子句

默認(rèn)情況下，對于每一個向量變體需要兩種實現(xiàn)：一種是調(diào)用時帶有掩碼條件，另一種是調(diào)用時不帶掩碼條件。如果程序中所有對該函數(shù)的調(diào)用都是帶條件的，則使用掩碼子句指導(dǎo)編譯器不生成不帶掩碼調(diào)用的函數(shù)體；反之，如果程序中所有對該函數(shù)的調(diào)用都是不帶條件的，則使用無掩碼子句，指導(dǎo)編譯器不生成帶有掩碼的函數(shù)體。掩碼子句格式如下：

mask-clause:

mask

nomask

默認(rèn)情況下編譯器會同時生成帶掩碼的向量函數(shù)體和不帶掩碼的向量函數(shù)體，同時使用掩碼子句和無掩碼子句是無效的。很多時候函數(shù)是在條件分支下被調(diào)用，如終止遞歸函數(shù)調(diào)用的執(zhí)行，必須生成一個特別的帶掩碼版本的向量函數(shù)并且保證其正確執(zhí)行。帶掩碼的向量函數(shù)有一個額外的bool型參數(shù)，函數(shù)體只有當(dāng)掩碼值為真時才被執(zhí)行。

4 實驗結(jié)果與分析

將本文提出的函數(shù)級向量化方法在開源編譯器Open64中實現(xiàn)，編譯環(huán)境為Linux操作系統(tǒng)，版本為Redhat Enterprise 5。實驗時首先用Open64編譯器 將源程序轉(zhuǎn)化為向量化程序，然后再用基礎(chǔ)編譯器編譯成二進(jìn)制代碼并在國產(chǎn)CPU 申威-1600上運(yùn)行，最后用串行程序的運(yùn)行時間除以向量化程序的運(yùn)行時間便得到向量化的加速比。實驗平臺CPU主頻為2.0 GHz，內(nèi)存為2 GB，L1數(shù)據(jù)cache為32 KB，L2 cache為256 KB，基本頁面為8 KB，向量寄存器的寬度為256位，可以同時處理4個浮點型數(shù)據(jù)或者8個整型數(shù)據(jù)。編譯器中還實現(xiàn)了訪存和循環(huán)等其他優(yōu)化，通過在程序中添加函數(shù)向量化子句指導(dǎo)編譯器完成向量化，同時添加對齊、一致、連續(xù)等屬性指導(dǎo)編譯器生成更高效的向量代碼。添加函數(shù)向量化子句后編譯運(yùn)行獲得向量化時間，關(guān)閉函數(shù)向量化子句后編譯運(yùn)行得到未向量化時間，最后利用未向量化時間除以向量化時間得到函數(shù)向量化的加速比。

實驗分析包括兩部分，分別是優(yōu)化測試分析和對比測試分析。優(yōu)化測試分析主要描述訪存和控制流等優(yōu)化對函數(shù)級向量化性能的影響；對比測試分析主要將本文提出的函數(shù)級向量化方法與現(xiàn)有的循環(huán)級和基本塊級向量化方法對比。

4.1 優(yōu)化測試分析

從不同的應(yīng)用領(lǐng)域選擇8個測試用例用于函數(shù)級向量化的優(yōu)化分析測試。這些測試用例覆蓋了一系列現(xiàn)實應(yīng)用，從排序算法到股票分析算法，從粒子運(yùn)動模擬到圖形圖像處理。表1列出了這些測試用例的信息，包括輸入數(shù)據(jù)的規(guī)則、代碼行數(shù)、控制流特征和測試用例功能描述。

為了評估訪存和控制流等優(yōu)化對函數(shù)級向量化的影響，比較不同優(yōu)化方案下獲得的代碼。在不實施函數(shù)級向量化時即串行執(zhí)行，用Scalar表示；將所有的性能優(yōu)化分析都關(guān)閉，稱為直接函數(shù)級向量化，用Naive表示，直接函數(shù)級向量化時關(guān)閉所有的優(yōu)化包括一致屬性和訪存操作屬性；訪存優(yōu)化表示實施函數(shù)級向量化時加入了一致、對齊和連續(xù)屬性，實施了訪存優(yōu)化，用MEM表示；All表示實施了本文提到的所有優(yōu)化，包括訪存相關(guān)的一致、對齊和連續(xù)屬性分析，也包括本文提到的插入超字跳轉(zhuǎn)指令、轉(zhuǎn)為標(biāo)量執(zhí)行和實例重組等。

表2是不同優(yōu)化方案下8個應(yīng)用的運(yùn)行時間，單位為ms。其中Speedup的Scalar/Navie表示Navie相對Scalar的加速比，其他依此類推；整體的觀察是隨著分析和優(yōu)化的加入，性能在不斷增加。圖4顯示了不同優(yōu)化方法對函數(shù)級向量化的性能測試結(jié)果。

表1 優(yōu)化測試分析用例Tab. 1 Use-case of optimization test and analysis

表2 不同優(yōu)化的運(yùn)行時間對比Tab. 2 Running time comparison of different optimizations

圖4 不同優(yōu)化的測試結(jié)果Fig. 4 Test results of different optimizations

1)直接函數(shù)級向量化(Scalar)。從表2與圖4中可以看出，與串行執(zhí)行相比，即使直接函數(shù)級向量化(Naive)也能獲得不錯的性能加速，如BlackScholesScalar 的向量化加速比為3.20，NBodyScalar的向量化加速比為2.13。這些測試用例是數(shù)據(jù)密集型應(yīng)用，帶有簡單的控制流，這樣的測試用例非常適合函數(shù)級向量化。然而，DCT的直接函數(shù)級向量化加速比僅為0.37，說明其直接函數(shù)級向量化的性能弱于標(biāo)量執(zhí)行性能，這樣的情況有4個例子出現(xiàn)。這種情況的主要原因是生成的向量代碼比較保守，所有的訪存操作都必須串行執(zhí)行，所有含有副作用的操作都需要通過if語句生成，所有的控制流都被線性化，這說明了函數(shù)級向量化分析和優(yōu)化的重要性。

2)加入一致、對齊和連續(xù)屬性訪存優(yōu)化的函數(shù)級向量化(MEM)。保留一致性證明是有效的，與直接實施函數(shù)級向量化相比，加入一致和連續(xù)屬性的優(yōu)化獲得的加速比為1.65。對于程序DwtHaar1D、DCT和 NBody，加入一致、對齊和連續(xù)屬性后，獲得了更好的加速效果，但它們的核心內(nèi)仍有大量的操作保持標(biāo)量。DwtHaar1D的一個重要性能提升是sqrt操作的參數(shù)轉(zhuǎn)為了一致屬性，如果這個函數(shù)調(diào)用沒有被標(biāo)記為一致屬性，在直接實施函數(shù)級向量化中，它會被保守地執(zhí)行，因此需要串行執(zhí)行并且加入條件。連續(xù)屬性對程序DCT有很好的效果。

3)實施所有優(yōu)化，包括訪存相關(guān)的一致、對齊和連續(xù)屬性分析，也包括本文提到的插入超字跳轉(zhuǎn)指令、轉(zhuǎn)為標(biāo)量執(zhí)行和實例重組等。本文最后的優(yōu)化方案是將所有的優(yōu)化手段都用上，這包括在控制流圖線性化階段保留部分控制流圖，這些控制流圖被證明實例不會分歧，這樣可以使得更少的代碼被執(zhí)行，向量寄存器壓力更小，掩碼開銷更少。例如在程序Histogram中，循環(huán)內(nèi)存在一個store操作，保守情況下，它需要被串行執(zhí)行并且需要考慮分歧控制流的影響；然而，這個循環(huán)最后被證明不存在分歧，并且會被所有的實例執(zhí)行。因此在向量化代碼生成時生成一個向量存指令，而不是幾條標(biāo)量存指令。

實例多版本和實例重組方法對程序DCT、Histogram和MersenneTwister獲得了較好的加速效果，對這三個程序有效果的主要是因為控制流相關(guān)的提升，加速比分別為1.47、1.19和1.52。不過這三種優(yōu)化對沒有分歧控制流的程序沒有任何優(yōu)化作用，如程序BitonicSort。與實施一致和連續(xù)優(yōu)化相比，實施多版本和實例重組后加速比平均為1.18。相比直接實施函數(shù)級向量化，采用訪存和控制流等優(yōu)化手段后平均加速比為2.00，說明了訪存和控制流優(yōu)化對函數(shù)級向量化性能提升有重要作用。

4.2 對比測試分析

從不同的應(yīng)用領(lǐng)域選擇6個測試用例來測試函數(shù)級向量化的效果，選擇的測試用例包括矩陣乘、矩陣轉(zhuǎn)置和卷積等多媒體領(lǐng)域的典型程序，以及曼德伯特集、光線追蹤等圖像仿真程序。表3對選擇的測試用例進(jìn)行了描述，包括數(shù)據(jù)規(guī)模、代碼行數(shù)、控制流特征和程序描述。

表3 對比測試分析用例Tab. 3 Use-case of comparison test and analysis

對選定的測試用例分別實施函數(shù)級向量化、循環(huán)級向量化和基本塊級向量化，測試分析不同向量化方法對選定測試用例的向量化效果，對比測試分析結(jié)果如圖5所示。圖5中函數(shù)級向量化方法的測試結(jié)果用WFV標(biāo)記，循環(huán)級向量化方法的測試結(jié)果用LOOP標(biāo)記，基本級向量化方法的測試結(jié)果用SLP標(biāo)記。在實施函數(shù)級向量化時，已經(jīng)添加了一致、連續(xù)等訪存優(yōu)化和實例重組等其他優(yōu)化。

圖5 對比測試分析結(jié)果Fig. 5 Results of comparison test and analysis

圖5的函數(shù)級向量化性能測試結(jié)果顯示加速比從1.56到3.22。其中Mandelbrot的加速比為3.22，Convolve的加速比為2.92，矩陣乘MMM的加速比為2.86，這3個程序的函數(shù)級向量化加速比較高是因為它們?yōu)楹唵吻短籽h(huán)，并且不含有復(fù)雜的控制流。N-Body的加速比為2.34，Transpose的加速比為1.72，Volume rendering的加速比為1.56，這3個程序的函數(shù)級向量化結(jié)果加速比不高是因為它們含有復(fù)雜的控制流，在函數(shù)級向量化時為了處理分歧引入了許多選擇指令，帶來了較大的開銷，抵消了部分向量化收益；并且由于目標(biāo)平臺不支持聚集、分散等高效的向量訪存操作，因此在代碼生成時還引入了大量的提取指令進(jìn)一步抵消了函數(shù)級向量化收益。

函數(shù)級向量化方法能夠成功向量化Mandelbrot，而循環(huán)級向量化方法和基本塊級向量化方法都不能成功向量化Mandelbrot。這是因為Mandelbrot的最內(nèi)層為while循環(huán)，循環(huán)退出條件不定。函數(shù)級向量化從一個更大的粒度，將整個while循環(huán)成功地進(jìn)行了向量化。在對N-Body實施循環(huán)級向量化時，由于數(shù)據(jù)跨幅較大導(dǎo)致向量化收益被數(shù)據(jù)重組抵消較大部分，因此僅獲得了1.24的加速比；在對N-Body實施基本塊級向量化方法時，由于同構(gòu)語句數(shù)量為3條同時還存在歸約操作，導(dǎo)致基本塊向量化方法不能充分利用向量寄存器，并且還存在額外的數(shù)據(jù)重組開銷，最后獲得了1.56的加速比；而在對N-Body實施函數(shù)級向量化時從一個更大的粒度向量化成功，因此獲得了2.34的加速比。對Volume rendering函數(shù)級向量化方法成功地實施了向量化，并獲得了1.56的加速比，而循環(huán)級和基本塊級向量化都沒有向量化成功。對比測試分析的三種向量化方法都成功地向量化了MMM、Convolve和Transpose，但是實施函數(shù)級向量化時由于過程間開銷導(dǎo)致函數(shù)級向量化效果略弱于基本塊級和循環(huán)級向量化方法，對于這3個程序基于循環(huán)展開的基本塊向量化方法和循環(huán)級向量化方法生成的向量代碼基本一致，因此獲得的加速比相近。

5 結(jié)語

本文提出了一種發(fā)掘函數(shù)級SIMD向量化的方法：首先說明了函數(shù)級向量化的概念、優(yōu)點和發(fā)掘函數(shù)級向量化時的主要問題；然后對函數(shù)級向量化時變量的屬性進(jìn)行了分析，基于靜態(tài)單賦值形式實現(xiàn)了函數(shù)級向量化并對生成的向量代碼進(jìn)行了優(yōu)化；接著提出了一組編譯指示子句指導(dǎo)編譯器發(fā)掘函數(shù)級向量化，編譯指示子句包括向量函數(shù)子句、一致子句、線性子句等；最后從多媒體和圖像處理領(lǐng)域選擇了6個測試用例來驗證本文提出的函數(shù)級向量化方法的正確性和有效性。在國產(chǎn)申威-1600平臺上進(jìn)行了性能測試，與程序串行執(zhí)行相比，采用函數(shù)級向量化后程序執(zhí)行效率比原來串行執(zhí)行的效率更高。編譯器如何自動地實現(xiàn)函數(shù)級向量化的發(fā)掘以及對函數(shù)級向量化的代碼優(yōu)化是下一步的研究工作。

References)

[1] 高偉,趙榮彩,韓林,等.SIMD自動向量化編譯優(yōu)化概述[J].軟件學(xué)報,2015,26(6):1265-1284. (GAO W, ZHAO R C, HAN L，et al. Research on SIMD auto-vectorization compiling optimization [J]. Journal of Software, 2015,26(6): 1265-1284.)

[2] 彭飛,顧乃杰,高翔,等.龍芯3B的SIMD編譯優(yōu)化及分析[J].小型微型計算機(jī)系統(tǒng),2012,33(12):2733-2737. (PENG F, GU N J, GAO X, et al. SIMD compiler optimization and analysis based on Godson-3B processor [J]. Journal of Chinese Computer Systems, 2012, 33(12): 2733-2737.)

[3] 陳書明,劉勝,萬江華,等.協(xié)同多核DSP YHFT-QMBase:體系結(jié)構(gòu)及實現(xiàn)[J].中國科學(xué):信息科學(xué),2015,45(4):560-573. (CHEN S M, LIU S, WAN J H, et al. Coordinate multi-core DSP YHFT-QMBase: architecture and implementation [J]. SCIENCE CHINA (Informationis), 2015, 45(4): 560-573.)

[4] 王向前,洪一,王昊,等.魂芯DSP的編譯器設(shè)計與優(yōu)化[J].電子學(xué)報,2015,43(8):1656-1661. (WANG X Q, HONG Y, WANG H, et al. Compiler design and optimization for BWDSP [J]. Acta Electronica Sinica, 2015, 43(8): 1656-1661.)

[5] CHEN L, JIANG P, AGRAWAL G. Exploiting recent SIMD architectural advances for irregular applications [C]// Proceedings of the 2016 IEEE/ACM International Symposium on Code Generation and Optimization. Piscataway, NJ: IEEE, 2016: 47-58.

[6] LEI?A R, HAFFNER I, HACK S. Sierra: a SIMD extension for C++ [C]// WPMVP ’14: Proceedings of the 2014 Workshop on Programming Models for SIMD/Vector Processing. New York: ACM, 2014: 17-24.

[7] HUO X, REN B, AGRAWAL G. A programming system for Xeon Phis with runtime SIMD parallelization [C]// ICS ’14: Proceedings of the 28th ACM International Conference on Supercomputing. New York: ACM, 2014: 283-292.

[8] EVANS G C, ABRAHAM S, KUHN B, et al. Vector seeker: a tool for finding vector potential [C]// WPMVP ’14: Proceedings of the 2014 Workshop on Programming Models for SIMD/Vector Processing. New York: ACM, 2014: 41-48.

[9] KENNEDY K, ALLEN J R. Optimizing Compilers for Modern Architectures: A Dependence-based Approach [M]. San Francisco, CA: Morgan Kaufmann, 2002.

[10] NUZMAN D, ZAKS A. Outer-loop vectorization: revisited for short SIMD architectures [C]// PACT ’08: Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques. Piscataway, NJ: IEEE, 2008: 2-11.

[11] TRIFUNOVIC K, NUZMAN D, COHEN A, et al. Polyhedral-model guided loop-nest auto-vectorization [C]// PACT ’09: Proceedings of the 18th International Conference on Parallel Architectures and Compilation Techniques. Piscataway, NJ: IEEE, 2009:327-337.

[12] KONG M, VERAS R, STOCK K, et al. When polyhedral transformations meet SIMD code generation [C]// PLDI ’13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design & Implementation. New York: ACM, 2013: 127-138.

[13] LARSEN S, AMARASINGHE S. Exploiting superword level parallelism with multimedia instruction sets [J]. ACM Sigplan Notices, 2000, 35(5): 145-156.

[14] WANG Y, WANG D, CHEN S, et al. Iteration interleaving-based SIMD lane partition [J]. ACM Transactions on Architecture & Code Optimization, 2016, 12(4): Article No. 58.

LIYingying, born in 1984, M. S., lecturer. Her research interests include advanced compilation technique.

GAOWei, born in 1988, Ph. D candidate. His research interests include high performance computing, advanced compilation technique.

GAOYuchen, born in 1988, M. S. candidate. His research interests include advanced compilation technique.

ZHAIShengwei, born in 1982, M. S., engineer. His research interests include advanced computing.

LIPengyuan, born in 1989, M. S., researcher. His research interests include high performance computing.

Methodforexploitingfunctionlevelvectorizationonsimpleinstructionmultipledataextensions

LI Yingying1,2, GAO Wei1,2, GAO Yuchen1,2*, ZHAI Shengwei3, LI Pengyuan4

(1.StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,ZhengzhouHenan450002,China；2.PLAInformationEngineeringUniversity,ZhengzhouHenan450002,China；3.The27thResearchInstitute,ChinaElectronicsTechnologyGroupCorporation,ZhengzhouHenan450047,China；4.BeijingInstituteofTrackingandTelecommunicationsTechnology,Beijing100094,China)

Currently, two vectorization methods which exploit Simple Instruction Multiple Data (SIMD) parallelism are loop-based method and Superword Level Parallel (SLP) method. Focusing on the problem that the current compiler cannot realize function level vectorization, a method of function level vectorization based on static single assignment was proposed. Firstly, the variable properties of program were analysed, and then a set of compiling directives including SIMD function annotations, uniform clauses, linear clauses were used to realize function level vectorization. Finally, the vectorized code was optimized by using the variable attribute result. Some test cases from the field of multimedia and image processing were selected to test the function and performance of the proposed function level vectorization on Sunway platform. Compared with the scalar program execution results, the execution of the program after the function level vectorization is more efficient. The experimental results show that the function level vectorization can achieve the same effect of task level parallelism, which is instructive to realize the automatic function level vectorization.

Single Instruction Multiple Data (SIMD) extension; parallelism; function level vectorization; compiler directive; static single assignment

TP301.6; TP311.53

A

2016- 12- 29;

2017- 03- 21。

李穎穎(1984—)，女，河南鄭州人，講師，碩士，主要研究方向：先進(jìn)編譯技術(shù)； 高偉(1988—)，男，黑龍江齊齊哈爾人，博士研究生，主要研究方向：高性能計算、先進(jìn)編譯技術(shù)； 高雨辰(1988—)，男，河南鄭州人，碩士研究生，主要研究方向：先進(jìn)編譯技術(shù)； 翟勝偉(1982—)，男，河南鄭州人，工程師，碩士，主要研究方向：先進(jìn)計算； 李朋遠(yuǎn)(1989—)，男，河南焦作人，研究員，碩士，主要研究方向：高性能計算。

1001- 9081(2017)08- 2200- 09

10.11772/j.issn.1001- 9081.2017.08.2200