并行编译简介.ppt

《并行编译简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、并行编译简介国家高性能计算中心（合肥）22021/7/23并行编译简介并行编译器的组成及任务数据依赖关系循环的向量化与并行化国家高性能计算中心（合肥）32021/7/23并行编译器的组成及任务源代码程序分析程序优化并行代码生成向量机：组织向量循环寄存器分配流水线调度共享存储多机系统：任务划分处理机调度同步分布存储多机系统：数据和计算分布通信同步数据依赖与控制依赖关系分析数据流分析包括循环向量化与并行化在内的各种优化并行语义识别，处理指令级并行调度国家高性能计算中心（合肥）42021/7/23数据依赖关系Def1:语句S和T，若存在变量x使之满足下述

2、条件之一，则称语句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；国家高性能计算中心（合肥）52021/7/23e.g.考虑语句序列：S:A=B+DT:C=A*3U:A=A+CV:E=A/2依赖关系示例IN:BD，OUT：AIN:A，OU

3、T：CIN:AC，OUT：AIN:A，OUT：ESfTSfUSoUTfUTaUUfV国家高性能计算中心（合肥）62021/7/23依赖关系示例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]

4、–1fa依赖关系：SfTSaT国家高性能计算中心（合肥）72021/7/23数据依赖关系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)输出依

5、赖：uOUT(S),vOUT(T)T对S的依赖即为满足上述条件的偶对（S(i),T(j)）的集合。国家高性能计算中心（合肥）82021/7/23依赖距离和依赖向量令α=(α1,α2,…,αn)和β=(β1,β2,…,βn)是n层循环内的n个整数下标向量，假定α和β存在数据相关性，则依赖距离向量（DependentDistanceVector）D=(D1,D2,…,Dn)定义为β-α；而依赖方向向量（DependentDirectionVector）d=(d1,d2,…,dn)定义为：或1或0或－1国家高性能计算中心（合肥）92021/7/23例

6、如，有如下的三层循环嵌套：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)和相关方向向量=(<,=,>)。相关方向向量对计算循环体间相关性十分有用，其相关性是通过相关方向向量不是”=”号的外层循环传递的；相关距离向量指明在同一存储单元的两次访问之间循环迭代的实际距离。它们对开发并行性或优化存储器层次结构时起到指引作用。国家高性能计算中心（合肥）10

7、2021/7/23语句依赖图和迭代依赖图语句依赖图－依赖关系的有向图。将语句，如S和T，看成结点，若有ST，则：间接依赖关系－，即依赖关系的传递闭包。若ST，则在语句依赖图中存在S到T的一条路径。迭代依赖图－即（循环）迭代之间的依赖关系。在循环L中，若语句T依赖于语句S，即ST。令S(I)和T(J)是满足依赖关系的偶对，S(I)T(J)，此时应该有I≤J。在I

8、(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