張素平，韓 林，丁麗麗，王鵬翔

(數(shù)學工程與先進計算國家重點實驗室(信息工程大學)，鄭州 450001)

(*通信作者電子郵箱892841546@qq.com)

新型超字級并行改進算法

張素平*，韓 林，丁麗麗，王鵬翔

(數(shù)學工程與先進計算國家重點實驗室(信息工程大學)，鄭州 450001)

(*通信作者電子郵箱892841546@qq.com)

對于超字級并行(SLP)算法不能有效地處理大型程序中并行代碼率較小，且可向量化的代碼中可能存在對向量化不利的代碼的問題，提出了一種新型的SLP改進算法NSLPO。首先，將程序中不能向量化的非同構語句進行同構化處理，定位SLP丟失的向量化機會;然后，通過冗余節(jié)點添加構建最大通用子圖,通過冗余刪除等優(yōu)化過程得到同構化之后的補充SLP圖，提高程序中代碼的并行性；最后，運用節(jié)流法將對向量化有害的代碼摒除在向量化之外，僅對它們進行標量處理，通過只向量化處理那些向量化有收益的代碼以盡可能地提升程序效率。在一組廣泛使用的內核測試集中進行實驗，結果顯示，與SLP算法相比，NSLPO算法性能更優(yōu),其執(zhí)行時間比SLP平均減少9.1%。

同構；節(jié)流法；向量化；超字級并行；補充圖

0 引言

高性能計算的迅猛發(fā)展使得能耗、訪存和通信等技術面臨發(fā)展瓶頸，自動并行化軟件的發(fā)展是當下解決此問題的關鍵所在。1996年，Intel在其Pentium處理器上集成了MMX(Multi-Media Extension)之后，大多數(shù)處理器都開始集成單指令多數(shù)據(jù)(Single Instruction Multiple Data, SIMD)擴展部件[1]，以充分發(fā)掘處理器的計算和圖形處理能力。SIMD不僅可以提升特定應用程序的性能，還可以提高大多數(shù)程序的效率。當前向量化的方法一般分為兩種：一種是人為地將串行代碼改為單指令多數(shù)據(jù)的向量化代碼的手工向量化；另一種是運用編譯器對代碼進行自動向量化處理，即分析編譯器，在編譯器中增加代碼自動向量化的模塊，使其可以自動地實現(xiàn)向量化的功能。第一種方法要求程序員對應用程序的結構和數(shù)據(jù)布局有深刻認識，而且還要掌握目標平臺所支持的擴展體系結構和指令集的特點，才能夠正確地修改程序結構和數(shù)據(jù)布局使之適合利用SIMD來提取并行性。這個過程較為復雜且容易出錯，效果并不完美。在這個轉換的過程中有很多數(shù)據(jù)訪問模式不易被轉換，而且要想完美地實現(xiàn)代碼轉換，必須要對數(shù)據(jù)依賴和數(shù)據(jù)重用模型有很深入的理解。所以，現(xiàn)在比較通用且流行的方法是自動向量化。目前自動向量化的方法主要有借鑒向量機上的傳統(tǒng)向量化和面向基本塊的超字級并行(Superword Level Parallelism， SLP)向量化。傳統(tǒng)的向量化方法主要是發(fā)掘最內層循環(huán)中語句級別的并行性，一般情況下，最內層循環(huán)向量化易實現(xiàn)，代價小，但當最內層循環(huán)存在依賴環(huán)、歸約或者數(shù)組引用相對于最內層循環(huán)索引不連續(xù)時，內層向量化代價較大甚至無法向量化。

Larsen等[2]在2000年提出了SLP的概念，此算法是從直線型標量代碼開始進行自動向量化，而且在大多數(shù)編譯器如GCC、LLVM、icc等主流編譯器中均已實現(xiàn)。其基本過程主要是從store指令開始沿著數(shù)據(jù)依賴圖向上直到達到load指令或者不能向量化的指令才停止，運用貪婪算法的方式將標量指令打包成向量指令。但對于大型應用來說，這個過程存在兩個問題:1)利用SLP進行向量化的前提是語句同構，因為現(xiàn)存的SLP算法只能夠打包同構的語句，對于結構相異的語句則只能跳過，不予處理。然而，大型應用程序中并行化代碼即同構的語句所占比例相對于程序龐大的代碼來說非常小，這樣就可能大大地降低向量化的效率。2)程序中可以進行向量化處理的代碼中可能存在對向量化有害的代碼，即對這部分代碼進行向量化處理有可能損害整體代碼的效率，這些代碼可能需要將代碼從標量寄存器移進向量寄存器中而增加代價，從而損失向量化收益。因為SLP處理針對的是整體代碼，不能單獨處理局部，即使有些代碼對向量化有害，仍舊會對其進行向量化從而可能極大地損害整體的效率。為了解決這兩個問題，本文提出一種改進的SLP算法——NSLPO(New Superword Level Parallel Optimization)。首先，對于結構相似的語句進行同構化處理，增加其向量化的可能性；然后運用節(jié)流法，一步步判斷每一組包形成時的向量化收益，尋找向量化最優(yōu)子圖，在向量化還有收益時盡早停止向量化，阻止那些不利于向量化的代碼進行向量化處理，最大可能地保持整個代碼的收益。實驗結果顯示，在一組廣泛使用的內核測試集中，NSLPO比SLP的執(zhí)行時間平均減少9.1%。

1 直線型SLP及相關研究

1.1 直線型SLP

SIMD擴展是當下主要的并行化處理技術之一，先前的多媒體擴展只能夠支持數(shù)據(jù)長度較短的數(shù)據(jù)類型，目前新的擴展可以支持128位甚至Intel的AVX可以支持256位，AVX2可以支持512位的超字操作。為滿足實際需要,2000年Larsen等[2]首先提出了面向基本塊的SLP向量化方法，用以處理較寬數(shù)據(jù)類型的數(shù)據(jù)并行。

SLP算法的過程如下：首先利用相鄰的內存訪問作為打包的種子,然后通過定義-使用鏈和使用-定義鏈啟發(fā)式的擴展包,最后利用依賴關系調度包。

1.2 相關研究

SLP向量化經(jīng)常需要用到打包、解包操作。在使用SLP時，為了滿足SIMD操作超字的要求，超字語句中的操作需要以特定的順序放入向量寄存器中。如果超字中的原操作在向量寄存器中不可用，就需要使用昂貴的訪存指令和額外的向量寄存器重排序指令來從內存中引入數(shù)據(jù)并按照要求在向量寄存器中對它們進行重新組織，這個過程叫作超字打包。同樣地，為了滿足后續(xù)的使用，將超字中的操作分散開來時仍然會有額外的開銷，這個過程叫作超字解包。先前的研究顯示由于超字打包/解包的開銷太高以至于可能超出SLP所帶來的性能優(yōu)化。因此，在應用SLP時盡可能地減少打包/解包的開銷相當重要。打包沖突圖提供了更多包重用的機會，在包調度時決定包的執(zhí)行順序和包內語句的順序，以減少拆包的次數(shù)[3]。采用多元決策圖可以有效地表示包內的數(shù)據(jù)，減少拆包的次數(shù)[4]。SLP算法只能處理同構語句，所以，代碼中含有足夠的同構語句對代碼效率的提高相當重要。對于循環(huán)來說，為了得到足夠多的地址連續(xù)的同構語句，在SLP打包前先作循環(huán)展開。對外層作循環(huán)展開和壓緊、對內層作循環(huán)展開的包轉置，可以解決內層循環(huán)攜帶依賴、外層循環(huán)可以向量化但是數(shù)組引用相對于外層循環(huán)索引不連續(xù)的問題[5]。將標量打包為向量需要將數(shù)據(jù)從標量寄存器轉入或者轉出向量寄存器，在這個過程中，較好的處理向量寄存器可以盡可能地減少開銷，Shin等[6-7]開發(fā)了一種策略來管理向量寄存器文件，使之作為編譯控制緩存，以提高對本地數(shù)據(jù)的管理效力；不僅如此，他們還在文獻[8-9]的研究中使用控制流指令斷言時派生出了一種識別更多的超字級并行的大型基本塊。Nuzman等在文獻[10]中給出了一種支持插入數(shù)據(jù)的高效向量化編譯技術，在文獻[11]中則提出了短SIMD框架的外層循環(huán)向量化技術。Barik等[12]提出在接近機器層的底層IR上進行自動向量化，能在動態(tài)編譯時獲得更高的編譯效率。侯永生等[13]針對不能正規(guī)化的循環(huán)提出了一種展開壓緊算法，并用超字級并行向量化方法發(fā)掘展開壓緊從而提高程序的效率。徐金龍等[14]提出了一種分段約束的SLP發(fā)掘路徑優(yōu)化算法，采用段間的SLP發(fā)掘來約束循環(huán)展開所帶來的過多的發(fā)掘路徑。魏帥等[15]提出了一種面向SLP的多重循環(huán)向量化方法。索維毅等[16]對SLP自動向量化中的指令分析和冗余優(yōu)化算法進行了添加和改進，解決了由于依賴關系或者數(shù)據(jù)非對齊而使向量化效率不高的問題。每一種算法都從不同的角度對SLP算法進行改進以提升不同應用程序的效率。本文主要是針對大型應用中并行代碼的占有率較低，且向量化代碼中可能含有對向量化不利的代碼的問題進行改進，首先盡可能地同結構化非同構語句，增強代碼的并行性，然后通過節(jié)流的方法盡可能地保證程序的收益。

2 NSLPO算法

NSLPO算法首先對需要向量化的循環(huán)作一些通用的預處理，如循環(huán)展開，然后將結構相似但非同構的語句進行冗余節(jié)點添加，使得其結構相同[17]；接著用節(jié)流法[18]迭代地對每組可以向量化處理的指令包進行收益分析，對于每一組包，如果向量化處理其收益為正，則證明該包對向量化有利，否則有害。為保證整體代碼的效率，對于那些向量化有害的代碼就停止向量化，進行標量計算。

算法具體思路如下：

1)對標量代碼中需要的循環(huán)進行循環(huán)展開等預處理，盡可能地增加程序的并行性。

2)對那些結構相似但非同構的語句進行同結構化處理[17]。

3)用SLP算法尋找向量化種子指令，構建SLP圖。

4)用節(jié)流法計算所有的有效節(jié)流點[18]。

5)根據(jù)有效節(jié)流點對SLP圖進行處理，生成優(yōu)化節(jié)流子圖。

6)運用精確的代價模型計算并保存各個節(jié)流子圖的收益。

7)對所有節(jié)流點進行上述4)～6)處理，找出最優(yōu)節(jié)流子圖，并按照最優(yōu)節(jié)流子圖所示用向量代碼代替標量代碼。

3 非同構語句同結構化

SLP算法處理的都是同構指令，所以其前提是需要語句同構，但是大型應用程序中同構語句的比例有限，所以為了盡可能地提高程序的并行性，增加向量化的可能性，提高程序效率，可以先將非同構語句進行同結構化處理[17]，處理步驟如下：

2)通過添加盡可能少的冗余節(jié)點構建SLP的補充依賴圖。

3.1 定位SLP可能丟失的向量化機會

因為在代碼進行SLP處理之前已經(jīng)經(jīng)歷過很多優(yōu)化，如冗余節(jié)點刪除等，很可能將本來可以同構的依賴圖變成異構的依賴圖，從而在SLP算法處理同構語句時被SLP排除在外，使得其丟失了這些本來可以向量化的機會。所以，首先要構建語句依賴圖，嘗試擬組建超字語句組，盡可能地定位這些丟失的向量化機會。

3.2 構建SLP補充依賴圖

定位到SLP丟失的向量化機會后，通過在依賴圖中添加盡可能少的冗余節(jié)點同結構化非同構語句，構建SLP補充依賴圖。一般需要如下步驟：

1)構建最大通用子圖。尋找兩個圖的最大通用子圖一般被認為是一個NP問題，由于現(xiàn)實中圖都較小，文獻[19]中提出用接近于最優(yōu)算法的快速backtracking算法來解決這個問題。

2)構建最小通用超圖。比較最大通用子圖與原圖的差異，可以得到最小通用超圖。例如，如果g1和g2是原圖，MCS是g1和g2的最大通用子圖，那么最小通用超圖MinS=MCS+dif1+dif2,其中:dif1=g1-MCS，dif2=g2-MCS。

3)經(jīng)過插入節(jié)點選擇、冗余刪除等步驟得到SLP補充依賴圖。

北辰教堂不僅在教牧人員內部組織對十九大精神、黨的宗教方針政策、《宗教事務條例》等法律法規(guī)的學習，更通過“北辰教堂宣傳文化走廊”、一年一次的“愛國愛教、遵紀守法”宣傳周等活動，對廣大信眾進行宣傳教育，教導廣大信眾，做愛國愛教、知法守法的好公民。

針對如下所示源碼，先構建其數(shù)據(jù)依賴圖如圖1(a)所示。如果按照SLP算法，則圖1(b)為其SLP依賴圖，從數(shù)據(jù)依賴圖中可得其可向量化處理的指令組有2組。因為SLP算法是從store指令開始，自底向上地搜索同類型的指令組，如果遇到load指令或者不能向量化的指令(如圖1(c)中兩指令類型不同)時就停止，最終只得到2個SLP指令組。而運用同結構化算法可得圖1(d)的SLP補充圖，此算法通過給依賴圖添加盡可能小的冗余節(jié)點來實現(xiàn)語句非同構語句同結構化處理，最終將圖1(a)的異構依賴圖補充為圖1(d)的同結構化數(shù)據(jù)依賴圖，由此補充依賴圖可以得到5組SLP指令組如圖1(e)所示。由此可以看出，在進行SLP處理之前，先將非同構語句進行同結構化處理可以大大地提高程序的并行性，從而達到提高程序效率的目的。

Float B[N]; Float C[N]; ? C[i]=B[i]*3.0+2.0; C[i+1]=B[i+1]+1.0; ?

4 節(jié)流優(yōu)化

當要處理的語句已進行同構化處理后，即基本上很多語句都可以進行向量化處理了，但是，由于SLP算法向量化處理代碼是以代碼的整體來計算收益的，不能分別計算每個語句中的操作組的收益，所以，代碼中可能含有對向量化有害的部分不能被它發(fā)掘出來，從而可能降低向量化的收益。本文采用節(jié)流優(yōu)化處理，即對每一個打包指令集分別計算其向量化收益，如果向量化處理該指令集收益為正，則進行向量化處理，否則按照標量處理。

圖1 同構化異構語句

4.1 節(jié)流處理過程

節(jié)流優(yōu)化處理過程如下，它前面的處理跟SLP算法相同，只是在后面計算指令代價時進行不同處理。

1)按照SLP算法的思路向量化種子指令集。這些指令一般包括：非依賴的內存指令，訪問相鄰內存地址；歸約指令；無依賴的簡單指令。由于相鄰內存訪問指令是最有優(yōu)勢的種子指令，所以大多數(shù)編譯器都首選此類指令作為種子指令。

2)從種子指令開始根據(jù)數(shù)據(jù)依賴圖構建最初的向量化指令組。一般都是從Store指令開始沿著數(shù)據(jù)依賴圖自底向上直到load指令或者不能向量化的指令為止。每一組首先要指出可以被向量化的標量指令，以及它的相關輔助數(shù)據(jù)，如該組的代價。

3)當數(shù)據(jù)依賴圖構建完畢時，SLP會運用特定平臺的代價模型靜態(tài)評估代碼性能，評估每條指令的向量代價Vcost和標量代價Scost,代價差異用Dfcost表示，如式(1)所示。

Dfcost=Vcost-Scost

(1)

4)如果Dfcost為負數(shù)，則表明該指令向量化對這個組來說是有收益的，否則為有害的。為了得到一個精確的代價，算法會將標量與向量之間的數(shù)據(jù)轉換所需要的額外指令(收集和擴散指令)計算在內，用SGcost表示(一般用一個收集或者擴散指令，其值就加1)。然后計算出總的代價Tlcost，它包括所有組的代價以及額外代價，如式(2)所示。

(2)

如果Tlcost<0，則說明向量化是有收益的，否則沒有。只有當向量化形式的代價比標量形式代價小時，向量化才是有收益的。

5)根據(jù)節(jié)流法計算每個節(jié)流子圖所有指令的總的代價差異，選擇代價差異最小圖的來作為最優(yōu)節(jié)流子圖，然后用SLP向量化最優(yōu)節(jié)流子圖，其余部分則標量處理，盡可能地保證向量化的收益。

SLP算法對實現(xiàn)程序完整向量化效用良好，但是它忽略了另一種收益形式，即代碼中部分代碼向量化有收益，其他部分則沒有收益的情況。SLP算法將代碼依賴圖當作一個獨立的不可分割的區(qū)域，它只能對其整體作向量化性能評估，從而確定對該代碼向量化是否有性能提升。但是如果代碼中部分向量化有收益，另一部分則對性能有損害，從而可能造成整體向量化性能為無收益的結果，就表示該代碼不能進行向量化處理或者最終的向量化結果非最優(yōu)狀態(tài)。圖2針對下述代碼展示了一個新型SLP改進算法的實現(xiàn)過程。

FloatA[N],B[N],C[N],D[N],E[N]; ?E[i]=(A[i]+(B[2*i]*(C[2*i]+ (D[2*i]*B[2*i]))))*3.0+1.0;

E[i+1]=(A[i+1]+(B[3*i]*(C[3*i]+ (D[3*i]*B[3*i]))))+2.0;

?

圖2(a)是上述代碼的數(shù)據(jù)依賴圖。數(shù)組E[]存儲數(shù)組A[]、B[]、C[]和D[]的計算結果。其中，E[i]和E[i+1]是連續(xù)的內存地址，與A[i]和A[i+1]中的load相同，但是來自于另外幾個數(shù)組的load則是非連續(xù)的(由數(shù)組的索引2*i和3*i可知)。圖中單獨的圓形load為非連續(xù)的load，大多向量化方法都不能實現(xiàn)這些非連續(xù)load的向量化處理?，F(xiàn)在對這些代碼進行SLP處理：因為圖2(a)所示兩個數(shù)據(jù)依賴圖不是同構的，所以應用異構語句同構化方法[17]對其作同構化處理得到圖2(b)。接著用SLP算法對其進行向量化處理：首先定位種子指令，即相鄰內存訪問指令，圖中E[i]和E[i+1]中的stores,它們形成一個個打包組g1(即圖2(c)中SLP圖的根)；然后算法根據(jù)依賴圖自底向上，嘗試把相同類型的指令構成更多的指令組；其他的乘指令、加指令以及來自A[]的指令也分別構成不同的指令組(從g2到g11),而來自于非連續(xù)內存地址訪問的load(數(shù)組B[]、C[]和D[]的loads)則保持標量執(zhí)行。每一個標量節(jié)點的數(shù)據(jù)如果被向量組使用則需要一個額外的插入指令將標量數(shù)據(jù)插入向量寄存器中，其代價會變大，因為每一個標量load的向量化代價都加1，所以如圖2(c)所示每一個圓形的load上該節(jié)點的代價差異都有一個+1的標識。一旦數(shù)據(jù)被插入向量寄存器中，它就可以在任何需要的時候從向量化寄存器中被讀出從而被重用，如圖2(c)中的g9和g11都可以重用數(shù)組B[]的數(shù)據(jù)。

圖2 新型SLP改進算法實現(xiàn)過程

算法向量化處理的性能由編譯器的代價模型來評估，代價模型可以評估出每條指令的代價。在我們使用的目標編譯器GCC代價模型中，每條指令代價顯示為1。圖2(c)中依賴圖節(jié)點都標有代價差異，組g1的差異代價Dfcost為-1，表示如果兩個stores指令向量化處理，其代價為1；但如果依然按標量處理，其代價為2，保持標量處理的指令代價差異為0。任何用來支持向量化處理的額外的指令，如插入指令，還有同構化處理時的選擇指令，都有一個正數(shù)的代價差異，因為如果保持標量狀態(tài)的開銷就不會使用它們。然后計算整體代價Tlcost,圖2(c)的整體代價為1，意味著向量化處理這段代碼沒有收益(只有當整體代價為負時，才表示向量化有收益)。

圖2(c)向量化處理之所以沒有收益主要是因為以g10為根的子圖對向量化來說是有害的(它的總代價為正4)。因為SLP算法將代碼看作一個整體，所以它不能識別出這些問題。為了改進這個狀況，在此處運用節(jié)流法將那些向量化處理時損害大于收益的代碼子區(qū)域分割出來，單獨計算其代價，如圖2(c)所示，在組g10處將其分割，以g10為根的子圖進行標量處理，而下面的部分則向量化處理，此時總代價Tlcost為-3，說明向量化是有收益的。

而Vanilla提出的SLP[2]只評估一次數(shù)據(jù)依賴圖的代價，而且評估的是它的整體代價，它不會以任何方式來改變圖，其缺點之一就是它不會移除圖中的任何一部分，即使這些部分向量化處理時對整體向量化性能有所損害。

4.2 計算有效節(jié)流點

要得到最優(yōu)節(jié)流子圖，首先需要計算出有效節(jié)流點。針對圖2以每個節(jié)點為根的子圖如圖3所示，根據(jù)每個子圖中的指令代價計算出其總代價，找出代價最小的子圖，即最優(yōu)子圖。根據(jù)圖2(c)中所標示的差異代價計算其代價得到表1數(shù)據(jù)。表1中：RootNode表示節(jié)點；SubTlcost表示以該節(jié)點為根的子圖向量化的總代價；Tlcost表示對子圖標量處理，對剩余圖進行向量化處理的總代價。由表1可以看出g4和g10為最優(yōu)節(jié)流點，由于后續(xù)處理的原因，需要盡可能多地向量化代碼，所以在同樣代價時，選擇g10作為節(jié)流點，在向量化處理時，對g10子圖作標量處理，對剩下的部分進行向量化處理。

表1 節(jié)流點子圖代價

圖3 節(jié)流子圖

5 算法偽代碼

構建節(jié)流SLP子圖集的偽代碼如下：

1)

輸入：SLP依賴圖

2)

輸出：SLP依賴圖的節(jié)流子圖集

3)

if(st==samestruct);

//判斷SLP圖是否同構

4)

Cutsubgraph();

//若返回true,直接調用節(jié)流函數(shù)；

5)

else

6)

{

7)

Samestruct(g1,g2)

//若返回false,則表示非同構,調用同結構化函數(shù)

8)

{

9)

insertMinNodes();

//根據(jù)需要計算插入最小冗余節(jié)點

10)

creatMaxS();

//構建最大通用子圖

11)

deletenodes();

//進行冗余刪除等處理

12)

returng3;

//返回同構化數(shù)據(jù)依賴圖g3;

13)

}

14)

}

15)

Cutsubgraph()

//對g3進行節(jié)流處理

16)

{

17)

Firstcut_subgraphs(g3)

//首先進行首處理函數(shù)，初始化依賴圖

18)

{

19)

root=g3.getroot();

20)

init_g();

21)

init_g.addnode(root);

22)

Latercut_subgraphs();

23)

}

24)

Latercut_subgraphs(sg)

//遞歸調用后處理函數(shù)

25)

{

26)

if(sgingset)

//sg在節(jié)流子圖集gset

27)

return;

28)

gset.insert(sg);

//將子圖插入節(jié)流子圖集中

29)

for(子圖的鄰近節(jié)點neighbor)

30)

{

31)

if(neighbor在sg中)

32)

Continue;

33)

sg_cp=copysg(sg);

//復制子圖

34)

sg_cp.addnode(neighbor);

35)

Latercut_subgraphs(sg_cp)

//遞歸調用后處理函數(shù)

36)

}

37)

}

38)

}

算法給出了生成有效節(jié)流子圖集的核心函數(shù)的輸入是依賴圖，輸出是節(jié)流子圖集(gset),即包含根節(jié)點的相關子圖。算法包含兩個主函數(shù)：同結構化函數(shù)Samestruct()和節(jié)流函數(shù)Cutsubgraph()。同結構化函數(shù)包含插入最小冗余節(jié)點insertMinNodes()、構建最大通用子圖creatMaxS()以及冗余刪除deletenodes()等內容。節(jié)流函數(shù)則主要包含兩個函數(shù)，首處理函數(shù)Firstcut_subgraph()和后處理函數(shù)Latercut_subgraphs()。這兩個函數(shù)分別可以遞歸的調用本身，首處理函數(shù)創(chuàng)造一個初始化圖init_g,它只包含初始化根節(jié)點，然后把它作為參數(shù)調用遞歸函數(shù)，遞歸函數(shù)是算法的計算核心，即將輸入子圖保留，然后每次增加一個相鄰節(jié)點并遞歸處理來擴展它，如果該圖已在有效節(jié)流子圖集中，則退出計算，否則將子圖插入到子圖集中。下面函數(shù)迭代地遍歷子圖中所有相鄰節(jié)點并逐一將它們插入子圖中，如果該節(jié)點已存在于子圖中，則跳過它；否則，創(chuàng)建一個包含鄰近節(jié)點的子圖副本(sg_cp)，然后將結果子圖作為一個遞歸的參數(shù)繼續(xù)調用后處理函數(shù)，直到所有的節(jié)點都遍歷完畢，得到所有的節(jié)流子圖。

得到子圖后，必須知道子圖中的代碼應該被向量化還是串行執(zhí)行。為了得到更好的性能提升，算法需要一個精確的代價模型，該模型能夠評估每種情況下的反應時間。GCC中的代價模型計算的代價等于所有單個指令代價的總和，每個指令的代價等于其花費在目標機器(比如x86/AVX2)上的執(zhí)行時間，但是如果存在流入或流出向量代碼的標量數(shù)據(jù)流，或者流入或流出標量代碼的向量數(shù)據(jù)流，則還需要把執(zhí)行數(shù)據(jù)移動的指令花費的時間添加到總的代價中。這些代價均和目標相關，并能夠通過代價模型計算出來。該代價模型簡單易懂，對目標流水的指令調度也能夠作精準的計算，特別是簡單有序的結構。

6 實驗評估

6.1 實驗環(huán)境

實驗平臺CPU主頻為2.10GHz，內存為2GB，L1數(shù)據(jù)cache為32KB，L2數(shù)據(jù)cache為256KB，基本頁面為8KB的E5- 2620v2型處理器，有6個處理器核。 操作系統(tǒng)內核為Linux2.6.18，版本為RedhatEnterpriseAS5.0，目前可以支持256位的向量計算。

6.2 實驗結果及分析

在GCC5.1.0編譯器上進行了實驗，用本文算法對現(xiàn)存的SLP算法作了一個擴展處理，用SPEC2006(StandardPerformanceEvaluationCorporation2006)[20]和NPB(NASparallelbenchmarksuite)[21]的以及MediaBenchII[22]和Polybench[23]的一些標準對本文算法進行了實驗評估，表2中給出了所用數(shù)據(jù)的詳細信息。

表2 實驗所用數(shù)據(jù)信息

在GCC中，-O3選項可以默認將向量化打開，所以在測試時最基本的選項就是-O3，然后在此基礎上再添加其他優(yōu)化選項，如循環(huán)展開、循環(huán)分布等，因為在預處理時可能用到循環(huán)展開，所以在測試時，把-O3、-funroll-loops(循環(huán)展開)等作為基礎的編譯選項，對基礎選項、以及基礎選項加SLP優(yōu)化、基礎選項加本文算法優(yōu)化三組數(shù)據(jù)作對比，結果如圖4所示。在實驗中，將只加基礎選項的組叫作基礎優(yōu)化，在圖中用Base來表示；加SLP優(yōu)化的稱為SLP優(yōu)化，在圖中用SLP表示；而本文算法優(yōu)化稱作新型SLP優(yōu)化，在圖中用NSLPO表示。實驗結果顯示，本文算法的執(zhí)行時間比基礎優(yōu)化減少了17.6%，比SLP減少了9.1%。

圖4顯示了在X86平臺上GCC編譯器中在基礎選項、SLP優(yōu)化以及新型SLP優(yōu)化三種優(yōu)化的性能對比，為了方便處理，computerhs、multsu3matvecsum4dir、ewaldLRcorrection、computertrianglebbox、lbmhandlelnOutFlow、su3-adjoint、jdct-ifast、floyd-warshall程序分別用數(shù)字1～8代表。由圖中可以看出，對大多數(shù)程序來說，新型SLP優(yōu)化性能都優(yōu)于SLP以及基礎優(yōu)化。新型SLP優(yōu)化最高能優(yōu)于基礎優(yōu)化49%(如jdct-ifast)，速度超出SLP優(yōu)化15%(computetrianglebbox)。computerhs和multsu3matvecsum4dir在新型SLP改進算法下有收益，但是在SLP算法下則沒有，這是因為SLP依賴圖中含有對向量化有害的代碼，所以代價模型評估時會得出這些代碼的向量化代價大于標量執(zhí)行代價；而SLP改進算法則可以將這些對向量化有害的代碼從整體中移除，只向量化那些向量化處理后有收益的代碼，對于有害的代碼則保持標量執(zhí)行，從而可以很大程度上提高向量化代碼的比率，提高程序的執(zhí)行效率。

ewald-LRcorrection和computetriangle-bbox無論是在SLP優(yōu)化下還是SLP改進算法優(yōu)化下性能都優(yōu)于基礎優(yōu)化，在這兩個程序中，由GCC代價模型評估出的向量化的代價都小于標量執(zhí)行的代價，所以，它們對程序來說有性能提升。從圖4可以看出，SLP改進算法性能優(yōu)于SLP算法。

圖4 基礎優(yōu)化、SLP優(yōu)化、NSLPO性能對比

核心jdct-ifast包含兩個不同類型的代碼，它們均在NSLPO中有收益。jdct-ifast源碼中包含同構計算，這些同構計算在經(jīng)過高級優(yōu)化時變成了非同構的計算，如圖5所示，它的優(yōu)點是實現(xiàn)了歸約。jdct-ifast源碼實現(xiàn)了一系列的數(shù)組常量的乘計算，有些值在數(shù)組中是平方數(shù)，這些特定值的乘指令歸約主要歸功于邏輯左移，因此打破了同構，所以，SLP算法不能對其實現(xiàn)向量化處理，然而本文的NSLPO算法由于包含同結構化異構語句這一模塊，所以可以實現(xiàn)它的向量化，從而能提高程序的處理效率。

圖5 由高級優(yōu)化引發(fā)的非同構(jdct-ifast)

盡管以上整體性能測試結果已經(jīng)能很好地說明NSLPO效果良好，但是，靜態(tài)測試結果也相當重要，因為靜態(tài)結果可以很好地展示在沒有其他干擾的情況下，一個精確的代價模型對該算法的性能評估，靜態(tài)結果是基于每一個向量化圖的整體代價，顯示了在一個特定代價模型下SLP和NSLPO的結果比較。NSLPO經(jīng)?？梢宰钚』粋€圖的代價，而SLP則只能用整體圖的代價來決定是否對代碼實行向量化處理。

圖6顯示了標量、SLP優(yōu)化、NSLPO優(yōu)化的整體靜態(tài)代價，應用GCC的代價模型，為了得到一個更加有意義的測試，這個代價是每一個工作的標量代價總和的形式化圖，由圖可以看出，就算不考慮真正的性能提升，NSLPO也成功地降低了向量化的代價。平均看來，NSLPO降低了約23%的代價，SLP也降低了約12%的代價。

所以，不論從整體性能還是靜態(tài)代價分析來看，本文的改進算法NSLPO性能都優(yōu)于SLP算法；而且本文方法應用了多種通用測試集中的程序進行了實驗，其結果顯示了應用有普遍性和可適用性。

7 結語

本文提出了一種SLP算法的改進算法NSLPO，該算法首先通過將非同構的語句進行同結構化處理，增加并行化代碼的比率；然后運用節(jié)流法對同構圖中的指令進行處理，消除那些能夠被向量化但是阻礙程序性能提升的代碼。該算法從原始SLP圖中生成各種子圖集合，并通過代價模型找出向量化性能最好的子圖，最后只向量化子圖中的語句，其他對向量化不利的語句則進行串行執(zhí)行的方式。SLP算法只能整體處理代碼，如果部分代碼向量化有收益，另一部分向量化有損害，也可能導致整體代碼向量化有損害，經(jīng)過SLP的代價分析，該代碼最后則不能進行向量化處理；而本文提出的算法可以很好地解決這個問題，不僅可以增加代碼向量化的效率，也可以提升程序的性能。從實驗結果來看，本文算法的性能良好，再加上它的適用性較為廣泛，雖然它的實現(xiàn)還需要較為精確的代價模型來配合，但是像GCC和LLVM這些通用的大型編譯器本身都具有一個較為好的代價模型，所以該算法具有一定通用性。

)

[1] 高偉,趙榮彩,韓林,等.SIMD自動向量化編譯優(yōu)化概述[J].軟件學報,2015,26(6):1265-1284.(GAOW,ZHAORC,HANL.ResearchonSIMDauto-vectorizationcompilingoptimization[J].JournalofSoftware, 2015, 26(6): 1265-1284.)

[2]LARSENS,AMARASINGHES.Exploitingsuperwordlevelparallelismwithmultimediainstructionsets[J].ACMSIGPLANNotices, 2000, 35(5): 145-156.

[3]TOUMAVITISG,WANGZ,FRANKEB,etal.Towardsaholisticapproachtoauto-parallelization:integratingprofile-drivenparallelismdetectionandmachine-learningbasedmapping[J].ACMSIGPLANNotices, 2009, 44(6): 177-187.

[4]HIROAKIT,AKEUCHIY,SAKANUSHIK,etal.Packinstructiongenerationformediaprocessorsusingmulti-valueddecisiondiagram[C]//Proceedingsofthe4thInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis.NewYork:ACM, 2006: 154-159.

[5]TENLLADOC,PIUELL,PRIETOM,etal.Improvingsuperwordlevelparallelismsupportinmoderncompilers[C]//CODES+ISSS’05:Proceedingsofthe3rdIEEE/ACM/IFIPInternationalConferenceonHardware/softwareCodesignandSystemSynthesis.Piscataway,NJ:IEEE, 2005: 303-308.

[6]SHINJ,CHAMEJ,HALLMW.Compiler-controlledcachinginsuperwordregisterfilesformultimediaextensionarchitectures[C]//PACT’02:Proceedingsofthe2002InternationalConferenceonParallelArchitectures&CompilationTechniques.Piscataway,NJ:IEEE, 2002: 45-55.

[7]SHINJ,CHAMEJ,HALLM.Exploitingsuperword-levellocalityinmultimediaextensionarchitectures[J].JournalofInstruction-LevelParallelism, 2003, 5: 1-28.

[8]SHINJ.Compileroptimizationsforarchitecturessupportingsuperword-levelparallelism[D].LosAngeles,CA:UniversityofSouthernCalifornia, 2005.

[9]SHINJ,HALLM,CHAMEJ.Superword-levelparallelisminthepresenceofcontrolflow[C]//CGO’05:Proceedingsofthe2005InternationalSymposiumonCodeGenerationandOptimization.Washington,DC:IEEEComputerSociety, 2005: 165-175.

[10]NUZMAND,ROSENI,ZAKSA.Auto-vectorizationofinterleaveddataforSIMD[J].ACMSIGPLANNotices, 2010, 41(6): 132-143.

[11]NUZMAND,ZAKSA.Outer-loopvectorization:revisitedforshortSIMDarchitectures[C]//PACT’08:Proceedingsofthe2008InternationalConferenceonParallelArchitecturesandCompilationTechniques.NewYork:ACM, 2008: 2-11.

[12]BARIKR,ZHAOJ,SARKARV.EfficientselectionofvectorInstructionsusingdynamicprogramming[C]//MICRO’43:Proceedingsofthe2010IEEE/ACMInternationalSymposiumonMicroarchitecture.Washington,DC:IEEEComputerSociety, 2010: 201-212.

[13] 侯永生, 趙榮彩, 高偉.非正規(guī)化循環(huán)的單指令多數(shù)據(jù)向量化[J].計算機應用,2013,33(11):3149-3154.(HOUYS,ZHAORC,GAOW.Singleinstructionmultipledatavectorizationofnon-normalizedloops[J].JournalofComputerApplications, 2013, 33(11): 3149-3154.)

[14] 徐金龍,趙榮彩,韓林.分段約束的超字并行向量發(fā)掘路徑優(yōu)化算法[J].計算機應用,2015,35(4):950-955.(XUJL,ZHAORC,HANL.Vectorexploringpathoptimizationalgorithmofsuperworldlevelparallelismwithsubsectionconstraints[J].JournalofComputerApplications,2015, 35(4): 950-955)

[15] 魏帥,趙榮彩,姚遠.面向SLP的多重循環(huán)向量化[J].軟件學報,2012,23(7):1717-1728.(WEIS,ZHAORC,YAOY.Loop-nestauto-vectorizationbasedonSLP[J].JournalofSoftware, 2012, 23(7): 1717-1728.)

[16] 索維毅,趙榮彩,姚遠,等.面向DSP的超字并行指令分析和冗余優(yōu)化算法[J].計算機應用,2012,32(12):3303-3307.(SUOWY,ZHAORC,YAOY,etal.SuperwordlevelparallelisminstructionanalysisandredundancyoptimizationalgorithmonDSP[J].JournalofComputerApplications, 2012, 32(12): 3303-3307.)

[17]PORPODASV,MAGNIA,JONESTM.PSLP:paddedSLPautomaticvectorization[C]//CGO’15:Proceedingsofthe13thIEEE/ACMInternationalSymposiumonCodeGenerationandOptimization.Washington,DC:IEEEComputerSociety, 2015: 190-201.

[18] PORPODAS V, JONES T M.Throttling automatic vectorization: when less is more [C]// Proceedings of the 2015 International Conference on Parallel Architecture & Compilation.Piscataway, NJ: IEEE, 2015: 432-444.

[19] WOLFE J M.High Performance Compilers for Parallel Computing[M].Boston, MA: Addison-Wesley, 1995: 225-231.

[20] Spec cpu2006 [EB/OL].[2016- 04- 06].http://www.spec.org/cpu2006/.

[21] NAS parallel benchmark suite [EB/OL].[2016- 04- 06].http://www.nas.nasa.gov/ Resources/Software/npb.html

[22] FRITTS J E, STEILING F W, TUCEK J A, et al.MediaBench Ⅱ video: expediting the next generation of video systems research [J].Microprocessors & Microsystems, 2005, 33(4): 301-318.

[23] POUCHET L N.PolyBench: the polyhedral benchmark suite [EB/OL].[2016- 04- 06].http://www.cs.ucla.edu/?pouchet/software/polybench/, 2012.

This work is partially supported by the National High Technology Research and Development Program (HeGaoJi Program) of China (2009ZX01036- 001- 001- 2).

ZHANG Suping, born in 1991, M.S.candidate.Her research interests include HPC, advanced compiler technology.

HAN Lin, born in 1978, Ph.D, associate professor.His research interests include HPC, advanced compiler technology.

DING Lili, born in 1992, M.S.candidate.Her research interests include HPC, advanced compiler technology.

WANG Pengxiang, born in 1988, M.S.candidate.His research interests include HPC, advanced compiler technology.

New improved algorithm for superword level parallelism

ZHANG Suping*, HAN Lin, DING Lili, WANG Pengxiang

(StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing(InformationEngineeringUniversity),ZhengzhouHenan450001,China)

For SLP (Superword Level Parallelism) algorithm cannot effectively process the large-scale applications covered with few parallel codes, and the codes which can be vectorized may be adverse to vectorization.A new improved algorithm for SLP was proposed, namely NSLPO.First of all, the non-isomorphic statements which cannot be vectorized were transformed to isomorphic statements as far as possible, thus locating the opportunities of vectorization which SLP has lost.Secondly, the Max Common Subgraph (MCS) was built by adding redundant nodes, and the supplement diagram of SLP was got by using some optimization such as redundancy deleting, which can greatly increase the parallelism of program.At last, the codes which are harmful to vectorization were exclued out of vectorization by using cutting method and executed in serial, only the valuable codes for vectorization were vectorized to improve the efficiency of programs as far as possible.Experiments were conducted on widely used kernel test sets.The experimental results show that compared with the SLP algorithm, the proposed NSLPO algorithm has better performance and its running time was reduced by 9.1%.

isomorphism; cutting method; vectorization; Superword Level Parallelism (SLP); supplement diagram

2016- 07- 31;

2016- 10- 24。 基金項目:“核高基”國家科技重大專項(2009ZX01036- 001- 001- 2)。

張素平(1991-),女,河南禹州人,碩士研究生,主要研究方向:高性能計算、先進編譯技術; 韓林(1978-),男,山東臨沂人，副教授,博士,主要研究方向:高性能計算、先進編譯技術; 丁麗麗(1992-),女,河南商丘人，碩士研究生, 主要研究方向:高性能計算、先進編譯技術; 王鵬翔(1988-),男,河南安陽人，碩士研究生, 主要研究方向:高性能計算。

1001- 9081(2017)02- 0450- 07

10.11772/j.issn.1001- 9081.2017.02.0450

TP314

A