中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT DF COMPUTE三巴 ENCE AND ECHNOLDD 数据依赖关系 Def2:语句5和T在循环L中。如果5的实例S(和T的实例T(j)以 及变量u∈S,变量ν∈T,满足: (1)u和V至少有一个是输出变量; (2)u∈S(和变量Ⅴ∈T()表示同一个存篇单元M (3)在L的顺序执行中,S()先于T( (4)在L的顺序执行中,S()之间T()没有其他对M的写操作; 则u、V引起T依赖于5,即5δ千,称为T)依赖于S(), 其 中: 流依赖:u∈OUT(S),V∈IN(T 反依赖:u∈IN(S),∈OUT(T 输出依赖:u∈OUT(S),V∈OUT(T T对5的依赖即为满足上述条件的偶对(S().T()的集合。 国家高性能计算中心(合肥) 2021/1/28
国家高性能计算中心（合肥） 7 2021/1/28 数据依赖关系 ▪ Def2：语句S和T在循环L中。如果S的实例S(i)和T的实例T(j)以 及变量uS，变量v T，满足： （1）u和v至少有一个是输出变量； （2）uS(i)和变量v T(j)表示同一个存储单元M （3）在L的顺序执行中，S(i)先于T(j) （4）在L的顺序执行中， S(i)之间T(j)没有其他对M的写操作； 则u、v引起T依赖于S，即S T，称为T(j)依赖于S(i)， 其 中： 流依赖： u OUT(S) , v IN(T) 反依赖： u IN(S) , v OUT(T) 输出依赖：u OUT(S) , v OUT(T) T 对S的依赖即为满足上述条件的偶对（S(i),T(j)）的集合
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 依赖距离和依赖向量 令x=(x1x2…,xn)和β=(31,32…,3D是n层循环内的n个整数 下标向量,假定α和β存在数据相关性,则依赖距离向量 ( Dependent Distance Vector)D=①D1D2…,D)定义为 β-αx;而依赖方向向量( Dependent Direction Vector)d (d1d2;…d)定义为: 或1 或0 >.> 或-1 国家高性能计算中心(合肥) 2021/1/28 8
国家高性能计算中心（合肥） 8 2021/1/28 依赖距离和依赖向量 ▪ 令α=(α1 ,α2 ,…,αn ) 和β=(β1 ,β2 ,…,βn )是n层循环内的n个整数 下标向量，假定α和β存在数据相关性，则依赖距离向量 （Dependent Distance Vector）D = (D1 ,D2 ,…,Dn )定义为 β-α；而依赖方向向量（Dependent Direction Vector）d = (d1 ,d2 ,…,dn )定义为： i i i i i i i < α <β d = = α =β > α >β 或 1 或 0 或 －1
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 例如,有如下的三层循环嵌套: for i= 1, to u do for j=l2 to u2 do for k=l3 to u, do A(i+l,k-1=A(1,j,k)+C endfor endfor endfor 则数组A的三维迭代之间的相关距离向量D=(+1-ij-jk-1 k)=(1,0,-1)和相关方向向量=(,=,>)。 相关方向向量对计算循环体间相关性十分有用,其相关性是通过相关 方向向量不是”=”号的外层循环传递的;相关距离向量指明在同 存储单元的两次访问之间循环迭代的实际距离。它们对开发并 行性或优化存储器层次结构时起到指引作用。 国家高性能计算中心(合肥) 2021/1/28
国家高性能计算中心（合肥） 9 2021/1/28 例如，有如下的三层循环嵌套： for i = l1 to u1 do for j = l2 to u2 do for k = l3 to u3 do A(i + 1, j, k – 1) = A(i, j, k) + C endfor endfor endfor 则数组A的三维迭代之间的相关距离向量D = (i + 1 – i, j – j, k – 1 – k ) = (1, 0, -1)和相关方向向量= (<, =, >)。 相关方向向量对计算循环体间相关性十分有用，其相关性是通过相关 方向向量不是”= ”号的外层循环传递的；相关距离向量指明在同 一存储单元的两次访问之间循环迭代的实际距离。它们对开发并 行性或优化存储器层次结构时起到指引作用
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 语句依赖图和送代依赖图 语句依赖图一依赖关系δ的有向图。将语句,如S和T, 看成结点,若有SδT,则: 间接依赖关系-δ,即依赖关系δ的传递闭包。 若SδT,则在语句依赖图中存在S到T的一条路径。 迭代依赖图一即(循环)迭代之间的依赖关系。在循环 L中,若语句T依赖于语句S,即SδT。令S(和T()是满 足依赖关系的偶对,S①δT①,此时应该有I≤J。在I< 时,称迭代H①依赖于迭代H①,记为H①δH①)。 国家高性能计算中心(合肥) 2021/1/28 10
国家高性能计算中心（合肥） 10 2021/1/28 语句依赖图和迭代依赖图 ▪ 语句依赖图－依赖关系的有向图。将语句，如S和T， 看成结点，若有S T，则： 间接依赖关系－ ，即依赖关系的传递闭包。 若S T，则在语句依赖图中存在S到T的一条路径。 ▪ 迭代依赖图－即（循环）迭代之间的依赖关系。在循环 L中，若语句T依赖于语句S，即S T。令S(I)和T(J)是满 足依赖关系的偶对，S(I) T(J)，此时应该有I≤J。在I<J 时，称迭代H(J)依赖于迭代H(I)，记为H(I) H(J)。 - S T -
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT DF COMPUTE三巴 ENCE AND ECHNOLDD 语勺保赖示例 有如下循环语句: for i= 4 to 200 do S:A()=B()+c() T:B(i+2)=A(-1)+A(-3)+c(-1) U:A(i+1)=B(2*i+3)+1 endfor 各语句间依赖关系如何呢? 国家高性能计算中心(合肥) 2021/1/28
国家高性能计算中心（合肥） 11 2021/1/28 语句依赖图示例 有如下循环语句： for i = 4 to 200 do S: A(i) = B(i) + c(i) T: B(i+2) = A(i-1) + A(i-3) + C(i-1) U: A(i+1) = B(2*i+3) + 1 endfor 各语句间依赖关系如何呢？