Microsoft PowerPoint - PC14.pptx

Transcription

1 并行计算 结构 算法 编程 主讲教师 : 谢磊

2 第十四章分布存储系统并行编 程

3 分布存储系统并行编程 14.1 基于消息传递的编程 14.2 MPI 并行编程 14.3 PVM 并行编程 14.4 基于数据并行的并行编程 14.5 HPF 并行编程

4 分布存储系统并行编程 分布存储系统的主要特点 系统通过互联网络将多个处理器连接起来 每个处理器均有自己的局部存储器, 所有的局部处理器就构成了整个地址空间 整个地址空间有局部和全局两种编址方式 全局编址方式 系统中所有局部存储器统一编址, 用户程序空间是一个统一的全局地址空间 远程存储器的访问与局部存储器的访问一样用指令来完成, 其指令地址是由处理器号和局部存储器地址所组成

5 分布存储系统并行编程 局部编址方式 系统中个局部存储器单独编址, 用户程序空间是多地址空间 远程存储器的访问要通过调用消息传递库来实现 上述特点导致了分布存储系统的两种并行编程模型 消息传递模型 SPMD,MPMD 数据并行模型 SIMD,SPMD

6 基于消息传递的并行编程 根据问题分解的两种形式, 消息传递并行性的开发有两种形式 域分解形式 :SPMD 编程 将一个大的问题区域分解成若干个较小的问题区域, 然后对其并行求解 函数分解形式 :MPMD 编程 将一个大的问题分解成若干个子问题, 然后对其并行求解

7 SPMD 并行程序 SPMD 就是同一程序复制到各个处理器上, 而不同的数据分布在不同的处理器上 这样在系统中各处理器均运行相同的程序, 但对不同的数据执行操作 设计 SPMD 形式的消息传递程序的主要步骤是 : 数据划分 : 尽量考虑负载平衡 存储空间的均衡使用以及减少处理器之间的通信 优化通信 : 尽量提高计算 / 通信比, 数据就地使用, 合并短消息成一个长消息进行传输 全局操作 : 将各处理器的局部结果组合起来形成整个问题的解, 这样的操作包括 : 全局同步 播送 归约 前缀运算 收集 / 散播等

8 SPMD 并行程序 编写 SPMD 形式的程序有两种方式 主机 / 节点式 (Host/Node) 主机程序 : 运行在控制节点上 节点程序 : 运行在所有的计算节点上 一个主机程序控制一组以 SPMD 方式执行的节点程序 无主机式 (Hostless) 一个应用程序整个运行在计算节点上, 而控制节点不起上节所说的主机节点的作用 在这种结构中, 程序控制也是在计算节点上完成的

9 MPMD 并行程序 MPMD 就是每个处理器执行不同的代码副本 各自对数据完成不同的运算 设计 MPMD 形式的消息传递程序的主要步骤是 : 子问题划分 : 尽量考虑各处理器负载均衡和充分利用各处理器的独特能力, 在全系统范围内合理分配各子问题于不同处理器上 确定子问题之间的相互作用方式

10 MPMD 并行程序 实现子问题之间相互作用的方式有两种 : 数据流方式和客户 / 服务器方式 数据流方式 : 用户将问题分解为各不相同的子问题 ; 根据子问题的相关性来组织并行, 按数据驱动的方式决定并行执行的先后次序 客户 / 服务器方式 : 用户将一些典型的不同的子问题求解作为相应的服务进程分布在各个计算节点上 整个问题的求解就归结为客户对各个服务器的一系列服务请求

11 基于消息传递的并行编程 1 消息传递库 2 消息传递方式

12 1 消息传递库 (Message-Passing Libraries) 表 1.1 一些最流行的消息传递软件的例子 Name Original Creator Distinct Features CMMD Thinking Machines Use Active Messages for low latency Express Parasoft Collective communication and I/O Fortran-M Argonne National Lab Modularity and Determinacy MPI MPI Forum A widely adopted standard NX Intel Originated from the Intel hypercube MPPs P4 Argonne National Lab Integrate shared memory and message passing PARMACS ANL/GMD Mainly used in Europe PVM Oak Ridge National Lab A widely used, stand-alone system UNIFY Mississippi State A system allowing both MPI and PVM calls Zipcode Livemore National Lab Contributed to the context concept 建议 : 一个终端用户在开发新的消息传递应用时使用 MPI 或 PVM. 原因是 : MPI 和 PVM 都是公用软件, 易于得到 多数厂家支持

13 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 等.

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

15 1 消息传递库 (Message-Passing Libraries) 1.1 MPI(Message Passing Interface) 简介 1992 年 4 月 组建了一个制定消息传递接口标准的工作组 1992 年 10 月 初稿形成, 主要定义了点对点通信接口 1993 年 1 月 第一届 MPI 会议在 Dallas 举行 1993 年 2 月 公布了 MPI-1 修定版本 1993 年 11 月 MPI 的草稿和概述发表在 Supercomputing 93 的会议论文集中 1994 年 5 月 MPI 标准正式发布 1994 年 7 月 发布了 MPI 标准的勘误表 1997 年 MPI 论坛发布了一个修订的标准, 叫做 MPI-2, 同时, 原来的 MPI 更名为 MPI-1 目标 : 是提供一个实际可用的 可移植的 高效的和灵活的消息传递接口标准. MPI 以语言独立的形式来定义这个接口库, 并提供了与 C Fortran 和 Java 语言的绑定. 这个定义不包含任何专用于某个特别的制造商 操作系统或硬件的特性. 由于这个原因, MPI 在并行计算界被广泛地接受.

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

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

18 2 消息传递方式 1.2 Message-Passing Modes 关于通信模式, 用户需要理解的有三个方面 : 共有多少个进程? 进程间如何同步? 如何管理通信缓冲区? 现在的消息传递系统多使用三种通信模式 : 同步的消息传递 (Synchronous Message Passing) 阻塞的消息传递 (Blocking Message Passing) 非阻塞的消息传递 (Nonblocking Message Passing)

19 2 消息传递方式 等待发送点 开始发送点 发送返回点 进程 P S_syn1 R_block2 R_Non_Block3 系统进程 进程 Q R_syn1 S_Non_Block3 S_Block2 开始接收点 接收返回点 发送例程 接收例程

20 2 消息传递方式 例 2.1 消息传递中的发送和接收缓冲 Process P: Process Q: M=10; L1: send M to Q; L2: M=20; goto L1; 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)

21 三种通信模式的比较 2 消息传递方式 通信事件 同步通信 阻塞的通信 非阻塞的通信 发送开始的条件 双方都到达了发送和接收点 发送方到达发送点 发送方到达发送点 发送返回意味着 消息已被收到 消息已被发送完 通知完系统某个消息要被发送 接收开始的条件 双方都到达了发送和接收点 接收方到达发送点 接收方到达发送点 接收返回意味着 消息已被收到 消息已被收到 通知完系统某个消息要被接收 语义 明确 二者之间 需做错误探测 是否需要系统提供 临时的消息缓冲区 不需要需要需要 状态检查不需要不需要需要 等待的时间开销最高二者之间最低 通信与计算 通信与 通信的重迭 不重迭重迭重迭 X , 21, -99

22 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;

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

24 基于数据并行的并行编程 数据并行模型的特点 对于有些问题, 常常要对大量的数据进行相同的 彼此独立的操作, 这些量大且互不影响的操作是可以并行执行的, 这就是数据并行名称的由来 例如 : 矩阵相乘, 这种程序很自然的适合在 SIMD 机器上实现 SPMD 是 SIMD 的特例,SPMD 是一种中粒度的并行, 是语句块和循环一级的同步, 而不是像 SIMD 那样是指令集的同步 在 SPMD 模式下, 每个处理器异步的执行相同的程序, 只有当处理器间需要交换数据时才施行同步 由于减少了同步,SPMD 模式在许多情况下比 SIMD 模式更有效

25 基于数据并行的并行编程 数据并行模型的特点 由于减少了同步,SPMD 模式在许多情况下比 SIMD 模式更有效 在大规模并行处理 MPP 系统中, 使用 SPMD 模式进行编程时, 用户程序把真个分布存储系统视为一个统一的全局空间, 由编译实现程序的逻辑地址到物理地址的映射 总之, 数据并行程序是一个单一控制线程的 并行操作于不同数据项的 语句循环级同步的 单一地址空间的 通信可由变量指派而隐含完成的一种并行程序

26 数据并行编程的基本问题 数据分布 建立数据集合到处理器集合之间的映射关系, 数据分布就是把数据按一定规则分配到各个处理器的存储单元中去 分布的目的是为了提高程序执行的并行性, 增强数据局部性, 减少通信, 从而提高程序的执行效率 常用的分布方法有 : 按块分布 循环分布 对准分布和静态 / 动态分布等

27 数据并行编程的基本问题 任务分配 把计算任务分配在各个处理器上, 使得程序可以在并行系统上高效执行 任务分配的准则是尽可能将计算和其所需的数据对准, 也就是数据分配到哪个处理器, 就将用到这些数据的计算操作也分配到哪个处理器, 即所谓的 属主 计算 原则 在进行数据并行编程时, 一般是先定义数据分布, 再将并行循环中的迭代计算按数据分布模式分配到各个处理器上去执行, 这样就实现了计算和数据的对准

28 数据并行编程的基本问题 同步通信 对于 SPMD 模式数据并行编程, 在共享变量模型下, 同步通信一般包含临界区 锁 路障和时间等 ; 编译系统给通信提供了较强的支持 : 对于点到点通信, 程序员可以写成赋值语句 ; 对于全局通信, 程序员可以调用系统库程序

29 数据并行编程的基本问题 处理器拓补结构 处理器拓补的形成就是把参加并行执行的处理器分配给分布数组的各维, 即决定各维分几个处理器 处理器拓补结构可由编译系统确定, 所依据的规则是数据分布大致均匀 地址计算尽量简单和通信尽可能少

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

31 数据并行程序设计 数据并行语言的发展 在 SIMD 机器 ILLIAC IV 开发的语言 IVTRAN, 是最早的允许用户控制数据布局的语言 Kali Fortran D/Vienna Fortran Fortran 90/ Fortran 95 Thinking Machines 公司的 C*/CM Fortran /*Lisp HPF/HPF+/F--/HPC++/HPJava

32 附录 MPI 并行编程详解 PVM 并行编程详解 HPF 并行编程详解

33 MPI 并行编程 1 MPI 中的消息 2 MPI 中的消息信封 3 MPI 中的四种通信模式 4 点对点的通信 5 群集通信 6 MPI 扩展 7 例子 : 计算 Pi 的 MPI 程序

34 #include 第五讲 "mpi.h" int foo(i) int i; {...} 1 MPI 中的消息 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 中 初始化 MPI 环境 得到缺省的进程组大小 得到每个进程在组中的编号 发送消息 接收消息 终止 MPI 环境

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

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

37 1 MPI 中的消息 例 1 用 MPI 发送一个数据数组 考虑一个用 C 语言声明的由 N 个复数组成的数组 double A[100] 假定进程 P 要把这个数组发送给进程 Q:

38 1 MPI 中的消息 要发送的消息可用的消息传递系统说明 (1) 发送整个数组 A (2) 发送数组 A 的头两个元素, 即 : A[0] 和 A[1] (3) 发送数组 A 中所有偶数编号的元素, 即 : A[0],A[2],A[4],... 国家高性能计算中心 ( 合肥 ) 理论的消息传递 send A to Q 商用的消息传递 ( 假定在一台计算机上, 一个双精度数是 64 位, 即 8 个字节.) send(a, 16, Q, tag) MPI 的消息传递 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,...); 消息缓冲由数组 A 标识, 信封就是进程名 Q. 使用的发送例程形式如下 : send (address, length, destination, tag) (address, length) 定义消息缓冲, (destination, tag) 定义消息信封. (1) 需要定义导出数据类型 (2) 使用发送例程形式如下 : MPI_Send (buffer, count, datatype, destination, tag, communicator) (buffer, count, datatype) 定义了消息缓冲, (destination, tag, communicator) 构成消息信封.

39 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) 消息信封

40 1 MPI 中的消息 MPI 的四个重要概念 : 消息数据类型 (message data types) 通信子 (communicators) 通信操作 (communication operations) 虚拟拓扑 (virtual topology)

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

42 1 MPI 中的消息 表 1 MPI 中预定义的数据类型 MPI(C 语言绑定 ) C MPI(Fortran 语言绑定 ) Fortran MPI_BYTE MPI_ BYTE MPI_CHAR signed char MPI_CHARACTER CHARACTER MPI_COMPLEX COMPLEX MPI_DOUBLE double MPI_DOUBLE_PRECISION DOUBLE_PRECISION MPI_FLOAT float MPI_REAL REAL MPI_INT int MPI_INTEGER INTEGER MPI_LOGICAL LOGICAL MPI_LONG long MPI_LONG_DOUBLE long double MPI_PACKED MPI_PACKED MPI_SHORT short MPI_UNSIGNED_CHAR unsigned char MPI_UNSIGNED unsigned int MPI_UNSIGNED_LONG unsigned long MPI_UNSIGNED_SHORT unsigned short

43 例 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); 例程 MPI_Pack_size malloc (BufferSize) for 循环 MPI_Pack (A+i*j, 1, MPI_DOUBLE, TempBuffe,BufferSize, &Position, comm); 说明 决定需要一个多大的临时缓冲区来存放 50 个 MPI_DOUBLE 数据项 为缓冲区 TempBuffer 动态分配内存 将数组 A 的 50 个偶序数元素打成一个包, 放在 TempBuffer 中 第一个参数是被打包的数组元素的地址. 第三个参数是被打包的数组元素的数据类型, position 用于跟踪已经有多少个数据项被打包. position 的最后值在接下来的 MPI_Send 中被用作消息计数.

44 例 3 在消息传递中发送一个混合数据类型 在下面的消息中, 假定每个双精度数有 8 字节长, 一个字符是 1 字节, 一个整型数是 4 字节. 序号要发送的消息消息的性质与定义方法 (1) 由数组 A 的所有元素组成的消息. A 有 100 个元素, 每个元素是一个双精度数. 这个消息由 100 项组成, 每项有一个 double 数据类型, 决定了每一项的大小是 8 字节. 第 i 项的起始地址是 A+8(i-1). (2) 由数组 A 的第 3 和第 4 项组成消息. 这个消息由两项 A[2] 和 A[3] 组成. 每项是一个 double 数据类型, 第一项始于 A+16, 第二项始于 A+24. (3) 由数组 A 的所有偶序数项组成的消息. 这个消息由 50 项 A[0],A[2],A[4],..., A[98] 组成. 每一项有一个 double 数据类型. 第 i 项的起始地址是 A+16(i-1). 由数组 A 的第 3 项, 后跟一个字符 c, 再跟一个整型数 k. (4) 这个消息由三个不同类型的数据组成. 假定它是一个数据结构 : struct{ double A[100]; char b,c; int j,k;} S 的一部分. 那么第一项 A[2] 的地址是 S+16, 第二项 c 的地址是 S+801, 第三项 k 的地址是 S+806. 国家高性能计算中心 ( 合肥 ) 这两个消息有两个性质 : 数据项的存放是连续的 ; 所有的数据项具有相同的数据类型. 这类消息可以方便地用三元组 (address, count, datatype) 来定义. 第 (1) 个消息可以用 (A, 100, MPI_DOUBLE) 来定义. 第 (2) 个消息可以用 (A+16,2,MPI_DOUBLE) 来定义. 第 (3) 个消息的性质 : 数据项没有放在一个连续的存储区中. 第 (4) 个消息的性质 : 数据不仅没有连续存放, 而且是混合数据类型. 上述简单的方法不能处理第 (3) 和第 (4) 个消息. MPI 引入导出数据类型 (derived data type ) 的概念, 允许定义可能是由混合数据类型 非连续存放的数据项组成的消息. 导出数据类型由用户的应用程序在运行时从基本的数据类型构造. MPI 提供了强大而全面的构造复杂数据类型的子例程.

45 例 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,...); MPI_Data_type 例程 MPI_Type_vector(50,1,2,MPI_DOUBLE,&E venelements) 说明 声明一个新的数据类型 EvenElements. 产生一个导出数据类型 EvenElements, 它由 50 个块组成. 每个块的组成是一个双精度数, 后跟一个 8 字节的间隔, 接在后面的是下一块. stride 是两个双精度数的大小, 即 16 字节. 8 字节的间隔用于跳过数组 A 的奇序数元素. MPI_Type_commit(&EvenElements) 这个新类型必须在被发送例程使用前交付使用. MPI_Send(A,1,EvenElements,destination,...) 注意 : EvenElements 的一个元素包含 A 的所有 50 个偶序数元素. 因此, MPI_Send 的 count 域值为 1.

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

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

48 1 MPI 中的消息 例 5 在一对进程间发送消息 考虑下列代码, 由进程 P 传送一个存放在数组 A 中的消息 M, 到进程 Q 的数组 B 中.

49 Process P: double A[ ]; send(a,32,q,tag); Process Q: double B[32]; recv(b,32,p,tag) A M B Process P (a) 只使用用户缓冲 Process Q A M Process T P B Process Q A M S B Process P Process Q (c) 使用了用户级的临时缓冲 T (b) 使用系统缓冲 S

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

51 2 MPI 中的消息信封 为什么要使用消息标签 (Tag)? 为了说明为什么要用标签, 我们先来看右面一段没有使用标签的代码 : 这段代码打算传送 A 的前 32 个字节进入 X, 传送 B 的前 16 个字节进入 Y. 但是, 如果消息 B 尽管后发送但先到达进程 Q, 就会被第一个 recv() 接收在 X 中. 使用标签可以避免这个错误. Process P: send(a,32,q) send(b,16,q) Process P: send(a,32,q,tag1) send(b,16,q,tag2) Process Q: recv(x, 32, P) recv(y, 16, P) Process Q: 未使用标签 使用了标签 recv (X, 32, P, tag1) recv (Y, 16, P, tag2)

52 例 6 在消息传递中使用标签 Process P: send (request1,32, Q) Process R: send (request2, 32, Q) 未使用标签 Process Q: while (true) { recv (received_request, 32, Any_Process); process received_request; } Process P: send(request1, 32, Q, tag1) 使用标签的另一个原因是可以简化对下列情形的处理. 假定有两个客户进程 P 和 R, 每个发送一个服务请求消息给服务进程 Q. 使用了标签 Process R: send(request2, 32, Q, tag2) Process Q: while (true){ recv(received_request, 32, Any_Process, Any_Tag, Status); if (Status.Tag==tag1) process received_request in one way; if (Status.Tag==tag2) process received_request in another way; }

53 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)

54 2 MPI 中的消息信封 例 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); parallel_fft(...); 含代码含代码 if (my_rank==0) MPI_Send(msg2, count1, MPI_INT,1,tag2,comm2);

55 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 的危险了.

56 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);

57 2 MPI 中的消息信封 MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld) 将创建一个新的通信子 MyWorld, 它是包含与原始的 MPI_COMM_WORLD 相同的 10 个进程的进程组, 但有不同的上下文. 表分裂一个通信子 MyWorld Rank in MyWorld Color Key Rank in SplitWorld(Color=0) Rank in SplitWorld(Color=1) Rank in SplitWorld(Color=2) 0 1 2

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

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

60 发送者进程总结如下 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) } 这两个域可以是 wildcard MPI_Any_source 和 MPI_Any_tag. 读出. 这个例程使用 Status 中的信息来决定给定数据类型 ( 在这里是 MPI_INT) 中的实际项数, 将这个数放在变量 C 中.

61 2 MPI 中的消息信封 例 9 消息传递中的状态 (Status) 字 当一个接收者能从不同进程接收不同大小和标签的信息时, 状态信息就很有用. 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; } }

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

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

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

65 4 点对点的通信 表 MPI 中不同的发送和接收操作 MPI Primitive Blocking Non-Blocking Standard Send MPI_Send MPI_Isend Synchronous Send MPI_ Ssend MPI_ Issend Buffered Send MPI_ Bsend MPI_ Ibsend Ready Send MPI_ Rsend MPI_ Irsend Receive MPI_Recv MPI_Irecv Completion Check MPI_Wait MPI_Test

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

67 4 点对点的通信 Receive X Xbuf 0 YBuf0 Send Y Y=Q(X) 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); }

68 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 的旧值.

69 5 群集通信 广播 (Broadcast) MPI_Bcast(Address, Count, Datatype, Root, Comm) 在下列 broadcast 操作中, 标号为 Root 的进程发送相同的消息给标记为 Comm 的通信子中的所有进程. 消息的内容如同点对点通信一样由三元组 (Address, Count, Datatype) 标识. 对 Root 进程来说, 这个三元组既定义了发送缓冲也定义了接收缓冲. 对其它进程来说, 这个三元组只定义了接收缓冲. processes data A0 broadcast (a) A0 A0 A0 A0 A0 A0

70 5 群集通信 播撒 (Scatter) MPI_Scatter (SendAddress,SendCount,SendDatatype, 聚集 (Gather) RecvAddress,RecvCount,RecvDatatype,Root,Comm) MPI_Gather (SendAddress,SendCount,SendDatatype, RecvAddress,RecvCount,RecvDatatype,Root,Comm)

71 5 群集通信 A0 A1 A2 A3 A4 A5 scatter A0 A1 gather A2 A3 A4 (b) A5 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) 标识.

72 5 群集通信 扩展的聚集和播撒操作 Allgather MPI_Allgather ( SendAddress, SendCount, SendDatatype, RecvAddress, RecvCount, RecvDatatype, Comm ) A0 B0 C0 allgather A0 A0 A0 B0 B0 B0 C0 D0 C0 D0 C0 D0 E0 E0 E0 F0 F0 F0 D0 E0 A0 A0 B0 B0 C0 D0 C0 D0 E0 E0 F0 F0 F0 (c) A0 B0 C0 D0 E0 F0

73 5 群集通信 全局交换 (Tatal Exchange) MPI_Alltoall(SendAddress, SendCount, SendDatatype, 每个进程发送一个消息给所有 n 个进程, 包括它自已. 这 n 个消息在它的发送缓冲中以标号的顺序有序地存放. 从另一个角度来看这个通信, 每个进程都从 n 个进程接收一个消息. 这 n 个消息以标号的顺序被连接起来, 存放在接收缓冲中. 注意, 全局交换等于由 n 个不同进程做的 n 次 Gather 操作. 因此, 不再需要 Root 参数. 所有对所有, 在一次全局交换中共有 n 2 个消息进行通信. RecvAddress, RecvCount, RecvDatatype, Comm) A0 B0 C0 D0 E0 F0 A1 B1 C1 D1 E1 F1 A2 A3 B2 B3 C2 C3 D2 D3 E2 E3 F2 F3 A4 B4 C4 D4 E4 F4 A5 B5 C5 D5 E5 D5 alltoall (d) A0 A1 A2 A3 A4 A5 B0 B1 B2 B3 B4 B5 C0 C1 C2 C3 C4 C5 D0 D1 D2 D3 D4 D5 E0 E1 E2 E3 E4 E5 F0 F1 F2 F3 F4 D5

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

75 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 操作

76 5 群集通信 路障 (Barrier) MPI_Barrier(Comm) 在路障操作中, 通信子 Comm 中的所有进程相互同步, 即, 它们相互等待, 直到所有进程都执行了他们各自的 MPI_Barrier 函数.

77 5 群集通信 表 MPI 中的群集通信 Type Routine Functionality Data movement MPI_Bcast 一对多播送相同的信息 MPI_Gather 多对一收集个人信息 MPI_Gatherv 通用的 MPI_Gather MPI_Allgather 全局收集操作 MPI_Allgatherv 通用的 MPI_Allgather MPI_Scatter 一对多播撒个人信息 MPI_Scatterv 通用的 MPI_Scatter MPI_Alltoall 多对多全交换个人信息 MPI_Alltoallv 通用的 MPI_Alltoall Aggregation MPI_Reduce 多对一归约 MPI_Allreduce 通用的 MPI_Reduce MPI_Reduce_scatter 通用的 MPI_Reduce MPI_Scan 多对多并行 prefix Synchronization MPI_Barrier 路障同步

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

79 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) 工具.

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

81 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 必须是一个空串, 允许运行时系统决定何地 如何启动该进程.

82 6 MPI 扩展 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)

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

84 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 )

85 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 )

86 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[];

87 { 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_W ORLD); if(my_rank==0) { /* Node 0 handles output */ printf("pi is approximately : %.16lf\n",pi); } MPI_Finalize();

88 7 例子 : 计算 Pi 的 MPI 程序 编译 : mpicc -o pi pi.c 运行 : mpirun -np 2 pi

89 并行虚拟机 (PVM) 1 并行虚拟机的构造 2 PVM 中的进程管理 3 PVM 中的通信 4 例子 : 计算 Pi 的 PVM 程序

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

91 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

92 1 并行虚拟机的构造 主要的 PVM 命令 表主要的 PVM 控制命令 命令 pvm>add apple pvm>delete apple pvm>conf pvm>spawn count 4 app pvm>jobs pvm>halt 含义将主机 apple 加入到虚拟机中从虚拟机中删除主机 apple 列出虚拟机的配置在虚拟机上启动 4 个任务运行 app 列出运行在虚拟机上的作业中止所有 PVM 进程, 关闭 PVM

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

94 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);

95 host H2(slave) host H1(master) host H3(new slave) task T( 用户进程 ) pvmd2( 系统进程 ) pvmd1( 系统进程 ) pvmd3( 系统进程 ) pvm_addhosts() Blocked dm_addhost() dm_htupd() dm_addhost() dm_startack() dm_htupdack() slave_config() dm_htupd() dm_htcommit() dm_addhostack() dm_htcommit() finished 图动态加入一个主机 H3

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

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

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

99 2 PVM 中的进程管理 选项符号 (Option Symbol) 表 pvm_spawn 中的 flag 参数 选项值 (Option Value) 含义 PvmTaskDefault 0 主机由 PVM 选择 PvmTaskHost 1 主机由某处定义 PvmTaskArch 2 体系结构由某处定义 PvmTaskDebug 4 在调试状态下启动进程 PvmTaskTrace 8 将生成 PVM 跟踪数据 PvmMppFront 16 在 MPP 前端启动进程 PvmHostCompl 32 使用 complement 主机集合

100 2 PVM 中的进程管理 表 PVM 进程管理函数 PVM 函数调用 tid=pvm_mytid(); tid=pvm_parent(); 含义 获取调用任务的任务标识号 获取父任务的任务标识号 info=pvm_exit(); 正在调用的任务退出 PVM, 继续作为 UNIX 进程运行. Numt=pvm_spawn(...); 派生一个 PVM 任务 info=pvm_kill(tid); 终止一个 PVM 任务 tstat=pvm_pstat(tid); 获取一个 PVM 任务的状态 info=pvm_tasks(...); 获取运行在虚拟机上的所有任务的信息 Mstat=pvm_mstat(host); 获取一个主机的状态 info=pvm_config(...); 获取整个虚拟机的配置信息

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

102 2 PVM 中的进程管理 表 PVM 组函数 PVM 函数调用 含义 inum=pvm_joingroup( world ); 调用任务加入 World 组并被分配一个成员 inum. info=pvm_lvgroup( world ); 调用任务离开 World 组 tid=pvm_gettid( world, inum); 从成员号中获取任务的标识号 inum=pvm_getinst( world, tid); 从任务的标识号获取成员号 gsize=pvm_gsize( world ); 获取组的大小 info=pvm_barrier( world, 10); 调用任务阻塞 ( 等待 ) 直到 World 的 10 个成 员调用了 pvm_barrier info=pvm_bcast( world, tag); 播送一个由标签标识的消息给所 World 的 有成员 info=pvm_reduce(...); 类似于 MPI 的 reduction

103 2 PVM 中的进程管理 S G H L 图 PVM 通用的任务标识符 TID 格式 表任务标识符的解释 S G H L 含义 任务标识符 不关心 Multicast 地址 本地 pvmd pvm 标识 1 1 Small negative number 错误代码

104 3 PVM 中的通信 PVM 有三种类型的通信 : pvmd 间通信 pvmd 与其任务间的通信 以及两个任务间的通信 task1 TCP task2 TCP TCP pvmd1 UDP pvmd2 图 通用的 PVM 中所用的通信协议

105 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)

106 4 例子 : 计算 π 的 PVM 程序 #define n 16 /* 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: ); else { scanf( %d, &N); pvm_initsend(pvmdataraw); pvm_pkint(&n, 1, 1); pvm_mcast(tids, n-1, 5); } 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();

107 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.

108 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);

109 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 个任务应在此同步 */

110 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;

111 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().

112 4 例子 : 计算 Pi 的 PVM 程序 编译 : pvmcc -o pi pi.c 运行 : $>pvmd d7 host_file& $>pvm pvm>span 4 pi pvm>halt

113 HPF 并行编程 1 高性能 Fortran(HPF) 简介 2 HPF 的数据并行机制 3 例子 : 高斯消去法的 HPF 程序

114 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 版基于 Fortran 年 11 月发布了 HPF 1.1 版 1997 年 1 月, 论坛发布了 HPF 2.0 基于 Fortran 95

115 1 高性能 Fortran(HPF) 简介 对 HPF 的批评主要有三个方面 : 认为 HPF 是一个太高层的语言, 不如 MPI 风格的语言适用 ; 认为 HPF 是一个太低层的语言, 通过改进语言编译技术和体系结构完全可以避开 HPF 风格的语言所要求的编译制导 ; 认为 HPF 尽管抽象层次适当, 但还要作一些扩充才能满足在某些将来的体系结构上处理某些应用的需要.

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

117 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): 用于匹配其它的编程方法, 支持混合语言编程 国家高性能计算中心 ( 合肥 )

118 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.

119 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}.

120 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 的子集.

121 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) 中.

122 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

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

124 2 HPF 的数据并行机制 一些重要的说明语句的例子 (1) 伪指令 PROCESSORS: 用于描述虚拟的处理机结构例 7!HPF$ PROCESSOR P4 (4) 注释 : 描述由 4 个处理机组成的虚结构!HPF$ PROCESSOR P22 (2, 2) 注释 : 描述两行两列共 4 个处理器组成的二维虚结构

125 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) 个元素分配到同一个处理器上.

126 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 行各元素所在的处理器上.

127 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 分成每块有 个元素组成的 4 个块, 分给 4 个处理器.

128 2 HPF 的数据并行机制!HPF$ DISTRIBUTE B (BLOCK, BLOCK) ONTO P22 注释 : 表示数组 B 在行列两个方向被分成 4 个块, 分给 4 个处理器.!HPF$ DISTRIBUTE B (*, BLOCK) ONTO P4 注释 : 表示数组 B 在列方向分成 4 个块, 行方向不分布

129 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) 等等.

130 2 HPF 的数据并行机制 (4) 一个数据映射的 HPF 程序段例 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

131 A(1) A(2) A(3)... A(100) B(1) B(2)... B(99) B(100) C(1) C(2) C(3)... C(101) ALIGN Logical Mapping A(1) A(2) A(3)... A(100) B(1) B(2)... B(99) B(100) DISTRIBUTE C(1) C(2) C(3)... C(101) Physical Mapping 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 N3 N2 N4 A Paragon Mesh N1, N2 N3, N4 A Uniprocessor N1, N2 N3, N4... High Performance Switch An IBM SP2

132 2 HPF 的数据并行机制 例 13!HPF$ PROCESSOR N(4, 5) 注释 : 定义 20 个节点组成的 4 5 网格.!HPF$ PROCESSOR N(4,5,6) 注释 : 定义 120 个节点组成的 网格.

133 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

134 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

135 3 高斯消去法的 HPF 程序 DISTRIBUTED 命令指出 A 的第一维应是成块分布. A 的第二维中的 * 号说明第二维已被折叠, 意味着部分数组 A(I,1:n) 被映射到同一结点. 假设有四个虚拟结点 N 1, N 2,N 3, N 4, 且 N 可为 4 整除. 那么, 数据分布便为如下 : N 1 : A(1:n/4,1:n), b(1:n/4), Temp(1:n/4), X(1:n) N 2 : 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) N 3 : A(2*n/4+1:3*n/4,1:n), b(2*n/4+1:n), Temp(2*n/4:3*n/4) N 4 : A(3*n/4+1:n,1:n), b(3*n/4+1:n), Temp(3*n/4+1:n), X(1:n)

136 3 高斯消去法的 HPF 程序 在四个结点中的数据分布 结点 1 A(1:8;1:33), X(1:8) 结点 2 A(9:16,1:33), X(9:16) 结点 3 A(17:24,1:33),X(17:24) 结点 4 A(25:32,1:33),X(25:32)