基于多面體模型的數(shù)據(jù)依賴分析方法*

李 川，陳朝暉

(北京控制工程研究所，北京 100190)

?

基于多面體模型的數(shù)據(jù)依賴分析方法*

李 川，陳朝暉

(北京控制工程研究所，北京 100190)

設(shè)計(jì)一種基于多面體模型的靜態(tài)數(shù)據(jù)依賴分析方法，對(duì)程序中的循環(huán)體進(jìn)行分析，將生存周期思想引入到數(shù)據(jù)的依賴分析中.數(shù)據(jù)的依賴關(guān)系中只有流依賴是無(wú)法消除的固有依賴，必須保持變換前的執(zhí)行順序，而輸出依賴和反依賴可以通過(guò)標(biāo)量擴(kuò)展及向前替換等方法消去.對(duì)傳統(tǒng)數(shù)據(jù)依賴分析進(jìn)行改進(jìn)，通過(guò)分析內(nèi)存單元的生存周期，摒除不必要的偽依賴，從而可以對(duì)更多的循環(huán)體進(jìn)行變換.通過(guò)實(shí)驗(yàn)表明了該方法的可行性和有效性.

依賴分析；多面體模型；生存周期；循環(huán)變換.

0 引 言

在并行編譯中，使用多面體模型[1]進(jìn)行循環(huán)變換是一種行之有效的方法[2-3].多面體模型方法是將循環(huán)體映射到多面體中，利用數(shù)學(xué)上已經(jīng)非常完備的多面體理論對(duì)多面體做各種形式的變換，再將其重新映射到程序中，生成新的循環(huán)體的方法，它幾乎涵蓋了所有傳統(tǒng)的循環(huán)變換類型.

為了保證循環(huán)變換及并行化的正確性，需要對(duì)數(shù)據(jù)間的依賴關(guān)系進(jìn)行分析.程序的數(shù)據(jù)依賴分為兩類：真依賴和偽依賴.其中真依賴即流依賴，是固有依賴，必須被滿足，以保證循環(huán)變換的正確性；偽依賴包括輸出依賴和反依賴，偽依賴降低了循環(huán)變換的自由度，可以通過(guò)標(biāo)量擴(kuò)展及向前替換等方法消去.傳統(tǒng)的多面體模型對(duì)所有依賴進(jìn)行分析，即只有滿足包括偽依賴的所有依賴關(guān)系，循環(huán)的轉(zhuǎn)換才是正確的.

如果僅考慮流依賴關(guān)系，忽略偽依賴，則不能保證變量或數(shù)組原本的讀寫(xiě)順序.因此，為每個(gè)變量或數(shù)組定義生存周期，并進(jìn)行生存周期分析，如果循環(huán)變換之后生存周期沒(méi)有沖突，則將該變換視為正確的.如果轉(zhuǎn)換產(chǎn)生了生存周期的沖突，仍可以通過(guò)標(biāo)量擴(kuò)展或向前替換消除沖突，從而保證變換的正確性.

文獻(xiàn)[4]給出了通過(guò)生存周期分析來(lái)檢測(cè)偽依賴，并使用標(biāo)量擴(kuò)展消除偽依賴的方法.利用文獻(xiàn)[4]中生存周期的概念，文獻(xiàn)[5]針對(duì)循環(huán)切片的循環(huán)變換方式，給出了一種忽略偽依賴以提高變換成功率的方法.文獻(xiàn)[6]也研究了類似問(wèn)題，通過(guò)限制標(biāo)量擴(kuò)展時(shí)內(nèi)存占用的大小，以在已知內(nèi)存限制的情況下提高并行化的效果，但增加了編譯的復(fù)雜度和編譯時(shí)間.相比文獻(xiàn)[4]的方法，本文的方法添加了對(duì)向前替換的支持，能夠更多地避免消除偽依賴時(shí)，使用標(biāo)量擴(kuò)展所增加的內(nèi)存占用.

本文設(shè)計(jì)一種基于多面體模型的數(shù)據(jù)依賴分析方法，來(lái)檢測(cè)偽依賴.先忽略程序的數(shù)據(jù)依賴關(guān)系，直接進(jìn)行循環(huán)的變換，之后對(duì)數(shù)據(jù)的流依賴及生存周期進(jìn)行分析.如果沒(méi)有沖突，則變換成功，否則通過(guò)標(biāo)量擴(kuò)展或向前替換消除偽依賴，以解決依賴沖突，保證變換的正確性.相較傳統(tǒng)數(shù)據(jù)依賴分析方法，本文的方法能使編譯器對(duì)更多的循環(huán)體進(jìn)行變換.

1 研究背景

1.1 多面體模型

本文的依賴分析方法基于多面體模型.多面體模型指將循環(huán)體映射到多面體中，利用數(shù)學(xué)上已經(jīng)非常完備的多面體理論，對(duì)該多面體做各種形式的變換，再將其重新映射到程序中，生成新的循環(huán)體的一種循環(huán)優(yōu)化方式.相比傳統(tǒng)技術(shù)，它能夠?qū)ρh(huán)進(jìn)行更為深入、精確的優(yōu)化.

定義1.迭代域：包括循環(huán)體內(nèi)所有語(yǔ)句的動(dòng)態(tài)實(shí)例，即循環(huán)體的所有歸納變量的可能取值的集合，通過(guò)仿射不等式的集合來(lái)表示，語(yǔ)句S的迭代域?yàn)?/p>

(1)

式中：i為迭代向量，g為全局參數(shù)，DS為循環(huán)體邊界的條件矩陣.

定義2.調(diào)度函數(shù)：用于描述迭代域中每個(gè)語(yǔ)句實(shí)例的執(zhí)行順序，通過(guò)改變調(diào)度函數(shù)，就可以改變語(yǔ)句的執(zhí)行順序，從而進(jìn)行循環(huán)變換.語(yǔ)句S的調(diào)度函數(shù)表示為

θS(i)=ΘS×[i,g,1]T

(2)

式中：i為迭代向量，g為全局參數(shù)，ΘS為由迭代順序矩陣、語(yǔ)句順序向量及參數(shù)矩陣所組成的矩陣，其結(jié)果是執(zhí)行語(yǔ)句S的時(shí)間戳矢量.

定義3.訪存函數(shù)：用于獲取循環(huán)體中所讀寫(xiě)的變量及數(shù)組元素的內(nèi)存位置，以進(jìn)行依賴分析.語(yǔ)句S的訪存函數(shù)表示為：

(3)

式中：i為迭代向量，g為全局參數(shù)，F(xiàn)為訪存矩陣，其結(jié)果是語(yǔ)句S所訪問(wèn)的內(nèi)存地址.

定義4.靜態(tài)控制塊SCoP(staticcontrolpart)：指循環(huán)邊界是循環(huán)迭代和參數(shù)的仿射函數(shù)的循環(huán)體，是構(gòu)建多面體模型的基礎(chǔ)，每個(gè)SCoP都被描述為一個(gè)多面體的集合

(4)

1.2 偽依賴的消除

在進(jìn)行循環(huán)變換時(shí)，總是會(huì)有數(shù)據(jù)間的依賴關(guān)系阻礙循環(huán)的變換，標(biāo)量擴(kuò)展和向前替換就是兩種消除其中的偽依賴關(guān)系的方法.

標(biāo)量擴(kuò)展(scalar expansion)[7]是通過(guò)增加內(nèi)存占用的方式來(lái)消除偽依賴的方法.如果一個(gè)變量或數(shù)組在循環(huán)的每次迭代中都重新被賦值和讀取，則這個(gè)變量或數(shù)組在每個(gè)迭代的取值可以被分別存儲(chǔ)在單獨(dú)的內(nèi)存單元中.每個(gè)迭代在單獨(dú)的內(nèi)存單元讀寫(xiě)，從而消除了對(duì)同一內(nèi)存單元讀寫(xiě)的數(shù)據(jù)依賴.

向前替換(forward substitution)[7]也是一種消除偽依賴的方法.編譯器在編譯時(shí)通常將一些經(jīng)常重復(fù)使用的表達(dá)式分配到一個(gè)臨時(shí)變量中，如GCC(the GNU compiler collection)的PRE(partial redundancy elimination)優(yōu)化.而如果這種優(yōu)化在循環(huán)中進(jìn)行，則會(huì)產(chǎn)生偽依賴中的輸出依賴，向前替換就是為了解決這種問(wèn)題，通過(guò)替換編譯器分配的臨時(shí)變量來(lái)消除偽依賴.

顯然，使用標(biāo)量擴(kuò)展時(shí)，有一個(gè)在并行效果和內(nèi)存使用量之間的權(quán)衡問(wèn)題：如果盡可能的進(jìn)行標(biāo)量擴(kuò)展，則可以為并行化得到最大的自由空間，但同時(shí)會(huì)消耗大量?jī)?nèi)存；如果根本不進(jìn)行擴(kuò)展，那么可以節(jié)省內(nèi)存，但并行化的效果會(huì)受很大影響.而如果盡可能進(jìn)行向前替換，則會(huì)抵消PRE的優(yōu)化效果，降低了程序的運(yùn)行效率；而不用向前替換也同樣會(huì)影響并行化效果.

因此，需要一個(gè)有效的依賴分析方法來(lái)確定標(biāo)量擴(kuò)展及向前替換的使用時(shí)機(jī)，本文所設(shè)計(jì)的依賴分析方法既是為了達(dá)到這一目標(biāo).

2 依賴分析方法的設(shè)計(jì)

2.1 生存周期

在程序中，一個(gè)變量或數(shù)組元素的生存周期，指在程序執(zhí)行過(guò)程中，從一個(gè)對(duì)其寫(xiě)入的語(yǔ)句，到下一個(gè)對(duì)其寫(xiě)入的語(yǔ)句之前所包括的所有語(yǔ)句.變量x的一個(gè)生存周期的實(shí)例表示為

Lx=Sdef∩

{Slive|lexmin(Slive)?Sdef∧lexmax(Slive)

(5)

為便于之后的計(jì)算，這里僅考慮對(duì)指定變量或數(shù)組元素寫(xiě)入和讀取的語(yǔ)句.用多面體表示一個(gè)生存周期的中所有讀語(yǔ)句

ω={iR|Ω×[i,g,1]T≥0}

(6)

用L代表一個(gè)生存周期的實(shí)例

L=(iW,ωS)

(7)

本文的方法在GCC的Graphite框架[8]中實(shí)現(xiàn).Graphite框架用于多面體分析和轉(zhuǎn)換，是GCC的一個(gè)優(yōu)化遍.其主要功能是從GCC的三地址Gimple中間表示中提取多面體，之后對(duì)該多面體進(jìn)行變換，最后生成變換之后的多面體所對(duì)應(yīng)的Gimple代碼.Graphite中使用的是傳統(tǒng)的依賴分析方法.

本文使用用于多面體模型編程的C語(yǔ)言庫(kù)ISL[9]，生存周期的表示如下：

struct live_range {

isl_map write;

isl_union_map reads;

};

其中：write表示寫(xiě)語(yǔ)句，reads表示讀語(yǔ)句的集合.

2.2 算法設(shè)計(jì)

本文的依賴分析方法主要由4個(gè)部分組成，分別是流依賴分析、生存周期分析、流依賴沖突分析以及生存周期沖突分析，其執(zhí)行流程如圖1所示.其中，流依賴分析及流依賴沖突分析在Graphite中已經(jīng)存在.循環(huán)變換指Graphite中對(duì)循環(huán)所做的循環(huán)交換等變換.

(1)流依賴分析

計(jì)算循環(huán)體中數(shù)據(jù)的流依賴關(guān)系，其計(jì)算結(jié)果將被用于之后的流依賴沖突分析.

(2)生存周期分析

計(jì)算循環(huán)體中讀寫(xiě)的每個(gè)的內(nèi)存單元所對(duì)應(yīng)的生存周期的集合.

圖1 依賴分析執(zhí)行流程Fig.1 Implementation of the dependence analysis

(3)循環(huán)變換

忽略數(shù)據(jù)中的依賴關(guān)系，對(duì)循環(huán)進(jìn)行變換，變換的正確性將在之后的步驟中驗(yàn)證，如果變換后有依賴沖突，則對(duì)循環(huán)進(jìn)行其它變換，或放棄對(duì)該循環(huán)的變換.

(4)流依賴沖突分析

分析循環(huán)變換之后的流依賴關(guān)系是否有沖突，保證循環(huán)變換后流依賴的正確性.

(5)生存周期沖突分析

分析循環(huán)變換之后的生存周期是否有沖突，如果有沖突，是否需要進(jìn)行標(biāo)量擴(kuò)展或向前替換，來(lái)消除偽依賴，從而使變換正確

2.3 流依賴分析

傳統(tǒng)依賴分析方法需要對(duì)流依賴、反依賴及輸出依賴進(jìn)行分析，這里僅對(duì)流依賴進(jìn)行分析.

對(duì)于指定的變量或數(shù)組的引用，流依賴分析將找到其所在的每個(gè)語(yǔ)句，計(jì)算出依賴關(guān)系δSj→Si的集合.每個(gè)依賴關(guān)系表示讀寫(xiě)同一個(gè)內(nèi)存單元的讀語(yǔ)句和寫(xiě)語(yǔ)句之間循環(huán)迭代的關(guān)系，其中讀語(yǔ)句Si讀取的是寫(xiě)入語(yǔ)句Sj寫(xiě)入的值，并且中間沒(méi)有其他的寫(xiě)入操作將Sj寫(xiě)入的值覆蓋.

2.4 生存周期分析

生存周期分析的目的是計(jì)算循環(huán)變換之前循環(huán)體中的所有生存周期的集合，以下是計(jì)算生存周期的算法：

算法計(jì)算生存周期M輸入: W:SCoP內(nèi)所有寫(xiě)語(yǔ)句的集合 R:SCoP內(nèi)所有讀語(yǔ)句的集合 M:內(nèi)存單元地址輸出: M:內(nèi)存單元M的所有生存周期的集合 forallSi∈Wdo forallSj∈Rdo ifbase(Si)=base(Sj)=Mthen M←M∪Sj endif endfor foralliSi∈Sido 計(jì)算ωM M←M∪(iSi,ωM) endforendfor

雖然在編譯時(shí)增加了生存周期分析，但同時(shí)省略了對(duì)輸出依賴和反依賴的分析，所以實(shí)際上減少了編譯的計(jì)算量.

2.5 流依賴沖突分析

通過(guò)變換之后的調(diào)度函數(shù)θ，將流依賴分析中計(jì)算得到的流依賴關(guān)系集合δSj→Si進(jìn)行轉(zhuǎn)換，檢測(cè)變換之后每個(gè)流依賴關(guān)系所代表的兩個(gè)語(yǔ)句執(zhí)行順序是否改變，如果有改變則是有沖突的，說(shuō)明循環(huán)變換不正確.

2.6 生存周期沖突分析

生存周期沖突分析的目的是判斷循環(huán)變換之后，原先的生存周期是否存在沖突.應(yīng)用循環(huán)變換之后，原生存周期內(nèi)語(yǔ)句的執(zhí)行順序可能發(fā)生改變，從而導(dǎo)致沖突，如果生存周期中的語(yǔ)句在循環(huán)變換后的執(zhí)行順序中有重疊，則稱這兩個(gè)生存周期有沖突.

生存周期沖突分析的算法如下：

算法 生存周期沖突分析輸入: θ:循環(huán)變換后的調(diào)度函數(shù) M:內(nèi)存單元M的所有生存周期的集合 forall(iSw,ωR)∈Mdo ←∪{(tW,tFR,tLR)|tW=θSW(iSW), tFR=min({θR(iR)|iR∈ωR}),tLR=max({θR(iR)|iR∈ωR})} endfor forall(tW,tFR,tLR)∈do forall(t'W,t'FR,t'LR)∈do ift'W?tLR∧tW?t'LR∧tW≠t'Wthen ift'FR?tLR∧tFR?t'LRthen 對(duì)M的賦值語(yǔ)句進(jìn)行向前替換 else 對(duì)M所屬的變量或數(shù)組進(jìn)行標(biāo)量擴(kuò)展 endif endif endforendfor

使用標(biāo)量擴(kuò)展及向前替換消除偽依賴，雖然會(huì)稍微增加編譯時(shí)間，但由于循環(huán)中所操作的內(nèi)存單元是有限的，因此增加的編譯時(shí)間是可以接受的.

通過(guò)向前替換及標(biāo)量擴(kuò)展的配合使用，在消除偽依賴，也同時(shí)減少了僅使用標(biāo)量擴(kuò)展時(shí)增加的內(nèi)存占用.

3 實(shí) 驗(yàn)

使用PolyBench(the polyhedral benchmark suite)測(cè)試集進(jìn)行實(shí)驗(yàn)，比較了Graphite中傳統(tǒng)的考慮所有依賴的依賴分析方法，以及本文中消除偽依賴的依賴分析方法，在程序并行化中的效果.

本實(shí)驗(yàn)的基準(zhǔn)使用GCC-4.8.2編譯，選項(xiàng)為-O2-floop-parallelize -all-ftree-parallelize-loops=4，即使用多面體模型對(duì)循環(huán)進(jìn)行依賴分析，對(duì)可并行化的循環(huán)進(jìn)行變換，將其分為4個(gè)線程運(yùn)行.

兩種方法中進(jìn)行變換的循環(huán)數(shù)量如表1所示，可以看出相比考慮所有依賴，通過(guò)使用本文中消除偽依賴的方法可以使更多的循環(huán)進(jìn)行并行化.其中對(duì)外層循環(huán)并行化時(shí)，增加了并行的粒度，提升了并行的效果.說(shuō)明了本文的方法能使更多循環(huán)進(jìn)行變換.

表1 并行化的循環(huán)數(shù)量

圖2顯示了表1所列測(cè)試程序運(yùn)行的加速比.加速比是用測(cè)試程序運(yùn)行時(shí)間與基準(zhǔn)運(yùn)行時(shí)間的比率，其中測(cè)試基準(zhǔn)時(shí)間的程序是僅使用-O2選項(xiàng)編譯所得到的.從圖中可見(jiàn)，由于消除偽依賴對(duì)更多循環(huán)進(jìn)行了并行化的變換，加速比也有了相應(yīng)的提高，進(jìn)一步證明了本方法的有效性.

圖2 加速比的比較Fig.2 Comparison of speedups

4 結(jié) 論

由于數(shù)據(jù)中存在的偽依賴關(guān)系并不是數(shù)據(jù)的固有關(guān)系，可以被消除，因此傳統(tǒng)依賴分析中必須滿足偽依賴關(guān)系的限制降低了并行化的效果.本文中基于多面體模型的依賴分析方法，通過(guò)引入生存周期的思想，配合使用標(biāo)量擴(kuò)展及向前替換消除偽依賴，可以使編譯器可以對(duì)更多的循環(huán)體進(jìn)行變換.本文基于ISL庫(kù)在Graphite中實(shí)現(xiàn)了該方法，使Graphite可以對(duì)更多的循環(huán)進(jìn)行并行化.實(shí)驗(yàn)測(cè)試表明，本文提出的消除偽依賴的依賴分析方法，對(duì)提高循環(huán)變換的數(shù)量是有效的.

[1] GIRBAL S, VASILACHE N BASTOUL C, et al. Semi-automatic composition of loop transformations for deep parallel-ism and memory hierarchies[J]. International Journal of Parallel Programming, 2006,34(3):261-317.

[2] SIMBüRGER A, APEL S, GR??LINGER A, et al. The potential of polyhedral optimization[C]//Automated Software Engineering (ASE), IEEE International Conference. New York: IEEE, 2013：11-15.

[3] ALNAELI S M, ALALI A, MALETIC J I. Empirically exam-ining the parallelizability of open source software systems[C]//Reverse Engineering, 2012 19thWorking Conference. New York: IEEE, 2012:377-386.

[4] TRIFUNOVIC K, COHEN A. Enabling more optimizations in GRAPHITE: ignoring memory-based dependences[C]// Proceddings of the 8thGCC Developper’s Summit. Ottawa, Canada: GNU: 2010:129-142.

[5] BAGHDADI R, COHEN A, VERDOOLAEGE S, et al. Improved loop tiling based on the removal of spurious false de-pendences[J]. ACM Transactions on Architecture and Code Optimization, 2013,9(4):52-53.

[6] VASILACHE N, MEISTER B, HARTONO A, et al. Trading off memory for parallelism quality[C]// International Workshop on Polyhedral Compilation Techniques. Paris, France: IMPACT, ACM TACO: 2012.

[7] MIDKIFF S P. Automatic parallelization: an overview of fundamental compiler techniques[J]. Synthesis Lec-tures on Computer Architecture, 2012,7(1):1-169.

[8] POP S, COHEN A, BASTOUl C, et al. GRAPHITE: Poly-hedral analyses and optimizations for GCC[C]//Proceedings of the 2006 GCC Developers Summit, Ottawa, Canada: GNU, 2006:179-197.

[9] VERDOOLAEGE S. isl: An integer set library for the poly-hedral model[C]//ICMS’10 Proceedings of the Third International Congress Conference on Mathematical Software Berlin, Germany: Springer-Verlag, 2010:299-302.

Data-Dependence Analysis Method Based on Polyhedral Model

LI Chuan, CHEN Zhaohui

(BeijingInstituteofControlEngineering，Beijing100190，China)

A static data-dependence analysis method for loops based on polyhedral model is designed. The concept of live range is introduced into analysis. Only flow dependences must keep consistent with the order that they appears in the original execution of the program. Output dependences and anti-dependences can be eliminated by scalar expansion or forward substitution. This analysis method reforms the traditional analysis by introducing live range and eliminating unnecessary false dependence, via which more loops can be transformed. The validity and efficiency of the presented method are demonstrated by experiment．

dependence analysis； polyhedral model； live range； loop transformation

*國(guó)家自然科學(xué)基金資助項(xiàng)目(91118007).

2014-12-17

TP31

A

1674-1579(2015)03-0043-05

10.3969/j.issn.1674-1579.2015.03.009

李 川(1987—)，男，碩士研究生，研究方向?yàn)椴⑿杏?jì)算；陳朝暉(1969—)，男，研究員，研究方向?yàn)楹教烨度胧杰浖夹g(shù).