并行计算,第一级,第二级,第三级,第一级,第二级,第三级,国家高性能计算中心（合肥）,*,*,并行算法实践,并行编译概述,并行编译器的组成及任务,数据依赖关系,循环的向量化与并行化,2024/10/22,2,国家高性能计算中心（合肥）,并行编译器的组成及任务,源代码,程序分析,程序优化,并行代码生成,向量机：,组织向量循环,寄存器分配,流水线调度,共享存储多机系统：,任务划分,处理机调度,同步,分布存储多机系统：,数据和计算分布,通信,同步,数据依赖与控制依赖关系分析,数据流分析,包括循环向量化与并行化在内的各种优化,并行语义识别，处理指令级并行调度,2024/10/22,3,国家高性能计算中心（合肥）,数据依赖关系,Def1:,语句,S,和,T,，若存在变量,x,使之满足下述条件之一，则称语句,T,依赖于语句,S,，记为,S,T,，否则,S,和,T,之间没有数据依赖关系：,（,1,）流依赖：,S,f,T,，若,xOUT,（,S,）且,xIN,（,T,）,且,T,使用,S,计算出的,x,的值；,T,流依赖于,S,；,（,2,）反依赖：,S,a,T,，若,xIN,（,S,）且,xOUT,（,T,）,但,S,使用,x,值先于,T,对,x,的定值；,T,反依赖于,S,；,（,3,）输出依赖：,S,o,T,，若,xOUT,（,S,）且,xOUT,（,T,）但,S,较之,T,先对,x,进行定值；,T,输出依赖于,S,；,2024/10/22,4,国家高性能计算中心（合肥）,e.g.,考虑语句序列,：,S:A=B+D,T:C=A*3,U:A=A+C,V:E=A/2,依赖关系示例,IN:B D,，,OUT,：,A,IN:A,，,OUT,：,C,IN:A C,，,OUT,：,A,IN:A,，,OUT,：,E,S,f,T,S,f,U,S,o,U,T,f,U,T,a,U,U,f,V,2024/10/22,5,国家高性能计算中心（合肥）,依赖关系示例,e.g.,循环语句：,for i=1 to 100 do,S:,Ai,=B i+2+1;,T:,Bi,=Ai-1 1;,end for,S(1):A1=B3 +1,T(1):B1=A0 1,S(2):A2=B4 +1,T(2):B2=A1 1,S(3):A3=B5 +1,T(3):B3=A2 1,.,S(100):A100=B102 +1,T(100):B100=A99 1,f,a,依赖关系：,S,f,T,S,a,T,2024/10/22,6,国家高性能计算中心（合肥）,数据依赖关系,Def2,：,语句,S,和,T,在循环,L,中。
如果,S,的实例,S(i,),和,T,的实例,T(j,),以及变量,u,S,，变量,v,T,，满足：,（,1,）,u,和,v,至少有一个是输出变量；,（,2,）,u,S(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,),）的集合2024/10/22,7,国家高性能计算中心（合肥）,依赖距离和依赖向量,令,=(,1,2,n,),和,=(,1,2,n,),是,n,层循环内的,n,个整数下标向量，假定,和,存在数据相关性，则,依赖距离向量,（,Dependent Distance Vector,）,D=(D,1,D,2,D,n,),定义为,-,；而,依赖方向向量,（,Dependent Direction Vector,）,d=(d,1,d,2,d,n,),定义为：,或,1,或,0,或,1,2024/10/22,8,国家高性能计算中心（合肥）,例如，有如下的三层循环嵌套：,for,i=,l,1,to,u,1,do,for,j=,l,2,to,u,2,do,for,k=,l,3,to,u,3,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),和相关方向向量,=(),。
相关方向向量对计算循环体间相关性十分有用，其相关性是通过相关方向向量不是”,=”,号的外层循环传递的；相关距离向量指明在,同一存储单元的两次访问之间循环迭代的实际距离,它们对开发并行性或优化存储器层次结构时起到指引作用2024/10/22,9,国家高性能计算中心（合肥）,语句依赖图和迭代依赖图,语句依赖图依赖关系,的有向图将语句，如,S,和,T,，看成结点，若有,S,T,，则：,间接依赖关系 ，即依赖关系的传递闭包若,S T,，则在语句依赖图中存在,S,到,T,的一条路径迭代依赖图即（循环）迭代之间的依赖关系在循环,L,中，若语句,T,依赖于语句,S,，即,S,T,令,S(I),和,T(J),是满足依赖关系的偶对，,S(I),T(J),，此时应该有,I,J,在,IJ,时，称迭代,H(J),依赖于迭代,H(I),，记为,H(I),H(J),S,T,2024/10/22,10,国家高性能计算中心（合肥）,语句依赖图示例,有如下循环语句：,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,各语句间依赖关系如何呢？,2024/10/22,11,国家高性能计算中心（合肥）,语句,T,流依赖于语句,S,，即,S,f,T,，满足依赖关系的偶对集合为：,|i=j-1;5,j,200 ,|i=j-3;7,j,200,语句,S,流依赖于语句,T,，即,T,f,S,，满足依赖关系的偶对集合为：,|i=j-2;6,j,200,语句,S,输出依赖于语句,U,，即,U,o,S,，满足依赖关系的偶对集合为：,|i=j-1;5,j,200,语句,T,反依赖于语句,U,，即,U,a,T,，满足依赖关系的偶对集合为：,|j=2*i+1;4,i99,语句,T,是否流依赖于语句,U,呢？,2024/10/22,12,国家高性能计算中心（合肥）,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,语句依赖图示例,S,T,U,f,f,o,a,2024/10/22,13,国家高性能计算中心（合肥）,迭代依赖图示例（,1,）,有如下二重循环：,for i=0 to 5 do,for j=0 to 4 do,S:,A(i+1,j+1),=,A(i,j,),+B(,i,j,),endfor,endfor,显然，,S,f,S,。
满足依赖关系的偶对集合：,|j1=i1+1,j2=i2+1,0,i1,4,0,i2,3,/,依赖方向向量和距离向量各是什么？,2024/10/22,14,国家高性能计算中心（合肥）,迭代依赖图（,1,）,2024/10/22,15,国家高性能计算中心（合肥）,迭代依赖图示例（,2,）,有如下二重循环：,L1:for i1=0 to 4 do,L2:for i2=0 to 4 do,S:,A(i1+1,i2),=,B(i1,i2),+C(i1,i2),T:,B(i1,i2+1),=,A(i1,i2+1),+1,U:D(i1,i2)=,B(i1,i2+1),2,endfor,endfor,2024/10/22,16,国家高性能计算中心（合肥）,语句,T,流依赖于语句,S,，即,S,f,T,，满足依赖关系的偶对：,S(i1,i2),T(j1,j2)|j1=i1+1,j2=i2-1,0,i1,3,1,i2,4,，距离向量为,(1,-1),，方向向量为,(1,-1),此依赖关系由循环,L1,携带；,语句,S,流依赖于语句,T,，即,T,f,S,，满足依赖关系的偶对：,T(i1,i2),S(j1,j2)|j1=i1,j2=i2+1,0,i1,4,0,i2,3,，距离向量为,(0,1),，方向向量为,(0,1),。
此依赖关系由循环,L2,携带；,语句,U,流依赖于语句,T,，即,T,f,U,，满足依赖关系的偶对：,T(i1,i2),U(j1,j2)|j1=i1,j2=i2,0,i1,4,0,i2,4,，距离向量为,(0,0),，方向向量为,(0,0),此依赖关系与循环无关2024/10/22,17,国家高性能计算中心（合肥）,S,T,U,f,f,f,语句依赖图,迭代依赖图,2024/10/22,18,国家高性能计算中心（合肥）,考虑如下循环的迭代依赖图：,for I=1 to 4 do,for J=1 to 4 do,S:A(I,J)=A(I-1,J)+A(I,J-1),endfor,endfor,2024/10/22,19,国家高性能计算中心（合肥）,依赖关系方程,假定循环中数组下标是循环索引变量的线性表达式,循环的一般表示：,(X,是,n,维数组，,f,和,g,是循环索引变量,I=(I,1,I,2,I,m,),的线性函数,),L,1,:for I,1,=p,1,to q,1,do,L,2,:for I,2,=p,2,to q,2,do,.,L,m,:for,I,m,=p,m,to,q,m,.,S:,X(f,1,(I),f,2,(I),f,n,(I,),=.,T:.=.,X(g,1,(I),g,2,(I),g,n,(I,),.,.,endfor,.,endfor,endfor,2024/10/22,20,国家高性能计算中心（合肥）,依赖关系方程,(,丢番图方程）,上述循环,L,中语句,S,和,T,，令,u=,X(f,1,(I),f,2,(I),f,n,(I,),是,S,的变量，而,v=,X(g,1,(I),g,2,(I),g,n,(I,),，,u,或,v,至少一个是相应语句的输出变量。
若,u,、,v,导致,S,和,T,之间的依赖关系，则以下方程组,f,1,(I),g,1,(J)=0,f,2,(I),g,2,(J)=0,.,f,n,(I,),g,n,(J,)=0,有满足下述约束条件的整数解（,i,j,），,i=(i,1,i,2,i,m,),j=(j,1,j,2,j,m,):,p,r,i,r,q,r,p,r,j,r,q,r,；且该解满足下述特定情况下的附加条件：,（,1,）若,S,T,且,S,T,则,i,j,（,2,）若,S,T,且,S,S,则,i,j,（,3,）若,S,j,2024/10/22,21,国家高性能计算中心（合肥）,如果依赖方程（丢番图方程）有满足上述条件的整数解（,i,，,j,），那么,（,1,）若,i,j,则,T,S,（,3,）若,i,j,且,S,T,，则,S,T,其中,表示,间接依赖关系,2024/10/22,22,国家高性能计算中心（合肥）,考虑如下程序段：,L1:for I=1 to 50 do,.,S:X(2*I)=.,.,T:.=.X(3*I+1).,.,endfor,这里：,f,1,(I)=2*I,；,g,1,(J)=3*J+1,依赖方程为：,f,1,(I)-g,1,(J)=0,2*I 3*J=1,而依赖约束为：,1,I,50,，,1,J,50,。
该方程的解（,I,J),对应的数组变量会导致,S,和,T,之间的依赖2024/10/22,23,国家高性能计算中心（合肥）,循环向量化,循环向量化,将仅含有数组赋值语句的循环,L,转换成等价。
