并行计算概述,MPI并行算法概述以及MPI并行程序设计基础。

献良发布于2019/01/26

注脚

展开查看详情

1.MPI 并行编程入门

2.主要内容 并行计算概述 MPI 并行算法概述 MPI 并行程序设计基础

3.并行计算机 - 并行机介绍

4.

5.Will this program still work? #include < stdio.h > int main(void) {   printf ("Hello, world!

6.并行计算机 - 并行机 结构 并行计算机 结构模型 根据指令流和数据流的不同,通常把计算机系统分为: 单指令单数据流 (SISD) 单指令多数据流 (SIMD) 多指令单数据流 (MISD) 多指令多数据流 (MIMD) 并行计算机系统多大部分为 MIMD 系统,包括: 对 称多处理机( SMP ) 分 布式共享存储多处理机( DSM ) 大规模并行处理机( MPP ) 机群( Cluster ) S M 指令个数 I 数据个数 D M S SIMD MISD SISD MIMD

7.多个 CPU 连接于统一的内存总线 内存地址统一编址,单一操作系统映像 可扩展性较差,一般 CPU 个数少于 32 个 目前商用服务器多采用这种架构 Chipset Memory NIC System CPUs CPUs CPUs CPUs I/O Bus Memory Bus >4 CPUs may require switching Local Area Network SMP- Symmetric MultiProcessing

8.物理上分布存储、所有内存模块统一编址 非一致内存访问( NUMA )模式 基于 Cache 的数据一致性,又称 CC-NUMA 节点数可扩展到几百个,小型机多为此类架构 Local Area Network ... System ... NIC Memory CPUs Chipset I/O Bus Memory Bus I/O NIC Memory CPUs Chipset I/O Bus Memory Bus I/O NIC Memory CPUs Chipset I/O Bus Memory Bus I/O NUMA Link NUMA Link DSM- Distributed Shared Memory

9.节点个数可达成百上千个 节点类型可以是 DM 、 SMP 、 DSM 节点之间采用专用高速互连设备 排列在 Top500 前面的多数系统属于这种类型 ... ... 专用高速互联 NIC Memory I/O Bus System 局部总线 / 互连网络 CPUs NIC Memory I/O Bus System CPUs 局部总线 / 互连网络 NIC Memory I/O Bus System CPUs 局部总线 / 互连网络 MPP- Massively Parallel Processors

10.独立的节点、商品化网络连接 开放的硬件设备、操作系统、应用编程接口 节点数可达几百个,性能已接近超级计算机系统 近年来发展很快,已广泛应用到高性能科学计算领域 ... ... System Area Network Local Area Network LAN Memory I/O Bus Memory Bus System Chipset SAN CPUs LAN Memory I/O Bus Memory Bus System Chipset SAN CPUs LAN Memory I/O Bus Memory Bus System Chipset SAN CPUs Cluster

11.各种架构对比 SMP 瓶颈在访存带宽,限制了可扩展性(性能会严重下降),通过增大 Cache 来缓解,又有数据一致性的问题。 DSM 具有较好的可扩展性,且具有与 SMP 相同的编程模式。共享存储的机器可以运行各种编程模式的程序,包括串行程序、共享存储并行程序和消息传递并行程序。 共享存储的机器首先可以看作是一个内存扩充了的串行机器,可以运行数据量极大的串行程序,如大数据量的数据库应用。利用多个处理器的并行处理性能,自动并行(靠编译器)作用有限,需要其他编程方式的应用,如 OpenMP 。

12.各种架构对比(续) 分布式存储体系结构 无共享的机器, MPP 和 Cluster ,具有最好的可扩展性,采用消息传递编程,可编程性不如 OpenMP ,也可以通过 DSM 软件的方式来模拟实现共享存储(其实还是通过消息传递,只不过对上层透明),性能受到影响,但可以运行 OpenMP 应用程序。 MPP/PVP 在构造大规模系统,应用饱和性能方面具有优势,资金充足的依然会选择; Cluster 由于无可比拟的性价比优势占据主流位置。 系统的高可用性 更高的计算能力 良好的可扩展性 更高的性价比

13.各种架构对比(续) 分布式存储体系结构 无共享的机器, MPP 和 Cluster ,具有最好的可扩展性,采用消息传递编程,可编程性不如 OpenMP ,也可以通过 DSM 软件的方式来模拟实现共享存储(其实还是通过消息传递,只不过对上层透明),性能受到影响,但可以运行 OpenMP 应用程序。 MPP/PVP 在构造大规模系统,应用饱和性能方面具有优势,资金充足的依然会选择; Cluster 由于无可比拟的性价比优势占据主流位置。 系统的高可用性 更高的计算能力 良好的可扩展性 更高的性价比

14.并行算法 并行计算的相关基本概念 并行化分解及通信方法 并行编程风范 并行算法 设计 基本原则和分类 数值计算并行算法

15.并行算法 并行算法设计:将一个任务分解为多个可同时执行的子任务,这些子任务分别运行在不同的处理器上,通过相互之间的数据交换完成同一个任务。 与并行计算有关的概念: 粒度 :两次并行或交互操作 之间所 执行的计算 负载 并行度:同时执行的分进程数 加速比: 效率: 性能: 并行度与并行粒度大小常互为倒数 : 增大 粒度会减小并行度 . 增加并行度会增加系统 ( 同步 ) 开销

16.并行程序设计 划分 按任务划分 通信 确定通信 组合 合理组织各任务 映射 按处理器来设计组合 起来的任务

17.原则 : 使系统大部分时间忙于计算 , 而不是闲置或忙于交互 ; 同时不牺牲并行性 ( 度 ). 划分 : 切割数据和工作负载 分配: 将划分好的数据和工作负载映射到计算结点 ( 处理器 ) 上 分配 方式: 显式分配 : 由用户指定数据和负载如何加载 隐式分配:由编译器和运行时支持系统决定 就近分配原则: 进程所需的数据靠近使用它的进程代码 并行化的基本思想 — 任务划分

18.区域分解法: 分解被执行的数据 非重叠的区域分解,这种分解将离散化后的方程化成一些独立的小规模问题和一个与每个小问题关联的全局问题,此种分解给出的方法是子结构方法。 带重叠的区域分解 并行化分解方法

19.功能分解法: 功能分解是将不同功能组成的问题,按照其功能进行分解的一种手段,其目的是逐一解决不同功能的问题,从而获得整个问题的解。 例如:使用 Newton 法求解非线性方程 F(x) = 0 在求解方程的过程中,需要用到函数值和导数值。因此,如果一部分处理机负责计算函数值,另一部分处理机负责计算导数值,就可以得到一种并行计算方法。 这时候计算是按照功能进行分配的,也既是所谓的功能分解。 并行化分解方法

20.流水线技术: 流水线技术是并行计算中一个非常有效的、常用的手段,在并行计算中起着非常重要的作用。 以求解一簇递推问题为例加以说明: 上述计算中,沿 j 方向的计算是互相独立的,而沿 i 方向的计算则存在着向前依赖关系 ( 递推关系 ) ,无法独立进行。 不失一般性,我们假设数据划分仅沿 i 方向进行,即假设在有 3 个处理器的分布式系统上, ai,j 被分成 3 段 , 如图所示,相同颜色的部分是可以并行计算的。 并行化分解方法 流水线计算示意图

21.分而治之方法: 以一个简单的求和问题为例,说明什么是分而治之方法。假设在 q = 2*2*2 个处理机上计算: 可以将计算依次分解为两个小的求和问题,用下图简单的描述(图中给出的是处理机号)。在图中,从上至下是分解的过程,从下至上是求部分和的过程。这就是有分有治的一个简单过程,也既是一种分而治之方法。 并行化分解方法 分而治之计算示意图

22.并行化的基石 — 通信 通信方式 共享变量 父进程传给子进程 ( 参数传递方式 ) 消息传递 同步: 导致进程间相互等待或继续执行的 操作 原子同步 控制同步 ( 路障 , 临界区 ) 数据同步 ( 锁 , 条件临界区 , 监控程序 , 事件 ) 聚集: 用一串超步将各分进程计算所得的部分结果合并为一个完整的结果 , 每个超步包含一个短的计算和一个简单的通信或 / 和同步 . 聚集方式 : 归约 扫描

23.通信 模式 一对一 : 点到点 (point to point) 一对多 : 广播 (broadcast), 播撒 (scatter) 多对一 : 收集 (gather), 归约 (reduce) 多对多 : 全交换 ( Tatal Exchange), 扫描 (scan) , 置换 / 移位 (permutation/shift)

24.五种并行编程风范 相并行( Phase Parallel ) 主从并行( Master-Slave Parallel ) 分 治并行( Divide and Conquer Parallel ) 流水线并行( Pipeline Parallel ) 工作池并行( Work Pool Parallel )

25.相并行( Phase Parallel ) 一组超级步(相) 步内各自计算 步间通信、同步 BSP 方便差错和性能分析 计算和通信不能重叠 C C C Synchronous Interaction ...... C C C Synchronous Interaction ......

26.主-从并行( Master-Slave Parallel ) 主进程:串行、协调任务 子进程:计算子任务 划分设计技 术 与相并行结合 主进程易成为瓶颈 Master Slave Slave Slave

27.分治并行( Divide and Conquer Parallel ) 父进程把负载分割并指派给子进程 递归 重点在于归并 分治设计技 术 难以负载平衡

28.流水线并行( Pipeline Parallel ) 一组进程 流水线作业 流水线设计技 术 P1 P2 P3

29.工作池并行( Work Pool Parallel ) 初始状态:一件工作 进程从池中取任务执行 可产生新任务放回池中 直至任务池为空 易与负载平衡 临界区问题(尤其消息传递) Work Pool P1 P2 P3

30.并行算法设计基本原则 与体系结构相结合 —— 线性结构,二维网络结构 …… 具有可扩展性 —— 并行算法是否随处理机个数增加而能够线性或近似线性的加速 粗粒度 —— 通常情况,粒度越大越好 减少通信 —— 减少通信量和通信次数 优化性能 —— 单机计算效率和并行效率 并行算法

31.并行算法分类 按运算的基本对象 数值并行算法 非数值并行算法 按进程间的依赖关系 同步并行算法 异步并行算法 纯并行算法 按并行计算任务的大小 粗粒度并行算法 细粒度并行算法 并行算法

32.数值计算是指基于代数关系运算的计算问题 如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的方法称为数值算法( Numerical Algorithm ) 科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题 非数值计算是指基于比较关系运算 诸如排序、选择、搜索、匹配等符号处理,相应的算法也称为非数值算法( Non-numerical Algorithm ) 非数值计算在符号类信息处理中获得广泛应用,如数据库领域的计算问题,海量数据挖掘等 近年来广泛关注的生物信息学主要也是非数值计算 并行算法

33.矩阵并行计算 行列分块算法 行行分块算法 列行分块算法 列列分块算法 Cannon 算法 线性方程组并行求解 并行 LU 分解算法 三角方程组的并行分解算法 对称正定线性方程组并行解法 代数特征值问题并行解法 迭代算法并行化 数值计算并行算法

34.矩阵并行计算 矩阵存储方式 —— 卷帘式 数值计算并行算法

35.串行矩阵乘法( i-j-k 形式) 行列分块并行算法 数值计算并行算法

36.行列分块算法示意图 数值计算并行算法

37.线性方程组的并行求解 线性方程组的定义和符号 a 1,1 x 1 + a 1,2 x 2 + … + a 1,n x n = b 1 a 2,1 x 1 + a 2,1 x 2 + … + a 2,n x n = b 2 , 记为 AX=b a n,1 x 1 + a n,1 x 2 + … + a n,n x n = b n 数值计算并行算法

38.线性方程组的 LU 分解算法 第一步: LU 分解 第二步:解三角方程组 数值计算并行算法

39.数值计算并行算法 分块矩阵在处理器阵列的数据分布情况 随机生成的稠密矩阵 被分成 的块,循环分布在 的二维处理器阵列上。

40.分块矩阵的 LU 分解过程示意 数值计算并行算法

41.分块矩阵的 LU 分解过程示意 数值计算并行算法

42.MPI 简介 MPI 的核心函数 MPI 的启动和结束 点对点通信 非阻塞通信 集合通信 MPI 的四种通信模式 MPI 并行程序的两种基本模式 MPI 并行程序设计基础

43.什么是 MPI? MPI(Message Passing Interface ) MPI 是一个库,而不是一门语言; MPI 是一种消息传递编程模型 ,并成为这种编程模型的代表和事实上的标准; MPI 是一种标准或规范的代表 ,而不特指某一个对它的具体实现; 目标: 是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准. MPI 提供 C/C++ 和 Fortran 语言的绑定

44. MPI 的实现 MPICH: 最重要的 MPI 实现 ( www-unix.mcs.anl.gov/mpi/ mpich ),与 MPI-1 规范同步发展的版本,支持部分 MPI-2 的特征如动态生成进程等。 CHIMP: EPCC(Edinburgh Parallel Computing Center) 开发。 (ftp://ftp.epcc.ed.ac.uk/pub/packages/chimp/release 下载 ) LAM(Local Area Multicomputer): Ohio State University 开发。 (http://www.lam-mpi.org/download/ 下载 )

45.MPI 的编译与运行 MPI 的编译: –mpif77 –o mpi_progmpi_prog.f –mpicc–o mpi_progmpi_proc.c –mpif90 –o mpi_progmpi_prof.f90 –mpiCC–o mpi_progmpi_prof.C MPI 的运行: mpirun –machinefile filename –np N <program name>

46.#include <stdio.h> #include “mpi.h” int main (int argc, char* argv[]) { int numProc, myRank; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &myRank); MPI_Comm_size (MPI_COMM_WORLD, &numProc); printf (“Hello. Process %d of %d here.

47.MPI 程序的运行 Execute on node1: mpirun –np 4 mpi_prog 1 Check the MPICH machine file: node1 node2 node3 node4 node5 node6 2 node1 mpi_prog (rank 0) node2 mpi_prog (rank 1) node3 mpi_prog (rank 2) node4 mpi_prog (rank 3) 3

48.MPI 程序的一般结构 BACK

49.MPI 的核心函数 MPI 的初始化和结束 MPI_Init , MPI_Finalize MPI_Comm_world MPI_Comm_size , MPI_Comm_rank 点到点通信 MPI_Send , MPI_Recv 非阻塞通信 MPI_Isend , MPI_Irecv , MPI_Wait 集合通信 MPI_Bcast , MPI_Reduce MPI 的四种通信模式

50.MPI 初始化: MPI_Init ( & argc , & argv ) MPI 的初始化例行函数,用于初始化 MPI 运行环境  每一个 MPI 进程调用的第一个 MPI 函数都是 MPI_Init 。该函数指示系统完成所有的初始化工作,以备对后续 MPI 库的调用进行处理。 MPI 结束: MPI_Finalize () 结束 MPI 执行环境。该函数一旦被应用程序调用时,就不能调用 MPI 的其它例行函数(包括 MPI_Init ),用户必须保证在进程调用 MPI_Finalize 之前把与完成进程有关的所有通信结束。 MPI 的初始化和结束

51.MPI_Init 建立通信域“ MPI_COMM_WORLD ” 通信域函数

52.确定通信域中的进程数量 MPI_Comm_size(MPI_Comm comm, int *size) 进程通过调用函数 MPI_Comm_size 来确定一个通信域中的进程总数。 确定进程的标识符 MPI_Comm_rank(MPI_Comm comm, int *rank) 当 MPI 初始化后,每一个活动进程变成了一个叫做 MPI_COMM_WORLD 的通信域中的成员。通信域是一个不透明的对象,提供了在进程之间传递消息的环境。 在一个通信域内的进程是有序的。在一个有 p 个进程的通信域中,每一个进程有一个唯一的序号( ID 号),取值为 0~p -1。 进程可以通过调用函数 MPI_Comm_rank 来确定它在通信域中的序号。 通信域函数

53.MPI 进程通信

54.MPI 进程通信 点到点通信 需要确认:

55.点到点通信

56.点到点通信

57.点到点通信

58.点到点通信

59.点到点通信

60.点到点通信

61.点到点通信

62.点到点通信

63.消息发送函数 MPI_Send ( buf,count,datatype,dest,tag,comm ) MPI_Send 将发送缓冲区中的 count 个 datatype 数据类型的数据发送到目的进程,目的进程在通信域中的标识号是 dest , 本次发送的消息标志是 tag, 使用这一标志,就可以把本次发送的消息和本进程向同一目的进程发送的其他消息区别开。 点到点通信 消息接收函数 MPI_Recv ( buf,count,datatype,source,tag,comm,status ) MPI_RECV 从指定的进程 source 接收消息,并且该消息的数据类型和消息标识和本接收进程的 datatype 和 tag 相一致,接收到的消息所包含的数据元素的个数最多不能超过 count 。

64.非阻塞通信 消息传送机制 阻塞方式: 它必须等到消息从本地送出之后才可以执行后续的语句 保证了缓冲区等资源的可再用性

65.非阻塞方式: 它不须等到消息从本地送出就可以执行后续的语句 但非阻塞调用的返回并不保证资源的可再用性 非阻塞通信主要用于 计算和通信的重叠 ,从而提高整个程序执行的效率。 非阻塞通信

66.阻塞与非阻塞调用的对比 非阻塞通信

67.非阻塞消息发送函数: MPI_Isend ( buf , count, datatype , dest , tag, comm , request) 参数说明: IN buf 发送缓冲区的起始地址 IN count 发送数据的个数 IN datatype 发送数据的数据类型 IN dest 目的进程号 IN tag 消息标志 IN comm 通信域 OUT request 返回的非阻塞通信(状况的)对象 MPI_ISEND 的功能是启动一个(标准的)非阻塞发送操作它调用后立即返回, MPI_ISEND 的调用返回并不意味着消息已经成功发送,它只表示该消息可以被发送。 非阻塞通信

68.非阻塞消息接收函数: MPI_Irecv ( buf , count, datatype , dest , tag, comm , request) 参数说明: OUT buf 接收缓冲区的起始地址 IN count 接收数据的最大个数 IN datatype 每个数据的数据类型 IN source 源进程标识 IN tag 消息标志 IN comm 通信域 OUT request 非阻塞通信 (状况的)对象 MPI_IRECV 的功能是启动一个(标准的)非阻塞接收操作,它调用后立即返回。 MPI_IRECV 调用的返回并不意味着已经接收到了相应的消息,它只表示符合要求的消息可以被接收。 非阻塞通信

69.非阻塞通信的完成 对于非阻塞通信调用的返回并不意味着通信的完成,需要专门的通信语句来完成或检查该非阻塞通信。 完成调用结束后,可以保证该非阻塞通信已正确完成。 MPI_WAIT( request,status ) 等到与该非阻塞通信对象相应的非阻塞通信完成后才返回,同时释放该阻塞通信对象。 MPI_TEST( request,flag,status ) 它的返回不一定等到与非阻塞通信对象相联系的非阻塞通信的结束。 若调用时该阻塞通信已经结束,则与 MPI_WAIT 效果相同,完成标志 flag=true 若调用时该阻塞通信还没完成,可以返回,但完成标志 flag=false 非阻塞通信

70.集合通信 集合通信是包含在通信因子中的所有进程都参加操作 集合通信一般实现三个功能 通信: 组内数据的传输 同步: 组内所有进程在特定的地点在执行进度上取得一致 计算: 对给定的数据完成一定的操作 集合操作的三种类型: 通信:广播 (broadcast) 、分散 (scatter) 、收集 (gather) 、全互换 ( alltoall ) 等 同步 (barrier) :集合中所有进程都到达后,每个进程再接着运行 规约 (reduction) :集合中的其中一个进程收集所有进程的数据并计算(如:求最大值、求最小值、加、乘等)

71.集合通信的通信功能 一对多通信 广播 MPI_Bcast() 散发 MPI_Scatter() 多对一通信 收集 MPI_Gather() 多对多通信 组收集 MPI_Allgather() 全互换 MPI_Alltoall()

72.组通信的同步功能 MPI_Barrier(MPI_Comm , comm) 在组中建立一个同步栅栏 当每个进程都到达 MPI_Barrier 调用后,程序才接着往下执行

73.集合通信的计算功能 归约操作 MPI_Reduce() ,就是接收缓冲区中数据的改变,而这是直接与各个进程发送缓冲区中的数据密切相关的。 归约、组归约、归约并散发、扫描及用户自定义归约操作等 MPI 预定义的归约操作有:求最大值、最小值、求和、求积、逻辑与、逻辑或等

74.例 2 :并行 PI 程序 π 的并行求解算法: 由三角函数和积分公式可知: 假设将区间 [0 , 1] 分成 n 等份,记 ,则采 用梯形积分公式计算上式积分如下: 由极限的定义,可以将 作为计算 π 的近似值。 即取 ,这里

75.算法的几何意义: 设计求 π 值并行算法的关键是构造一个合适的函数 f ( x) , 使得它计算起来既简便,误差又小。 例 2 :并行 PI 程序

76.例 2 :并行 PI 程序 #include "mpi.h" #include <stdio.h> #include <math.h> double f(double); double f(double x) /* 定义函数 f(x) */ { return (4.0 / (1.0 + x*x)); } int main(int argc,char *argv[]) { int done = 0, n, myid, numprocs, i; double PI25DT = 3.141592653589793238462643; /* 准确的 π 值* / double mypi, pi, h, sum, x; double startwtime = 0.0, endwtime; int namelen; char processor_name[MPI_MAX_PROCESSOR_NAME];

77.MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); /* 参加运算进程数* / MPI_Comm_rank(MPI_COMM_WORLD,&myid); /* 当前进程标识号* / MPI_Get_processor_name(processor_name,&namelen); /* 本进程机器名字* / fprintf(stdout,"Process %d of %d on %s

78.for (i = myid + 1; i <= n; i += numprocs) /* 每一个进程计算一部分矩形的面积,若进程总数 numprocs 为 4 ,将 0-1 区间划分为 100 个矩形,则各个进程分别计算矩形块: 0 进程 1 5 9 13 ... 97 1 进程 2 6 10 14 ... 98 2 进程 3 7 11 15 ... 99 3 进程 4 8 12 16 ... 100*/ { x = h * ((double)i - 0.5); sum += f(x); } mypi = h * sum; /* 各个进程并行计算得到的部分和* / MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,MPI_COMM_WORLD); /* 将部分和累加得到所有矩形的面积该面积和即为近似 π 值* / 例 2 :并行 PI 程序

79.例 2 :并行 PI 程序 if (myid == 0) /* 执行累加的 0 号进程将近似值打印出来* / { printf("pi is approximately %.16f, Error is %.16f

80.MPI 的四种通信模式 标准通信模式( standard mode ) MPI_SEND MPI_RECV 是否对发送的数据进行缓存是由 MPI 自身决定的,而不是由并行程序员来控制。也就是说,没准是否进行缓存。 缓存通信模式( buffered-mode ) MPI_BSEND 使用缓冲区发送消息 , 只要缓冲区足够大 , 而不管接收进程是否开始接收它都将立即返回 , 也就是说 , 在发送消息时是不需要等待的。 消息发送能否进行及能否正确返回不依赖于接收进程,完全依赖于是否有足够的通信缓冲区可用。 同步通信模式( synchronous-mode ) MPI_SSEND 它可以在没有接收信号时就开始发送 , 但要等到接收完成之后才能结束通信操作 , 好处是无需用户自己申请缓冲区 . 就绪通信模式( ready-mode ) MPI_RSEND 只当已经有接收信号时才开始发送消息 , 否则将出现错误 .

81.MPI 预定义数据类型 MPI 预定义类型与 C 数据类型对应关系 BACK

82.MPI 并行程序的两种基本模式 两种最基本的并行程序设计模式: 对等模式: 各个部分地位相同,功能和代码基本一致,只不过是处理的数据或对象不同,也容易用同样的程序来实现。( 典型应用如 Jacobi 迭代) 主从模式: 具有主进程和从进程,主进程接收从进程的处理结果,并进行汇总处理。(典型应用如矩阵向量乘法)

83.对等模式 — 并行 jacobi 程序 问题描述 ——Jacobi 迭代 Jacobi 迭代是一种比较常见的迭代方法,简单的说, Jacobi 迭代得到的新值是原来旧值点相邻数值点的平均。 Jacobi 迭代的局部性很好,可以取得很高的并行性。将参加迭代的数据按块分割后,各块之间除了相邻的元素需要通信外,在各块的内部可以完全独立的并行计算。

84.串行表示的 Jacobi 迭代 …… REAL A(N+1,N+1),B(N+1,N+1) …… DO K=1,STEP DO J=2,N DO I=2,N B(I,J)=0.25*(A(I-1,J)+A(I+1,J)+A(I,J+1)+A(I,J-1)) END DO END DO DO J=2,N DO I=2,N A(I,J)=B(I,J) END DO END DO END DO 对等模式 — 并行 jacobi 程序

85.为了并行求解,这里将参加迭代的数据按列进行分割,假设有4个进程同时并行计算,数据的分割结果如图: 边界点新值的计算需要相邻边界其他块的数据,因此在每一个数据块的两侧各增加1列 进程 0 进程 1 进程 2 进程 3 按列划分 对等模式 — 并行 jacobi 程序

86.对等模式 — 并行 jacobi 程序 假设需要迭代的数据是 M*M 的二维数组 A(M,M), 令 M=4*N, 按上图进行数据划分,则分布在 4 个不同进程上的数据分别是: 进程 0 : A(M,1:N); 进程 1 : A(M,N+1:2*N); 进程 2 : A(M,2*N+1:3*N); 进程 3 : A(M,3*N+1:4*N). 由于在迭代过程中,边界点新值的计算需要相邻边界其他块的数据,因此在每一个数据块的两侧各增加 1 列的数据空间,用于存放从相邻数据块通信得到的数据。每个数据块的大小就从 M*N 扩大到 M*(N+2) 。 计算和通信过程是这样的:首先对数组赋初值,边界赋为 8 ,内部为 0 。然后开始迭代,迭代之前,每个进程都需要从相邻的进程得到数据块,同时也向相邻的进程提供数据块

87.进程0 进程1 进程2 进程3 发送 发送 发送 发送 发送 发送 接收 接收 接收 接收 接收 接收 对等模式 — 并行 jacobi 程序

88.主从模式 — 矩阵向量乘积 对于矩阵 C=A*B ,主进程将向量 B 广播给所有的从进程,然后将矩阵 A 的各行依次发送给从进程。 从进程计算一行和 B 相乘的结果然后将结果发送给主进程。主进程循环向各个从进程发送一行的数据直到将 A 各行的数据发送完毕。 一旦主进程将 A 的各行发送完毕则每收到一个结果就向相应的从进程发送结束标志,从进程接收到结束标志后退出执行主进程收集完所有的结果后也结束。 从进程 主进程 发送矩阵 A 的各行数据 回收各行与 B 相乘的结果 计 算 计 算 计 算 计 算 送回结果

89.谢 谢!