并行编译简介

并行编译简介国家高性能计算中心（合肥）22019/12/16并行编译简介并行编译器的组成及任务数据依赖关系循环的向量化与并行化国家高性能计算中心（合肥）32019/12/16并行编译器的组成及任务源代码程序分析程序优化并行代码生成向量机：•组织向量循环•寄存器分配•流水线调度共享存储多机系统：•任务划分•处理机调度•同步分布存储多机系统：•数据和计算分布•通信•同步数据依赖与控制依赖关系分析数据流分析包括循环向量化与并行化在内的各种优化并行语义识别，处理指令级并行调度国家高性能计算中心（合肥）42019/12/16数据依赖关系Def1:语句S和T，若存在变量x使之满足下述条件之一，则称语句T依赖于语句S，记为ST，否则S和T之间没有数据依赖关系：（1）流依赖：SfT，若xOUT（S）且xIN（T）且T使用S计算出的x的值；T流依赖于S；（2）反依赖：SaT，若xIN（S）且xOUT（T）但S使用x值先于T对x的定值；T反依赖于S；（3）输出依赖：SoT，若xOUT（S）且xOUT（T）但S较之T先对x进行定值；T输出依赖于S；国家高性能计算中心（合肥）52019/12/16e.g.考虑语句序列：S:A=B+DT:C=A*3U:A=A+CV:E=A/2依赖关系示例IN:BD，OUT：AIN:A，OUT：CIN:AC，OUT：AIN:A，OUT：ESfTSfUSoUTfUTaUUfV国家高性能计算中心（合肥）62019/12/16依赖关系示例e.g.循环语句：fori=1to100doS:A[i]=B[i+2]+1;T:B[i]=A[i-1]–1;endforS(1):A[1]=B[3]+1T(1):B[1]=A[0]–1S(2):A[2]=B[4]+1T(2):B[2]=A[1]–1S(3):A[3]=B[5]+1T(3):B[3]=A[2]–1...S(100):A[100]=B[102]+1T(100):B[100]=A[99]–1fa依赖关系：SfTSaT国家高性能计算中心（合肥）72019/12/16数据依赖关系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)）的集合。国家高性能计算中心（合肥）82019/12/16依赖距离和依赖向量令α=(α1,α2,…,αn)和β=(β1,β2,…,βn)是n层循环内的n个整数下标向量，假定α和β存在数据相关性，则依赖距离向量（DependentDistanceVector）D=(D1,D2,…,Dn)定义为β-α；而依赖方向向量（DependentDirectionVector）d=(d1,d2,…,dn)定义为：iiiiiiiαβd==α=βαβ或1或0或－1国家高性能计算中心（合肥）92019/12/16例如，有如下的三层循环嵌套：fori=l1tou1doforj=l2tou2dofork=l3tou3doA(i+1,j,k–1)=A(i,j,k)+Cendforendforendfor则数组A的三维迭代之间的相关距离向量D=(i+1–i,j–j,k–1–k)=(1,0,-1)和相关方向向量=(,=,)。相关方向向量对计算循环体间相关性十分有用，其相关性是通过相关方向向量不是”=”号的外层循环传递的；相关距离向量指明在同一存储单元的两次访问之间循环迭代的实际距离。它们对开发并行性或优化存储器层次结构时起到指引作用。国家高性能计算中心（合肥）102019/12/16语句依赖图和迭代依赖图语句依赖图－依赖关系的有向图。将语句，如S和T，看成结点，若有ST，则：间接依赖关系－，即依赖关系的传递闭包。若ST，则在语句依赖图中存在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)。-ST-国家高性能计算中心（合肥）112019/12/16语句依赖图示例有如下循环语句：fori=4to200doS: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)+1endfor各语句间依赖关系如何呢？国家高性能计算中心（合肥）122019/12/16语句T流依赖于语句S，即SfT，满足依赖关系的偶对集合为：{S(i),T(j)|i=j-1;5≤j≤200}∪{S(i),T(j)|i=j-3;7≤j≤200}语句S流依赖于语句T，即TfS，满足依赖关系的偶对集合为：{T(i),S(j)|i=j-2;6≤j≤200}语句S输出依赖于语句U，即UoS，满足依赖关系的偶对集合为：{U(i),S(j)|i=j-1;5≤j≤200}语句T反依赖于语句U，即UaT，满足依赖关系的偶对集合为：{U(i),T(j)|j=2*i+1;4≤i≤99}语句T是否流依赖于语句U呢？国家高性能计算中心（合肥）132019/12/16fori=4to200doS: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)+1endfor语句依赖图示例STUffoa国家高性能计算中心（合肥）142019/12/16迭代依赖图示例（1）有如下二重循环：fori=0to5doforj=0to4doS:A(i+1,j+1)=A(i,j)+B(i,j)endforendfor显然，SfS。满足依赖关系的偶对集合：{S(i1,i2),S(j1,j2)|j1=i1+1,j2=i2+1,0≤i1≤4,0≤i2≤3}//依赖方向向量和距离向量各是什么？国家高性能计算中心（合肥）152019/12/16迭代依赖图（1）012345i1234j国家高性能计算中心（合肥）162019/12/16迭代依赖图示例（2）有如下二重循环：L1:fori1=0to4doL2:fori2=0to4doS:A(i1+1,i2)=B(i1,i2)+C(i1,i2)T:B(i1,i2+1)=A(i1,i2+1)+1U:D(i1,i2)=B(i1,i2+1)–2endforendfor国家高性能计算中心（合肥）172019/12/16语句T流依赖于语句S，即SfT，满足依赖关系的偶对：{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fS，满足依赖关系的偶对：{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fU，满足依赖关系的偶对：{T(i1,i2),U(j1,j2)|j1=i1,j2=i2,0≤i1≤4,0≤i2≤4}，距离向量为(0,0)，方向向量为(0,0)。此依赖关系与循环无关。国家高性能计算中心（合肥）182019/12/16STUfff语句依赖图01234i1234j迭代依赖图国家高性能计算中心（合肥）192019/12/16考虑如下循环的迭代依赖图：forI=1to4doforJ=1to4doS:A(I,J)=A(I-1,J)+A(I,J-1)endforendfor国家高性能计算中心（合肥）202019/12/16依赖关系方程假定循环中数组下标是循环索引变量的线性表达式循环的一般表示：(X是n维数组，f和g是循环索引变量I=(I1,I2,…,Im)的线性函数)L1:forI1=p1toq1doL2:forI2=p2toq2do...Lm:forIm=pmtoqm...S:X(f1(I),f2(I),…,fn(I))=...T:...=...X(g1(I),g2(I),…,gn(I))......endfor...endforendfor国家高性能计算中心（合肥）212019/12/16依赖关系方程(丢番图方程）上述循环L中语句S和T，令u=X(f1(I),f2(I),…,fn(I))是S的变量，而v=X(g1(J),g2(J),…,gn(J))，u或v至少一个是相应语句的输出变量。若u、v导致S和T之间的依赖关系，则以下方程组f1(I)－g1(J)=0f2(I)－g2(J)=0...fn(I)－gn(J)=0有满足下述约束条件的整数解（i,j），i=(i1,i2,…,im),j=(j1,j2,…,jm):pr≤ir≤qrpr≤jr≤qr；且该解满足下述特定情况下的附加条件：（1）若ST且ST则i≤j（2）若S＝T且SS则ij（3）若ST且TS则ij国家高性能计算中心（合肥）222019/12/16如果依赖方程（丢番图方程）有满足上述条件的整数解（i，j），那么（1）若ij,则S’T（2）若ij,则T’S（3）若i＝j,且S＝T，则S’T其中’表示间接依赖关系。国家高性能计算中心（合肥）232019/12/16考虑如下程序段：L1:forI=1to50do...S:X(2*I)=......T:...=...X(3*I+1)......endfor这里：f1(I)=2*I；g1(J)=3*J+1。依赖方程为：f1(I)-g1(J)=02*I–3*J=1,而依赖约束为：1≤I≤50，1≤J≤50。该方程的解（I,J)对应的数组变量会导致S和T之间的依赖。国家高性能计算中心（合肥）242019/12/16循环向量化循环向量化将仅含有数组赋值语句的循环L转换成等价的向量语句如：循环forI=1toNdoS:A(I)=D(I)*ET:C(I)=A(I)+B(I)endfor可以改写为等价的向量语句：S’:A(1:N)=D(1:N)*ET’:C(1:N)=A(1:N)+B(1:N)国家高性能计算中心（合肥）252019/12/16可向量化循环如果将循环内的数组赋值改为相应的向量语句后，按原来语句次序执行所得结果与原来串行执行一样，那么...但以下循环不可向量化：forI=1toNdoS:A(I)=A(I-1)+1;//不能写成A(1:N)=A(0:N-1)+1endfor而以下循环却可以向量化：forI=1toNdoS1:A(I)=A(I+1)+1;//可以写成A(1:N)=A(2:N＋1)+1endfor为什么？国家高性能计算中心（合肥）262019/12/16可向量化循环的充要条件对于循环L=(L1,L2,...,Lm)其最内层循环Lm可向量化当且仅当：Lm中任意两个语句S和T，（1）当ST时，不存在方向向量为(0,0,…,1)的S对T的依赖关系，TS；（三种依赖关系中任何一种）（2）当S＝T时，不存在方向向量为(0,0,…,1)的S对T的流依赖关系，TfS；换言之，最内层循环中如果不存在与语句词法顺序相反的依赖关系（即反向依赖），则最内层循环可向量化。再次考察：forI=1toNdoS:A(I)=A(I-1)+1;//不能写成A(1:N)=A(0:N-1)+1endfor//此循环中存在SfS，且方向为(1),距离为(1)国