并行计算-多媒体课件-并行程序设计-ch06HPF编程指南.ppt

1、并行算法实践,上篇 并行程序设计导论,国家高性能计算中心（合肥）,2,2020/8/25,并行算法实践上篇 并行程序设计导论,单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法,国家高性能计算中心（合肥）,3,2020/8/25,单元II 并行程序编程指南,第四章 MPI编程指南 第五章 PVM编程指南 第六章 HPF编程指南 第七章 OpenMP编程指南,国家高性能计算中心（合肥）,4,2020/8/25,第六章 HPF编程指南,6.1 HPF概述 6.2 HPF编程简介 6.3 数据映射 6.4 数据并行结构 6.5 HPF语言的过程 6.6 HPF实例分析

2、：2D FFT 6.7 HPF语言其他特性,国家高性能计算中心（合肥）,5,2020/8/25,6.1 HPF概述,引言 HPF的语言特点 HPF的语言模型,国家高性能计算中心（合肥）,6,2020/8/25,引言,HPF语言基础 HPF历史 HPF的设计目标,国家高性能计算中心（合肥）,7,2020/8/25,HPF语言基础,HPF语言以FORTRAN90基础 扩展了FORTRAN90 在并行机上支持数据对界和分布的控制； 加入新的数据并行结构； 内部过程和标准库提供很多有用的高级抽象功能； EXTRINSIC过程使得和其他语言或风格的接口进行标准化； 提供指令用于解决一些顺序和存储关联问题

3、；,国家高性能计算中心（合肥）,8,2020/8/25,HPF历史,DEC，高性能FORTRAN版本， 组织HPF论坛，1992年1月； 论坛正式成立，1992年3月； 发布HPF1.0，1993年5月； 发布HPF1.1，1994年11月； 发布HPF2.0，1997年1月；,国家高性能计算中心（合肥）,9,2020/8/25,HPF设计目标,首要目标： 对数据并行程序设计的支持； 跨越不同体系结构的可扩展性； 在具有不同存储访问开销的并行计算机上的高性能 ； 以标准Fortran作为基础、与其它语言以及其它程序设计风格之间的开放接口和互操作性。 次要目标 能在有限时间内完成实现上的可行性；

4、 为Fortran和C将来的标准活动提供支持； 为以一致的方式向语言中增加高级特征提供一条有发展的途径。,国家高性能计算中心（合肥）,10,2020/8/25,HPF的语言特点,HPF2.0的组成； HPF2.0的一些基本特征；,国家高性能计算中心（合肥）,11,2020/8/25,HPF2.0的组成,HPF2.0语言的组成 语言的基本部分； 已经核准的扩展部分； 已被承认的外部接口；,国家高性能计算中心（合肥）,12,2020/8/25,HPF2.0的一些基本特征,数据并行制导 ； 数据映射制导； 新的内部过程和库过程 ； 外部过程 ；,国家高性能计算中心（合肥）,13,2020/8/25,

5、HPF的语言模型,HPF的并行方式 HPF模型的一些不足,国家高性能计算中心（合肥）,14,2020/8/25,HPF的并行方式,HPF支持非协作任务的并行方式 ： HPF程序中派生线程来执行细粒度的并行任务 将全部的HPF程序作为一个任务，提供了粗粒度的并行性，在每个任务中可以利用细粒度的循环或数组并行,国家高性能计算中心（合肥）,15,2020/8/25,HPF模型的一些不足,对以不太结构化的方式来表示并行性支持不够 ； 对有一些数据并行应用HPF处理得不好 ； HPF 不能和SMP构成的机群系统相结合,国家高性能计算中心（合肥）,16,2020/8/25,6.2 HPF编程简介,一个简单

6、的HPF程序实例； HPF的基本特征；,国家高性能计算中心（合肥）,17,2020/8/25,一个简单的HPF程序实例,program example! declare variable integer a(1024)，b(1024)，c(1024) integer : result = 0! declare distribute !hpf$ distribute a(block) !hpf$ distribute b(block) !hpf$ distribute c(block)! align values to distributed variables a=1 b=2! add the

7、m c = a + b! calculate the sum in all elements of c result = sum( c )! print the result print *， “The last element is”，c(1024) print *， “The sum in all elements is ”， resultend,国家高性能计算中心（合肥）,18,2020/8/25,一个简单的HPF程序实例,它的输出如下： The last element is 3The sum in all elements is 3072,国家高性能计算中心（合肥）,19,2020/

8、8/25,HPF的基本特性1,变量声明 integer : x,y integer : result = 0 real x,y integer a(1024) ，b(1024)， c(1024) 指令前缀 HPF指令是以Fortran 90语言中注释的形式出现的 !hpf$ Chpf$ *hpf$,国家高性能计算中心（合肥）,20,2020/8/25,HPF的基本特性2,数据分布 作用：允许程序员向编译器建议如何将数组元素指定到处理器存储器中。 !hpf$ distribute a(block) 实例程序的分布图,国家高性能计算中心（合肥）,21,2020/8/25,HPF的基本特性3,顺序变

9、量 没有显式指示为分布的数组和所有的标量 处理器的私有变量 分布数组的赋值 a=1，b=2,国家高性能计算中心（合肥）,22,2020/8/25,HPF的基本特性4,多个分布数组之间的运算 被选择的分布数组需满足如下条件 ： 在语句中，该数组的同一元素最多只访问一次，该数组多次在语句中出现时除外； 根据该数组将运算分配到各处理器后，引起的通信最少； 右部优先于左部 ； 效果图,国家高性能计算中心（合肥）,23,2020/8/25,HPF的基本特性5,分布数组的归约 result = sum(c)； 将c数组中所有元素求和，赋给顺序变量result；,国家高性能计算中心（合肥）,24,2020/

10、8/25,HPF的基本特性5,打印分布数组元素 HPF中I/O语句在非并行代码段中，在处理器0上执行。 例 ：print *，“The last element is :”，c(1024) 处理器0访问了处理器3上的分布数组元素， 引起了处理器间通信。,国家高性能计算中心（合肥）,25,2020/8/25,6.3 数据映射,目的: 使处理器间的通信开销最小； 负载在可用的处理器间均匀分布；,国家高性能计算中心（合肥）,26,2020/8/25,数据映射说明语句,模版 简单的抽象空间，可将其看成一个没有内容的数组 属性： 名字 、维数、维大小 !HPF$ TEMPLATE tem(4 , 8),

11、国家高性能计算中心（合肥）,27,2020/8/25,数据映射说明语句,虚拟处理器阵列 虚拟处理器阵列有名字、维数、维大小三个属性 PROCESSORS指令用于定义虚拟处理器阵列 虚拟处理器阵列中的处理器总数不得大于实际的物理处理器数 !HPF$PROCESSORS P(2,4),国家高性能计算中心（合肥）,28,2020/8/25,数据映射说明语句,模板到虚拟处理器阵列的映射 HPF提供了DISTRIBUTE编译指示 分布的方式 : 块分布 循环分布 块循环分布,国家高性能计算中心（合肥）,29,2020/8/25,模板到虚拟处理器阵列的映射,块分布 将数据分成相邻的P块(P为虚拟处理器阵列

12、上相应维的大小) 例子： !HPF$ TEMPLATE tem(16) !HPF$ PROCESSORS p(4) !HPF$ DISTRIBUTE tem(BLOCK) ONTO p,国家高性能计算中心（合肥）,30,2020/8/25,模板到虚拟处理器阵列的映射,循环分布 将模板该维中的元素依次轮流分给不同的处理器 ； 例子： !HPF$ TEMPLATE tem(16) !HPF$ PROCESSORS p(4) !HPF$ DISTRIBUTE tem(CYCLIC) ONTO p,国家高性能计算中心（合肥）,31,2020/8/25,模板到虚拟处理器阵列的映射,块循环分布 将模板该维

13、划分为相邻的大小为M的子块，然后将这些子块依次轮流分给不同处理器 例子： !HPF$ TEMPLATE tem(6) !HPF$ PROCESSORS p(4) !HPF$ DISTRIBUTE tem( CYCLIC( 2 ) ) ONTO p,国家高性能计算中心（合肥）,32,2020/8/25,模板到虚拟处理器阵列的映射,分布数组与模板 一个数组要分布必须要有一个模板 模板来源： 与定义的模板对界（Alignment）； 缺省的模板； 与另一个有模板的数组对界 ；,国家高性能计算中心（合肥）,33,2020/8/25,分布数组与模板,与模板对界 ALIGN编译指示，用来描述数组与模板的关

14、系 例子： REAL a(8) !HPF$ TEMPLATE tem(16) !HPF$ DISTRIBUTE tem(BLOCK) !HPF$ ALIGN a(i) WITH tem( 2*i ),国家高性能计算中心（合肥）,34,2020/8/25,分布数组与模板,缺省的模版 HPF中可以用DISTRIBUTE编译指示直接说明数组的分布方式 例子： INTEGER a(1024)!HPF$ DISTRIBUTE a(BLOCK) 等价于： INTEGER a(1024) !HPF$ TEMPLATE tem(1024) !HPF$ DISTRIBUTE tem(BLOCK) !HPF$ A

15、LIGN a(i) WITH tem(i),国家高性能计算中心（合肥）,35,2020/8/25,分布数组与模板,分布数组之间的对界 a(2*i) = b(i)*2 对应于： REAL a(200), b(100)!HPF$ TEMPLATE tem(600)!HPF$ DISTRIBUTE tem(BLOCK)!HPF$ ALIGN a(i) WITH tem(3*i)!HPF$ ALIGN b(i) WITH a(2*i),国家高性能计算中心（合肥）,36,2020/8/25,一个数据映射的HPF程序段分析,考虑如下程序段 ： INTEGERa(100) , b(100) , c(101)

16、 , i!HPF$ ALIGN a(i) WITH b(i-1)!HPF$ PROCESSORSp(4)!HPF$ DISTRIBUTE a(BLOCK) ONTO p!HPF$ DISTRIBUTE c(CYCLIC) ONTO p FORALL ( i = 2 ：100) a(i) = a(i) + b(i1) c(i) = c(i1) + c(i) + c(i+1) ENDFORALL,国家高性能计算中心（合肥）,37,2020/8/25,一个数据映射的HPF程序段分析,数据映射过程：,国家高性能计算中心（合肥）,38,2020/8/25,6.4 数据并行结构,数组运算 FORALL语句

17、和FORALL结构 INDEPENDENT指示,国家高性能计算中心（合肥）,39,2020/8/25,数组运算,数组和数组段 全数组和数组段都表示一批数据 数组段可以有起点、终点、步长 例子：a(1:3, 1:2) 数组段有一个重要的形属性 例子：a(2:3, 4:9)的形是(2, 6) 数组表达式 全数组或数组段可以和运算符一起组成数组表达式 数组表达式中全数组和数组段的形必须相同 例子 a(2 :4 :1) +b(1：3) a(2 ：4 ) +b( 1：3),国家高性能计算中心（合肥）,40,2020/8/25,数组运算,数组赋值 必须满足的条件： 左右表达式的形相同； 右部为标量表达式

18、； 例子： a(2 ：4, 5 ：8) = b(3 ：5, 1 ：4) a(1 ：4, 1 ：3) = a(1 ：2, 1 ：6) 当把一个标量赋值给一个数组段时，标量的值赋给该数组段的所有元素； 数组赋值是HPF编译器能识别的最小可并行的单位 ； 数组赋值能否真正并行，关键在于左部数组是否是分布的；,国家高性能计算中心（合肥）,41,2020/8/25,数组运算,WHERE语句及其结构 作用：给那些满足逻辑条件的数组元素赋值 ； 例子： INTEGER a(100), b(100)WHERE(a0) b = 0 只允许进行数组的赋值 WHERE结构不允许嵌套 数组内部函数 可以接收全数组或数

19、组段作为参数的库函数 可以返回一个标量，也可以返回一批数据，即有形。,国家高性能计算中心（合肥）,42,2020/8/25,FORALL语句和FORALL结构,FORALL语句 保持了数组赋值的语义； 例如：FORALL ( i = 1:n , j = 1:n) a(i,j) =0 等价于a(1:n,1:n)=0 用FORALL表示起来很简单，但用数组赋值却不容易表示 例如：FORALL(i=1:n, j=1:m) a(i,j) =i+j 一些例子： FORALL (k=1, m1) x (k+1)=x(k) FORALL (i=2:5, x(i)0) x(i)=x(i1)+x(i+1) FO

20、RALL (k=1:m, y(k).ne.0.0) x (k)=1.0/y(k) FORALL (i=1:2, j=1:3, y(i,j)0) z(i,j)=1/y(i,j),国家高性能计算中心（合肥）,43,2020/8/25,FORALL语句和FORALL结构,FORALL结构 在FORALL和ENDFORALL之间, 加入多条语句 ； 只能使用： 赋值语句、FORALL语句、FORALL结构、WHERE语句及WHILE结构 ； 使用注意： 只能含赋值语句，赋值语句左部必须是数组元素； 同一赋值语句不能对左部的同一数组元素多次赋值 ； 调用的函数必须是纯函数 ； 要使FORALL结构并行执

21、行，需要有分布数组 ； 例子； FORALL (i=1:n)a(i) = 1b(i) = 2END FORALL,国家高性能计算中心（合肥）,44,2020/8/25,INDEPENDENT指示,如果循环中不含迭代间的相关，该循环是可并行的 ； 迭代间相关: 读写迭代间相关 输出迭代间相关 可用于： DO循环； FORALL结构；,国家高性能计算中心（合肥）,45,2020/8/25,DO循环的INDEPENDENT指示,DO循环能加INDEPENDENT指示的条件是 ： 紧嵌套循环 ； 如果某一层加上INDEPENDENT，则内层的循环也必须是INDEPENDENT； 循环内的语句只能是赋值

22、语句和if语句； 循环内的函数只能是纯函数； 循环不含迭代间相关； 循环内被定值的非分布量，在循环外不能直接引用 ；,国家高性能计算中心（合肥）,46,2020/8/25,DO循环的INDEPENDENT指示,例子： step = ntotalDO l=1, lognimax = step / 2DO m=0, n / step-1k=m*stept1=temp(m)t2=temp(ntotal/2+m)!HPF$ INDEPENDENTDO i=k, k+imax-1g1=t1*fintr(i+imax)-t2*finti(i+imax)g2=t1*finti(i+imax)+t2*fint

23、r(i+imax)fintr(i+imax)=fintr(i)-g1finti(i+imax)=finti(i)-g2fintr(i)=fintr(i)+g1finti(i)=finti(i)+g2END DOEND DOEND DO,国家高性能计算中心（合肥）,47,2020/8/25,FORALL结构的INDEPENDENT指示,FORALL结构加INDEPENDENT指示的条件是： 不含迭代间相关； 循环内被定值的非分布量，在循环外不能直接引用 ；,国家高性能计算中心（合肥）,48,2020/8/25,6.5 HPF语言的过程,HPF语言的一般函数和子程序 ； HPF语言内部函数 ； H

24、PF语言的库函数 ；,国家高性能计算中心（合肥）,49,2020/8/25,HPF语言的一般函数和子程,分布数组函数 标量函数只能返回一个值，而数组函数可以返回一批数据； 对数组函数进行分布描述，数组函数便成了分布数组函数； 纯函数 遵守某些限制的函数 ； 不能修改全局变元和全局数据的值，也不能进行I/O ； 用户在纯函数中不能对分布数组赋值 ； 例子： PUREREAL FUNCTION vol(h,w,d)REAL h,w,d INTENT(IN) :：h,w,d vol = h*w*d END FUNCTION vol,国家高性能计算中心（合肥）,50,2020/8/25,HPF语言的一

25、般函数和子程,EXTRINSIC子程序 目的：为了改变程序的执行模式 ； 用户要关心并行执行的细节 ，可以使用EXTRINSIC子程序 ；,国家高性能计算中心（合肥）,51,2020/8/25,HPF语言内部函数,系统查询内部函数 计算内部函数,国家高性能计算中心（合肥）,52,2020/8/25,系统查询内部函数,NUMBER_OF_PROCESSORS(DIM)： 可选参数：DIM 描述： 返回程序所能利用的全部处理器数或者沿处理器数组的某一指定维程序所能利用的处理器的数目 ； 参数： DIM(可选的)必须是一个标量，且是一个整型数，其值的范围是1DIMn，其中n是处理器数组的维数 ； 结

26、果类型，类型参数，和形状： 缺省整数标量 结果值： 结果值等于依赖于实现的硬件处理器数组第DIM维的范围，或者如果DIM不存在，则等于依赖于实现的硬件处理器数组的全部元素数。结果总是大于0。,国家高性能计算中心（合肥）,53,2020/8/25,系统查询内部函数,PROCESSORS_SHAPE()： 描述： 返回依赖于实现的处理器数组的形状； 参数： 无； 结果类型，类型参数，和形状： 结果是一个缺省的一维整数数组，该数组的大小等于依赖于实现的处理器数组的维数； 结果值： 结果值是依赖于实现的处理器数组的形状；,国家高性能计算中心（合肥）,54,2020/8/25,计算内部函数,ILEN(I

27、) ： 描述： 对于一个用2的补码表示的整数，返回其位长减1； 参数： I必须是整型的； 结果类型和类型参数： 同I； 结果值： 如果I是非负的，则ILEN(I)的值是 ；如果I是负的，则ILEN(I)的值是 ；,国家高性能计算中心（合肥）,55,2020/8/25,HPF语言的库函数,映射查询函数 映射查询函数允许程序在运行时确定一个数组的实际映射 ； 描述了数组实际上是怎样被映射到机器上； 位维护函数 LEADZ计算一个整数描述中前导零的位数； POPCNT统计整数中1的位数； POPPAR计算一个整数的奇偶性 ；,国家高性能计算中心（合肥）,56,2020/8/25,HPF语言的库函数,

28、数组归约函数 操作方式与FORTRAN的SUM和ANY内部函数相同 ； 新的归约函数是 ：IALL、IANY、IPARITY和PARITY ； 例子： result=IAND_IDENTITY_ELEMENTDO i_1=LBOUND(array,1),UBOUND(array,1).DO i_n=LBOUND(array,n),UBOUND(array,n)IF(mask(i_1,i_2,.,i_n)&result=IAND(result,array(i_1,i_2,.,i_n)END DO.END DO,国家高性能计算中心（合肥）,57,2020/8/25,HPF语言的库函数,数组组合散播

29、函数 函数是一些一般化的数组归约函数； 一般形式 XXX_SCATTER(ARRAY,BASE,INDX1,.,INDXn,MASK) XXX所允许的值是ALL，ANY，COPY，COUNT，IALL，IANY，IPARITY，MAXVAL，MINVAL，PARITY，PRODUCT，以及SUM； INDX数组是整型的，并且INDX参数的个数必须等于BASE的维数 ； 参数MASK是逻辑型的，而且是可选的 ；,国家高性能计算中心（合肥）,58,2020/8/25,HPF语言的库函数,数组前缀和后缀函数 函数提供了对数组的和子数组扫描操作 ； 一般形式XXX_PREFIX(ARRAY,DIM,M

30、ASK,SEGMENT,EXCLUSIVE)；XXX_SUFFIX(ARRAY,DIM,MASK,SEGMENT,EXCLUSIVE)； XXX的允许值是ALL，ANY，COPY，COUNT，IALL，IPARITY，MAXVAL，MINVAL，PARITY，PRODUCT和SUM 参数MASK和SEGMENT必须是逻辑型的 ； SEGMENT必须与ARRAY具有相同的形状 ； MASK必须与ARRAY相符 ； EXCLUSIVE是一个逻辑型标量； DIM是一个介于1和ARRAY的维数之间的整数； 结果值与ARRAY具有相同的形状,国家高性能计算中心（合肥）,59,2020/8/25,HPF语

31、言的库函数,数组排序函数 SORT_UP和SORT_DOWN函数返回排序过的数组； GRADE_UP和GRADE_DOWN函数返回排序过的置换。,国家高性能计算中心（合肥）,60,2020/8/25,6.4 HPF实例分析2D FFT,串行2D FFT代码如下： REAL ，DIMENSION(n,n) ： a1，a2 DO WHILE(.true.) READ (unit = 1，end = 100) a1 CALL rowffts(a1) a2 = a1 CALL colffts(a2) WRITE (unit = 2) a2 CYCLE 100 CONTINUE EXIT END DO,

32、国家高性能计算中心（合肥）,61,2020/8/25,6.4 HPF实例分析2D FFT,流水线任务和数据并行的2D FFT 的HPF程序 ： REAL ，DIMENSION(n,n) ： a1,a2 LOGICAL done1 !HPF$ PROCESSORS procs(8) !HPF$ DISTRIBUTE a1(block,*) ONTO procs(1：4) !HPF$ DISTRIBUTE a2(*,block) ONTO procs(5：8) !HPF$ TEMPLATE，DIMENSION(4)，DISTRIBUTE(BLOCK) ONTO procs(1：4) ： td1 !

33、HPF$ ALIGN WITH td1(*) ： done1 !HPF$ TASK_REGION done1 = .false。 DO WHILE (.true.) !HPF$ON (procs(1：4) BEGIN，RESIDENT READ (unit = iu,end=100) a1 CALL rowffts(a1) GOTO 101 100 done1 = .true。 101 CONTINUE !HPF$ END ON IF (done1) EXIT a2 = a1 !HPF$ON (procs(5：8) BEGIN，RESIDENT CALL colffts(a2) WRITE(unit = ou) a2 !HPF$END ON END DO !HPF$ END TASK_EGION,国家高性能计算中心（合肥）,62,2020/8/25,6.4 HPF实例分析2D FFT,为每个处理器简化SPMD代码 ： REAL DIMENSION(n