并行算法实践 上篇 并行程序设计导论

并行算法实践 上篇 并行程序设计导论 单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法 并行算法实践 上篇 并行程序设计导论 单元I 并行程序设计基础 单元II 并行程序编程指南 单元III 并行程序开发方法 国家高性能计算中心（合肥） 2018/12/2

单元I 并行程序设计基础 第一章 并行计算机系统与结构模型 第二章 PC机群的搭建 第三章 并行程序设计简介 国家高性能计算中心（合肥） 2018/12/2

第三章 并行程序设计简介 3.1 并行程序开发方法 3.2 并行程序设计模型 3.3 并行编程语言和环境概述 3.1.1 并行层次与代码粒度 3.1.2 并行程序开发策略 3.1.3 并行编程模式 3.1.4 并行应用编程过程 3.2 并行程序设计模型 3.2.1 计算π样本程序 3.2.2 数据并行模型 3.2.3 消息传递模型 3.2.4 共享变量模型 3.3 并行编程语言和环境概述 3.3.1 早期并行编程语言 3.3.2 近代并行编程语言与环境 3.3.3 并行说明性语言环境 3.4 循环程序并行化的一般方法 3.4.1 数据相关分析 3.4.2 .数据划分与处理器指派 3.4.3 循环重构 国家高性能计算中心（合肥） 2018/12/2

并行层次与代码粒度 国家高性能计算中心（合肥） 2018/12/2

并行层次 粒度（指令数） 并行实施 编程支持 甚细粒度指令级并行 几十条，如多指令发射、内存交叉存取 硬件处理器 细粒度数据级并行 几百条，如循环指令块 编译器 共享变量 中粒度控制级并行 几千条，如过程、函数 程序员（编译器） 共享变量、消息传递 粗粒度任务级并行 数万条，如独立的作业任务 操作系统 消息传递 国家高性能计算中心（合肥） 2018/12/2

并行程序开发策略 国家高性能计算中心（合肥） 2018/12/2

并行编程模式 主-从式（Master-Slave） 单程序多数据流（Single Program Multiple Data ） 数据流水线（Data Pipelining） 分治策略（Divide and Conquer） 国家高性能计算中心（合肥） 2018/12/2

主-从式（Master-Slave） 其基本思想是将一个待求解的任务分成一个主任务（主进程）和一些从任务（子进程）。主进程负责将任务的分解、派发和收集诸子任务的求解结果并最后汇总得到问题的最终解。诸子进程接收主进程发来的消息；并行进行各自计算；向主进程发回各自的计算结果。 国家高性能计算中心（合肥） 2018/12/2

单程序多数据流（SPMD） 亦称为单控制流多数据流模式，其基本思想是并行运行的进程均执行相同的代码段，但却操作在各自不同的数据上。这种编程模式首先需要将应用程序的数据预先分配给各个计算进程（处理器）；然后诸计算进程并行的完成各自的计算任务，包括计算过程中各进程间的数据交换（施行通信同步）；最后才将各计算结果汇集起来。 国家高性能计算中心（合肥） 2018/12/2

数据流水线（Data Pipelining） 其基本思想是将各计算进程组织成一条流水线，每个进程执行一个特定的计算任务，相应于流水线的一个阶段。一个计算任务在功能上划分成一些子任务（进程），这些子任务完成某种特定功能的计算工作，而且一旦前一个子任务完成，后继的子任务就可立即开始。在整个计算过程中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，且通信可以完全异步地进行。 国家高性能计算中心（合肥） 2018/12/2

分治策略（Divide and Conquer） 其基本思想是将一个大而复杂的问题分解成若干个特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，则可反复使用分治策略，直至很容易求解诸子问题为止。问题求解可分为三步：①将输入分解成若干个规模近于相等的子问题；②同时递归地求解诸子问题；③归并各子问题的解成为原问题的解。 国家高性能计算中心（合肥） 2018/12/2

并行应用编程过程－PCAM 设计并行应用的四个阶段 划分：分解成小的任务，开拓并发性； 通信：确定诸任务间的数据交换，监测划分的合理性； 划分(Partitioning) 通信(Communication) 组合(Agglomeration) 映射(Mapping) 划分：分解成小的任务，开拓并发性； 通信：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高并行性能。 国家高性能计算中心（合肥） 2018/12/2

PCAM设计过程 国家高性能计算中心（合肥） 2018/12/2

划分方法描述 充分开拓算法的并发性和可扩放性； 先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)； 使数据集和计算集互不相交； 划分阶段忽略处理器数目和目标机器的体系结构； 能分为两类划分： 域分解(Domain Decomposition) 功能分解(Functional Decomposition) 国家高性能计算中心（合肥） 2018/12/2

域分解 划分的对象是数据，可以是程序中的输入数据、中间处理数据和输出数据； 将数据分解成大致相等的小数据片； 划分时考虑数据上的相应操作； 如果一个任务需要别的任务中的数据，则会产生任务间的通信； 国家高性能计算中心（合肥） 2018/12/2

域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法： 国家高性能计算中心（合肥） 2018/12/2

域分解 不规则区域的分解示例： 国家高性能计算中心（合肥） 2018/12/2

功能分解 划分的对象是计算（亦称为任务分解或计算划分），将计算划分为不同的任务，其出发点不同于域分解； 划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着存在大量的通信开销，要重新进行域分解和功能分解； 功能分解是一种更深层次的分解。 国家高性能计算中心（合肥） 2018/12/2

功能分解 示例1：搜索树 示例2：气候模型 国家高性能计算中心（合肥） 2018/12/2

划分判据 划分是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否合理？ 国家高性能计算中心（合肥） 2018/12/2

通信分析 通信是PCAM设计过程的重要阶段； 划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信； 功能分解确定了诸任务之间的数据流； 诸任务是并发执行的，通信则限制了这种并发性； 国家高性能计算中心（合肥） 2018/12/2

四种通信模式 局部/全局通信 结构化/非结构化通信 静态/动态通信 同步/异步通信 国家高性能计算中心（合肥） 2018/12/2

局部通信 通信限制在一个邻域内 国家高性能计算中心（合肥） 2018/12/2

全局通信 通信非局部的 例如： All to All Master-Worker 1 5 2 3 7 国家高性能计算中心（合肥） 2018/12/2

结构化通信 每个任务的通信模式是相同的； 下面是否存在一个相同通信模式？ 国家高性能计算中心（合肥） 2018/12/2

非结构化通信 没有一个统一的通信模式 例如：无结构化网格 国家高性能计算中心（合肥） 2018/12/2

静态/动态通信 通信伙伴的身份不随时间改变；动态通信中，通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。 国家高性能计算中心（合肥） 2018/12/2

同步/异步通信 同步通信时，接收方和发送方协同操作；异步通信中，接收方获取数据无需与发送方协同。 国家高性能计算中心（合肥） 2018/12/2

通信判据 所有任务是否执行大致相当的通信? 是否尽可能的局部通信？ 通信操作是否能并行执行? 同步任务的计算能否并行执行？ 国家高性能计算中心（合肥） 2018/12/2

任务组合 组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行； 合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程； 通过增加任务的粒度和重复计算，可以减少通信成本； 保持映射和扩展的灵活性，降低软件工程成本； 国家高性能计算中心（合肥） 2018/12/2

表面-容积效应 通信量与任务子集的表面成正比，计算量与任务子集的体积成正比； 增加重复计算有可能减少通信量； 国家高性能计算中心（合肥） 2018/12/2

重复计算 重复计算减少通信量，但增加了计算量，应保持恰当的平衡； 重复计算的目标应减少算法的总运算时间； 国家高性能计算中心（合肥） 2018/12/2

重复计算 示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 二叉树上求和，共需2logN步 国家高性能计算中心（合肥） 2018/12/2

重复计算 示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 蝶式结构求和，使用了重复计算，共需logN步 国家高性能计算中心（合肥） 2018/12/2

组合判据 增加粒度是否减少了通信成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通信？ 有没有减少并行执行的机会？ 国家高性能计算中心（合肥） 2018/12/2

处理器映射 每个任务要映射到具体的处理器，定位到运行机器上； 任务数大于处理器数时，存在负载平衡和任务调度问题； 映射的目标：减少算法的执行时间 并发的任务  不同的处理器 任务之间存在高通信的  同一处理器 映射实际是一种权衡，属于NP完全问题； 国家高性能计算中心（合肥） 2018/12/2

负载平衡 静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的： 递归对剖 局部算法 概率方法 循环映射 国家高性能计算中心（合肥） 2018/12/2

任务分配与调度 负载平衡与任务分配/调度密切相关，任务分配通常有静态的和动态的两种方法。 静态分配一般是任务到进程的算术映射。静态分配的优点是没有运行时任务管理的开销，但为了实现负载平衡，要求不同任务的工作量和处理器的性能是可以预测的并且拥有足够的可供分配的任务。 静态调度（Static Scheduling）方案一般是静态地为每个处理器分配个连续的循环迭代，其中为迭代次数，是处理器数。也可以采用轮转（Round-robin）的方式来给处理器分配任务，即将第i个循环迭代分配给第i mod p个处理器。 国家高性能计算中心（合肥） 2018/12/2

任务分配与调度 动态分配与调度相对灵活，可以运行时在不同处理器间动态地进行负载的调整。 各种动态调度（Dynamic Scheduling）技术是并行计算研究的热点，包括基本自调度SS（Self Scheduling）、块自调度BSS（Block Self Scheduling）、 指导自调度GSS（Guided Self Scheduling）、因子分解调度FS（Factoring Scheduling）、梯形自调度TSS（Trapezoid Self Scheduling）、 耦合调度AS（Affinity Scheduling）、安全自调度SSS（Safe Self Scheduling）和自适应耦合调度AAS（Adapt Affinity Scheduling）。 国家高性能计算中心（合肥） 2018/12/2

经理/雇员模式任务调度 任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。 国家高性能计算中心（合肥） 2018/12/2

映射判据 采用集中式负载平衡方案，是否存在通信瓶颈？ 采用动态负载平衡方案，调度策略的成本如何？ 国家高性能计算中心（合肥） 2018/12/2

并行程序设计模型 数据并行模型（Data Parallel） 消息传递模型（Message Passing） 共享变量模型（Shared Variable） 国家高性能计算中心（合肥） 2018/12/2

π的计算 国家高性能计算中心（合肥） 2018/12/2

计算π的串行C代码 #define N 1000000 main() { double local, pi = 0.0, w; long i; w=1.0/N; for (i = 0; i<N; i ++) { local = (i + 0.5)*w; pi = pi + 4.0/(1.0+local * local); } printf(“pi is %f \n”, pi *w); 国家高性能计算中心（合肥） 2018/12/2

数据并行（Data Parallel） 概况： SIMD的自然模型，也可运行于SPMD、MIMD机器上 局部计算和数据选路操作 适合于使用规则网络，模板和多维信号及图像数据集来求解细粒度的应用问题 数据并行操作的同步是在编译时而不是在运行时完成的 特点： 单线程 并行操作于聚合数据结构（数组） 松散同步 全局命名空间 隐式相互作用 隐式/半隐式数据分布 国家高性能计算中心（合肥） 2018/12/2

计算π的数据并行代码 main( ){ long i，j，t，N=100000； double local [N]，temp [N]，pi，w； A： w=1.0/N； B： forall (i=0；i<N ； i++){ P： local[i]=(i+0.5)*w； Q： temp[i]=4.0/(1.0+local[i]*local[i])； } C： pi = sum (temp)； D： printf (“pi is %f \ n”，pi * w )； } / *main( ) * / 国家高性能计算中心（合肥） 2018/12/2

消息传递（Message Passing） 概况： MPP, COW的自然模型，也可应用于共享变量多机系统，适合开发大粒度的并行性 广泛使用的标准消息传递库MPI和PVM 特点： 多线程 异步并行性 分开的地址空间 显式相互作用 显式数据映射和负载分配 常采用SPMD形式编码 国家高性能计算中心（合肥） 2018/12/2

计算π的MPI代码 # define N 100000 main ( ){ double local=0.0，pi，w，temp=0.0； long i ，taskid，numtask； A： w=1.0/N； MPI_ Init(&argc，& argv)； MPI _Comm _rank (MPI_COMM_WORLD，&taskid)； MPI _Comm _Size (MPI_COMM_WORLD，&numtask)； B： for (i= taskid； i< N； i=i + numtask){ P： temp = (i+0.5)*w； Q： local=4.0/(1.0+temp*temp)+local； } C： MPI_Reduce (&local,&pi,1,MPI_Double,MPI_SUM,0, MPI_COMM_WORLD)； D： if (taskid = =0) printf(“pi is %f \ n”，pi* w)； MPI_Finalize ( ) ； } / * main ( )*/ 国家高性能计算中心（合肥） 2018/12/2

共享变量（Shared Variable） 概况： PVP, SMP, DSM的自然模型 特点： 多线程：SPMD, MPMD 异步 单一共享地址空间 显式同步 隐式/隐式数据分布 隐式通信（共享变量的读/写） 国家高性能计算中心（合肥） 2018/12/2

计算π的共享变量程序代码 # define N 100000 main ( ){ double local，pi=0.0 ，w； long i ； A ： w=1. 0/N； B ： # Pragma Parallel # Pragma Shared (pi，w) # Pragma Local (i，local) { # Pragma pfor iterate(i=0；N；1) for (i=0；i<N，i++){ P： local = (i+0.5)*w； Q： local=4.0/(1.0+local*local)； } C ： # Pragma Critical pi =pi +local ； D： printf (“pi is %f \ n”，pi *w)； }/ *main( ) */ 国家高性能计算中心（合肥） 2018/12/2

三种显式并行程序设计模型主要特性 特 性 数据并行 消息传递 共享变量 控制流（线） 单线程 多线程 进程间操作 松散同步 异步 地址空间 特 性 数据并行 消息传递 共享变量 控制流（线） 单线程 多线程 进程间操作 松散同步 异步 地址空间 单一地址 多地址空间 单地址空间 相互作用 隐式 显式 数据分配 隐式或半隐式 国家高性能计算中心（合肥） 2018/12/2

并行编程语言和环境概述 早期机制 近代机制 并行说明性机制 共享存储 分布存储 逻辑语言 函数语言 Semaphores （信号灯） CCRs （条件 临界区） Monitors （管理） Sockets （套接字） RPCs （远程过程 调用） Rendezvous （汇合） Pthreads Java Threads SHMEM OpenMP HPF （虚拟 共享） Ada MPI PVM DCE dist. Java IC-Prolog PARLOG GHCs Multilisp Sisal 国家高性能计算中心（合肥） 2018/12/2