基于多面体模型的数据依赖分析方法*

李 川，陈朝晖

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



基于多面体模型的数据依赖分析方法*

李 川，陈朝晖

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

设计一种基于多面体模型的静态数据依赖分析方法，对程序中的循环体进行分析，将生存周期思想引入到数据的依赖分析中.数据的依赖关系中只有流依赖是无法消除的固有依赖，必须保持变换前的执行顺序，而输出依赖和反依赖可以通过标量扩展及向前替换等方法消去.对传统数据依赖分析进行改进，通过分析内存单元的生存周期，摒除不必要的伪依赖，从而可以对更多的循环体进行变换.通过实验表明了该方法的可行性和有效性.

依赖分析；多面体模型；生存周期；循环变换.

0 引 言

在并行编译中，使用多面体模型[1]进行循环变换是一种行之有效的方法[2-3].多面体模型方法是将循环体映射到多面体中，利用数学上已经非常完备的多面体理论对多面体做各种形式的变换，再将其重新映射到程序中，生成新的循环体的方法，它几乎涵盖了所有传统的循环变换类型.

为了保证循环变换及并行化的正确性，需要对数据间的依赖关系进行分析.程序的数据依赖分为两类：真依赖和伪依赖.其中真依赖即流依赖，是固有依赖，必须被满足，以保证循环变换的正确性；伪依赖包括输出依赖和反依赖，伪依赖降低了循环变换的自由度，可以通过标量扩展及向前替换等方法消去.传统的多面体模型对所有依赖进行分析，即只有满足包括伪依赖的所有依赖关系，循环的转换才是正确的.

如果仅考虑流依赖关系，忽略伪依赖，则不能保证变量或数组原本的读写顺序.因此，为每个变量或数组定义生存周期，并进行生存周期分析，如果循环变换之后生存周期没有冲突，则将该变换视为正确的.如果转换产生了生存周期的冲突，仍可以通过标量扩展或向前替换消除冲突，从而保证变换的正确性.

文献[4]给出了通过生存周期分析来检测伪依赖，并使用标量扩展消除伪依赖的方法.利用文献[4]中生存周期的概念，文献[5]针对循环切片的循环变换方式，给出了一种忽略伪依赖以提高变换成功率的方法.文献[6]也研究了类似问题，通过限制标量扩展时内存占用的大小，以在已知内存限制的情况下提高并行化的效果，但增加了编译的复杂度和编译时间.相比文献[4]的方法，本文的方法添加了对向前替换的支持，能够更多地避免消除伪依赖时，使用标量扩展所增加的内存占用.

本文设计一种基于多面体模型的数据依赖分析方法，来检测伪依赖.先忽略程序的数据依赖关系，直接进行循环的变换，之后对数据的流依赖及生存周期进行分析.如果没有冲突，则变换成功，否则通过标量扩展或向前替换消除伪依赖，以解决依赖冲突，保证变换的正确性.相较传统数据依赖分析方法，本文的方法能使编译器对更多的循环体进行变换.

1 研究背景

1.1 多面体模型

本文的依赖分析方法基于多面体模型.多面体模型指将循环体映射到多面体中，利用数学上已经非常完备的多面体理论，对该多面体做各种形式的变换，再将其重新映射到程序中，生成新的循环体的一种循环优化方式.相比传统技术，它能够对循环进行更为深入、精确的优化.

定义1.迭代域：包括循环体内所有语句的动态实例，即循环体的所有归纳变量的可能取值的集合，通过仿射不等式的集合来表示，语句S的迭代域为

(1)

式中：i为迭代向量，g为全局参数，DS为循环体边界的条件矩阵.

定义2.调度函数：用于描述迭代域中每个语句实例的执行顺序，通过改变调度函数，就可以改变语句的执行顺序，从而进行循环变换.语句S的调度函数表示为

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

(2)

式中：i为迭代向量，g为全局参数，ΘS为由迭代顺序矩阵、语句顺序向量及参数矩阵所组成的矩阵，其结果是执行语句S的时间戳矢量.

定义3.访存函数：用于获取循环体中所读写的变量及数组元素的内存位置，以进行依赖分析.语句S的访存函数表示为：

(3)

式中：i为迭代向量，g为全局参数，F为访存矩阵，其结果是语句S所访问的内存地址.

定义4.静态控制块SCoP(staticcontrolpart)：指循环边界是循环迭代和参数的仿射函数的循环体，是构建多面体模型的基础，每个SCoP都被描述为一个多面体的集合

(4)

1.2 伪依赖的消除

在进行循环变换时，总是会有数据间的依赖关系阻碍循环的变换，标量扩展和向前替换就是两种消除其中的伪依赖关系的方法.

标量扩展(scalar expansion)[7]是通过增加内存占用的方式来消除伪依赖的方法.如果一个变量或数组在循环的每次迭代中都重新被赋值和读取，则这个变量或数组在每个迭代的取值可以被分别存储在单独的内存单元中.每个迭代在单独的内存单元读写，从而消除了对同一内存单元读写的数据依赖.

向前替换(forward substitution)[7]也是一种消除伪依赖的方法.编译器在编译时通常将一些经常重复使用的表达式分配到一个临时变量中，如GCC(the GNU compiler collection)的PRE(partial redundancy elimination)优化.而如果这种优化在循环中进行，则会产生伪依赖中的输出依赖，向前替换就是为了解决这种问题，通过替换编译器分配的临时变量来消除伪依赖.

显然，使用标量扩展时，有一个在并行效果和内存使用量之间的权衡问题：如果尽可能的进行标量扩展，则可以为并行化得到最大的自由空间，但同时会消耗大量内存；如果根本不进行扩展，那么可以节省内存，但并行化的效果会受很大影响.而如果尽可能进行向前替换，则会抵消PRE的优化效果，降低了程序的运行效率；而不用向前替换也同样会影响并行化效果.

因此，需要一个有效的依赖分析方法来确定标量扩展及向前替换的使用时机，本文所设计的依赖分析方法既是为了达到这一目标.

2 依赖分析方法的设计

2.1 生存周期

在程序中，一个变量或数组元素的生存周期，指在程序执行过程中，从一个对其写入的语句，到下一个对其写入的语句之前所包括的所有语句.变量x的一个生存周期的实例表示为

Lx=Sdef∩

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

(5)

为便于之后的计算，这里仅考虑对指定变量或数组元素写入和读取的语句.用多面体表示一个生存周期的中所有读语句

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

(6)

用L代表一个生存周期的实例

L=(iW,ωS)

(7)

本文的方法在GCC的Graphite框架[8]中实现.Graphite框架用于多面体分析和转换，是GCC的一个优化遍.其主要功能是从GCC的三地址Gimple中间表示中提取多面体，之后对该多面体进行变换，最后生成变换之后的多面体所对应的Gimple代码.Graphite中使用的是传统的依赖分析方法.

本文使用用于多面体模型编程的C语言库ISL[9]，生存周期的表示如下：

struct live_range {

isl_map write;

isl_union_map reads;

};

其中：write表示写语句，reads表示读语句的集合.

2.2 算法设计

本文的依赖分析方法主要由4个部分组成，分别是流依赖分析、生存周期分析、流依赖冲突分析以及生存周期冲突分析，其执行流程如图1所示.其中，流依赖分析及流依赖冲突分析在Graphite中已经存在.循环变换指Graphite中对循环所做的循环交换等变换.

(1)流依赖分析

计算循环体中数据的流依赖关系，其计算结果将被用于之后的流依赖冲突分析.

(2)生存周期分析

计算循环体中读写的每个的内存单元所对应的生存周期的集合.

图1 依赖分析执行流程Fig.1 Implementation of the dependence analysis

(3)循环变换

忽略数据中的依赖关系，对循环进行变换，变换的正确性将在之后的步骤中验证，如果变换后有依赖冲突，则对循环进行其它变换，或放弃对该循环的变换.

(4)流依赖冲突分析

分析循环变换之后的流依赖关系是否有冲突，保证循环变换后流依赖的正确性.

(5)生存周期冲突分析

分析循环变换之后的生存周期是否有冲突，如果有冲突，是否需要进行标量扩展或向前替换，来消除伪依赖，从而使变换正确

2.3 流依赖分析

传统依赖分析方法需要对流依赖、反依赖及输出依赖进行分析，这里仅对流依赖进行分析.

对于指定的变量或数组的引用，流依赖分析将找到其所在的每个语句，计算出依赖关系δSj→Si的集合.每个依赖关系表示读写同一个内存单元的读语句和写语句之间循环迭代的关系，其中读语句Si读取的是写入语句Sj写入的值，并且中间没有其他的写入操作将Sj写入的值覆盖.

2.4 生存周期分析

生存周期分析的目的是计算循环变换之前循环体中的所有生存周期的集合，以下是计算生存周期的算法：

算法计算生存周期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 流依赖冲突分析

通过变换之后的调度函数θ，将流依赖分析中计算得到的流依赖关系集合δSj→Si进行转换，检测变换之后每个流依赖关系所代表的两个语句执行顺序是否改变，如果有改变则是有冲突的，说明循环变换不正确.

2.6 生存周期冲突分析

生存周期冲突分析的目的是判断循环变换之后，原先的生存周期是否存在冲突.应用循环变换之后，原生存周期内语句的执行顺序可能发生改变，从而导致冲突，如果生存周期中的语句在循环变换后的执行顺序中有重叠，则称这两个生存周期有冲突.

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

算法 生存周期冲突分析输入: θ:循环变换后的调度函数 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所属的变量或数组进行标量扩展 endif endif endforendfor

使用标量扩展及向前替换消除伪依赖，虽然会稍微增加编译时间，但由于循环中所操作的内存单元是有限的，因此增加的编译时间是可以接受的.

通过向前替换及标量扩展的配合使用，在消除伪依赖，也同时减少了仅使用标量扩展时增加的内存占用.

3 实 验

使用PolyBench(the polyhedral benchmark suite)测试集进行实验，比较了Graphite中传统的考虑所有依赖的依赖分析方法，以及本文中消除伪依赖的依赖分析方法，在程序并行化中的效果.

本实验的基准使用GCC-4.8.2编译，选项为-O2-floop-parallelize -all-ftree-parallelize-loops=4，即使用多面体模型对循环进行依赖分析，对可并行化的循环进行变换，将其分为4个线程运行.

两种方法中进行变换的循环数量如表1所示，可以看出相比考虑所有依赖，通过使用本文中消除伪依赖的方法可以使更多的循环进行并行化.其中对外层循环并行化时，增加了并行的粒度，提升了并行的效果.说明了本文的方法能使更多循环进行变换.

表1 并行化的循环数量

图2显示了表1所列测试程序运行的加速比.加速比是用测试程序运行时间与基准运行时间的比率，其中测试基准时间的程序是仅使用-O2选项编译所得到的.从图中可见，由于消除伪依赖对更多循环进行了并行化的变换，加速比也有了相应的提高，进一步证明了本方法的有效性.

图2 加速比的比较Fig.2 Comparison of speedups

4 结 论

由于数据中存在的伪依赖关系并不是数据的固有关系，可以被消除，因此传统依赖分析中必须满足伪依赖关系的限制降低了并行化的效果.本文中基于多面体模型的依赖分析方法，通过引入生存周期的思想，配合使用标量扩展及向前替换消除伪依赖，可以使编译器可以对更多的循环体进行变换.本文基于ISL库在Graphite中实现了该方法，使Graphite可以对更多的循环进行并行化.实验测试表明，本文提出的消除伪依赖的依赖分析方法，对提高循环变换的数量是有效的.

[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—)，男，研究员，研究方向为航天嵌入式软件技术.