中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）并行编译简介

中国科学技术大学计算机科学与技术系 UST University of Science and Technology of China DEPARTMENT DF COMPUTER SCIENCE AND TECHNOLOOY 并行编译简介 并行编译器的组成及任务 数据依赖关系 循环的向量化与并行化 国家高性能计算中心(合肥) 2021/1/28 2

国家高性能计算中心（合肥） 2 2021/1/28 并行编译简介 ▪ 并行编译器的组成及任务 ▪ 数据依赖关系 ▪ 循环的向量化与并行化

中国科学技大学计算机科学与技术系 University of Science and Technology of China DEPARTMENT OF COMPUTER SCIENCE AND TECHNOLOOY 并行编译器的组成及任务 源代码 数据依赖与控制依赖关系分析 程序分析 数据流分析 程序优化包括循环向量化与并行化在内的 各种优化 并行代码生成并行语义识别,处理指令级并行 调度 向量机: 共享存储多机系统: 分布存储多机系统: 组织向量循环 任务划分 数据和计算分布 ·寄存器分配 处理机调度 通信 ·流水线调度 同步 同步 国家高性能计算中心(合肥) 2021/1/28 3

国家高性能计算中心（合肥） 3 2021/1/28 并行编译器的组成及任务 源代码 程序分析 程序优化 并行代码生成 向量机： •组织向量循环 •寄存器分配 •流水线调度 共享存储多机系统： •任务划分 •处理机调度 •同步 分布存储多机系统： •数据和计算分布 •通信 •同步 数据依赖与控制依赖关系分析 数据流分析 包括循环向量化与并行化在内的 各种优化 并行语义识别，处理指令级并行 调度

UST 中国科学技大学计算机科学与技术系 University of Science and Technology of China DEPARTMENT OF COMPUTER SCIENCE AND TECHNOLOOY 数据依赖关系 Def1:语句S和T,若存在变量使之满足下述条件之一, 则称语句T依赖于语句S,记为ST,否则S和T之间没有 数据依赖关系: (1)流依赖:ST,若X∈OUT(S)且∈IN(T) 且T使用S计算出的X的值;工流依赖于S; (2)反依赖:SaT,若x∈IN(S)且x∈OUT(T) 但S使用值先于T对x的定值;工反依赖于S; (3)输出依赖:δT,若x∈OUT(S)且 x∈OUT(T)但S较之先对进行定值; T输出依赖于S; 国家高性能计算中心(合肥) 2021/1/28

国家高性能计算中心（合肥） 4 2021/1/28 数据依赖关系 ▪ Def1: 语句S和T，若存在变量x使之满足下述条件之一， 则称语句T依赖于语句S，记为S  T，否则S和T之间没有 数据依赖关系： （1）流依赖 ： S  f T，若xOUT（S）且 xIN（T） 且T使用S计算出的x的值；T流依赖于S； （2）反依赖 ： S  a T，若xIN（S）且 xOUT（T） 但S使用x值先于T对x的定值；T反依赖于S； （3）输出依赖 ： S  o T，若xOUT（S）且 xOUT（T）但S较之T先对x进行定值； T输出依赖于S；

UST 中国科学技术大学计算机科学与技术系 University of Science and Technology of China DEPARTMENT OF COMPUTER SCIENCE AND TECHNOLOGY 依赖关系示例 e.g.考虑语句序列: S: A=B+D IN: BD, OUT: A T: C= A* 3 IN: A, OUT:C U: A=A+ IN: AC, OUT: A V: E=A/2 IN: A, OUT: E tof U UU 国家高性能计算中心(合肥) 2021/1/28 5

国家高性能计算中心（合肥） 5 2021/1/28 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

中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 依赖关系示例 eg.循环语句: S(1):A[1]=B[3]+1 for i= 1 to 100 do T(1):B[1]=A[0]-1 s:A[j]=B[i+2]+1:5(2):A[2]=B4]+1 T:]=A[i1]-1;T2:2]=A[-1 end for S(3):A[3]=B[5]+1 T(3):B[3]=A[2]-1 依赖关系 S(100):A[100]=B[102]+1 sfT T(100):B[100]=A[99]-1 SSaT 国家高性能计算中心(合肥) 2021/1/28

国家高性能计算中心（合肥） 6 2021/1/28 依赖关系示例 e.g. 循环语句： for i = 1 to 100 do S : A[i] = B[ i+2] + 1; T : B[i] = A[i-1] – 1; end for S(1) : A[1] = B[3] + 1 T(1) : B[1] = A[0] – 1 S(2) : A[2] = B[4] + 1 T(2) : B[2] = A[1] – 1 S(3) : A[3] = B[5] + 1 T(3) : B[3] = A[2] – 1 . . . S(100) : A[100] = B[102] + 1 T(100) : B[100] = A[99] – 1  f  a 依赖关系： S  f T S  a T

中图种学学计算机科学与术系 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)以 及变量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)）的集合

中图种学学计算机科学与术系 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 α >β 或 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 各语句间依赖关系如何呢？