文档介绍：并行算法的一般设计过程 PCAM设计方法1PCAM设计方法学设计并行算法的四个阶段划分(Partitioning)munication)组合(Agglomeration)映射(Mapping)划分:分解成小的任务,开拓并发性;通讯:确定诸任务间的数据交换,监测划分的合理性;组合:依据任务的局部性,组合成更大的任务;映射:将每个任务分配到处理器上,提高算法的性能。2PCAM设计过程3划分1方法描述 2域分解 3功能分解 4划分判据4划分方法描述充分开拓算法的并发性和可扩放性;先进行数据分解(称域分解),再进行计算功能的分解(称功能分解);使数据集和计算集互不相交;划分阶段忽略处理器数目和目标机器的体系结构;能分为两类划分:域分解(position)功能分解(position)5域分解划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据;将数据分解成大致相等的小数据片;划分时考虑数据上的相应操作;如果一个任务需要别的任务中的数据,则会产生任务间的通讯;6域分解示例:三维网格的域分解,各格点上计算都是重复的。下图是三种分解方法:实际上,分解沿X、Y、Z维及它们的任意组合都可以进行。开始时,应进行三维划分,因为该方法能提供最大灵活性。7域分解不规则区域的分解示例:8功能分解划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解;划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠,意味着要重新进行域分解和功能分解;功能分解是一种更深层次的分解。9功能分解示例1:搜索树搜索树没有明显的可分解的数据结构,但易于进行细粒度的功能分解:开始时根生成一个任务,对其评价后,如果它不是一个解,就生成若干叶结点,这些叶结点可以分到各个处理器上并行地继续搜索。示例2:气候模型10