徐金龍，趙榮彩，劉 鵬，李曉亮

（1．?dāng)?shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，鄭州450001；2．解放軍93010部隊(duì)，沈陽110000）

1 概述

目前多數(shù)通用處理器上已經(jīng)集成了SIMD（Single Instruction Multiple Data）擴(kuò)展［1－4］。為了方便有效地使用這種向量并行部件，大部分編譯器也都集成了自動(dòng)向量化模塊［5－7］。為了實(shí)現(xiàn)更多程序的向量化，出現(xiàn)了很多面向向量化的分析方法，這些方法基本原理是依據(jù)數(shù)據(jù)依賴關(guān)系尋找可并行的語句，然后將可并行的語句用向量方式并行執(zhí)行［8］。

向量化是一種細(xì)粒度的并行化，不僅需要依賴關(guān)系滿足并行需求，對訪存模式也有較苛刻的要求。目前，多數(shù)編譯器自動(dòng)向量化模塊僅支持連續(xù)訪存模式。大量訪存模式較復(fù)雜的循環(huán)，編譯器直接放棄對其進(jìn)行向量化。GCC（GUN Compiler）和ICC（Intel C＋＋Compiler）的向量化模塊都嘗試支持某些不太復(fù)雜的訪存模式。GCC最初向量化模塊只支持loop－based向量化方法，某些偽跨幅訪存不能被正確識(shí)別，偽跨幅訪存是指：語句被孤立分析時(shí)，訪存不連續(xù)，但考慮迭代內(nèi)并行其訪存是連續(xù)的，因此，GCC引入了SLP算法發(fā)掘迭代內(nèi)并行，解決了偽跨幅訪存的問題［9］。ICC提供了一種高效的向量化方法來專門處理訪存跨幅為2的冪的情況［10］，并改進(jìn)了數(shù)據(jù)重組方式，可以充分利用Intel處理器提供的跨幅訪存指令。需要指出的是，GCC實(shí)際上并未支持跨幅訪存的向量化，它僅僅是在迭代內(nèi)發(fā)現(xiàn)了連續(xù)的訪存，ICC真正支持了跨幅訪存，但它支持的模式過于單一，難以支持較復(fù)雜的跨幅訪存，不具有通用性，也不能支持程序中普遍存在的非規(guī)則訪存。

本文提出一種面向向量化的非規(guī)則訪存識(shí)別及處理方法，以消除非規(guī)則的訪存對向量并行帶來的不利影響。

2 訪存特征的分類及檢測

2．1 訪存特征分類

本文提到的訪存特征是指：對程序中多條訪存指令訪問的內(nèi)存位置進(jìn)行總結(jié)后體現(xiàn)出來的性質(zhì)。本文概述中介紹了ICC和GCC的相關(guān)工作，對訪存特征進(jìn)行簡單分類為4種情況，例1是最簡單的連續(xù)訪存模式，例2是GCC可處理的偽跨幅訪存模式，例3是ICC可處理的簡單跨幅訪存，例4屬于不規(guī)則訪存模式。

本節(jié)提供一種更細(xì)致的分類方法。由于經(jīng)過向量化之后，數(shù)組的訪存通常會(huì)變換為向量訪存，而訪存指令一般對應(yīng)較大的執(zhí)行代價(jià)，因此向量化主要關(guān)注循環(huán)中數(shù)組的訪存特征，包括普通數(shù)組訪存和結(jié)構(gòu)體數(shù)組訪存。本文假定不同數(shù)組名之間不存在別名關(guān)系，因此，對同一數(shù)組的多次引用進(jìn)行分析才是有意義的。以普通數(shù)組訪存為例來介紹一種訪存特征分類方法。

數(shù)組訪存具有以下3個(gè)性質(zhì)：

（1）冗余性，即訪存是否存在冗余，對同一內(nèi)存位置的連續(xù)2次讀或?qū)戯@然是冗余的。冗余與非冗余的區(qū)別如圖1（a）所示。

（2）飽和性，某段連續(xù)內(nèi)存如果全被訪問到，那么就稱對這段內(nèi)存的訪問是飽和。飽和余非飽和的區(qū)別如圖1（b）所示。

（3）順序性，如果訪存的地址是鄰接遞增（遞減），或者通過合法的代碼變換可使訪存地址也具有這種性質(zhì)，則稱訪存是順序的，否則訪存是亂序的。順序與亂序的區(qū)別如圖1（c）所示。

圖1 數(shù)組訪存性質(zhì)示意圖

向量并行化分析過程中對訪存的上述3個(gè)性質(zhì)最為敏感，本文依據(jù)訪存是否冗余、是否飽和、是否順序?qū)⒃L存進(jìn)行詳細(xì)分類，結(jié)果如表1所示，其中，T表示TRUE；F表示FALSE。

2．2 訪存特征檢測

顯然，2．1節(jié)的訪存特征都是基于多條語句所涉及內(nèi)存的位置關(guān)系來確定的。訪存特征的檢測不僅要考慮統(tǒng)同一訪存語句在不同迭代（相鄰迭代）的內(nèi)存位置關(guān)系，也要考慮不同訪存語句在同一迭代中的內(nèi)存位置關(guān)系。這是因?yàn)?，僅對迭代內(nèi)基本塊進(jìn)行分析只能得到局部訪存特征，僅考慮迭代間又會(huì)忽略掉迭代內(nèi)的訪存特征，例如不能正確分析如例2所示的偽跨幅訪存。

訪存特征的檢測較復(fù)雜，為便于檢測，本文提出基于循環(huán)展開的訪存模式檢測方法：即先將目標(biāo)循環(huán)展開，分析被展開循環(huán)的訪存特征。本文方法的設(shè)計(jì)思想是，通過循環(huán)展開將迭代間訪存特征檢測轉(zhuǎn)移到迭代內(nèi)，然后在迭代內(nèi)實(shí)施統(tǒng)一檢測。

圖2展示了訪存模式檢測的詳細(xì)流程。

所謂西學(xué)之用，實(shí)為清廷應(yīng)對日趨嚴(yán)峻的外交局面，有限度地變更舊制勢在必行，被壓抑的入侵文化的聲音也因此得以顯現(xiàn)于譯文，現(xiàn)代法律意識(shí)的雛形伴隨著殖民權(quán)力的擴(kuò)張悄然扎根。盡管如此，中學(xué)為體的理念根深蒂固。洋務(wù)運(yùn)動(dòng)的中堅(jiān)兩江總督張之洞在《勸學(xué)篇》中甚至將三綱五常提升到國家民族生死存亡的高度：“保種必先保教，保教必先保國”(2002：1)。即便到了十九世紀(jì)末，維新變法的代表康有為依然鼓吹：“必有宋學(xué)義理之體，而講西學(xué)政藝之用，然后收其用也?！?/p>

圖2 訪存特征檢測流程

具體包括以下步驟：

（1）循環(huán)展開：SIMD向量并行實(shí)際上是一種全局串行，局部并行的并行方式。因此，面向SIMD的向量化只關(guān)注局部并行的幾次迭代，向量局部并行的迭代次數(shù)最多為VF，因此，將循環(huán)展開因子設(shè)置為VF，可將充足的迭代間訪存特征暴露在迭代內(nèi)。后續(xù)的討論中，假定VF＝4。針對例1～例4所示程序做循環(huán)展開可得到如下結(jié)果，顯然，例1和例2是無冗余飽和順序的，而例3和例4是無冗余非飽和順序的。

（2）訪存收集及分組：遍歷展開后的循環(huán)體基本塊，收集其中所有內(nèi)存引用，并為它們分組，依據(jù)分別為：讀寫類型、數(shù)組名稱、數(shù)組訪問索引系數(shù)。舉例來講，收集例1的展開版本中循環(huán)體中的引用，可得到3個(gè)分組：

其中，第1項(xiàng)是讀寫類型（R代表內(nèi)存讀，W代表內(nèi)存寫）；第2項(xiàng)為數(shù)組名稱；第3項(xiàng)為索引系數(shù)，最后一項(xiàng)為符合前3項(xiàng)的訪存對應(yīng)的內(nèi)存集合。

（3）冗余性檢查：遍歷步驟（2）所得到的所有分組，對每一個(gè)分組，遍歷組內(nèi)的訪存語句，對比任意2個(gè)訪存語句的內(nèi)存位置，若相同，那么存在冗余讀或?qū)?，?biāo)記這2條語句。

（4）飽和性檢查：遍歷步驟（2）所得到的所有分組，對每一個(gè)分組，遍歷組內(nèi)的訪存語句，尋找組內(nèi)語句訪存位置的頂端和底端，如果這之間的任何一個(gè)內(nèi)存位置都存在對應(yīng)的訪存語句，那么訪存是飽和的，否則，非飽和。

（5）順序性檢查：遍歷步驟（2）所得到的所有分組，對每一個(gè)分組，遍歷組內(nèi)的訪存語句，判斷訪存語句訪問的內(nèi)存位置是否為遞增或遞減的。

（6）結(jié)果匯總：根據(jù)冗余性－飽和性－順序性的檢測結(jié)果得到綜合特征。對某一循環(huán)進(jìn)行上述3個(gè)性質(zhì)綜合后能夠確定該循環(huán)的訪存特征屬于表1中的哪一類。

3 面向向量化的非規(guī)則訪存處理

（1）無冗余飽和順序模式是理想的訪存模式，如例1和例3，足夠的多次數(shù)組訪存可直接用向量訪存指令來代替。例1的對應(yīng)向量化代碼如圖3所示。顯然，向量化后的代碼將會(huì)帶來明顯的效率提升。

圖3 無冗余飽和順序模式代碼的向量化

（2）對于無冗余飽和亂序模式，從整體來觀察，多條語句的操作數(shù)訪存順序不對應(yīng)，如圖4所示，對數(shù)組a和數(shù)組b的訪問順序是一致的，數(shù)組c的訪問順序與前者不一致。將數(shù)組c讀進(jìn)向量寄存器后，需要調(diào)整數(shù)據(jù)的排序。通常數(shù)組訪存順序不一致的情況下，對其進(jìn)行向量化需要用向量訪存指令和混洗指令聯(lián)合實(shí)現(xiàn)。

圖4 無冗余飽和亂序模式代碼的向量化

（3）對于無冗余非飽和順序模式，相對于理想訪存模式的不同點(diǎn)在于非飽和，這意味著需要將不連續(xù)內(nèi)存中的數(shù)據(jù)裝載到向量寄存器中并保證內(nèi)存中不連續(xù)的數(shù)據(jù)在寄存器中是相鄰的。具體方法為：采用普通向量裝載指令裝載不連續(xù)的數(shù)據(jù)，使用混洗指令在向量寄存器中組成相鄰的數(shù)據(jù)。向量化結(jié)果如圖5所示。

圖5 無冗余非飽和順序模式代碼的向量化

（4）無冗余非飽和亂序模式，相對于模式3的不同點(diǎn)在于其亂序特性。由于可以采用數(shù)據(jù)混洗的方法來將亂序訪存調(diào)整為順序訪存，因此它的向量化方法類似于模式3對應(yīng)的方法，不同點(diǎn)在于混洗模式的配置，如圖6所示。

（5）上文已經(jīng)給出了表1中1～4的無冗余模式處理方法，對于存在冗余的情況，首先需要進(jìn)行冗余刪除，再按照上述的4種方法進(jìn)行向量化，如圖7所示。

圖7 存在冗余模式的向量化

4 非規(guī)則訪存向量化收益分析

4．1 必要性分析

第3節(jié)介紹了各種訪存模式的向量化方式，從中可知，非規(guī)則的訪存主要是通過規(guī)則向量訪存與向量混洗結(jié)合的的方法來實(shí)現(xiàn)向量化。向量化后生成的混洗指令數(shù)目是不同的，不同平臺(tái)的向量混洗的指令代價(jià)也是不同的，因此，向量化帶來并行收益的同時(shí)，也需要付出多余的向量重組代價(jià)，并不是所有的向量化都能帶來正收益，綜合收益可能為0或?yàn)樨?fù)。因此，必須通過精確的收益分析來指導(dǎo)向量化，若無收益或負(fù)收益，目標(biāo)循環(huán)保持串行執(zhí)行。

4．2 收益計(jì)算方法

向量化收益是指向量并行執(zhí)行相對于標(biāo)量串行執(zhí)行所帶來的性能提升，可以用串行標(biāo)量執(zhí)行代價(jià)（CS）減去并行向量執(zhí)行代價(jià)（CV）來刻畫，即：

并行向量執(zhí)行代價(jià)CS是指用標(biāo)量的方法將整個(gè)循環(huán)執(zhí)行完畢所需要的時(shí)間，即每條標(biāo)量指令執(zhí)行時(shí)間的疊加，如式（2）所示，其中，ITER為迭代次數(shù)；CSi為每條指令的執(zhí)行代價(jià)；m為基本塊內(nèi)標(biāo)量操作的數(shù)量。

并行向量執(zhí)行代價(jià)CV是指用向量的方法將整個(gè)循環(huán)執(zhí)行完畢所需要的時(shí)間，即每條向量指令執(zhí)行時(shí)間的疊，加如式（3）所示，其中，ITERV為向量化后的迭代次數(shù)；CVi為每條向量指令的執(zhí)行代價(jià)；n為基本塊內(nèi)向量操作的數(shù)量。

通過上述方法獲得向量化收益B，若B＞0，那么循環(huán)將被向量化，否則將保持串行執(zhí)行。

5 功能驗(yàn)證

本文選取了gcc的testsuite測試集中符合條件的測試用例，包括vect－10．c，slp－8．c，slp－11b．c。另外根據(jù)測試需要對上述用例作調(diào)整產(chǎn)生新的版本，例如，vect－2的核心循環(huán)為：

稍作改動(dòng)即可產(chǎn)生“非飽和版本”：

利用上述測試用例對本文提出的算法和GCC自動(dòng)向量化進(jìn)行測試得到如表2所示的結(jié)果。結(jié)果表明，本文方法可以處理文中提到的各類訪存類型的向量化，而GCC只能處理“非冗余－飽和－順序”的情況。顯然本文方法在面向復(fù)雜訪存類型處理方面強(qiáng)于GCC，達(dá)到了預(yù)期目標(biāo)。

表2 功能驗(yàn)證結(jié)果

需要指出的是，本文方法目前主要應(yīng)用于訪存類型比較明確的小循環(huán)，存在很多更復(fù)雜的訪存模式將影響本方法的使用，例如，代碼中既存在飽和訪存又存在非飽和訪存。這屬于需要進(jìn)一步研究的內(nèi)容，目前將直接跳過向量化階段。

6 結(jié)束語

目前多數(shù)自動(dòng)向量化算法的設(shè)計(jì)思路是：依據(jù)數(shù)據(jù)依賴關(guān)系尋找可并行的語句，通過循環(huán)變換使依賴關(guān)系符合向量化需求，然后將可并行的語句用向量方式并行執(zhí)行。然而，對于非規(guī)則的訪存研究者卻沒有提出統(tǒng)一的處理方法，非規(guī)則的訪存成為制約自動(dòng)向量化的關(guān)鍵因素之一。針對此情況，本文從訪存特征入手，提出對訪存特征的分類及檢測方法，并最終給出了面向不同特征的向量化方法。

本文主要針對程序中的訪存特征方面進(jìn)行討論，未將其他特征納入到考慮范圍，對此需要進(jìn)一步深入分析研究。此外文中提供的向量化收益分析的前提是整個(gè)循環(huán)全部被向量化，對于部分向量化的程序并不適用，后續(xù)工作將繼續(xù)完善非規(guī)則訪存的向量化收益分析模塊，使其具有更廣泛的適用性。

［1］Intel Corporation．Intel?64and IA－32Architectures Software Developer’s Manual［EB／OL］．［2014－11－15］．http：／／www．intel．com／Assets／PDF／manual／252046．pdf．

［2］Stewart J．An Investigation of SIMD Instruction Sets［D］．Ballarat，Australia：University of Ballarat，2005．

［3］Kahle J A，Day M N，Hofstee H P，et al．Introduction to the Cell Multiprocessor［J］．IBM Journal of Research and Development，2005，49（4）：589－604．

［4］D’Arcy P，Beach S．StarCore SC140：A New DSP Architecture for Portable Devices［Z］．1999．

［5］Amarasinghe S P，Anderson J A M，Lam M S，et al．An Overview of the SUIF Compiler for Scalable Parallel Machines［C］／／Proceedings of the 7th SIAM Con－ference on Parallel Processing for Scientific Computing．Philadelphia，USA：SIAM，1995：662－667．

［6］Naishlos D．Autovectorization in GCC［C］／／Proceedings of 2004GCC Developers Summit．Ottawa，Canada：［s．n．］，2004：105－118．

［7］Open64．Overview of the Open64Compiler Infrastructure［EB／OL］．［2014－11－15］．http：／／open64．source forge．net．

［8］Allen R，Kennedy K．現(xiàn)代體系結(jié)構(gòu)的優(yōu)化編譯器［M］．張兆慶，喬如良，馮曉兵，等，譯．北京：機(jī)械工業(yè)出版社，2004．

［9］Rosen I，Nuzman D，Zaks A．Loop－aware SLP in GCC［C］／／Proceedings of 2007GCC Summit．New York，USA：［s．n．］，2007：131－142．

［10］Nuzman D，Rosen I，Zaks A．Auto－vectorization of Inter－leaved Data for SIMD［J］．ACM SIGPLAN Notices，2006，41（6）：132－143．