| 1.2 HPF语言模型 |
|
HPF的一个重要目标是实现跨越不同并行机的代码可扩展性. 这就要求HPF程序不仅能在所有的目标机器上编译, 而且要求能在某一并行机上高效运行的HPF程序同时也能在其它具有可比数目处理器的并行机上实现适当的高效率. 否则, 当HPF代码移植到其它机器上时, 程序员为实现在某一机器上获得高性能而付出的努力将付之东流. 虽然共享存储的机器和分布存储的机器可能使用不同的低级原语, 但是这些机器上影响并行程序性能的基本因素具有广泛的相似性. 这就使得在不同的并行机上使用同样的高层次HPF程序来获得高效率成为可行的目标. 影响并行程序性能的一些基本因素包括可获得的并行度, 数据局部性的开发, 以及适当任务粒度的选择. HPF为程序员提供了一些机制使其能够按照这些因素来引导编译器.
HPF的第一个版本被定义成Fortran 90的扩展. HPF 2.0则被定义成当前Fortran标准(Fortran 95)的扩展. 随着Fortran标准中的高级特征被ISO所认可, HPF的未来修订版本将包括它们并与其保持一 致.
基于Fortran, HPF语言特征可被划分为四类:
. HPF指令
. 新的语言文法
. 新的库例程;以及
. 语言的变化和约束
HPF指令以结构化注释的形式出现, 它们或者暗示了实现策略或者向编译器表明了关于程序的一些事实. 当适当使用这些指令时, 它们仅影响计算的执行效率, 但不改变程序的计算结果. HPF指令的这种形式便于将来的Fortran标准将这些特征作为完整的语句包含在语言中, 那时仅需删除前面的注释头即可.
一些新的语言特征已被定义成Fortran文法和解释的直接扩展. 这些新的HPF语言特征不同于HPF指令, 因为它们是第一级的语言结构, 而且能够直接影响程序的计算结果.
HPF的计算函数库定义了一个同某些例程的标准接口, 这些例程在高性能计算中证明是很有用的. 这些附加的函数包括映射查询, 位维护, 数组归约(array reduction), 数组组合分散(array combining scatter), 前缀和后缀, 以及分类等.
同时对Fortran 95还定义了少量的变化和约束. 其中最重要的约束是那些强加的顺序和存储相联的使用, 因为它们同HPF的数据分配特征不兼容. 但是通过使用某种显式PF指令也有可能在程序中保留顺序和存储相联语义.
HPF中基本的并行模型是具有全局共享地址空间的单线索数据并行执行. Fortran的数组语句和FORALL语句是指定数据并行计算的自然方式. 另外, HPF提供了INDEPENDENT原语. 可使用它来声明某个循环未携带任何依赖, 因此可以并行执行.
数据局部性的开发是在高性能计算机上获得高性能的关键, 这些高性能计算机可以是单处理器工作站, 工作站网络或者并行计算机. 在一个非一致存储访问(NUMA)的并行计算机上, 处理器存储器间有效的数据分配对于减少数据移动开销是很重要的. HPF的一个关键特征是提供了一个允许用户指定数据映射的机制. HPF提供了并行机的一个逻辑视图, 这个视图指明了抽象处理器在一维或多维空间中的线形排列. 程序员可以指定不同程序数组元素的相对排列, 以及数组在逻辑处理器网格上的分配. 可使用HPF指令来指定数据映射, 这样可以帮助编译器优化并行性能, 但是它对于程序的语义没有影响. 如下例所示:
REAL A(1000, 1000)
!HPF$ PROCESSORS procs(4,4)
!HPF$ DISTRIBUTE(BLOCK, BLOCK) ONTO procs:: A
DO k = 1, num_iter
FORALL(i = 2:999, j=2:999)
A(i , j) = (A(i , j)+A(i-1 , j)+A(i , j+1)+A(i+1 , j))/4
END FORALL
END DO
此代码段描述了一个使用二维浮点数组A的简单Jacobi松弛迭代. HPF指令以结构化注释形式出现. PROCESSORS指令指定了一个逻辑上的4*4处理器网格procs. DISTRIBUTE指令推荐编译器将数组A沿它的每一维划分为等大小的块. 这将导致一个4*4的块结构, 每一块包括250*250个元素, 每个处理器一块. PROCESSORS和DISTRIBUTE指令将在第2节详细描述.
外层的DO k 循环共需迭代num_iter个Jacobi松弛步. 内层使用了Fortran 95的FORALL结构. 它指明了当i和j的值的变化范围从2到999时循环体的执行. FORALL的语义要求对于所有的迭代(例如, 对于所有2到999之间的i和j值), 其右手部表达式的估计都可在左部变量的赋值被执行之前完成.
当一个在分布存储机器上的执行被对准时, HPF编译器将产生SPMD代码, 并使每个处理器的局存包含全局数组A的一部分. 外层的k循环串行执行, 而内层FORALL并行执行. 每个处理器将需要一些数组A的"边界"元素, 这些元素是在划分时被映射到其它处理器的的局存中. 对于那些能够完成必要的处理器间通信的原语, 由HPF编译器将它们插入到所产生的SPMD代码中. 这种具有全局名字空间的单线索数据并行模型使得程序员能够在较高的抽象层次很方便地指定并行策略和数据划分. 从抽象的全局名字空间到单个处理器局存空间的那些乏味的低级翻译细节以及处理器间通信的显式管理都被留给编译器去做.
下面的例子阐述了标量赋值语句的一些通信含义. 目的是为了阐述并行执行中关于通信要求方面的数据分配说明的含义. 给出的解释不必要反映实际的编译处理.
考虑下面的代码段:
REAL a(1000), b(1000), c(1000), x(500), y(0:501)
INTEGER inx(100)
!HPF$ PROCESSORS procs(10)
!HPF$ DISTRIBUTE(BLOCK) ONTO procs :: a, b, inx
!HPF$ DISTRIBUTE(CYLIC) ONTO procs :: c
!HPF$ ALIGN x(i) WITH y(i+1)
...
a(i) = b(i) !赋值1
x(i) = y(i+1) !赋值2
a(i) = c(i) !赋值3
a(i) = a(i-1) + a(i) + a(i+1) !赋值4
c(i) = c(i-1) + c(i) + c(i+1) !赋值5
x(i) = y(i) !赋值6
a(i) = a(inx(i))+b(inx(i)) !赋值7
在本例中, PROCESSORS指令指定了10个处理器的一个线性排列. DISTRIBUTE指令向编译器推荐数组a, b, inx应以块方式(block)分配在10个处理器上, 并使每个处理器的每个块中包含100个连续元素. 数组c则是以循环方式(cyclic)分配在处理器上, 即c(1), c(11), ..., c(991)映射到处理器procs(1)上; c(2), c(12), ..., c(992)映射到处理器procs(2)上; 等等. 程序中没有指定数组x和y向处理器上的完整映射, 但是通过ALIGN指令指明了它们的相对排列. ALIGN推荐对于所有的i值x(i)和y(i+1)应被存储到同一处理器上, 而不管编译器对y的实际分配是怎样(y(0)和y(1)未和x的任何元素对准). PROCESSORS, DISTRIBUTE, 以及ALIGN指令将在第二节详细讨论.
在赋值1中(a(i) = b(i)), a和b的同一分配指明了对于所有的i, a(i)和b(i)的相应元素应被映射同一处理器上. 因此, 执行这条语句不需要处理器间数据值的通信.
在赋值2中(x(i) = y(i+1)), 也没有固有的通信. 在这种情况下, 对于数组的所有实际分配, 两个数组的相对排列都和此赋值语句相匹配.
虽然赋值3(a(i) = c(i))看起来与第一个赋值非常相似, 但是由于a和c的不同分配,
使得它们的通信要求也是非常不同的.对于所有的i值, 仅有10%的可能使得数组元素a(i)和c(i)被映射到同一处理器上.
(这一点可从第二节中对BLOCK和CYLIC的定义中看出). 当且仅当
{［（i-1)/100]=(i-1)mod
100}时, 这些元素才能位于同一处理器上. 例如, 如果i = 1或者i =102, 则此赋值不涉及到通信,但是,
如果i = 2, 则一定需要通信.
在赋值4中(a(i)=a(i-1)+a(i)+a(i+1)), 对于大约98%的i的可能取值, 数组a的引用在同一处理器上. 例外的情形是i = 100*k(k = 1,2,...,9), 这时, a(i)和a(i-1)在处理器procs(k)上, 而a(i+1)在procs(k+1)上; 同时, i = 100*k + 1(k=1,2,...,9)时, a(i)和a(i+1)在procs(k+1)上, 而a(i-1)在procs(k)上. 此语句仅对每个处理器上的"边界"元素要求通信.
赋值5(c(i) = c(i-1) + c(i) + c(i+1))虽然表面上与赋值4相似, 但却具有非常不同的的通信行为. 因为c的分配是CYCLIC而不是BLOCK, 这就使得对于任一个i值, c(i), c(i-1)和c(i+1)这三个引用将被映射到三个不同的处理器上. 因此, 不管是何种实现策略, 在此语句中都至少有两个右手部的引用需要通信.
从最后的两个赋值, 所能得到的关于通信要求的信息非常有限. 在赋值6中(x(i) = y(i)), 可获得的唯一信息是x(i)和y(i+1)在同一处理器上; 而x(i)和y(i)之间没有逻辑上的因果关系. 这样, 在运行时, 如果没有进一步的信息, 就无法知道本语句的通信要求是怎样的. 在赋值7中(a(i)=a(inx(i))+b(inx(i))), 可以证明a(inx(i))和b(inx(i))总是映射到同一处理器上. 类似地, 很容易推导出a(i)和inx(i)是映射到一起的. 可是由于没有存储到inx中的值的信息, 因此无法知道a(i)和a(inx(i))以及a(i)和b(inx(i))之间的关系.
| Copyright: NPACT |
|