并行算法的一般设计过程

并行算法的一般设计过程第一页，共四十七页，编辑于2023年，星期六第二篇并行算法的设计

第四章并行算法的设计基础

第五章并行算法的一般设计方法

第六章并行算法的基本设计技术

第七章并行算法的一般设计过程

第二页，共四十七页，编辑于2023年，星期六第七章并行算法的一般设计过程

7.1PCAM设计方法学

7.2划分

7.3通讯

7.4组合

7.5映射

7.6小结

第三页，共四十七页，编辑于2023年，星期六

PCAM设计方法学设计并行算法的四个阶段划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通讯：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。2023/5/284第四页，共四十七页，编辑于2023年，星期六

PCAM设计过程2023/5/285第五页，共四十七页，编辑于2023年，星期六第七章并行算法的一般设计过程

7.1PCAM设计方法学

7.2划分

7.3通讯

7.4组合

7.5映射

7.6小结

第六页，共四十七页，编辑于2023年，星期六7.2划分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4划分判据第七页，共四十七页，编辑于2023年，星期六划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(domaindecomposition)功能分解(functionaldecomposition)2023/5/288第八页，共四十七页，编辑于2023年，星期六7.2划分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4划分判据第九页，共四十七页，编辑于2023年，星期六域分解划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯；2023/5/2810第十页，共四十七页，编辑于2023年，星期六域分解示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：2023/5/2811第十一页，共四十七页，编辑于2023年，星期六域分解不规则区域的分解示例：2023/5/2812第十二页，共四十七页，编辑于2023年，星期六7.2划分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4划分判据第十三页，共四十七页，编辑于2023年，星期六功能分解划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。2023/5/2814第十四页，共四十七页，编辑于2023年，星期六功能分解示例1：搜索树示例2：气候模型2023/5/2815第十五页，共四十七页，编辑于2023年，星期六7.2划分

7.2.1方法描述

7.2.2域分解

7.2.3功能分解

7.2.4划分判据第十六页，共四十七页，编辑于2023年，星期六划分判据划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否合理？2023/5/2817第十七页，共四十七页，编辑于2023年，星期六第七章并行算法的一般设计过程

7.1PCAM设计方法学

7.2划分

7.3通讯

7.4组合

7.5映射

7.6小结

第十八页，共四十七页，编辑于2023年，星期六7.3通讯

7.3.1方法描述

7.3.2四种通讯模式

7.3.3通讯判据

第十九页，共四十七页，编辑于2023年，星期六通讯方法描述通讯是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯则限制了这种并发性；2023/5/2820第二十页，共四十七页，编辑于2023年，星期六7.3通讯

7.3.1方法描述

7.3.2四种通讯模式

7.3.3通讯判据

第二十一页，共四十七页，编辑于2023年，星期六四种通讯模式局部/全局通讯结构化/非结构化通讯静态/动态通讯同步/异步通讯2023/5/2822第二十二页，共四十七页，编辑于2023年，星期六局部通讯通讯限制在一个邻域内2023/5/2823第二十三页，共四十七页，编辑于2023年，星期六全局通讯通讯非局部的例如：AlltoAllMaster-Worker537212023/5/2824第二十四页，共四十七页，编辑于2023年，星期六结构化通讯每个任务的通讯模式是相同的；下面是否存在一个相同通讯模式？2023/5/2825第二十五页，共四十七页，编辑于2023年，星期六非结构化通讯没有一个统一的通讯模式例如：无结构化网格2023/5/2826第二十六页，共四十七页，编辑于2023年，星期六7.3通讯

7.3.1方法描述

7.3.2四种通讯模式

7.3.3通讯判据

第二十七页，共四十七页，编辑于2023年，星期六通讯判据所有任务是否执行大致相当的通讯?是否尽可能的局部通讯？通讯操作是否能并行执行?同步任务的计算能否并行执行？2023/5/2828第二十八页，共四十七页，编辑于2023年，星期六第七章并行算法的一般设计过程

7.1PCAM设计方法学

7.2划分

7.3通讯

7.4组合

7.5映射

7.6小结第二十九页，共四十七页，编辑于2023年，星期六7.4组合

7.4.1方法描述

7.4.2表面-容积效应

7.4.3重复计算

7.4.4组合判据第三十页，共四十七页，编辑于2023年，星期六方法描述组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；保持映射和扩展的灵活性，降低软件工程成本；2023/5/2831第三十一页，共四十七页，编辑于2023年，星期六7.4组合

7.4.1方法描述

7.4.2表面-容积效应

7.4.3重复计算

7.4.4组合判据第三十二页，共四十七页，编辑于2023年，星期六表面-容积效应通讯量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通讯量；2023/5/2833第三十三页，共四十七页，编辑于2023年，星期六7.4组合

7.4.1方法描述

7.4.2表面-容积效应

7.4.3重复计算

7.4.4组合判据第三十四页，共四十七页，编辑于2023年，星期六重复计算重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；2023/5/2835第三十五页，共四十七页，编辑于2023年，星期六重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。

二叉树上求和，共需2logN步2023/5/2836第三十六页，共四十七页，编辑于2023年，星期六重复计算示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。

蝶式结构求和，使用了重复计算，共需logN步2023/5/2837第三十七页，共四十七页，编辑于2023年，星期六7.4组合

7.4.1方法描述

7.4.2表面-容积效应

7.4.3重复计算

7.4.4组合判据第三十八页，共四十七页，编辑于2023年，星期六组合判据增加粒度是否减少了通讯成本？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通讯？有没有减少并行执行的机会？2023/5/2839第三十九页，共四十七页，编辑于2023年，星期六第七章并行算法的一般设计过程

7.1PCAM设计方法学

7.2划分

7.3通讯

7.4组合

7.5映射

7.6小结第四十页，共四十七页，编辑于2023年，星期六7.5映射

7.5.1方法描述

7.5.2负载平衡算法

7.5.3任务调度算法

7.5.4映射判据第四十一页，共四十七页，编辑于2023年，星期六方法描述每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务不同的处理器任务之间存在高通讯的同一处理器映射实际是一种权衡，属于NP完全问题；2023/5/2842第四十二页，共四十七页，编辑于2023年，星期六7.5映射

7.5.1方法描述

7.5.2负载平衡算法

7.5.3任务调度算法

7.5.4映射判据第四十三页，共四十七页，编辑于2023年，星期六负载平衡算法静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；基于域分解的：递归对剖局部算法概率方法循环映射2023/5/2844第四十四页，共四十七页，编辑于2023年，星期六7.5映射

7.5.1方法描述

7.5.2负载平衡算法

7.5.3任务调度算法