李 川，陳朝暉

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

?

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

李 川，陳朝暉

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

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

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

0 引 言

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

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

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

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

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

1 研究背景

1.1 多面體模型

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

定義1.迭代域：包括循環(huán)體內所有語句的動態(tài)實例，即循環(huán)體的所有歸納變量的可能取值的集合，通過仿射不等式的集合來表示，語句S的迭代域為

(1)

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

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

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

(2)

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

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

(3)

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

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

(4)

1.2 偽依賴的消除

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

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

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

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

因此，需要一個有效的依賴分析方法來確定標量擴展及向前替換的使用時機，本文所設計的依賴分析方法既是為了達到這一目標.

2 依賴分析方法的設計

2.1 生存周期

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

Lx=Sdef∩

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

(5)

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

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

(6)

用L代表一個生存周期的實例

L=(iW,ωS)

(7)

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

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

struct live_range {

isl_map write;

isl_union_map reads;

};

其中：write表示寫語句，reads表示讀語句的集合.

2.2 算法設計

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

(1)流依賴分析

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

(2)生存周期分析

計算循環(huán)體中讀寫的每個的內存單元所對應的生存周期的集合.

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

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

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

(4)流依賴沖突分析

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

(5)生存周期沖突分析

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

2.3 流依賴分析

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

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

2.4 生存周期分析

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

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

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

2.5 流依賴沖突分析

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

2.6 生存周期沖突分析

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

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

算法 生存周期沖突分析輸入: θ:循環(huán)變換后的調度函數(shù) M:內存單元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 對M的賦值語句進行向前替換 else 對M所屬的變量或數(shù)組進行標量擴展 endif endif endforendfor

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

通過向前替換及標量擴展的配合使用，在消除偽依賴，也同時減少了僅使用標量擴展時增加的內存占用.

3 實 驗

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

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

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

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

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

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

4 結 論

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

*國家自然科學基金資助項目(91118007).

2014-12-17

TP31

A

1674-1579(2015)03-0043-05

10.3969/j.issn.1674-1579.2015.03.009

李 川(1987—)，男，碩士研究生，研究方向為并行計算；陳朝暉(1969—)，男，研究員，研究方向為航天嵌入式軟件技術.