中国科学技术大学：《并行计算 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