并行算法实践

《并行算法实践》由会员分享，可在线阅读，更多相关《并行算法实践（54页珍藏版）》请在金锄头文库上搜索。

1、并行算法实践上篇 并行程序设计导论国家高性能计算中心（合肥）22024/8/12并行算法实践上篇 并行程序设计导论 单元单元单元单元I I 并行程序设计基础并行程序设计基础并行程序设计基础并行程序设计基础 单元单元单元单元II II 并行程序编程指南并行程序编程指南并行程序编程指南并行程序编程指南 单元单元单元单元III III 并行程序开发方法并行程序开发方法并行程序开发方法并行程序开发方法国家高性能计算中心（合肥）32024/8/12单元I 并行程序设计基础 第一章第一章第一章第一章 并行计算机系统与结构模型并行计算机系统与结构模型并行计算机系统与结构模型并行计算机系统与结构模型 第二章第

2、二章第二章第二章 PCPC机群的搭建机群的搭建机群的搭建机群的搭建 第三章第三章第三章第三章 并行程序设计简介并行程序设计简介并行程序设计简介并行程序设计简介国家高性能计算中心（合肥）42024/8/12第三章 并行程序设计简介 3.1 3.1 并行程序开发方法并行程序开发方法 3.1.1 3.1.1 并行层次与代码粒度并行层次与代码粒度 3.1.2 3.1.2 并行程序开发策略并行程序开发策略 3.1.3 3.1.3 并行编程模式并行编程模式 3.1.4 3.1.4 并行应用编程过程并行应用编程过程 3.2 3.2 并行程序设计模型并行程序设计模型 3.2.1 3.2.1 计算计算 样本程序

3、样本程序 3.2.2 3.2.2 数据并行模型数据并行模型 3.2.3 3.2.3 消息传递模型消息传递模型 3.2.4 3.2.4 共享变量模型共享变量模型 3.3 3.3 并行编程语言和环境概述并行编程语言和环境概述 3.3.1 3.3.1 早期并行编程语言早期并行编程语言 3.3.2 3.3.2 近代并行编程语言与环境近代并行编程语言与环境 3.3.3 3.3.3 并行说明性语言环境并行说明性语言环境 3.4 3.4 循环程序并行化的一般方法循环程序并行化的一般方法 3.4.1 3.4.1 数据相关分析数据相关分析 3.4.2 .3.4.2 .数据划分与处理器指派数据划分与处理器指派 3

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

5、务操作系统操作系统消息传递消息传递国家高性能计算中心（合肥）72024/8/12并行程序开发策略国家高性能计算中心（合肥）82024/8/12并行编程模式 主主- -从式（从式（Master-SlaveMaster-Slave） 单程序多数据流（单程序多数据流（Single Program Multiple Data Single Program Multiple Data ） 数据流水线（数据流水线（Data PipeliningData Pipelining） 分治策略（分治策略（Divide and ConquerDivide and Conquer）国家高性能计算中心（合肥）92024

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

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

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

9、相算过程中各进程之间的通信模式非常简单，仅发生在相邻的阶段之间，且通信可以完全异步地进行。邻的阶段之间，且通信可以完全异步地进行。 国家高性能计算中心（合肥）122024/8/12国家高性能计算中心（合肥）132024/8/12分治策略（Divide and Conquer） 其基本思想是将一个大而复杂其基本思想是将一个大而复杂的问题分解成若干个特性相同的问题分解成若干个特性相同的子问题分而治之。若所得的的子问题分而治之。若所得的子问题规模仍嫌过大，则可反子问题规模仍嫌过大，则可反复使用分治策略，直至很容易复使用分治策略，直至很容易求解诸子问题为止。问题求解求解诸子问题为止。问题求解可分为三步

10、：可分为三步：将输入分解成将输入分解成若干个若干个规模近于相等规模近于相等的子问题；的子问题；同时同时递归地递归地求解诸子问题；求解诸子问题；归并各子问题的解成为原问归并各子问题的解成为原问题的解。题的解。国家高性能计算中心（合肥）142024/8/12并行应用编程过程PCAM设计并行应用的四个阶段 划分划分( (P Partitioningartitioning) ) 通信通信( (C Communicationommunication) ) 组合组合( (A Agglomerationgglomeration) ) 映射映射( (MMappingapping) )划分：分解成小的任务，开拓

11、并发性；分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高并行性能。将每个任务分配到处理器上，提高并行性能。国家高性能计算中心（合肥）152024/8/12 PCAM设计过程国家高性能计算中心（合肥）162024/8/12 划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：

12、 域分解域分解( (Domain DecompositionDomain Decomposition) ) 功能分解功能分解( (Functional DecompositionFunctional Decomposition) )国家高性能计算中心（合肥）172024/8/12域分解 划分的对象是数据，可以是程序中的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通信；国家高性能计算中心（合肥）182024/8/12域分解 示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：国家高

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

14、能分解；功能分解是一种更深层次的分解。功能分解是一种更深层次的分解。国家高性能计算中心（合肥）212024/8/12功能分解 示例示例1 1：搜索树：搜索树示例示例2 2：气候模型：气候模型国家高性能计算中心（合肥）222024/8/12划分判据 划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？国家高性能计算中心（合肥）232024/8/12 通信分析通信是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解确定了诸任务之间的数据流；

15、诸任务是并发执行的，通信则限制了这种并发性；国家高性能计算中心（合肥）242024/8/12 四种通信模式局部/全局通信结构化/非结构化通信静态/动态通信同步/异步通信国家高性能计算中心（合肥）252024/8/12局部通信通信限制在一个邻域内国家高性能计算中心（合肥）262024/8/12全局通信通信非局部的例如：All to AllAll to AllMaster-WorkerMaster-Worker53721国家高性能计算中心（合肥）272024/8/12结构化通信每个任务的通信模式是相同的；下面是否存在一个相同通信模式？国家高性能计算中心（合肥）282024/8/12非结构化通信没有

16、一个统一的通信模式例如：无结构化网格国家高性能计算中心（合肥）292024/8/12静态/动态通信通信伙伴的身份不随时间改变；动态通信中，通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。 国家高性能计算中心（合肥）302024/8/12同步/异步通信同步通信时，接收方和发送方协同操作；异步通信中，接收方获取数据无需与发送方协同。国家高性能计算中心（合肥）312024/8/12通信判据 所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行?同步任务的计算能否并行执行？国家高性能计算中心（合肥）322024/8/12任务组合 组合是由抽象到具体的过程，是将组合的任务

17、能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通信成本；保持映射和扩展的灵活性，降低软件工程成本；国家高性能计算中心（合肥）332024/8/12表面-容积效应通信量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通信量；国家高性能计算中心（合肥）342024/8/12重复计算重复计算减少通信量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；国家高性能计算中心（合肥）352024/8/12重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处

18、理器均保持全和。 二叉树上求和，共需二叉树上求和，共需2logN2logN步步国家高性能计算中心（合肥）362024/8/12重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 蝶式结构求和，使用了重复计算，共需蝶式结构求和，使用了重复计算，共需logNlogN步步国家高性能计算中心（合肥）372024/8/12组合判据 增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？国家高性能计算中心（合肥）382024/8/12处理器映射 每个任务要映射到具体

19、的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务并发的任务 不同的处理器不同的处理器任务之间存在高通信的任务之间存在高通信的 同一处理器同一处理器映射实际是一种权衡，属于NP完全问题；国家高性能计算中心（合肥）392024/8/12负载平衡 静态的：事先确定；事先确定；概率的：随机确定；随机确定；动态的：执行期间动态负载；执行期间动态负载；基于域分解的：递归对剖递归对剖局部算法局部算法概率方法概率方法循环映射循环映射国家高性能计算中心（合肥）402024/8/12任务分配与调度 负载平衡与任务分配负载平衡与任务分配/ /调度

20、密切相关，任务分配通常有调度密切相关，任务分配通常有静态的和动态的两种方法。静态的和动态的两种方法。 静态分配一般是任务到进程的算术映射。静态分配一般是任务到进程的算术映射。静态分配的优静态分配的优点是没有运行时任务管理的开销，但为了实现负载平衡，点是没有运行时任务管理的开销，但为了实现负载平衡，要求不同任务的工作量和处理器的性能是可以预测的并要求不同任务的工作量和处理器的性能是可以预测的并且拥有足够的可供分配的任务。且拥有足够的可供分配的任务。 静态调度静态调度静态调度静态调度（Static SchedulingStatic Scheduling）方案一般是静态地为）方案一般是静态地为每个处

21、理器分配个连续的循环迭代，其中为迭代次数，每个处理器分配个连续的循环迭代，其中为迭代次数，是处理器数。也可以采用是处理器数。也可以采用轮转轮转轮转轮转（Round-robinRound-robin）的方式）的方式来给处理器分配任务，即将第来给处理器分配任务，即将第i i个循环迭代分配给第个循环迭代分配给第i i mod pmod p个处理器。个处理器。国家高性能计算中心（合肥）412024/8/12任务分配与调度 动态分配与调度相对灵活，可以运行时在不同处理器间动态分配与调度相对灵活，可以运行时在不同处理器间动态地进行负载的调整。动态地进行负载的调整。 各种各种动态调度动态调度动态调度动态调度

22、（Dynamic SchedulingDynamic Scheduling）技术是并行计算）技术是并行计算研究的热点，包括研究的热点，包括基本自调度基本自调度基本自调度基本自调度SSSSSSSS（Self SchedulingSelf Scheduling）、）、块自调度块自调度块自调度块自调度BSSBSSBSSBSS（Block Self SchedulingBlock Self Scheduling）、）、 指导自调指导自调指导自调指导自调度度度度GSSGSSGSSGSS（Guided Self SchedulingGuided Self Scheduling）、）、因子分解调度因子分解调

23、度因子分解调度因子分解调度FSFSFSFS（Factoring SchedulingFactoring Scheduling）、）、梯形自调度梯形自调度梯形自调度梯形自调度TSSTSSTSSTSS（Trapezoid Self SchedulingTrapezoid Self Scheduling）、）、 耦合调度耦合调度耦合调度耦合调度ASASASAS（Affinity SchedulingAffinity Scheduling）、）、安全自调度安全自调度安全自调度安全自调度SSSSSSSSSSSS（Safe Safe Self SchedulingSelf Scheduling）和）和自适

24、应耦合调度自适应耦合调度自适应耦合调度自适应耦合调度AASAASAASAAS（Adapt Adapt Affinity SchedulingAffinity Scheduling）。）。国家高性能计算中心（合肥）422024/8/12经理/雇员模式任务调度 任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。国家高性能计算中心（合肥）432024/8/12映射判据 采用集中式负载平衡方案，是否存在通信瓶颈？采用动态负载平衡方案，调度策略的成本如何？国家高性能计算中心（合肥）442024/8/12并行程序设计模型数据并行模型（数据并行模型（Data ParallelD

25、ata Parallel）消息传递模型（消息传递模型（Message PassingMessage Passing）共享变量模型（共享变量模型（Shared VariableShared Variable）国家高性能计算中心（合肥）452024/8/12的计算国家高性能计算中心（合肥）462024/8/12计算的串行C代码#define N 1000000#define N 1000000main() main() double local, pi = 0.0, w;double local, pi = 0.0, w;long i;long i;w=1.0/N;w=1.0/N;for (i =

26、 0; iN; i +) for (i = 0; iN; i +) local = (i + 0.5)*w;local = (i + 0.5)*w;pi = pi + 4.0/(1.0+local * local);pi = pi + 4.0/(1.0+local * local); printf(“pi is %f n”, pi *w);printf(“pi is %f n”, pi *w); 国家高性能计算中心（合肥）472024/8/12数据并行（Data Parallel） 概况：概况： SIMDSIMD的自然模型，也可运行于的自然模型，也可运行于SPMDSPMD、MIMDMIMD机器

27、上机器上 局部计算和数据选路操作局部计算和数据选路操作 适合于使用规则网络，模板和多维信号及图像数据集来求解细适合于使用规则网络，模板和多维信号及图像数据集来求解细粒度的应用问题粒度的应用问题 数据并行操作的同步是在编译时而不是在运行时完成的数据并行操作的同步是在编译时而不是在运行时完成的 特点：特点： 单线程单线程 并行操作于聚合数据结构（数组）并行操作于聚合数据结构（数组） 松散同步松散同步 全局命名空间全局命名空间 隐式相互作用隐式相互作用 隐式隐式/ /半隐式数据分布半隐式数据分布国家高性能计算中心（合肥）482024/8/12计算的数据并行代码main( ) long i，j，t，N

28、=100000； double local N，temp N，pi，w； A： w=1.0/N； B： forall (i=0；iN ； i+) P： locali=(i+0.5)*w； Q： tempi=4.0/(1.0+locali*locali)； C： pi = sum (temp)； D： printf (“pi is %f n”，pi * w )； / *main( ) * /国家高性能计算中心（合肥）492024/8/12消息传递（Message Passing） 概况：概况： MPP, COWMPP, COW的自然模型，也可应用于共享变量多机系的自然模型，也可应用于共享变量多机

29、系统，适合开发大粒度的并行性统，适合开发大粒度的并行性 广泛使用的标准消息传递库广泛使用的标准消息传递库MPIMPI和和PVMPVM 特点：特点： 多线程多线程 异步并行性异步并行性 分开的地址空间分开的地址空间 显式相互作用显式相互作用 显式数据映射和负载分配显式数据映射和负载分配 常采用常采用SPMDSPMD形式编码形式编码国家高性能计算中心（合肥）502024/8/12计算的MPI代码 # define N 100000 main ( ) double local=0.0，pi，w，temp=0.0； long i ，taskid，numtask； A： w=1.0/N； MPI_ In

30、it(&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

31、%f n”，pi* w)； MPI_Finalize ( ) ； / * main ( )*/国家高性能计算中心（合肥）512024/8/12共享变量（Shared Variable） 概况：概况： PVP, SMP, DSMPVP, SMP, DSM的自然模型的自然模型 特点：特点： 多线程：多线程：SPMD, MPMDSPMD, MPMD 异步异步 单一共享地址空间单一共享地址空间 显式同步显式同步 隐式隐式/ /隐式数据分布隐式数据分布 隐式通信（共享变量的读隐式通信（共享变量的读/ /写）写）国家高性能计算中心（合肥）522024/8/12计算的共享变量程序代码# define N 1

32、00000 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；iN，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

33、)； / *main( ) */国家高性能计算中心（合肥）532024/8/12 三种显式并行程序设计模型主要特性 特特 性性数据并行数据并行消息传递消息传递共享变量共享变量控制流（线）控制流（线）单线程单线程多线程多线程多线程多线程进程间操作进程间操作松散同步松散同步异步异步异步异步地址空间地址空间单一地址单一地址多地址空间多地址空间单地址空间单地址空间相互作用相互作用隐式隐式显式显式显式显式数据分配数据分配 隐式或半隐式隐式或半隐式显式显式隐式或半隐式隐式或半隐式国家高性能计算中心（合肥）542024/8/12并行编程语言和环境概述 早期机制早期机制近代机制近代机制并行说明性机制并行说明性机制共享存储共享存储分布存储分布存储共享存储共享存储分布存储分布存储逻辑语言逻辑语言函数语言函数语言Semaphores（信号灯）CCRs（条件临界区）Monitors（管理）Sockets（套接字）RPCs（远程过程调用）Rendezvous（汇合）PthreadsJava ThreadsSHMEMOpenMPHPF（虚拟共享）PthreadsAdaMPIPVMDCEdist. JavaIC-PrologPARLOGGHCsMultilispSisal