《并行算法的一般设计过程.ppt》由会员分享,可在线阅读,更多相关《并行算法的一般设计过程.ppt(47页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、并行算法的一般设计过程现在学习的是第1页,共47页第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程现在学习的是第2页,共47页第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 现在学习的是第3页,共47页 PCAM设计方法学设计并行算法的四个阶段 划分划分(Partitioning)(Partitioning)通讯通讯(Communication)(Communication)组合组合(Agglomeration)(A
2、gglomeration)映射映射(Mapping)(Mapping)划分:分解成小的任务,开拓并发性;分解成小的任务,开拓并发性;通讯:确定诸任务间的数据交换,监测划分的合理性;确定诸任务间的数据交换,监测划分的合理性;组合:依据任务的局部性,组合成更大的任务;依据任务的局部性,组合成更大的任务;映射:将每个任务分配到处理器上,提高算法的性能。将每个任务分配到处理器上,提高算法的性能。2022/9/304现在学习的是第4页,共47页 PCAM设计过程2022/9/305现在学习的是第5页,共47页第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4
3、组合 7.5 映射 7.6 小结 现在学习的是第6页,共47页7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据现在学习的是第7页,共47页 划分方法描述充分开拓算法的并发性和可扩放性;先进行数据分解(称域分解),再进行计算功能的分解(称功能分解);使数据集和计算集互不相交;划分阶段忽略处理器数目和目标机器的体系结构;能分为两类划分:域分解域分解(domain decompositiondomain decomposition)功能分解功能分解(functional decompositionfunctional decomposition)20
4、22/9/308现在学习的是第8页,共47页7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据现在学习的是第9页,共47页域分解 划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据;将数据分解成大致相等的小数据片;划分时考虑数据上的相应操作;如果一个任务需要别的任务中的数据,则会产生任务间的通讯;2022/9/3010现在学习的是第10页,共47页域分解 示例:三维网格的域分解,各格点上计算都是重复的。下图是三种分解方法:2022/9/3011现在学习的是第11页,共47页域分解 不规则区域的分解示例:2022/9/3012现在学习的
5、是第12页,共47页7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据现在学习的是第13页,共47页功能分解 划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解;划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠,意味着要重新进行域分解和功能分解;功能分解是一种更深层次的分解。2022/9/3014现在学习的是第14页,共47页功能分解 示例1:搜索树示例2:气候模型2022/9/3015现在学习的是第15页,共47页7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解
6、7.2.4 划分判据现在学习的是第16页,共47页划分判据 划分是否具有灵活性?划分是否避免了冗余计算和存储?划分任务尺寸是否大致相当?任务数与问题尺寸是否成比例?功能分解是一种更深层次的分解,是否合理?2022/9/3017现在学习的是第17页,共47页第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 现在学习的是第18页,共47页7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据现在学习的是第19页,共47页 通讯方法描述通讯是PCAM设计过程的重要阶段;划分产生的诸任务,一般不
7、能完全独立执行,需要在任务间进行数据交流;从而产生了通讯;功能分解确定了诸任务之间的数据流;诸任务是并发执行的,通讯则限制了这种并发性;2022/9/3020现在学习的是第20页,共47页7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据现在学习的是第21页,共47页 四种通讯模式局部/全局通讯结构化/非结构化通讯静态/动态通讯同步/异步通讯2022/9/3022现在学习的是第22页,共47页局部通讯通讯限制在一个邻域内2022/9/3023现在学习的是第23页,共47页全局通讯通讯非局部的例如:All to AllAll to AllMaster-Worker
8、537212022/9/3024现在学习的是第24页,共47页结构化通讯每个任务的通讯模式是相同的;下面是否存在一个相同通讯模式?2022/9/3025现在学习的是第25页,共47页非结构化通讯没有一个统一的通讯模式例如:无结构化网格2022/9/3026现在学习的是第26页,共47页7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据现在学习的是第27页,共47页通讯判据 所有任务是否执行大致相当的通讯?是否尽可能的局部通讯?通讯操作是否能并行执行?同步任务的计算能否并行执行?2022/9/3028现在学习的是第28页,共47页第七章 并行算法的一般设计过程 7
9、.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结现在学习的是第29页,共47页7.4 组合 7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据现在学习的是第30页,共47页方法描述 组合是由抽象到具体的过程,是将组合的任务能在一类并行机上有效的执行;合并小尺寸任务,减少任务数。如果任务数恰好等于处理器数,则也完成了映射过程;通过增加任务的粒度和重复计算,可以减少通讯成本;保持映射和扩展的灵活性,降低软件工程成本;2022/9/3031现在学习的是第31页,共47页7.4 组合 7.4.1 方法描述 7.4.
10、2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据现在学习的是第32页,共47页表面-容积效应通讯量与任务子集的表面成正比,计算量与任务子集的体积成正比;增加重复计算有可能减少通讯量;2022/9/3033现在学习的是第33页,共47页7.4 组合 7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据现在学习的是第34页,共47页重复计算重复计算减少通讯量,但增加了计算量,应保持恰当的平衡;重复计算的目标应减少算法的总运算时间;2022/9/3035现在学习的是第35页,共47页重复计算示例:二叉树上N个处理器求N个数的全和,要求每个处理器均
11、保持全和。二叉树上求和,共需2logN步2022/9/3036现在学习的是第36页,共47页重复计算示例:二叉树上N个处理器求N个数的全和,要求每个处理器均保持全和。蝶式结构求和,使用了重复计算,共需logN步2022/9/3037现在学习的是第37页,共47页7.4 组合 7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据现在学习的是第38页,共47页组合判据 增加粒度是否减少了通讯成本?重复计算是否已权衡了其得益?是否保持了灵活性和可扩放性?组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通讯?有没有减少并行执行的机会?2022/9/303
12、9现在学习的是第39页,共47页第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结现在学习的是第40页,共47页7.5 映射 7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据现在学习的是第41页,共47页方法描述 每个任务要映射到具体的处理器,定位到运行机器上;任务数大于处理器数时,存在负载平衡和任务调度问题;映射的目标:减少算法的执行时间并发的任务并发的任务 不同的处理器 任务之间存在高通讯的任务之间存在高通讯的 同一处理器同一处理器映射实际是一种权衡,属于NP完全问题
13、;2022/9/3042现在学习的是第42页,共47页7.5 映射 7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据现在学习的是第43页,共47页负载平衡算法 静态的:事先确定;事先确定;概率的:随机确定;动态的:执行期间动态负载;执行期间动态负载;基于域分解的:递归对剖递归对剖局部算法 概率方法概率方法循环映射2022/9/3044现在学习的是第44页,共47页7.5 映射 7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据现在学习的是第45页,共47页任务调度算法 任务放在集中的或分散的任务池中,使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式:经理/雇员模式非集中模式2022/9/3046现在学习的是第46页,共47页7.5 映射 7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据现在学习的是第47页,共47页
限制150内