第十四章 分布存储系统并行编程 国家高性能计算中心（合肥）.

Presentation on theme: "第十四章 分布存储系统并行编程 国家高性能计算中心（合肥）."— Presentation transcript:

1 第十四章 分布存储系统并行编程 国家高性能计算中心（合肥）

2 分布存储系统并行编程 14.1 基于消息传递的编程 14.2 MPI并行编程 14.3 PVM并行编程 14.4 基于数据并行的并行编程
14.5 HPF并行编程 国家高性能计算中心（合肥）

3 基于消息传递的并行编程 1 消息传递库 2 消息传递方式 国家高性能计算中心（合肥）

4 1 消息传递库(Message-Passing Libraries)
建议: 一个终端用户在开发新的消息传递应用时使用MPI或PVM. 原因是: MPI和PVM都是公用软件, 易于得到 多数厂家支持 国家高性能计算中心（合肥）

5 1 消息传递库(Message-Passing Libraries)
CMMD: 是一个用于Thinking Machines CM-5系统的消息传递库, 其特点是基于主动消息(Active Message)机制在用户空间实现通信以减少通信延迟; Express: 是一个支持点到点和群集通信以及并行I/O的程序设计环境; Nx: 是为Intel MPP(例如, Hypercubes和 Paragon)开发的微核系统. 现在已由用于Intel/Sandia ASCI TFLOPS 系统中的新的微核系统PUMA代替. Fortran-M: 是对Fortran77的扩展, 它在设计上既支持共享存储也支持消息传递, 但当前只实现了对消息传递的支持. 该语言提供了许多机制用于支持开发行为确定、模块化的并行程序. P4(Parallel Programs for Parallel Processors) : 是一组宏和子程序, 用于支持共享存储和消息传递系统中的程序设计, 它可以移植到许多体系结构上. 其它的消息传递软件系统还有Vertex, PARMACS, Zipcode, UNIFY和PICL等. 国家高性能计算中心（合肥）

6 1 消息传递库(Message-Passing Libraries)
在当前所有的消息传递软件中, 最重要最流行的是MPI和PVM, 它们能运行在所有的并行平台上, 包括SMP和PVP. 二者已经在Windows NT 和Windows 95这样的非Unix平台上实现. 程序设计语言支持C, Fortran和Java. 在国产的三大并行机系列神威、银河和曙光上都实现了对MPI和PVM和支持. 国家高性能计算中心（合肥）

7 1 消息传递库(Message-Passing Libraries)
1.1 MPI(Message Passing Interface) 简介 目标: 是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准. MPI以语言独立的形式来定义这个接口库, 并提供了与C、Fortran和Java语言的绑定. 这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性. 由于这个原因, MPI在并行计算界被广泛地接受. 国家高性能计算中心（合肥）

8 1 消息传递库(Message-Passing Libraries)
MPI的实现 建立在厂家专用的环境之上 IBM SP2的POE/MPL, Intel Paragon的OSF/Nx 公共的MPI环境: CHIMP Edinburg 大学 LAN(Local Area Multicomputer) Ohio超级计算中心 MPICH Argonne国家实验室与Mississippi州立大学 MPICH是MPI在各种机器上的可移植实现,可以安装在几乎所有的平台上: PC 工作站 SMP MPP COW 国家高性能计算中心（合肥）

9 1 消息传递库(Message-Passing Libraries)
1.2 PVM(Parallel Virtual Machine) 简介 开发时间: 始于1989年 开发单位: 美国Tennessee大学、Oak Ridge国家实验室和Emory大学联合研制 特点: 具有较好的适应性、可扩展性、可移植性和易使用性等特点, 源代码可以免费获取, 现已被用户广泛采纳. 现状: 目前对它的研究和开发工作仍在各大学和研究机构进行. 尽管已经有越来越多的人开始使用MPI, 但PVM仍然是做并行处理最流行的软件之一. 随着它的不断流行, 已经被移植到PVP, SMP, MPP, 工作站和PC组成的机群系统. 国家高性能计算中心（合肥）

10 1 消息传递库(Message-Passing Libraries)
PVM和MPI间的主要差别: (1)PVM是一个自包含的系统, 而MPI不是. MPI依赖于支持它的平台提供对进程的管理和I/O功能. 而PVM本身就包含这些功能. (2) MPI对消息传递提供了更强大的支持. (3) PVM不是一个标准, 这就意味着PVM可以更方便、更频繁地进行版本更新. MPI和PVM在功能上现在正趋于相互包含. 例如, MPI-2增加了进程管理功能, 而现在的PVM也提供了更多的群集通信函数. 与MPI不同的是, 国家高性能计算中心（合肥）

11 2 消息传递方式 关于通信模式, 用户需要理解的有三个方面: 共有多少个进程? 进程间如何同步? 如何管理通信缓冲区?
2 消息传递方式 1.2 Message-Passing Modes 关于通信模式, 用户需要理解的有三个方面: 共有多少个进程? 进程间如何同步? 如何管理通信缓冲区? 现在的消息传递系统多使用三种通信模式: 同步的消息传递 (Synchronous Message Passing) 阻塞的消息传递 (Blocking Message Passing) 非阻塞的消息传递 (Nonblocking Message Passing) 国家高性能计算中心（合肥）

12 2 消息传递方式 进程 Q 接收返回点 开始接收点 R_syn1 S_Block2 S_Non_Block3 进程 P 开始发送点
2 消息传递方式 进程 Q 接收返回点 开始接收点 R_syn1 S_Block2 S_Non_Block3 进程 P 开始发送点 发送返回点 S_syn1 R_block2 R_Non_Block3 系统进程 等待发送点 发送例程 接收例程 国家高性能计算中心（合肥）

13 2 消息传递方式 Process P: M=10; Process Q:
2 消息传递方式 例2.1 消息传递中的发送和接收缓冲 Process P: M=10; L1: send M to Q; L2: M=20; goto L1; Process Q: L1: S= -100; L2: receive S from P; X=S+1; M 称为发送消息缓冲 (send message buffer, or send buffer) S 称为接收消息缓冲 (receive message buffer, or receive buffer) 国家高性能计算中心（合肥）

14 三种通信模式的比较 2 消息传递方式 国家高性能计算中心（合肥）

15 2 消息传递方式 Process P: Process Q: 例2.2 非阻塞模式下, 强制进程等待直到安全时再继续执行 M=10;
2 消息传递方式 例2.2 非阻塞模式下, 强制进程等待直到安全时再继续执行 Process P: M=10; send M to Q; do some computation which does not change M; wait for M to be sent; M=20; Process Q: S=-100; receive S from P; do some computation which does not use S; wait for S to be received; X=S+1; 非阻塞模式本身也会带来一些额外开销: 作为临时缓冲区用的内存空间 分配缓冲区的操作 将消息拷入和拷出临时缓冲区 执行一个额外的检测和等待函数 国家高性能计算中心（合肥）

16 2 消息传递方式 消息传递的特点: 在消息传递模型中, 一个并行应用由一组进程组成, 每个进程的代码是本地的, 只能访问私有数据, 进程之间通过传递消息实现数据共享和进程同步. 优点: 用户可以对并行性的开发、数据分布和通信实现完全控制. 缺点: 要求程序员显式地处理通信问题, 如, 消息传递调用的位置, 数据移动, 数据复制, 数据操作, 数据的一致性等等. 对大多数科学计算程序来说, 消息传递模型的真正困难还在于显式的域分解, 也就是说, 将对相应数据的操作限定在指定的处理器上进行, 在每个处理器上只能看见整个分布数据的一部分. 无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出来. 大量的散布在程序各处的域分解要求整个程序由串行到并行的转换一次性实现, 而共享存储方法允许在现有的串行代码中插入并行说明从而实现逐步转换.与之相比, 这是消息传递的一个明显的缺点. 国家高性能计算中心（合肥）

17 分布存储系统并行编程 14.1 基于消息传递的编程 14.2 MPI并行编程 14.3 PVM并行编程 14.4 基于数据并行的并行编程
14.5 HPF并行编程 国家高性能计算中心（合肥）

18 MPI并行编程 1 MPI中的消息 2 MPI中的消息信封 3 MPI中的四种通信模式 4 点对点的通信 5 群集通信 6 MPI扩展
国家高性能计算中心（合肥）

19 第五讲 1 MPI中的消息 例1.1 一个计算∑foo(i)的MPI SPMD消息传递程序, 存放在文件 “myprog.c”中
#include "mpi.h" int foo(i) int i; {...} main(argc, argv) int argc; char* argv[] { int i, tmp, sum=0, group_size, my_rank, N; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &group_size); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); if (my_rank==0) { printf("Enter N:"); scanf("%d",&N); for (i=1;i<group_size;i++) MPI_Send(&N, 1, MPI_INT, i, i, MPI_COMM_WORLD); for (i=my_rank;i<N;i=i+group_size) sum=sum+tmp; for (i=1;i<group_size;i++) { MPI_Recv(&tmp,1,MPI_INT,i,i,MPI_COMM_WORLD,&status); sum=sum+tmp; } printf("\n The result = %d", sum); else { MPI_Recv(&N,1,MPI_INT,i,i,MPI_COMM_WORLD,&status); for (i-my_rank;i<N;i=i+group_size) sum=sum+foo(i); MPI_Send(&sum,1,MPI_INT,0,i,MPI_COMM_WORLD); MPI_Finalize(); 例1.1 一个计算∑foo(i)的MPI SPMD消息传递程序, 存放在文件 “myprog.c”中 1 MPI中的消息 初始化MPI环境 得到缺省的进程组大小 得到每个进程在组中的编号 发送消息 接收消息 终止MPI环境 国家高性能计算中心（合肥）

20 1 MPI中的消息 这个程序用以下并行C编译器mpcc来编译: mpcc myprog.c –o myprog
执行下列命令将可执行程序myprog加载到n个节点上: MPIRUN myprog –np n MPI进程是重型的单线进程. 它们拥有不同的地址空间. 因此, 一个进程不能直接访问另一个进程地址空间的中的变量. 进程间的通信用消息传递来实现. 国家高性能计算中心（合肥）

21 1 MPI中的消息 为什么MPI中的发送和接收操作要做得这么复杂呢? MPI消息的组成:
send M to Q; receive S from P MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD) MPI_Recv(&N,1,MPI_INT,0,i,MPI_COMM_WORLD,&status) MPI消息的组成: 消息的内容 (即, 信的内容), 称为消息缓冲(message buffer) 消息的接收者 (即, 写在信封上面的东西), 称为消息信封(message envelop) 国家高性能计算中心（合肥）

22 1 MPI中的消息 例1 用MPI发送一个数据数组 考虑一个用C语言声明的由N个复数组成的数组 double A[100]
假定进程P要把这个数组发送给进程Q: 国家高性能计算中心（合肥）

23 1 MPI中的消息 国家高性能计算中心（合肥）

24 1 MPI中的消息 子程序名 消息长度 接收进程标识号 通信子 MPI_Send (&N, 1, MPI_INT, i, i, MPI_COMM_WORLD) 消息地址 消息数据类型 消息标签 MPI_Send (buffer, count, datatype, destination, tag, communicator) (buffer, count, datatype) 消息缓冲 (destination, tag, communicator) 消息信封 国家高性能计算中心（合肥）

25 1 MPI中的消息 MPI的 四个重要概念: 消息数据类型 (message data types) 通信子 (communicators)
通信操作 (communication operations) 虚拟拓扑 (virtual topology) 国家高性能计算中心（合肥）

26 1 MPI中的消息 为什么需要定义消息数据类型? 理由有两个: 一是支持异构计算 另一是允许非连续, 非均匀内存区中的消息.
异构计算(heterogeneous computing ): 指的是在由不同计算机, 如工作站网络, 组成的系统上运行应用程序. 系统中的每台计算机可能由不同的厂商生产、使用不同的处理器和操作系统 当这些计算机使用不同的数据表示时如何保证互操作性. 国家高性能计算中心（合肥）

27 1 MPI中的消息 国家高性能计算中心（合肥）

28 例2 发送非连续数据项 double A[100]; MPI_Pack_size (50,MPI_DOUBLE,comm,&BufferSize); TempBuffer = malloc(BufferSize); j = sizeof(MPI_DOUBLE); Position = 0; for (i=0;i<50;i++) MPI_Pack(A+i*j,1,MPI_DOUBLE,TempBuffer,BufferSize,&Position,comm); MPI_Send(TempBuffer,Position,MPI_PACKED,destination,tag,comm); 国家高性能计算中心（合肥）

29 例 3 在消息传递中发送一个混合数据类型 在下面的消息中, 假定每个双精度数有8字节长, 一个字符是1字节, 一个整型数是4字节.
国家高性能计算中心（合肥）

30 例4 发送一数组的所有偶序数元素 double A[100]; MPI_Data_type EvenElements; ... ...
例4 发送一数组的所有偶序数元素 double A[100]; MPI_Data_type EvenElements; MPI_Type_vector(50,1,2,MPI_DOUBLE,&EvenElements); MPI_Type_commit(&EvenElements); MPI_Send(A,1,EvenElements,destination, ...); 国家高性能计算中心（合肥）

31 1 MPI中的消息 说明: MPI_Type_vector(count, blocklength, stride, oldtype, &newtype) 是构造导出数据类型的MPI例程. 导出类型newtype由blocks的拷贝count份组成. 每块(blocks)由已有的数据类型oldtype的blocklength份连续项的拷贝组成. stride定义每两个连续的块之间的oldtype元素个数. 因此, (stride-blocklength)即是两个块之间的间隔. 国家高性能计算中心（合肥）

32 1 MPI中的消息 消息缓冲 消息缓冲(message buffer, 简称buffer), 在不同的消息传递使用场合有不同的含义. 下面给出一些例子: 消息缓冲指的是由程序员定义的应用程序的存储区域, 用于存放消息的数据值. 例如, 在Send(A, 16, Q, tag)中, 缓冲A是在用户应用程序中声明的变量. 该缓冲的起始地址在消息例程中被使用. 消息缓冲也可以指由消息传递系统(而非用户)创建和管理的一些内存区, 它用于发送消息时暂存消息. 这种缓冲不在用户的应用程序中出现, 有时被称为系统消息缓冲(或系统缓冲). MPI允许第三种可能的定义. 用户可以划出一定大小的内存区, 作为出现在其应用中的任意消息的中间缓冲. 国家高性能计算中心（合肥）

33 1 MPI中的消息 例5 在一对进程间发送消息 考虑下列代码, 由进程P传送一个存放在数组A中的消息M, 到 进程Q的数组B中.
例5 在一对进程间发送消息 考虑下列代码, 由进程P传送一个存放在数组A中的消息M, 到 进程Q的数组B中. 国家高性能计算中心（合肥）

34 Process P: double A[2000000]; send(A,32,Q,tag); Process Q:
double B[32]; recv(B,32,P,tag) Process P Process Q B A M Process P Process Q B A M (a) 只使用用户缓冲 T Process P S Process Q B A M (c) 使用了用户级的临时缓冲T (b) 使用系统缓冲S 国家高性能计算中心（合肥）

35 2 MPI中的消息信封 用户如何来定义消息的接收者呢? 在下面列出的MPI发送例程中, 消息信封由三项组成. destination 域是一个整数, 标识消息的接收进程. MPI_Send (address, count, datatype, destination, tag, communicator) 消息标签(message tag), 也称为消息类型(message type), 是程序员用于标识不同类型消息、限制消息接收者的一个整数. 国家高性能计算中心（合肥）

36 2 MPI中的消息信封 为什么要使用消息标签(Tag)? 未使用标签 为了说明为什么要用标签, 我们先来看右面一段没有使用标签的代码:
这段代码打算传送A的前32个字节进入X, 传送B的前16个字节进入Y. 但是, 如果消息B尽管后发送但先到达进程Q,就会被第一个recv()接收在X中. 使用标签可以避免这个错误. 使用了标签 国家高性能计算中心（合肥）

37 例6 在消息传递中使用标签 未使用标签 使用标签的另一个原因是可以简化对下列情形的处理.
假定有两个客户进程P和R, 每个发送一个服务请求消息给服务进程Q. 使用了标签 国家高性能计算中心（合肥）

38 一个进程组(process group)+上下文(context).
2 MPI中的消息信封 什么是通信子? MPI_Send (address, count, datatype, destination, tag, communicator) 通信子(communicator): 一个进程组(process group)+上下文(context). 进程组: 是进程的有限有序集. 有限意味着, 在一个进程组中, 进程的个数n是有限的, 这里的n称为进程组的大小(group size). 有序意味着n 个进程是按整数0, 1, ..., n-1进行编号的. 一个进程在一个通信子(组)中用它的编号进行标识. 组的大小和进程编号可以通过调用以下的MPI例程获得: MPI_Comm_size(communicator, &group_size) MPI_Comm_rank(communicator, &my_rank) 国家高性能计算中心（合肥）

39 2 MPI中的消息信封 例7 通信子的使用 Process 0:
例7 通信子的使用 Process 0: MPI_Send(msg1, count1, MPI_INT, 1, tag1, comm1); parallel_fft(...); Process 1: MPI_Recv(msg1, count1, MPI_INT, 0, tag1, comm1); 含代码 含代码 if (my_rank==0) MPI_Send(msg2, count1, MPI_INT,1,tag2,comm2); 国家高性能计算中心（合肥）

40 2 MPI中的消息信封 存在问题: 不可能保证tag1 和tag2一定取了不同的值: 标签是由用户定义的整数值, 用户可能会出错.
即使用户不会弄错, 也难以或不可能保证tag1 和tag2有不同的值. 函数parallel_fft( )可能是由其它用户写的, 或者它是一个库例程. 这样, 用户可能不知道tag2的值. 即使用户总能知道tag2的值, 仍然可能出错. 因为MPI_Recv 例程可能决定使用一个通配的(wildcard)标签MPI_Any_tag. 解决办法: 在parallel_fft( )中的通信使用不同的通信子, 它可能包含相同的进程组(如, 进程0和1), 但每个通信子有系统指定的不同的上下文, 与comm1的不同. 因此, MPI_Recv 不再有偶然会从parallel_fft( )的MPI_Send中接收msg2的危险了. 国家高性能计算中心（合肥）

41 2 MPI中的消息信封 例8 MPI中的新通信子 考虑如下由10个进程执行的代码:
MPI_Comm MyWorld, SplitWorld; int my_rank,group_size, Color, Key; MPI_Init(&argc, &argv); MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld); MPI_Comm_rank(MyWorld,&my_rank); MPI_Comm_size(MyWorld,&group_size); Color=my_rank%3; Key=my_rank/3; MPI_Comm_split(MyWorld,Color,Key,&SplitWorld); 国家高性能计算中心（合肥）

42 MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld)
将创建一个新的通信子MyWorld, 它是包含与原始的MPI_COMM_WORLD相同的10个进程的进程组,但有不同的上下文. 国家高性能计算中心（合肥）

43 2 MPI中的消息信封 MPI-1被设计成使不同通信子中的通信是相互分开的, 以及任何群集通信是与任何点对点通信分开的, 即使它们是在相同的通信子内. 通信子概念尤其方便了并行库的开发. MPI-1只支持组内通信 (intra-communication) MPI-2支持组间通信 (inter-communication) 国家高性能计算中心（合肥）

44 第一个参数指明消息缓存的起始地址, 即存放要发送的数据信息. 第二个参数指明消息中给定的数据类型有多少项, 这个数据类型由第三个参数给定.
MPI消息特性的总结 发送者进程总结如下 MPI_Send(buffer, count, datatype, destination, tag, communicator) 例子: MPI_Send(&N, 1, MPI_INT, i, i , MPI_COMM_WORLD); 第一个参数指明消息缓存的起始地址, 即存放要发送的数据信息. 第二个参数指明消息中给定的数据类型有多少项, 这个数据类型由第三个参数给定. 数据类型要么是基本数据类型, 要么是导出数据类型, 后者由用户生成指定一个可能是由混合数据类型组成的非连续数据项. 第四个参数是目的进程的标识符(进程编号) 第五个是消息标签 第六个参数标识进程组和上下文, 即, 通信子. 通常, 消息只在同组的进程间传送. 但是, MPI允许通过intercommunicators在组间通信. 国家高性能计算中心（合肥）

45 发送者进程总结如下 MPI_Recv(address, count, datatype,source, tag, communicator, status) 例: MPI_Recv(&tmp, 1, MPI_INT, i, i, MPI_COMM_WORLD,&Status)   第一个参数指明接收消息缓冲的起始地址, 即存放接收消息的内存地址 第二个参数指明给定数据类型的最大项数, 它存放在第三个参数内, 可以被接收. 接收到的实际项数可能少一些 第四个参数是源进程标识符 (编号) 第五个是消息标签 第六个参数标识一个通信子 第七个参数是一个指针, 指向一个结构 MPI_Status Status 存放了各种有关接收消息的各种信息. Status.MPI_SOURCE 实际的源进程编号 Status.MPI_TAG 实际的消息标签 实际接收到的数据项数由MPI例程 MPI_Get_count(&Status, MPI_INT, &C) 读出. 这个例程使用Status中的信息来决定给定数据类型(在这里是MPI_INT)中的实际项数, 将这个数放在变量C中. 这两个域可以是wildcard MPI_Any_source和MPI_Any_tag. } 国家高性能计算中心（合肥）

46 2 MPI中的消息信封 例9 消息传递中的状态(Status)字 while (true){
当一个接收者能从不同进程接收不同大小和标签的信息时, 状态信息就很有用. while (true){ MPI_Recv(received_request,100,MPI_BYTE,MPI_Any_source, MPI_Any_tag,comm,&Status); switch (Status.MPI_Tag) { case tag_0: perform service type0; case tag_1: perform service type1; case tag_2: perform service type2; } 国家高性能计算中心（合肥）

47 3 MPI中的四种通信模式 用在MPI中的通信模式(communication mode) 同步的(synchronous)
直到相应的接收已经启动发送才返回, 因此接收端要有存放到达消息的应用缓冲. 注意: 在MPI中可以有非阻塞的同步发送, 它的返回不意味着消息已经被发出! 它的实现不需要在接收端有附加的缓冲, 但需要在发送端有一个系统缓冲. 为了消除额外的消息拷贝, 应使用阻塞的同步发送. S R Synchronous 1 2 3 国家高性能计算中心（合肥）

48 3 MPI中的四种通信模式 缓冲的(buffered)
缓冲的发送假定能得到一定大小的缓冲空间, 它必须事先由用户程序通过调用子例程MPI_Buffer_attch(buffer,size)来定义, 由它来分配大小为size的用户缓冲. 这个缓冲可以用MPI_Buffer_detach(*buffer, *size )来实现. S R Buffer 1 2 国家高性能计算中心（合肥）

49 3 MPI中的四种通信模式 标准的(standard) 发送可以是同步的或缓冲的, 取决于实现. Standard S R 1
就绪的(ready) 在肯定相应的接收已经开始才进行发送. 它不像在同步模式中那样需要等待. 这就允许在相同的情况下实际使用一个更有效的通信协议. S R Ready 1 2 国家高性能计算中心（合肥）

50 4 点对点的通信 国家高性能计算中心（合肥）

51 4 点对点的通信 例10 使用消息传递的进程流水线 图中是一条三进程的流水线, 一个进程连续地从左边接收一个输入数据流, 计算一个新的值, 将它发送给右边.下面的代码示出了基本思想. X=P(W) W Y=Q(X) X Z=R(Y) Y Z 进程流水线中的数据流 进程Q的一段代码 while (Not_Done){ MPI_Irevc(NextX, ...); MPI_Isend(PreviousY, ...); CurrentY=Q(CurrentX); } 国家高性能计算中心（合肥）

52 4 点对点的通信 Xbuf 0 Y=Q(X) YBuf0 Send Y Xbuf 1 Ybuf1 进程流水线中的双缓冲 进程Q的代码
4 点对点的通信 Xbuf 0 Receive X Y=Q(X) YBuf0 Send Y Xbuf 1 Ybuf1 进程流水线中的双缓冲 进程Q的代码 while (Not_Done){ if (X==Xbuf0) {X=Xbuf1; Y=Ybuf1; Xin=Xbuf0; Yout=Ybuf0;} else {X=Xbuf0; Y=Ybuf0; Xin=Xbuf1; Yout=Ybuf1;} MPI_Irevc(Xin, ..., recv_handle); MPI_Isend(Yout, ..., send_handle); Y=Q(X); /* 重迭计算*/ MPI_Wait(recv_handle,recv_status); MPI_Wait(send_handle,send_status); } 国家高性能计算中心（合肥）

53 4 点对点的通信 例11 发送和接收中的死锁 Process P: ... ... X=0;
4 点对点的通信 例11 发送和接收中的死锁 Process P: X=0; MPI_Issend(&X, ..., Q, ...); Process Q if (Y==5)MPI_Irecv(&Y, ..., P, ...); printf(“Y is %d”, Y); 这是一段错误代码, 可能会有下列结果: 死锁. 例程MPI_Issend是非阻塞的、同步的发送. 它直到相应的MPI_Irecv 已经启动执行才返回, 如果条件Y==5不为真, 则MPI_Irecv就不会被执行. Y为0. 假定当if语句被执行后Y==5为真. 则MPI_Irecv会从进程P接收X的值(为0)到它的变量Y, 并打印它. Y为5. 另一个可能的情况是当Y==5为真时, 打印会在接收到X的值并存入Y之前执行(因为MPI_Irecv是非阻塞的接收). 因此打印出的是Y的旧值. 国家高性能计算中心（合肥）

54 5 群集通信 广播(Broadcast) MPI_Bcast(Address, Count, Datatype, Root, Comm)
在下列broadcast操作中, 标号为Root的进程发送相同的消息给标记为Comm的通信子中的所有进程. 消息的内容如同点对点通信一样由三元组(Address, Count, Datatype)标识. 对Root进程来说, 这个三元组既定义了发送缓冲也定义了接收缓冲. 对其它进程来说, 这个三元组只定义了接收缓冲. 国家高性能计算中心（合肥）

55 5 群集通信 播撒(Scatter) MPI_Scatter (SendAddress,SendCount,SendDatatype,
RecvAddress,RecvCount,RecvDatatype,Root,Comm) 聚集(Gather) MPI_Gather (SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Root,Comm) 国家高性能计算中心（合肥）

56 5 群集通信 MPI_Scatter Scatter只执行与Gather相反的操作. Root进程发送给所有n个进程发送一个不同的消息, 包括它自已. 这n个消息在Root进程的发送缓冲区中按标号的顺序有序地存放. 每个接收缓冲由三元组(RecvAddress, RecvCount, RecvDatatype)标识. 所有的非Root进程忽略发送缓冲. 对Root进程, 发送缓冲由三元组(SendAddress, SendCount, SendDatatype)标识. MPI_ Gather Root进程从n个进程的每一个接收各个进程(包括它自已)的消息. 这n个消息的连接按序号rank进行, 存放在Root进程的接收缓冲中. 每个发送缓冲由三元组(SendAddress, SendCount, SendDatatype) 标识. 所有非Root进程忽略接收缓冲. 对Root进程, 发送缓冲由三元组(RecvAddress, RecvCount, RecvDatatype)标识. 国家高性能计算中心（合肥）

57 5 群集通信 扩展的聚集和播撒操作Allgather
MPI_Allgather ( SendAddress, SendCount, SendDatatype, RecvAddress, RecvCount, RecvDatatype, Comm ) 国家高性能计算中心（合肥）

58 5 群集通信 全局交换(Tatal Exchange)
MPI_Alltoall(SendAddress, SendCount, SendDatatype, RecvAddress, RecvCount, RecvDatatype, Comm) 每个进程发送一个消息给所有n个进程, 包括它自已. 这n个消息在它的发送缓冲中以标号的顺序有序地存放. 从另一个角度来看这个通信, 每个进程都从n个进程接收一个消息. 这n个消息以标号的顺序被连接起来, 存放在接收缓冲中. 注意, 全局交换等于由n 个不同进程做的n次Gather操作. 因此, 不再需要Root参数. 所有对所有, 在一次全局交换中共有n2个消息进行通信. 国家高性能计算中心（合肥）

59 5 群集通信 聚合(Aggregation) MPI提供了两种类型的聚合操作: 归约(reduction)和扫描(scan).
MPI_Reduce(SendAddress, RecvAddress, Count, Datatype, Op, Root, Comm) 这里每个进程的部分值存放在SendAddress中. 所有进程将这些值归约为最终结果并将它存入Root进程的RecvAddress. 数据项的数据类型在Datatype域中定义. 归约操作由Op域定义. 国家高性能计算中心（合肥）

60 5 群集通信 扫描(scan) MPI_scan(SendAddress, RecvAddress, Count, Datatype,
Op, Comm) scan操作省去了Root域, 因为scan是将部分值组合成n个最终值, 并存放在n个进程的RecvAddress. scan操作由Op域定义. MPI的reduction和scan操作允许每个进程贡献向量值, 而不只是标量值. 向量的长度由Count定义. MPI支持用户自定义的reduction和scan操作 国家高性能计算中心（合肥）

61 5 群集通信 路障(Barrier) MPI_Barrier(Comm)
在路障操作中, 通信子Comm中的所有进程相互同步, 即, 它们相互等待, 直到所有进程都执行了他们各自的MPI_Barrier函数. 国家高性能计算中心（合肥）

62 5 群集通信 国家高性能计算中心（合肥）

63 5 群集通信 群集例程的共同特点 一个进程一旦结束了它所参与的群集操作就从群集例程中返回.
通信子中的所有进程必须调用群集通信例程. 如果代码中只有通信子中的一部分成员调用了一个群集例程而其它没有调用, 则是错误的. 一个错误代码的行为是不确定的, 意味着它可能发生任何事情, 包括死锁或产生错误的结果. 一个进程一旦结束了它所参与的群集操作就从群集例程中返回. 除了MPI_Barrier以外, 每个群集例程使用类似于点对点通信中的标准(standard)、阻塞的通信模式. 例如, 当Root进程从MPI_Bcast中返回时, 它就意味着发送缓冲的Address可以被安全地再次使用. 其它进程可能还没有启动它们相应的MPI_Bcast! 一个群集例程也许是也许不是同步的, 取决于实现. MPI要求用户负责保证他的代码无论实现是否是同步的都是正确的. Count 和Datatype在所包含的所有进程中必须是一致的. 在群集例程中没有tag参数. 消息信封由通信子参数和源/目的进程定义. 例如, 在MPI_Bcast中, 消息的源是Root, 目的是所有进程(包括Root). 在MPI-1 中, 只支持阻塞和通信子内(intra-communicator)群集通信. 国家高性能计算中心（合肥）

64 6 MPI扩展 MPI-2对MPI-1的扩展 动态进程 单边通信 非阻塞群集通信模式和通信子间群集通信模式.
对可扩展的I/O的支持, 叫做MPI-IO. 在MPI-1中, I/O问题全部忽略. MPI-1只定义对Fortran77和C语言的绑定. MPI-2将语言绑定扩展到Fortran90和C++. 对实时处理的支持. 扩展了MPI-1的外部接口, 以便使环境工具的开发者更易于访问MPI对象. 这将有助于开发剖析(profiling)、 监视(monitoring)和调试(debugging)工具. 国家高性能计算中心（合肥）

65 6 MPI扩展 动态进程 MPI-2决定支持动态进程, 这带来了以下好处:
MPI-1不定义如何创建进程和如何建立通信. 因此, MPI-1需要支撑平台提供这种能力, 像SP2中的POE和工作站网络中的rsh. MPI-2中的动态进程机制以可移植的方式(平台独立)提供了这种能力 动态进程有利于将PVM程序移植到MPI上. 并且还可能支持一些重要的应用类型, 如, Client/Server和Process farm. 动态进程允许更有效地使用资源和负载平衡. 例如, 所用节点数可以按需要减少和增加 支持容错. 当一个结点失效, 运行在其上的进程能在另一个结点上创建一个新进程完成其工作. 国家高性能计算中心（合肥）

66 6 MPI扩展 int MPI_Spawn ( char* command_line, int minprocs,
int maxprocs, char* info, int root, MPI_Comm comm, MPI_Comm* intercomm int* array_of_errcodes ) /* 可执行程序和参数 */ /* 最少要派生的进程数 */ /* 最多要派生的进程数 */ /* 在何处何时启动该进程 */ /* 根进程的编号 */ /* 根进程的通信子 */ /* comm与新派生的进程组间的互连通信子*/ /* 每个派生进程一个出错代码 */ 这个函数试图派生maxprocs个子进程, 每个子进程执行相同代码, 这个代码在command_line中定义. 如果MPI不能派生maxprocs个进程, 它可以按minprocs指定的数目派生进程. 如果它连minprocs个进程都派生不了, MPI_Spawn就返回一个出错代码. info 必须是一个空串, 允许运行时系统决定何地、如何启动该进程. 国家高性能计算中心（合肥）

67 int MPI_Parent(MPI_Comm* intercomm)
MPI_Spawn是一个群集操作, 也就是说, 通信子comm中的所有成员必须调用它派生进程. 但是, 只有root进程中的参数command_line, minprocs, maxprocs, 和info是有意义的, 而忽略其它进程上的这些参数值. 这样, 尽管派生的进程可以看成comm中所有进程的子进程, 但只有 root进程是真正的父进程. 子进程是MPI进程意味着它们必须调用MPI_Initialize, 它与父进程中的MPI_Spawn同是群集操作. 子进程和父进程可以通过intercommunicator intercomm 进行通信, 它从父进程中的MPI_Spawn返回, 子进程通过调用MPI_parent函数能获得intercommunicator的句柄. MPI_parent函数的形式如下: int MPI_Parent(MPI_Comm* intercomm) 国家高性能计算中心（合肥）

68 6 MPI扩展 单边通信 MPI-2包括一个新的点对点通信模式, 叫做远程存储访问(remote memory access, RMA), 它允许一个进程执行单边通信. 即, 一个进程可以发送一个数据值到一个目的地, 也可以从一个数据源取一个数据值, 无需另一边的参与. 在MPI-1中, 所有的点对点通信都是双边的, 发送者和接收者都必需参与. 国家高性能计算中心（合肥）

69 6 MPI扩展 单边接收(MPI_get) int MPI_Get ( void* dest_addr,
MPI_Init dest_count, MPI_Datatype dest_datatype, int source_rank, int source_disp, int source_count, MPI_Datatype source_datatype, MPI_Comm comm ) 国家高性能计算中心（合肥）

70 6 MPI扩展 单边发送(MPI_Put) int MPI_Put ( void* source_addr,
MPI_Init source_count, MPI_Datatype source_datatype, int dest_rank, int dest_disp, int dest_count, MPI_Datatype dest_datatype, MPI_Comm comm ) 国家高性能计算中心（合肥）

71 7 例子:计算Pi的MPI程序 #include <stdio.h> #include <mpi.h>
#include <math.h> long n, /*number of slices */ i; /* slice counter */ double sum, /* running sum */ pi, /* approximate value of pi */ mypi, x, /* independent var */ h; /* base of slice */ int group_size,my_rank; main(argc,argv) int argc; char* argv[];  国家高性能计算中心（合肥）

72 { int group_size,my_rank; MPI_Status status; MPI_Init(&argc,&argv);
MPI_Comm_rank( MPI_COMM_WORLD, &my_rank); MPI_Comm_size( MPI_COMM_WORLD, &group_size); n=2000; /* Broadcast n to all other nodes */ MPI_Bcast(&n,1,MPI_LONG,0,MPI_COMM_WORLD); h = 1.0/(double) n; sum = 0.0; for (i = my_rank+1; i <= n; i += group_size) { x = h*(i-0.5); sum = sum +4.0/(1.0+x*x); } mypi = h*sum; /*Global sum */ MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); if(my_rank==0) { /* Node 0 handles output */ printf("pi is approximately : %.16lf\n",pi); MPI_Finalize(); 国家高性能计算中心（合肥）

73 7 例子:计算Pi的MPI程序 编译： mpicc -o pi pi.c 运行： mpirun -np 2 pi 国家高性能计算中心（合肥）

74 提纲 14.1 基于消息传递的编程 14.2 MPI并行编程 14.3 PVM并行编程 14.4 基于数据并行的并行编程
14.5 HPF并行编程 国家高性能计算中心（合肥）

75 并行虚拟机(PVM) 1 并行虚拟机的构造 2 PVM中的进程管理 3 PVM中的通信 4 例子: 计算Pi的PVM程序
1 并行虚拟机的构造 2 PVM中的进程管理 3 PVM中的通信 4 例子: 计算Pi的PVM程序 国家高性能计算中心（合肥）

76 1 并行虚拟机的构造 PVM系统的组成(两部分) PVM监控进程(daemon), 称为pvmd, 它常驻在虚拟机的每个计算机上
1 并行虚拟机的构造 PVM系统的组成(两部分) PVM监控进程(daemon), 称为pvmd, 它常驻在虚拟机的每个计算机上 用户可调用的库, 称为libpvm3.a, 它与用户的应用程序链接, 用于进程管理, 消息传递和虚拟机管理. 在PVM中, 节点(a node)称为主机(a host). 进程(a process)称为任务(a task). 并行虚拟机的组成 1~多台主机(硬件) 唯一1个master pvmd(系统软件), 运行在称为控制台的主机上 0~多个slave pvmd(系统软件) 国家高性能计算中心（合肥）

77 1 并行虚拟机的构造 PVM 控制台(Console) pvmd 的启动方法 master pvmd启动slave pvmd的方法
1 并行虚拟机的构造 PVM 控制台(Console) 安装了PVM后, 用户在任何一台主机上键入以下命令创建PVM控制台: pvm host_file 这个命令执行成功后将在调用它的主机和host_file文件中所列的每台主机上启动一个pvmd监控进程, 并在调用它的主机上显示下列提示符: pvm> 它指示主机当前处于PVM控制台模式. pvmd 的启动方法 master pvmd: 必须手工启动 slave pvmds: 只能由master pvmd依次启动 master pvmd启动slave pvmd的方法 用rsh, rexec(), 或其它方法启动一个slave 国家高性能计算中心（合肥）

78 1 并行虚拟机的构造 主要的PVM命令 国家高性能计算中心（合肥）

79 1 并行虚拟机的构造 启动文件: host_file
1 并行虚拟机的构造 启动文件: host_file 并行虚拟机的硬件配置在主机表(host table)文件中说明. 它常驻在虚拟机的每台主机上. 主机表中有一项叫做主机描述子(host descriptor), 对应于虚拟机中的每台主机. 主机描述子中保存有主机配置信息, 以及packet queues 和通信信息缓冲. 最初, 主机表只有master host一项. 当一个新的slave加入到虚拟机后, master host的主机表被修改, 添加一个与新加入的slave对应的新项. 然后, 修改后的主机表的信息被播送到整个虚拟机, 包括新加入的slave hosts. 这样, 虚拟机中所有主机的主机表被同步, 并且保持一致, 除非哪台机器不转了或网络失效. 国家高性能计算中心（合肥）

80 1 并行虚拟机的构造 虚拟机的动态配置 用户可以调用PVM库函数来动态配置虚拟机.
1 并行虚拟机的构造 虚拟机的动态配置 用户可以调用PVM库函数来动态配置虚拟机. pvm_addhosts函数: 向虚拟机中加入一至多台主机 pvm_delhosts 函数: 从虚拟机中删除一至多台主机 例子 int info, nhost=2, infos[2]; char *host[]={“apple”, “orange.cs.ustc.edu.cn”} info=pvm_addhosts(hosts, nhost, infos); info=pvm_delhosts(hosts, nhost, infos); 国家高性能计算中心（合肥）

81 图 动态加入一个主机H3 host H2(slave) host H1(master) host H3(new slave)
task T(用户进程) pvmd2(系统进程) pvmd1(系统进程) pvmd3(系统进程) pvm_addhosts() Blocked finished dm_addhost() dm_htupd() dm_htcommit() dm_addhostack() dm_addhost() dm_startack() dm_htupdack() slave_config() dm_htupd() dm_htcommit() 图 动态加入一个主机H3 国家高性能计算中心（合肥）

82 2 PVM中的进程管理 PVM支持实现静态和动态的并行性 静态并行程序 例子: foo为一个SPMD程序, 在控制台上执行命令
pvm>spawn –count 4 foo 将创建一个4个任务(或进程)的并行应用, 运行在虚拟机上. 每个任务执行同一个代码foo, 如果foo不调用动态任务创建函数pvm_spawn(), 这个应用将有一个静态的DOP(并发度)为4. 国家高性能计算中心（合肥）

83 2 PVM中的进程管理 程序到主机的映射 缺省: 由PVM提供的应用算法将任务映射到主机上. 每台主机上可映射多个任务.
用户自定义: 由用户为每个任务显式地定义一个特定的主机或体系结构类型 例子: 在控制台上执行命令: pvm> spawn –(apple) foo 将在主机apple上启动一个任务执行代码foo pvm> spawn –(RS6K) foo 将在任意的RS/6000节点上使用AIX操作系统启动一个任务执行代码foo 国家高性能计算中心（合肥）

84 2 PVM中的进程管理 动态并行程序与进程管理 PVM支持开发MPMD并行程序和动态进程管理. 最重要的函数是pvm_spawn().
int numt // 实际被启动的任务数 =pvm_spawn( char *progm, // 可执行文件名 char **argv, // 指向参数数组的指针 int flag, // 选项 char *where, // 与flag配合使用 int ntask, // 可执行文件启动的拷贝数 int *tid // 保存派生任务的tid ) 国家高性能计算中心（合肥）

85 2 PVM中的进程管理 国家高性能计算中心（合肥）

86 2 PVM中的进程管理 国家高性能计算中心（合肥）

87 2 PVM中的进程管理 PVM支持动态分组, 任何任务都可以在任意时候加入或离开一个组. PVM 的分组功能由一个叫做group server的daemon完成, 当第一个组函数被调用时自动地启动这个daemon. PVM动态分组概念是很灵活的. 可以有多个组, 一个任务在任何时候可以属于不同的组. 一个任务可以在任何时候加入和离开一个组, 无需通知组内的其它成员(不像MPI, 一个任务在一组内总有一个唯一的编号). 一个任务可以播送一个消息给一个组, 即使它不是这个组的成员. 动态分组带来程序行为的非确定性. 例如: 一个播送操作可以有不同的结果, 如果一个任务加入或离开一个组. 任务可能会也可能不会得到这个广播的消息. 如果成员任务离开一个组, 路障同步操作可能会死锁. 国家高性能计算中心（合肥）

88 2 PVM中的进程管理 国家高性能计算中心（合肥）

89 2 PVM中的进程管理 S G H L 图 PVM通用的任务标识符TID格式 国家高性能计算中心（合肥）

90 3 PVM中的通信 PVM有三种类型的通信: pvmd间通信 pvmd与其任务间的通信 以及两个任务间的通信 task1 pvmd1
UDP TCP 图 通用的PVM中所用的通信协议 国家高性能计算中心（合肥）

91 3 PVM中的通信 PVM通信函数实例 int bufid =pvm_initsend(int encoding)
int info=pvm_pkint(int * p, int nitem, int stride) int info=pvm_send(int tid, int tag) int info=pvm_mcast(int *tids, int ntasks, int tag) int bufid=pvm_recv(int tid, int tag) int bufid=pvm_nrecv(int tid, int tag) int bufid=pvm_trecv(int tid, int tag, struct timeval *tmout) int bufid=pvm_probe(int tid, int tag) int bufid=pvm_bufinfo(int bufid, int *bytes, int *tag, int *tid) int info=pvm_upkint(int *p, int nitem, int stride) 国家高性能计算中心（合肥）

92 4 例子: 计算π的PVM程序 #define n /* number of tasks */ #include “pvm3.h” main(int argc, char **argv) { int mytid, tids[n], me, i, N, rc, parent; double mypi, h, sum=0.0, x; me=pvm_joingroup( “PI”); parent=pvm_parent( ); if (me= =0) { pvm_spawn( “pi”, (char**)0, 0, “”, n-1, tids); printf(“Enter the number of regions:”); scanf( “%d”, &N); pvm_initsend(PvmDataRaw); pvm_pkint(&N, 1, 1); pvm_mcast(tids, n-1, 5); } else { pvm_recv(parent,5); pvm_upkint(&N,1,1); 这个SPMD程序划分间隔[0,1]进入N个区域, 并启用n个任务. 每个任务负责由N/n区域计算一个部分和mypi. 然后这n个部分和由归约(reduction)操作聚积成一个总和. pvm_barrier( “PI”,n); /* optional */ h=1.0/(double) N; for (i=me+1;i<=N; i+=n){ x=h*((double)i-0.5); sum+=4.0/(1.0+x*x); } mypi=h*sum; pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6, “PI”,0); if (me==0) printf( “pi is approximately %.16f\n”, mypi); pvm_lvgroup( “PI”); pvm_exit(); 国家高性能计算中心（合肥）

93 4 例子: 计算π的PVM程序 假定源码包含在文件pi.c中. 可执行文件pi用以下命令得到:
cc –I/pvm3/include pi.c libgpvm3.a libpvm3.a –o pi 用户调用第一个任务, 它派生出其它n-1个任务. 每个任务首先用以下语句: me=pvm_joingroup( “PI”); 加入一个组PI, 变量me将包含组内任务的编号(实例号). 初始任务的编号为0. 下一条语句 parent= pvm_parent(); 找出父任务的ID. 初始任务没有父亲, 这个函数调用返回0. 对其它任务, 这个函数调用返回初始任务的ID. 国家高性能计算中心（合肥）

94 4 例子: 计算Pi的PVM程序 初始任务执行 pvm_spawn( “pi”, (char**)0,0, “”, n-1, tids);
派生n-1个子任务, 执行文件 “pi”中的代码和他们的任务ID在数组tids中返回. 其它三个参数为null(0), 这是许多PVM程序的典型情况. 初始任务执行下面的代码提示用户键入变量N中的区域数: printf( “Enter the number of regions:”); scanf(“%d”, &N); 国家高性能计算中心（合肥）

95 4 例子: 计算Pi的PVM程序 然后, 它执行下列代码将这个值播送给所有子任务: pvm_initsend(PvmDataRaw);
pvm_pkint(&N, 1, 1); pvm_mcast(tids, n-1, 5); 这里, 5是一个任意的消息标签. 同时, 每个子任务将执行下列代码匹配这个播送: pvm_recv(parent,5); /* 5是与pvm_mcast中的标签相匹配的标签*/ pvm_upkint(&N,1,1); 然后所有的任务执行一个路障同步: pvm_barrier( “PI”,n); /* 在组PI中的n个任务应在此同步 */ 国家高性能计算中心（合肥）

96 4 例子: 计算Pi的PVM程序 接下来的几行只是正常的计算: h=1.0/(double) N;
for (i=me+1;i<=N; i+=n){ x=h*((double)i-0.5); sum+=4.0/(1.0+x*x); } mypi=h*sum; 国家高性能计算中心（合肥）

97 4 例子: 计算Pi的PVM程序 接下来做归约操作:
pvm_reduce(PvmSum,&mypi,1,PVM_DOUBLE,6, “PI”,0); 这是一个组PI中所有的任务的求和归约. 每个任务从本地mypi贡献一个类型为PVM_DOUBLE数据项. 最终的结果存放在初始任务(编号为0)的mypi中. 数6也是一个任意的消息标签. 一般地, 一个PVM归约具有以下函数原型 pvm_reduce(void(*func)(),void *buffer, int nitem, int datatype, int tag, char *group, int root); 打印出这个结果后, 程序调用以下函数清理环境 pvm_lvgroup(“PI”) and pvm_exit() . 国家高性能计算中心（合肥）

98 4 例子: 计算Pi的PVM程序 编译： pvmcc -o pi pi.c 运行： $>pvmd –d7 host_file&
pvm>span –4 pi pvm>halt 国家高性能计算中心（合肥）

99 提纲 14.1 基于消息传递的编程 14.2 MPI并行编程 14.3 PVM并行编程 14.4 基于数据并行的并行编程
14.5 HPF并行编程 国家高性能计算中心（合肥）

100 数据并行程序设计 数据并行模型的特点 单线程 在密集的数据结构上的并行操作 全局命名空间 隐式的同步和通信 隐式的计算和数据分布
具有很好的可移植性. 包括SIMD, MIMD,共享和分布存储机器 数据并行模型的目的是要在分布存储的机器上实现在全局名空间进行并行程序设计, 以屏蔽显式的数据分布和通信问题, 是一种细粒度的并行. 与消息传递模型相比, 数据并行程序设计能在一定程度上减轻程序员的负担, 但是完全依赖于程序员能否确定一个好的数据分布. 国家高性能计算中心（合肥）

101 数据并行程序设计 数据并行语言的发展 在SIMD机器ILLIAC IV开发的语言IVTRAN,是最早的允许用户控制数据布局的语言 Kali
Fortran D/Vienna Fortran Fortran 90/ Fortran 95 Thinking Machines公司的C*/CM Fortran /*Lisp HPF/HPF+/F--/HPC++/HPJava 国家高性能计算中心（合肥）

102 提纲 14.1 基于消息传递的编程 14.2 MPI并行编程 14.3 PVM并行编程 14.4 基于数据并行的并行编程
14.5 HPF并行编程 国家高性能计算中心（合肥）

103 HPF并行编程 高性能Fortran(HPF)简介 HPF的数据并行机制 例子: 高斯消去法的HPF程序 国家高性能计算中心（合肥）

104 1 高性能Fortran(HPF)简介 发展历史
1991年, DEC的D.Lovman和Rice大学的K.Kennedy在Supercomputing’91大会上提出了他们的高性能Fortran版本, 以统一在分布存储机器上的编程方法 1992年1月, 在Rice大学召开了第一次HPF会议, 一致通过组织HPF论坛 1992年3月, 该论坛正式成立 1993年5 月, 发布了HPF 1.0版 基于Fortran90 1994年11月发布了HPF 1.1版 1997年1月, 论坛发布了HPF 基于Fortran 95 国家高性能计算中心（合肥）

105 1 高性能Fortran(HPF)简介 对HPF的批评主要有三个方面: 认为 HPF是一个太高层的语言, 不如MPI风格的语言适用;
国家高性能计算中心（合肥）

106 1 高性能Fortran(HPF)简介 HPF主要的设计目标如下: (1) 支持数据并行程序设计;
(2) 最大限度地发挥非均匀存储访问的MIMD和SIMD计算机的性能; (3) 能够调整代码适应各种体系结构的计算机. HPF2.0语言的组成包括三个部分: (1) 语言的基本部分: 包括任何HPF编译器必须支持的特性; (2) 已经核准的扩展部分: 包括满足某些特殊需要的高级结构, 早期的编译器可能不支持这部分; (3) 已被承认的外部接口: 是HPF论坛批准的一组接口, 但是由他人设计并为HPF用户提供具体的服务内容. 国家高性能计算中心（合肥）

107 (1) 数据并行说明(Data parallel directives):达到第一个目标
HPF2.0的一些基本特性如下: (1) 数据并行说明(Data parallel directives):达到第一个目标 INDEPENDENT：声明一个循环没有依赖, 可以并行执行 REDUCTION：标识被不同迭代使用结合的和可交换的运算修改的变量 (2) 数据映射说明(Data mapping directives):达到第二个目标 ALIGN：数据对准 DISTRIBUTE：数据分布（映射） 声明如何在处理器间分配数据, 使得通信开销最小, 负载平衡. (3) 新的内部函数和库函数(New intrinsic and library functions):用于实现第三个目标, 允许用户利用特定机器的低层特性. 归约(reduction)函数／组合分散(Combining-Scatter)函数, 前缀(Prefix)/后缀(Suffix)函数 分类(Sorting)函数/位操作(Bit-Manipulation)函数 (4) 外部过程(Extrinsic procedures): 用于匹配其它的编程方法，支持混合语言编程 国家高性能计算中心（合肥）

108 2 HPF的数据并行机制 3.1 FORALL结构(FORALL construct) 例1 简单的FORALL语句
FORALL (K=1, M―1) X (K+1)=X(K) 注释: 语句执行后, X(I―1)的值送入X ( I )中. FORALL (I=1:N, J=1, N) X(I, J) = Y (J, I) 注释: 语句执行后, Y的转置矩阵被送入X. 国家高性能计算中心（合肥）

109 2 HPF的数据并行机制 例2 带限制的FORALL语句
FORALL (i=2:5, X(i)>0) X(i)=X(i―1)+X(i+1) 注释: i是索引变量, i=2:5称为for-三元组, 等价于i=2:5:1, 表示i的变化范围下界是2, 上界是5, 缺省步长为1. 即i的有效值取{2, 3, 4, 5}. 假设在上述FORALL语句中, 初始X={1,―1,2,―2, 3,―3}, 在i的有效值范围内, 满足X(i)>0 的索引i的活动集合为{3, 5}. 求出这个活动索引值集合后, 所有赋值表达式同时计算: X(3) <= X(3-1)+X(3+1)= ―3 X(5) <= X(5-1)+X(5+1)= ―5 FORALL语句结束后, X={1,―1,―3,―2,―5,―3}. 国家高性能计算中心（合肥）

110 2 HPF的数据并行机制 例3 FORALL (K=1:M, Y(K).NE.0.0) X (K)=1.0/Y(K)
注释: 对Y(K)的值不为0的K, 把Y(K)的倒数送入X(K). 例4 在FORALL语句中, 可能有不止一个for-三元组, 则用的是联合索引. FORALL(i=1:2, j=1:3, Y(i,j)>0) Z(i,j)=1/Y(i,j) 注释: 该语句等价于Fortran90语句 where (Y(1:2, 1:3)>0) Z(1:2, 1:3)= 1/ Y(1:2, 1:3) 则联合索引的有效值取集合{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)}, 联合索引的活动值取上述集合中使Y(i,j)>0的子集. 国家高性能计算中心（合肥）

111 2 HPF的数据并行机制 有时, 用户希望在一个FORALL语句中包含几个赋值, 这可用FORALL结构来实现. FORALL结构是对FORALL语句的进一步扩充, 即在FORALL和ENDFORALL之间, 可以写多条语句. 但限制FORALL结构中只能使用赋值语句、FORALL语句、FORALL结构、WHERE语句及WHILE结构. 例5 FORALL (I=2: 9) A(I) = A(I―1) + A(I+1) B(I) = A(I) ENDFORALL 注释: 首先， 对从2到9的各I, 求值A(I―1)+A(I+1), 然后, 将其结果送入A(2)到A(9)中, 再将求得的A(2)到A(9)的值送入B(2)到B(9)中. 国家高性能计算中心（合肥）

112 2 HPF的数据并行机制 例6 FORALL(i=1:n) A (i) = sin (B(i));
C (i) = sqrt (A(i)* A(i)) D (i) = B (i)+2 ENDFORALL 国家高性能计算中心（合肥）

113 2 HPF的数据并行机制 3.2 数据映射(Data mapping)
数据映射: 指的是将数据分布到处理器上. 要在分布存储系统上实现并行处理, 首先要对数据(主要是数组)进行划分, 然后分配给各个处理机, 再在各个处理器上进行计算. 数据映射要达到以下目的: (1) 使处理器间的通信开销最小; (2) 负载在可用的处理器间均匀分布. HPF编译器可以利用owner-compute 规则分布负载: 在数据所在的处理器上执行与该数据有关的计算. 因此数据映射直接决定负载分布. HPF提供了许多说明语句用于指示编译器如何最佳地分布数据到计算节点上去. 国家高性能计算中心（合肥）

114 2 HPF的数据并行机制 一些重要的说明语句的例子 (1) 伪指令PROCESSORS: 用于描述虚拟的处理机结构 例7
!HPF$ PROCESSOR P4 (4) 注释: 描述由4个处理机组成的虚结构 !HPF$ PROCESSOR P22 (2, 2) 注释: 描述两行两列共4个处理器组成的二维虚结构 国家高性能计算中心（合肥）

115 2 HPF的数据并行机制 (2) 伪指令ALIGN: 用于描述数据对准 例8 同维数组间的对准
!HPF$ ALIGN A(I) WITH B(I) 注释: 表示把A的第I个元素与B的第I个元素分配到同一个处理器上. !HPF$ ALIGN A(I) WITH B(I+1) 注释: 表示把A的第I个元素与B的第I+1个元素分配到同一个处理器上. !HPF$ ALIGN A(I, J) WITH B(J, I) 注释: 表示把A的第(I, J)个元素与B的第(J, I)个元素分配到同一个处理器上. 国家高性能计算中心（合肥）

116 2 HPF的数据并行机制 例9 不同维数组间的对准 !HPF$ ALIGN A(I, *) WITH B(I)
注释: 表示把A的第I行的所有元素与B的第I个元素分配到同一个处理器上. !HPF$ ALIGN A(I) WITH B(I, *) 注释: 表示把A的第I个元素重复分配到B的第I行各元素所在的处理器上. 国家高性能计算中心（合肥）

117 2 HPF的数据并行机制 (3) 伪指令DISTRIBUTE: 用于描述数据映射(分布)
有分块(BLOCK(n))和循环(CYCLIC(n)) 两种分布方式. 例10 以分块方式进行数据分布 !HPF$ DISTRIBUTE A (BLOCK) ONTO P4 注释: 表示将A分成每块有25个元素组成的4个块, 分给4个处理器. !HPF$ DISTRIBUTE A (BLOCK(30)) ONTO P4 注释: 表示将A分成每块有30、30、30、10个元素组成的4个块, 分给4个处理器. 国家高性能计算中心（合肥）

118 2 HPF的数据并行机制 !HPF$ DISTRIBUTE B (BLOCK, BLOCK) ONTO P22
!HPF$ DISTRIBUTE B (*, BLOCK) ONTO P4 注释: 表示数组B在列方向分成4个块, 行方向不分布 国家高性能计算中心（合肥）

119 2 HPF的数据并行机制 例11 以循环方式进行数据分配 !HPF$ DISTRIBUTE A (CYCLIC) ONTO P4
注释: 表示从A(1)开始, 把各元素循环分配给从第1到第n (这里n=4)个处理器, 如, 第1个处理器分到了A(1), A(5), A(9)等. !HPF$ DISTRIBUTE A (CYCLIC (2)) ONTO P4 注释: 表示把数组元素从前往后, 每两个分为一组, 循环分给从第1至第n (=4) 个处理器. 如, 处理机1分到了A(1), A(2), A(9), A(10), 处理器2分到了A(3), A(4), A(11), A(12)等等. 国家高性能计算中心（合肥）

120 2 HPF的数据并行机制 (4) 一个数据映射的HPF程序段 例12 考虑如下代码段:
例12 考虑如下代码段: integer A(100), B(100), C(101), i !HPF$ ALIGN A(i) WITH B(i-1) !HPF$ PROCESSOR N(4) !HPF$ DISTRIBUTE A(BLOCK) ONTO N !HPF$ DISTRIBUTE C(CYCLIC) ONTO N FORALL (i=2: 100) A(i) = A(i)+B(i―1) C(i) = C(i―1) + C(i) +C(i+1) ENDFORALL 国家高性能计算中心（合肥）

121 High Performance Switch
Logical Mapping ALIGN DISTRIBUTE A(1:25) B(1:24) C(1:101:4) A(26:50) B(25:49) C(2:101:4) A(51:75) B(50:74) C(3:101:4) A(76:100) B(75:99) C(4:101:4) N1 N2 N3 N4 N1, N2 N3, N4 High Performance Switch . . . A Paragon Mesh A Uniprocessor An IBM SP2 Physical Mapping C(1) C(2) C(3) C(101) B(1) B(2) B(99) B(100) A(1) A(2) A(3) A(100) 国家高性能计算中心（合肥）

122 2 HPF的数据并行机制 例13 !HPF$ PROCESSOR N(4, 5) 注释: 定义20个节点组成的4×5网格.
注释: 定义120个节点组成的4×5×6网格. 国家高性能计算中心（合肥）

123 3 高斯消去法的HPF程序 parameter n=32 real A(n,n+1), x(n)
integer i,pivot_location(1) !HPF$ PROCESSOR Nodes(4) !HPF$ ALIGN x(i) WITH A(i,j) !HPF$ DISTRIBUTE A(BLOCK,*) ONTO Nodes do i=1,n-1 ! pivoting(选主元) pivot_location=MAXLOC(ABS(A(i:n,i))) swap(A(i,i:n+1),A(i-1+pivot_location(1),i:n+1)) ! triangularization(三角化) A(i,i:n+1)=A(i,i:n+1)/A(i,i) FORALL (j=i+1:n,k=i+1:n+1) A(j,k)=A(j,k)-A(j,i)*A(i,k) end do 国家高性能计算中心（合肥）

124 3 高斯消去法的HPF程序 !back substitution(反向替换) do i=n,1,-1 x(i)=A(i,n+1)
A(1:i-1,n+1)=A(1:i-1,n+1)-A(1:i-1,i)*x(i) end do 国家高性能计算中心（合肥）

125 3 高斯消去法的HPF程序 DISTRIBUTED 命令指出A的第一维应是成块分布. A的第二维中的*号说明第二维已被折叠, 意味着部分数组A(I,1:n)被映射到同一结点. 假设有四个虚拟结点N1, N2,N3, N4, 且N可为4整除. 那么, 数据分布便为如下: N1: A(1:n/4,1:n), b(1:n/4), Temp(1:n/4), X(1:n) N2: A(n/4+1:2*n/4,1:n), b(n/4+1:2*n/4), Temp(n/4+1:2*n/4), X(1:n) N3: A(2*n/4+1:3*n/4,1:n), b(2*n/4+1:n), Temp(2*n/4:3*n/4) N4: A(3*n/4+1:n,1:n), b(3*n/4+1:n), Temp(3*n/4+1:n), X(1:n) 国家高性能计算中心（合肥）

126 3 高斯消去法的HPF程序 在四个结点中的数据分布 结点1 A(1:8;1:33), X(1:8)
国家高性能计算中心（合肥）