并行算法设计

《并行算法设计》由会员分享，可在线阅读，更多相关《并行算法设计（6页珍藏版）》请在装配图网上搜索。

1、并行程序的设计方法余筱(华南理工大学 电子与信息学院，广东 广州 510640)摘要：本文通过有系统的方法来设计简单的并行算法，并可识别减低效率或可扩 展性的设计缺陷。本文使用域分解和功能分解方法来剖析划分计算，并了解如何 识别并执行本地和全局、静态和动态、结构化和非结构化及同步和异步通信结构。 并且能够通过聚合来降低通信和执行成本的方法，并熟悉一系列负载平衡策略。 关键词：并行算法 剖析划分 计算中国分类号：TP 319.9Design Method of Parallel ProgramXiao Yu(South China University of Technology, school

2、 of electronic and information engineering； Guangzhou 510000)Abstract: The paper design simple parallel algorithms in a methodical fashion and recognize design flaws that compromise efficiency or scalability. It adopts partition computations, using both domain and functional decomposition techniques

3、, and knows how to recognize and implement local and global, static and dynamic, structured and unstructured, and synchronous and asynchronous communication structures. The paper also uses agglomeration as a means of reducing communication and implementation costs and should be familiar with a range

4、 of load-balancing strategies.Key words: Parallel Algorithm Partition Computing1.引言并行算法设计并不仅限于一种方法的提出，还需要一种创造性的整体思维模 式，而这种思维模式可以从最大化考虑范围的研究方法入手，它提供了评价选择 方案的机制，并且减少了错误抉择引起的回溯开销。本文所描述的就是这样一种 方法，并且根据这种并行算法设计方法搭建起框架，深入理解好的并行算法组成 结构。本文通过有系统的方法来设计简单的并行算法，并可识别减低效率或可扩 展性的设计缺陷。本文使用域分解和功能分解方法来剖析划分计算，并了解如何 识别并

5、执行本地和全局、静态和动态、结构化和非结构化及同步和异步通信结构。 并且能够通过聚合来降低通信和执行成本的方法，并熟悉一系列负载平衡策略。 2.设计并行算法2.1系统设计 大多数程序设计问题都有若干套并行解决方案。最佳解决方案可能不同于现 有循序算法所建议的解决方案。本文描述的设计方法旨在创建一种探索性设计方 式，其中会提早考虑诸如并发性等与计算机无关的问题，而且设计中计算机特定 的方面延迟到设计流程的后期。此方法构成的设计流程分为四个不同阶段： 剖 析划分、通信、聚合及映射。在前两个阶段，本文重点关注并发性和可扩展性， 并设法找到具有这些特性的算法。在第三个和第四个阶段，转而关注区域和其它

6、与性能相关的问题。图 1 说明了这四个阶段，并概括如下：（1）剖析划分：要执行的计算和该计算所处理的数据被分解为若干小任务。将 忽略诸如目标计算机中处理器数目等实际问题，并重点关注对并行执行机会的发 现。（2）通信：确定协调任务执行所需的通信，并定义适当的通信结构和算法。（3）聚合：评估设计的前两个阶段所定义的任务和通信结构的性能要求和实施 成本。如有需要，任务会合并为较大任务，以提高性能或降低开发成本。（4）映射：给每项任务分配一个处理器以设法实现竞争性目标，即最大化处理 器利用率并最小化通信成本。可静态地指定映射，或通过负载平衡算法在运行时 确定。OO QO-.-OO 0000 0 2 0

7、 0 0 0000 -.50002-1 PCAM:并行程序的设计方法从问题说明开始，先进行剖析划分，确定通信要求，聚合任务，最后将任务 映射到处理器。此设计流程可通过以下方式生成动态创建及销毁任务的程序:使 用负载平衡方法控制任务到处理器的映射。或者，它可以是为每个处理器都创建 一项任务的 SPMD 程序。虽然目标是生成 SPMD 程序，但相同的算法发现流程适 用这两种情况，而且映射相关问题将提交到设计的聚合阶段。2.2 剖析划分设计的剖析划分阶段旨在显示并行执行的机会。因而重点是定义大量的小任 务，以阐述何为所谓的问题精密分解。正如细沙比一堆砖块更容易倾倒出一样， 精密分解在潜在的并行算法方

8、面具有最大灵活性。在后期的设计阶段，对通信要 求、目标结构或软件工程问题的评估可能会让我们预先了解此阶段所识别的并行 执行机会。然后，我们重新访问原始剖析划分并聚合任务，以增加其大小或粒度。适宜的剖析划分可分为更小的部分，即与问题相关的计算和该计算所处理的 数据。程序员在设计剖析划分时，通常先会关注与问题相关的数据，然后确定适 用该数据的剖析划分，最后确定计算与数据的关联方式。此剖析划分方法称为域 分解。替代方法（即先分解要执行的计算，然后处理数据）称为功能分解。这些 是补充方法，可应用于一个问题的不同方面乃至同一问题，以便获得替代并行算 法。在设计的第一个阶段，我们设法避免计算和数据的重复，

9、即设法定义将计算 和数据划分为不相交集的任务。与粒度一样，我们以后可能会重新访问这一设计 方面。若重复计算或数据可让我们减少通信要求，这样做就是值得的。2.2.1 域分解在针对问题剖析划分的域分解方法中，我们先设法分解与问题相关的数据。 如有可能，我们会将这些数据分为大小几乎相同的更小部分。下面，我们会剖析 划分要执行的计算，而且一般采用使各项操作与其操作的数据关联的方式。这种 剖析划分会产生大量任务，而每项任务都包含某些数据和针对该数据的操作集。 一项操作可能需要来自多项任务的数据。在这种情况下，需利用通信在任务间移 动数据。在设计流程的下一阶段会满足此要求。图 2.2 三维网格的域分解分解

10、的数据可能是程序的输入、程序所计算的输出或程序所维护的中间值。 剖析划分可能视数据结构的不同而异。适宜的经验法则将先用于最大的或最常访 问的数据结构。不同的计算阶段可能会对不同的数据结构进行处理，或要求对相 同的数据结构进行不同的分解。在这种情况下，我们会单独处理每个阶段，然后 确定如何制定分解和并行算法以使各个阶段结合在一起。2.2.2 功能分解功能分解表示通过其他的补充性方法考虑问题。此方法首先关注于要执行的 计算，而非该计算所处理的数据。若成功地将计算分为不相交的任务，则会继续 检查这些任务的数据要求。这些数据要求可能不相交，其中剖析划分是完整的。 或者，它们可能明显重叠，此时将需要大量

11、通信以避免数据重复。这通常提示应 考虑采用域分解方法。虽然域分解方法构成了大多数并行算法的基础，但功能分解作为考虑问题的 不同方法也非常有用。有鉴于此，在探讨可能的并行算法时，应考虑到它。对要 执行的计算的关注有时会揭示问题的结构，并因此会提供优化机会，而这些机会 在单纯数据研究中是不明显的。2.3 通信 剖析划分任务的意图是并行处理这些任务，但一般情况下，这些任务都是独 立执行的，单个任务中的计算可能需要其他任务中的数据，为了执行单个任务的 计算就必须要求任务之间能够传输数据，通信阶段就是基于这个目的而设计的。 两个任务之间的通信需要一条连接任务的信道来提供信息的传送和接收。因此， 该算法的

12、通信定义为两个阶段：定义连接任务的信道结构和指定待传送的数据。 信道定义包括计算开销和传送数据的物理开销，所以要避免不必要的信道和通信 操作，并且通过给任务分配通信操作和重组并行执行的通信操作来优化性能。在域分解问题上很难决定通信要求，前一阶段把数据剖析划分为不相交的子 集然后把任务操作所需的数据联系在一起，但是一些需要很多任务产生的数据的 操作就无法执行，这时候就需要通信来连接不同任务的数据，有效的重组通信十 分具有挑战性，有时即使简单的分解也会导致复杂的通信结构。相反，功能分解 的通信要求就很直接，只要求任务之间的数据传输，例如基于功能分解的气候模 型，每个模型要素都可视为要通过域分解来并

13、行化的单独任务。箭头代表计算过 程中组件间的数据交换： 例如，大气模型可生成海洋模型所用的风速数据，而 海洋模型则生成大气模型所用的海面温度数据。图 2.3 气候模型的功能分解可以从四个不同的角度来划分通信阶段，如下所述：1）局部通信：每个任务和其他的部分任务通信； 全局通信：每个任务和几乎所有的任务通信。2）规则通信：任务之间的通信形成固定的结构； 不规则通信：任务之间的通信结构是任意的。3）静态通信：通信双方不随时间改变； 动态通信：通信结构随着执行产生的数据而改变并且动态变化着4）同步通信：发送方和接收方协同操作； 异步通信：接收方获取数据无需与发送方协同。2.4 聚合第三个阶段聚合是抽

14、象到具体的过程，前两个阶段剖析划分和通信都是为了 得到一种能够在某些并行处理机上有效计算的算法，而在这个阶段考虑的是把划 分的某些任务聚合成单个大任务是否有效，是否值得复制数据和通信。聚合后的 任务数尽管减少了还是要比处理机的数量要多，由于所有的任务最终都是要映射 到处理机，所以还是要继续抽象化把任务数减少到和处理机的数量刚好相同。然 后要考虑任务粒度的问题，通过增加任务粒度和重复计算可以减少通信成本，然 而保持映射和扩展的灵活性可以降低软件工程的成本，这两者是相互冲突的，所 以要找到一个平衡点来权衡他们。图 2.4 聚合举例2.5 映射 并行算法设计的最后一个阶段是确定任务在哪里执行，目的是

15、要在可扩展的 并行处理机上实现映射机制并且最小化总的运行时间，可基于两种方法实现：在 不同的处理器上执行并发的任务以提高并行性；在同一处理器上执行高通信的任 务以提高局部性。这两种方法是相冲突的，故需要在设计上折中考虑。图 2.5 相同计算量和通信量的网格映射许多算法采用域分解的方法把任务划分为相同大小，通信量也相同的任务， 然后就可以按照图 2.5 的方法直接映射，把任务聚合到相同的处理机上，这样可 以减少处理机内部的通信数。在复杂的域分解算法中，每个任务涉及大量的工作， 通信模式也是不规则的，聚合和映射的方法对于这种情况就不怎么适用，因此就 需要负载平衡算法来确定更有效的聚合和映射。执行算

16、法所需的时间必须要和减 少的执行时间权衡，负载平衡算法比开发结构的方法开销小。在程序执行的时候，最复杂的是任务数，计算量和通信量都是动态变化的， 可以采用动态平衡算法来决定新的聚合和映射，因为负载平衡算法在程序执行的 过程中可以多次采用，局部算法也不需要计算状态的整体知识。基于功能分解的 算法经常需要许多短期任务的计算，这些任务只在执行的开始和终止过程中和其 他任务协调，这种情况就需要任务调度算法，把任务分配到空闲的处理机上。 3.小结本文介绍了一种四步并行算法设计方法，用于问题说明和处理的初始阶段。 首先把一个问题剖析划分为许多个小任务，可以采用与分解和功能分解的方法来 剖析划分，然后根据任务执行所需的数据来组织通信，主要划分为局部和全局通 信，静态和动态通信，规则和不规则通信以及同步和异步通信结构，接着采用聚 合来减少通信和处理开销，必要的时候保持其灵活性，最后把任务映射到处理机 上，目的是减少总运行时间，负载平衡和任务调度都能用来改善映射质量。 参考文献：1 Foster,lan T.Designing and Building Parallel Programs. Boston: Addison Wesley,1995.2 www-unix.mcs.anl.gov/dbpp