向量化友好的循環(huán)分塊因子選擇算法

柴曉菲，劉 松，屈 彬，王 倩，伍衛(wèi)國

西安交通大學(xué) 電子與信息工程學(xué)部，西安 710049

1 引言

在許多計算密集型應(yīng)用程序中，特別是科學(xué)和工程計算應(yīng)用程序，嵌套循環(huán)會耗費大部分的運行時間，成為亟待解決的程序熱點[1]。循環(huán)分塊[2-7]是一種應(yīng)用廣泛的循環(huán)優(yōu)化技術(shù)，通過仿射變換對程序的嵌套循環(huán)部分進行代碼轉(zhuǎn)換，一方面增強程序的數(shù)據(jù)局部性，降低cache失效率；另一方面開發(fā)循環(huán)代碼的粗粒度并行性，充分利用多核處理器的計算性能。分塊后的循環(huán)迭代根據(jù)分塊因子大小重置訪存順序，從而減小數(shù)據(jù)重用距離。因此，分塊因子大小的選擇對循環(huán)分塊代碼的性能有著重要的影響。近年來，隨著SIMD擴展部件在微處理器和協(xié)處理器中的發(fā)展，向量寄存器的位數(shù)逐漸增加，使得自動向量化技術(shù)在開發(fā)嵌套循環(huán)的細(xì)粒度并行性方面得到有效提高[8-10]。但是，循環(huán)分塊的分塊因子大小不僅影響程序的局部性，也影響程序的自動向量化收益。因此，如何選擇合適的分塊因子，在保持程序訪存局部性的同時充分利用向量化收益，對程序性能的提高具有積極的意義。

早期比較成熟的循環(huán)分塊因子選擇算法（Tile Size Selection，TSS）主要以改善程序局部性和開發(fā)程序粗粒度并行性為優(yōu)化目標(biāo)，而近年來提出的TSS算法不僅考慮了以上目標(biāo)，還將開發(fā)程序的細(xì)粒度并行性作為一個優(yōu)化目標(biāo)。Feld等人[11]通過限定可向量化循環(huán)層的分塊因子為向量因子（即向量寄存器可存放的最大操作數(shù)數(shù)目）的倍數(shù)關(guān)系來避免非對齊數(shù)據(jù)訪問，并通過分析程序的內(nèi)存訪問模式，以最大化利用L1級cache為目標(biāo)來確定最外層循環(huán)的分塊因子。Mehta等人[12]通過對建立的TSS模型進行分析，指出在某些嵌套循環(huán)中，循環(huán)分塊與向量化存在相互制約的關(guān)系，即循環(huán)分塊會對循環(huán)迭代進行分割而向量化則需要較長的循環(huán)迭代，因此對可向量化循環(huán)層不進行分塊處理。此后，Mehta等人[13]針對訪存數(shù)組規(guī)模較大的嵌套循環(huán)，提出了一種改進的TTS模型，以充分利用微處理器的數(shù)據(jù)預(yù)取功能。雖然以上這些算法考慮了分塊因子對向量化的影響，但是并沒有量化地分析不同分塊因子對向量化收益的影響。此外，以上算法研究的對象是訪存數(shù)組大小為向量因子整數(shù)倍的嵌套循環(huán)，對于不滿足該條件的嵌套循環(huán)（稱為病態(tài)規(guī)模循環(huán)），以上研究并未給出詳細(xì)分析。

為了解決這些問題，本文提出了一種針對可向量化嵌套循環(huán)的分塊因子選擇算法（VECtorization Tile Size Selection，VEC-TSS），能夠使分塊后的程序同時充分地利用編譯器的自動向量化技術(shù)和處理器的多級cache架構(gòu)資源。該算法的創(chuàng)新點主要有：（1）量化分析了循環(huán)分塊后程序的向量化收益；（2）詳細(xì)分析了病態(tài)規(guī)模問題的分塊因子選擇過程。

2 VEC-TSS算法

通常情況下，當(dāng)嵌套循環(huán)的最內(nèi)層循環(huán)沒有跨迭代依賴時，主流編譯器會對該層循環(huán)進行自動向量化處理。本文提出的VEC-TSS算法僅適用于具有可向量化循環(huán)層的嵌套循環(huán)。對于正常問題規(guī)模的嵌套循環(huán)，只要分塊因子的大小是向量因子的整數(shù)倍，就可以避免地址非對齊數(shù)據(jù)訪問，不會影響向量化收益。但是對于病態(tài)規(guī)模問題，任何一種分塊因子都會導(dǎo)致向量化時的地址非對齊數(shù)據(jù)訪問。當(dāng)嵌套循環(huán)為病態(tài)規(guī)模問題時，相較于其他TSS算法，VEC-TSS算法更能有效地降低向量化收益受分塊因子大小的影響。VEC-TSS算法分為兩個部分：可向量化循環(huán)層的分塊因子選擇和其他循環(huán)層的分塊因子選擇。

2.1 可向量化循環(huán)層的分塊因子選擇

為了有利于編譯器對嵌套循環(huán)進行自動向量化，可以借助代碼轉(zhuǎn)換工具（如PLuTo）將可向量化循環(huán)層置換到最內(nèi)層，本節(jié)討論可向量化循環(huán)層的分塊因子選擇，即嵌套循環(huán)的最內(nèi)層循環(huán)的分塊因子選擇。

程序能夠向量化的前提有兩點：（1）訪問地址連續(xù)的數(shù)據(jù)；（2）訪問地址對齊的數(shù)據(jù)[14]。經(jīng)過循環(huán)分塊后的程序改變了循環(huán)邊界，進而改變了向量寄存器訪問數(shù)據(jù)的地址對齊性，但是并不會影響分塊內(nèi)訪問數(shù)據(jù)的地址連續(xù)性，因此本文僅討論循環(huán)分塊對地址對齊性的影響。不同大小的分塊因子產(chǎn)生的循環(huán)邊界不同，使得分塊后的嵌套循環(huán)中非對齊數(shù)據(jù)的數(shù)量也不相同。目前的主流處理器對存在地址非對齊數(shù)據(jù)訪問的程序進行自動向量化時，會額外采用循環(huán)展開、循環(huán)剝離、數(shù)組填充等技術(shù)[15-16]，從而增加了開銷，降低了向量化收益。為了便于接下來的分析，定義可向量化數(shù)據(jù)塊為內(nèi)存中連續(xù)的向量因子大小的數(shù)據(jù)，其第一個數(shù)據(jù)的地址對齊于向量寄存器；定義可向量化數(shù)據(jù)的數(shù)目（記為NUM_VEC）為所有可向量化數(shù)據(jù)塊中的數(shù)據(jù)個數(shù)?？上蛄炕瘮?shù)據(jù)越多，向量化收益也越大。為了獲得最大化的向量收益，本文選擇的可向量化循環(huán)層分塊因子大小應(yīng)使得循環(huán)體中所有可向量化數(shù)據(jù)的數(shù)目最大。

以圖1為例進行說明，（a）和（b）分別表示矩陣乘法分塊前后的核心代碼。其中，分塊因子為(I,J,K)，參與計算的數(shù)據(jù)類型為8 Byte的雙精度浮點型。目標(biāo)機器的向量寄存器大小為256位，則向量寄存器一次能夠存取4個數(shù)據(jù)，要求存取的第一個數(shù)據(jù)的內(nèi)存地址是32 Byte對齊的。假設(shè)數(shù)組的首內(nèi)存地址為32 Byte對齊，當(dāng)問題規(guī)模N=13時，數(shù)組C[i][j]在內(nèi)存中的數(shù)據(jù)存儲情況如圖2所示。圖中每一個方格代表數(shù)組的一個元素。以分塊因子(I,J,K)對循環(huán)進行分塊，則影響數(shù)組C[i][j]的分塊因子是(I,J)，行分塊因子是I，列分塊因子是J。圖2中相同顏色（灰度）的方格表示在相同的分塊中。因為 j循環(huán)層可以向量化，此時可向量化循環(huán)層分塊因子為J。

圖1 分塊前后矩陣乘法matmul的核心代碼

圖2 內(nèi)存中數(shù)組C的數(shù)據(jù)布局（分塊因子為6）

觀察圖2，數(shù)組的第一行C[0][:]分成三部分，位于三個塊中。第一塊中的C[0][0:5]首先被載入cache中參與計算，其中C[0][0:3]是可向量化數(shù)據(jù)，而C[0][4:5]大小不是向量寄存器大小，無法向量化，故記可向量化數(shù)據(jù)個數(shù)為4。第二塊中的C[0][6:11]被載入cache中參與計算時，C[0][6]的內(nèi)存地址非對齊，C[0][6:7]無法向量化，而C[0][8:11]可以向量化，故記可向量化數(shù)據(jù)個數(shù)為4。同理分析數(shù)組的其余行，最終得到當(dāng) J=6時，NUM_VEC=104。

為了使可向量化循環(huán)層的收益最大，要求該層的分塊因子J對應(yīng)的NUM_VEC最大。當(dāng)數(shù)組大小為N時，遍歷所有的分塊因子 J(1≤J≤N)，并計算相應(yīng)的NUM_VEC值，則可向量化循環(huán)層的最優(yōu)分塊因子Best_J的計算如公式（1）所示：

2.2 其他循環(huán)層的分塊因子選擇

本節(jié)將詳細(xì)分析影響分塊因子選擇的另外兩個重要因素——程序局部性和并行粒度，并由此建立候選分塊因子的搜索空間，從中確定最優(yōu)分塊因子。

2.2.1 候選分塊因子的搜索空間

（1）程序局部性

循環(huán)分塊技術(shù)通過減小塊內(nèi)數(shù)據(jù)的重用距離，使得數(shù)據(jù)在下一次被訪問時沒有因為cache容量被替換出去而得到重用，從而帶來局部性收益。因此本文以數(shù)據(jù)重用距離（Reuse Distance，RD）來度量程序局部性。RD指同一個數(shù)據(jù)在兩次重用之間所訪問的其他不同數(shù)據(jù)的個數(shù)。以圖1（b）的代碼為例，分塊因子為(I,J,K)，對于數(shù)組B[k][j]來說，塊內(nèi)循環(huán)的最外層i每迭代一次，數(shù)組B才能得到重用。數(shù)組B的兩次重用之間總共訪問了數(shù)組A[i][k]的K個不同元素、數(shù)組C[i][j]的J個不同元素以及數(shù)組B[k][j]本身的K×J-1個不同元素，故數(shù)組B的重用距離RDB=K+J+(K×J-1)。推廣到一般情況，下面給出數(shù)據(jù)重用距離RD的計算公式。

對于一個n層嵌套循環(huán)，分塊因子為T=(T1,T2,…,Tn)，其中Ti代表第i層循環(huán)的分塊因子。循環(huán)語句S訪問的數(shù)組有A1,A2,…,Am，則此嵌套循環(huán)中的數(shù)據(jù)訪問矩陣ACC的結(jié)構(gòu)如公式（2）所示：

其中ai,j代表數(shù)組Ai在第 j層循環(huán)上的數(shù)據(jù)訪問情況，如公式（3）所示：

ai,j=1表示數(shù)組Ai在第 j層循環(huán)上具有數(shù)據(jù)重用。標(biāo)記重用循環(huán)層的向量C=(C1,C2,…,Cm)表示訪問矩陣ACC每一行中第一次出現(xiàn)1的列號，代表的含義是數(shù)組Ai在第Ci層循環(huán)上具有數(shù)據(jù)重用。則數(shù)組Ai的重用距離和循環(huán)語句S的數(shù)據(jù)重用距離分別如公式（4）和（5）所示：

由公式（5）可知，循環(huán)語句S數(shù)據(jù)重用距離為語句中所有數(shù)組的最大重用距離。

通過以上分析可知，圖1（b）示例的循環(huán)語句S中RDB最大。當(dāng)RDB小于某級cache的大小時，說明數(shù)組B[k][j]兩次重用之間所有訪問的數(shù)據(jù)都可以放入該級cache中，則數(shù)組 B[k][j]在該級cache中能夠得到重用。因為RDA和RDC都小于RDB，當(dāng)數(shù)組B[k][j]得到重用時，A[i][k]和C[i][j]也一定得到重用。因此，定義循環(huán)語句S的數(shù)據(jù)重用距離為：RDS=max(RDA,RDB,RDC)。當(dāng)RDS小于某級cache大小時，除去無法避免的第一次訪問數(shù)據(jù)冷失效外，語句S中的數(shù)據(jù)都能夠在該級cache中得到重用，從而獲得局部性收益。

當(dāng)塊內(nèi)循環(huán)語句S的數(shù)據(jù)重用距離RDS小于某級cache大小時，說明語句S中的所有數(shù)組均能在該級cache中得到重用，因此可以將整個分塊的工作集映射到該級cache，以發(fā)掘塊內(nèi)的局部性收益。以圖1（b）的代碼為例來說明分塊內(nèi)工作集大小的計算，循環(huán)層i、k、j構(gòu)成一個分塊，塊內(nèi)包含參與運算的數(shù)據(jù)總共有數(shù)組 A[i][k]的 I×K個元素，數(shù)組B[k][j]的K×J個元素和數(shù)組C[i][j]的I×J個元素，故一個分塊的工作集大小為：I×K+K×J+I×J。因此，可以建立一個基于程序局部性的分塊因子(I,K)的搜索空間，如公式（6），其中 SizeL2、SizeL2和 SizeL3分別為L1、L2和L3級cache的大小。

考慮到多級cache架構(gòu)的特點，對于同時存儲數(shù)據(jù)和指令的cache，根據(jù)文獻[5]的處理方式，將可用于數(shù)據(jù)存儲的容量設(shè)為該級cache容量的75%。對于r個核共享的cache，將可用于數(shù)據(jù)存儲的容量設(shè)為該級cache容量的1/r。

（2）并行粒度

當(dāng)采用多核對程序進行并行計算時，多核之間的負(fù)載均衡對并行收益有較大影響。文獻[5]提到當(dāng)每個核處理的分塊數(shù)量大于2時，程序的并行收益能夠得到保證，且多個核之間也是相對負(fù)載均衡的。本文通過大量實驗也證實了這一點。

以圖1（b）的程序為例，最外層循環(huán)是iT，該層循環(huán)迭代的數(shù)目為。當(dāng)使用r個核并行執(zhí)行程序，granularity表示分配給每個核的負(fù)載數(shù)目（即分塊數(shù)目）時，為了保持良好的并行粒度，則應(yīng)該滿足公式（7）：

2.2.2 優(yōu)化目標(biāo)函數(shù)

數(shù)據(jù)在cache中的重用次數(shù)（Reuse Count，RC）越多，局部性收益越大，因此本文采用數(shù)據(jù)的重用次數(shù)來度量嵌套循環(huán)的局部性收益。以圖1（b）的循環(huán)為例，通過公式（4）可以得到一個分塊內(nèi)語句S中數(shù)組B的重用距離最大，在數(shù)組B得到重用的同時，數(shù)組A和數(shù)組C都得到了重用。定義主導(dǎo)數(shù)組為執(zhí)行語句中重用距離最大的數(shù)組，圖1（b）中的主導(dǎo)數(shù)組為數(shù)組B，則主導(dǎo)數(shù)組帶來的局部性收益可以代表整個分塊的局部性收益。由于不同分塊內(nèi)的數(shù)組重用情況相同，因此研究一個分塊內(nèi)數(shù)組B的重用情況，可以代表整個程序的局部性收益。下面依然以圖1（b）的代碼來說明RC的計算過程。

假設(shè)公式（6）為L2 cache建立的搜索空間，即RDS

根據(jù)以上分析，當(dāng)RCB取最大時，分塊能夠得到最大局部性收益。

通過以上分析，可以得到選擇最優(yōu)分塊因子大小的過程。首先針對向量化收益，求出可向量化循環(huán)層的分塊因子J。然后通過公式（6）和（7）建立分塊因子(I,K)的搜索空間，并在搜索空間中找到使得公式（8）中RCB最大的分塊因子(I,K)。最后組合得到的(I,K,J)即為最優(yōu)的分塊因子大小。其中在搜索空間中尋找分塊因子時，為了更好地利用空間局部性，K的取值全部為CLS的倍數(shù)，CLS表示一個cache行能包含數(shù)組元素的個數(shù)。

3 VEC-TSS算法的應(yīng)用

VEC-TSS算法可以作為一個獨立的分塊因子選擇模塊，嵌入到其他針對嵌套循環(huán)優(yōu)化的工具中，例如PLuTo。PLuTo[8]是一款優(yōu)化嵌套循環(huán)的代碼轉(zhuǎn)換工具，它本身并不提供TSS策略，只采用默認(rèn)32的分塊因子大小，但其為研究人員預(yù)留了重寫分塊因子的接口。本文將VEC-TSS算法在PLuTo中進行了集成和應(yīng)用。圖3展示了PLuTo的框架和循環(huán)代碼轉(zhuǎn)換流程，以及VECTSS算法在PLuTo中的模塊位置，如圖中虛線框所示。

圖3 VEC-TSS算法在PLuTo中的應(yīng)用

此外，相關(guān)的實現(xiàn)包含以下三部分。

（1）嵌套循環(huán)的可向量化識別。由于VEC-TSS算法的適用對象是可向量化的嵌套循環(huán)，因此第一步需要判斷嵌套循環(huán)是否具有可向量化循環(huán)層。在PLuTo的結(jié)構(gòu)體hyperplane_properties中定義變量vec，用來標(biāo)記每個循環(huán)層是否可以向量化。PLuTo中存在發(fā)掘分塊后程序可向量化循環(huán)層的函數(shù)pluto_pre_vectorize_band（）。借鑒以上函數(shù)可以實現(xiàn)函數(shù)pluto_pre_vectorize（），用來識別分塊前程序各循環(huán)層是否可以向量化。

（2）VEC-TSS算法模塊。如果嵌套循環(huán)存在可以向量化的循環(huán)層，則調(diào)用VEC-TSS算法。PLuTo工具利用Candl模塊和isl模塊，將程序的特征信息提取到多面體模型中，如問題規(guī)模、數(shù)組個數(shù)、數(shù)據(jù)類型、數(shù)組下標(biāo)及循環(huán)層順序等。VEC-TSS模塊把以上信息作為輸入，計算得到最優(yōu)分塊因子。為了使得計算結(jié)果能夠被調(diào)用，定義全局結(jié)構(gòu)體vec_tile_size來存儲計算結(jié)果。

（3）調(diào)用VEC-TSS算法的結(jié)果。PluTo預(yù)留的重寫分塊因子接口為tile.sizes文件，PluTo通過函數(shù)read_tile_sizes（）讀取tile.sizes文件中的各循環(huán)層分塊因子。故可以通過修改函數(shù)read_tile_sizes（），使得PLuTo自動調(diào)用結(jié)構(gòu)體vec_tile_size中的數(shù)據(jù)來進行代碼分塊。

4 實驗分析

為了驗證VEC-TSS算法的有效性，本文在一臺Intel Xeon E7-4820服務(wù)器上進行了實驗。該服務(wù)器具有4個8核的處理器，每個核擁有32 KB的L1級和256 KB的L2級cache，每個處理器具有16 MB的共享L3級cache；SIMD單元為256 bit；運行64位服務(wù)器版的CentOS 7.1.1503操作系統(tǒng)；采用icc 15.0.2編譯器，編譯選項為O3 parallel openmp。實驗使用的PLuTo版本為pluto-0.11.4。

本文從PLuTo的程序集PLuToBench和多面體編譯優(yōu)化領(lǐng)域的PolyBench 3.2基準(zhǔn)測試集[9]中選取了8個可以向量化的基準(zhǔn)測試程序。其中測試程序matmul、dsyrk、dsyr2k、lu和trisolv的操作數(shù)為雙精度浮點型，測試程序tmm、corcol和covcol的操作數(shù)為單精度浮點型。

4.1 病態(tài)問題規(guī)模結(jié)果與分析

不同問題規(guī)模的嵌套循環(huán)會有不同的最優(yōu)分塊因子。本文首先選取了一系列病態(tài)規(guī)模的程序進行測試，將VEC-TSS算法與目前先進的SICA算法[11]和TTS算法[13]進行比較。為了驗證算法的有效性，排除線程數(shù)目的影響，本組測試程序均采用8線程執(zhí)行。圖4展示了分別采用三種算法的分塊程序相對于未分塊的原始程序的平均加速比。觀察圖4可知，隨著問題規(guī)模的擴大，VEC-TSS算法的優(yōu)勢逐漸明顯。這是由于隨著問題規(guī)模的增大，可向量化的數(shù)據(jù)量也明顯增加，向量化技術(shù)帶來的優(yōu)勢更加顯著，VEC-TSS算法能夠使嵌套循環(huán)的向量化收益最大，比其他兩個算法更具有優(yōu)勢。

圖4 病態(tài)問題規(guī)模時VEC-TSS算法平均加速比

此外，表1展示了問題規(guī)模為3 199時各測試程序的分塊因子。觀察表1可知，各基準(zhǔn)測試程序通過三種算法得到的分塊因子類似，是由于這些基準(zhǔn)測試程序雖然具有不同的循環(huán)結(jié)構(gòu)和循環(huán)體，但是數(shù)據(jù)重用距離大小和嵌套循環(huán)中工作集大小卻高度相似。

另外，通過VEC-TSS算法分塊后的測試程序tmm、corcol和covcol的加速比較為突出。這是因為這三個程序的操作數(shù)為單精度浮點型，相較于雙精度浮點型來說，向量寄存器中可以存放的數(shù)據(jù)更多，導(dǎo)致分塊不恰當(dāng)時，更容易產(chǎn)生數(shù)據(jù)非對齊問題。VEC-TSS算法能夠更好地解決這個問題，相較于其他算法，性能更加優(yōu)越。

表1 問題規(guī)模為3 199時的分塊大小

4.2 可擴展性結(jié)果與分析

循環(huán)分塊技術(shù)不僅能夠改善程序的局部性，還能夠開發(fā)程序的并行性。為了測試VEC-TSS算法對分塊后程序并行可擴展性的影響，本文在問題規(guī)模為3 199時，分別采用線程數(shù)為1、4、8、16和32測試了分塊后程序的加速比，結(jié)果如圖5所示。

圖5 VEC-TSS算法對程序并行可擴展性的影響

觀察圖5可以發(fā)現(xiàn)，隨著線程數(shù)的增多，分塊后程序的加速比近似表現(xiàn)為線性增長，這說明采用VEC-TSS算法的程序具有良好的并行可擴展性。究其原因有兩方面：第一，VEC-TSS算法考慮到了多核共享L3 cache的情況，將L3 cache的容量均分給多個核，故分塊后程序在多線程并行處理時，線程間不會競爭使用L3 cache；第二，VEC-TSS算法通過并行粒度分析限定最外層循環(huán)的分塊因子，使得每個核分配到的循環(huán)塊個數(shù)大于2，保證了多核之間的負(fù)載均衡。此外，測試程序lu和trisolv的并行可擴展性卻不理想，如表2所示。這是因為程序本身具有較好的局部性，在多線程并行執(zhí)行時，反而容易造成偽共享，增加了數(shù)據(jù)一致性開銷。

表2 lu和trisolv的多線程加速比測試結(jié)果

本文僅采用Intel的CPU進行實驗驗證。但是本文提出的VEC-TSS算法同樣適用于與Intel具有相同SIMD擴展指令集的AMD CPU[17]，以及具有相似SIMD擴展的國產(chǎn)飛騰、申威等處理器[18-19]。

5 結(jié)束語

本文針對病態(tài)規(guī)模的嵌套循環(huán)經(jīng)過循環(huán)分塊后會產(chǎn)生許多非對齊數(shù)據(jù)訪問，從而影響自動向量化收益的問題，提出了一種VEC-TSS算法。該算法對于大規(guī)模的嵌套循環(huán)具有較明顯的優(yōu)勢，且采用該算法分塊后的循環(huán)具有良好的并行性。目前該算法僅適用于CPU處理器，對于具有向量化處理優(yōu)勢的GPU并不適用。下一步將會考慮GPU架構(gòu)的特點，并將該算法擴展到GPU架構(gòu)中。