07-第07章-并行算法的一般设计过程-并行算法的设计-并行计算(共15章)

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心((合肥合肥))20042004年年1212月月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第七章并行算法的一般设计过程7.1PCAM设计方法学7.2划分7.3通讯7.4组合7.5映射7.6小结国家高性能计算中心（合肥）42013/7/24WednesdayPCAM设计方法学设计并行算法的四个阶段设计并行算法的四个阶段划分划分(Partitioning)(Partitioning)通讯通讯(Communication)(Communication)组合组合(Agglomeration)(Agglomeration)映射映射(Mapping)(Mapping)划分：划分：分解成小的任务，开拓并发性；分解成小的任务，开拓并发性；通讯：通讯：确定诸任务间的数据交换，监测划分的合理性；确定诸任务间的数据交换，监测划分的合理性；组合：组合：依据任务的局部性，组合成更大的任务；依据任务的局部性，组合成更大的任务；映射：映射：将每个任务分配到处理器上，提高算法的性能。将每个任务分配到处理器上，提高算法的性能。国家高性能计算中心（合肥）52013/7/24WednesdayPCAM设计过程问题划分映射组合通信第七章并行算法的一般设计过程7.1PCAM设计方法学7.2划分7.3通讯7.4组合7.5映射7.6小结7.2划分7.2.1方法描述7.2.2域分解7.2.3功能分解7.2.4划分判据国家高性能计算中心（合肥）82013/7/24Wednesday划分方法描述充分开拓算法的并发性和可扩放性；充分开拓算法的并发性和可扩放性；先进行数据分解先进行数据分解((称域分解称域分解))，再进行计算，再进行计算功能的分解功能的分解((称功能分解称功能分解))；；使数据集和计算集互不相交；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体划分阶段忽略处理器数目和目标机器的体系结构；系结构；能分为两类划分：能分为两类划分：域分解域分解((domaindecompositiondomaindecomposition))功能分解功能分解((functionaldecompositionfunctionaldecomposition))7.2划分7.2.1方法描述7.2.2域分解7.2.3功能分解7.2.4划分判据国家高性能计算中心（合肥）102013/7/24Wednesday域分解划分的对象是数据，可以是算法的输入划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，如果一个任务需要别的任务中的数据，则会产生任务间的通讯；则会产生任务间的通讯；国家高性能计算中心（合肥）112013/7/24Wednesday域分解示例：三维网格的域分解，各格点上计算示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：都是重复的。下图是三种分解方法：图7.2‐1D‐2D‐3D国家高性能计算中心（合肥）122013/7/24Wednesday域分解不规则区域的分解示例：不规则区域的分解示例：7.2划分7.2.1方法描述7.2.2域分解7.2.3功能分解7.2.4划分判据国家高性能计算中心（合肥）142013/7/24Wednesday功能分解划分的对象是计算，将计算划分为不同划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，的；如果数据有相当的重叠，意味着要意味着要重新进行域分解和功能分解；重新进行域分解和功能分解；功能分解是一种更深层次的分解。功能分解是一种更深层次的分解。国家高性能计算中心（合肥）152013/7/24Wednesday功能分解示例示例11：搜索树：搜索树示例示例22：气候模型：气候模型7.2划分7.2.1方法描述7.2.2域分解7.2.3功能分解7.2.4划分判据国家高性能计算中心（合肥）172013/7/24Wednesday划分判据划分是否具有灵活性？划分是否具有灵活性？划分是否避免了冗余计算和存储？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？划分任务尺寸是否大致相当？任务数与问题尺寸是否成比例？任务数与问题尺寸是否成比例？功能分解是一种更深层次的分解，是否功能分解是一种更深层次的分解，是否合理？合理？第七章并行算法的一般设计过程7.1PCAM设计方法学7.2划分7.3通讯7.4组合7.5映射7.6小结7.3通讯7.3.1方法描述7.3.2四种通讯模式7.3.3通讯判据国家高性能计算中心（合肥）202013/7/24Wednesday通讯方法描述通讯是通讯是PCAMPCAM设计过程的重要阶段；设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产行，需要在任务间进行数据交流；从而产生了通讯；生了通讯；功能分解确定了诸任务之间的数据流；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯则限制了这种诸任务是并发执行的，通讯则限制了这种并发性；并发性；7.3通讯7.3.1方法描述7.3.2四种通讯模式7.3.3通讯判据国家高性能计算中心（合肥）222013/7/24Wednesday四种通讯模式局部局部//全局通讯全局通讯结构化结构化//非结构化通讯非结构化通讯静态静态//动态通讯动态通讯同步同步//异步通讯异步通讯国家高性能计算中心（合肥）232013/7/24Wednesday局部通讯通讯限制在一个邻域内通讯限制在一个邻域内国家高性能计算中心（合肥）242013/7/24Wednesday全局通讯通讯非局部的通讯非局部的例如：例如：AlltoAllAlltoAllMasterMaster--WorkerWorker53721国家高性能计算中心（合肥）252013/7/24Wednesday结构化通讯每个任务的通讯模式是相同的；每个任务的通讯模式是相同的；下面是否存在一个相同通讯模式？下面是否存在一个相同通讯模式？国家高性能计算中心（合肥）262013/7/24Wednesday非结构化通讯没有一个统一的通讯模式没有一个统一的通讯模式例如：无结构化网格例如：无结构化网格7.3通讯7.3.1方法描述7.3.2四种通讯模式7.3.3通讯判据国家高性能计算中心（合肥）282013/7/24Wednesday通讯判据所有任务是否执行大致相当的通讯所有任务是否执行大致相当的通讯??是否尽可能的局部通讯？是否尽可能的局部通讯？通讯操作是否能并行执行通讯操作是否能并行执行??同步任务的计算能否并行执行？同步任务的计算能否并行执行？第七章并行算法的一般设计过程7.1PCAM设计方法学7.2划分7.3通讯7.4组合7.5映射7.6小结7.4组合7.4.1方法描述7.4.2表面-容积效应7.4.3重复计算7.4.4组合判据国家高性能计算中心（合肥）312013/7/24Wednesday方法描述组合是由抽象到具体的过程，是将组合的组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过数恰好等于处理器数，则也完成了映射过程；程；通过增加任务的粒度和重复计算，可以减通过增加任务的粒度和重复计算，可以减少通讯成本；少通讯成本；保持映射和扩展的灵活性，降低软件工程保持映射和扩展的灵活性，降低软件工程成本；成本；7.4组合7.4.1方法描述7.4.2表面-容积效应7.4.3重复计算7.4.4组合判据国家高性能计算中心（合肥）332013/7/24Wednesday表面-容积效应通讯量与任务子集的表面成正比，计算通讯量与任务子集的表面成正比，计算量与任务子集的体积成正比；量与任务子集的体积成正比；增加重复计算有可能减少通讯量；增加重复计算有可能减少通讯量；7.4组合7.4.1方法描述7.4.2表面-容积效应7.4.3重复计算7.4.4组合判据国家高性能计算中心（合肥）352013/7/24Wednesday重复计算重复计算减少通讯量，但增加了计算量，重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；应保持恰当的平衡；重复计算的目标应减少算法的总运算时重复计算的目标应减少算法的总运算时间；间；国家高性能计算中心（合肥）362013/7/24Wednesday重复计算示例：二叉树上示例：二叉树上NN个处理器求个处理器求NN个数的全个数的全和，要求每个处理器均保持全和。和，要求每个处理器均保持全和。二叉树上求和，共需二叉树上求和，共需2logN2logN步步国家高性能计算中心（合肥）372013/7/24Wednesday重复计算示例：二叉树上示例：二叉树上NN个处理器求个处理器求NN个数的全个数的全和，要求每个处理器均保持全和。和，要求每个处理器均保持全和。蝶式结构求和，使用了重复计算，共需蝶式结构求和，使用了重复计算，共需logNlogN步步7.4组合7.4.1方法描述7.4.2表面-容积效应7.4.3重复计算7.4.4组合判据国家高性能计算中心（合肥）392013/7/24Wednesday组合判据增加粒度是否减少了通讯成本？增加粒度是否减少了通讯成本？重复计算是否已权衡了其得益？重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例组合的任务数是否与问题尺寸成比例??是否保持了类似的计算和通讯？是否保持了类似的计算和通讯？有没有减少并行执行的机会？有没有减少并行执行的机会？第七章并行算法的一般设计过程7.1PCAM设计方法学7.2划分7.3通讯7.4组合7.5映射7.6小结7.5映射7.5.1方法描述7.5.2负载平衡算法7.5.3任务调度算法7.5.4映射判据国家高性能计算中心（合肥）422013/7/24Wednesday方法描述每个任务要映射到具体的处理器，定位到每个任务要映射到具体的处理器，定位到运行机器上；运行机器上；任务数大于处理器数时，存在负载平衡和任务数大于处理器数时，存在负载平衡和任务调度问题；任务调度问题；映射的目标：减少算法的执行时间映射的目标：减少算法的执行时间并发的任务并发的任务不同的处理器不同的处理器任务之间存在高通讯的任务之间存在高通讯的同一处理器同一处理器映射实际是一种权衡，属于映射实际是一种权衡，属于NPNP完全问题；完全问题；7.5映射7.5.1方法描述7.5.2负载平衡算法7.5.3任务调度算法7.5.4映射判据国家高性能计算中心（合肥）442013/7/24Wednesday负载平衡算法静态的：静态的：事先确定；事先确定；概率的：概率的：随机确定；随机确定；动态的：动态的：执行期间动态负载；执行期间动态负载；基于域分解的：基于域分解的：递归对剖递归对剖局部算法局部算法概率方法概率方法循环映射循环映射7.5映射7.5.1方法描述7.5.2负载平衡算法7.5.3任务调度算法7.5.4映