并行算法设计

《并行算法设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、并行程序的设计方法余筱（华南理工大学电子与信息学院，广东广州510640）摘要：本文通过冇系统的方法来设计简单的并行算法，并可识别减低效率或可扩展性的设计缺陷。本文使用域分解和功能分解方法来剖析划分计算，并了解如何识别并执行木地和全局、静态和动态、结构化和非结构化及同步和界步通信结构。并且能够通过聚合來降低通信和执行成本的方法，并熟悉一系列负载平衡策略。关键词：并行算法剖析划分计算中国分类号：TP319.9DesignMethodofParallelProgramXiaoYu(SouthChinaUniversityofTechnology^schoolofelectronic

2、andinformationengineering；Guangzhou510000)Abstract:Thepaperdesignsimpleparallelalgorithmsinamethodicalfashionandrecognizedesignflawsthatcompromiseefficiencyorscalability.Itadoptspartitioncomputations,usingbothdomainandfunctionaldecompositiontechniques,andknowshowtorecognizeandimplementlocala

3、ndglobal,staticanddynamic,structuredandunstructured,andsynchronousandasynchronouscommunicationstructures.Thepaperalsousesagglomerationasameansofreducingcommunicationandimplementationcostsandshouldbefamiliarwitharangeofload-balancingstrategies-Keywords:ParallelAlgorithmPartitionComputing1.引言并

4、行算法设计并不仅限于一种方法的捉出，述需要一种创造性的整体思维模式，而这种思维模式可以从最大化考虑范围的研究方法入手，它捉供了评价选择方案的机制，并冃减少了错误抉择引起的回溯开销。本文所描述的就是这样一种方法，并冃根据这种并行算法设计方法搭建起框架，深入理解好的并行算法组成结构。本文通过冇系统的方法来设计简单的并行算法，并可识别减低效率或可扩展性的设计缺陷。本文使用威分解和功能分解方法来剖析划分计算，并了解如何识别并执行本地和全局、静态和动态、结构化和非结构化及同步和异步通信结构。并冃能够通过聚合来降低通信和执行成本的方法，并熟悉一系列负载平衡策略。2•设计并行算法2.1系统设

5、计大多数程序设计问题都有若干套并行解决方案。最佳解决方案可能不同于现有循序算法所建议的解决方案。本文描述的设计方法旨在创建一种探索性设计方式，其中会提早考虑诸如并发性等与计算机无关的问题，而且设计中计算机特定的方面延迟到设计流程的后期。此方法构成的设计流程分为四个不同阶段：剖析划分、通信、聚合及映射。在丽两个阶段，本文重点关注并发性和可扩展性,并设法找到具有这些特性的算法。在第三个和第四个阶段，转而关注区域和其它与性能相关的问题。图1说明了这四个阶段，并概括如2(1)剖析划分：要执行的计算和该计算所处理的数据被分解为若干小任务。将忽略诸如目标计算机中处理器数目等实际问题，并重点

6、关注对并行执行机会的发现。(2)通信：确定协调任务执行所需的通信，并定义适当的通信结构和算法。(3)聚合：评估设计的而两个阶段所定义的任务和通信结构的性能要求和实施成本。如有需要，任务会合并为较大任务，以提高性能或降低开发成本。(4)映射：给每项任务分配一个处理器以设法实现竞争性目标，即最大化处理器利用率并最小化通信成木。可静态地指定映射，或通过负载平衡算法在运行时确定。OOOOOOOOOOOOOOOOOOOOOOOOOOOO2-1PCAM：并行程序的设计方法从问题说明开始，先进行剖析划分，确定通信要求，聚合任务，最后将任务映射到处理器。此设计流程可通过以下方式生成动态创建及销

7、毁任务的程序：使用负载平衡方法控制任务到处理器的映射。或者，它可以是为每个处理器都创建一项任务的SPMD程序。虽然目标是生成SPMD程序，但和同的算法发现流程适用这两种情况，而口映射相关问题将提交到设计的聚合阶段。2.2剖析划分设计的剖析划分阶段旨在显示并行执行的机会。因而重点是定义大量的小任务，以阐述何为所谓的问题精密分解。止如细沙比一堆砖块更容易倾倒出一样,精密分解在潜在的并行算法方面具有最大灵活性。在后期的设计阶段，对通信要求、冃标结构或软件工程问题的评估可能会让我们预先了解此阶段所识