浅谈并行编程中的任务分解模式

浅谈并行编程中的任务分解模式

并行编程使用线程来使得多个操作能够同时运行。并行编程主要包括应用程序中线程设计，开发和部署以及线程间相互协调和各自的操作。

在下文中我们将讨论怎样分割适合线程化大小的编程任务来多任务化一个应用程序。设计线程

不熟悉并行编程的开发者通常对例如面向对象的传统的编程模式感到非常适应。在传统的编程模式下，程序以预先定义的起点开始运行，譬如main函数，然后接连地做完一系列任务。如果程序依赖用户交互，主要的工作代码通常被封装在一个处理用户事件的循环里。

从一个约定事件开始，譬如点击按钮，程序运行一段已经制定的顺序行为，最终以等待用户下个动作结束。

当设计这样的程序时，程序员喜欢一个相对简单的编程模式因为在任意一段给定的时间内只有一个事件发生。如果程序任务必须按某种方式顺序运行，程序员必须在这些事件上特意安排顺序。在这个过程的任一时刻，程序运行一步接着下一步，最终基于预先确定的参数到达一个预见的结果。

从这种线性的模式到并行编程模式，程序设计者必须重新思考程序的过程流。相比顺序执行序列限制，程序员应该识别出那些能被并行化的行为。

要这样做，他们必须把程序看作一组相互间有依赖关系的任务。把程序分解成一些独立的任务并识别这些任务间的依赖性。这个过程被称为分解。

一个问题有许多分解方式:按任务，数据，或者按数据流。下面的表总结了这些分解的形式。您将很快看到，这些不同分解形式对应了不同的编程行为。分解类型设计评论任务不同的行为分配给不同的线程通常在GUI应用数据多个线程对不同的数据集执行同样的操作通常在音频处理，做图和科学编程数据流一个线程的输出是第二个线程的输入需要特别关注消除开始和结束的延迟主要的分解形式总结任务分解

按功能分解一个程序被称为任务分解。这是一种实现并行执行最简单的方式。使用这种方法，每个任务被按目录分类。

如果它们中的两个能同时运行，它们会被程序员按此调度。以这种方式并行运行任务通常需要对每个函数做小量修改来避免冲突，并指出这些任务已经不再连续。

以园艺工作举例，任务分解会建议园丁按工作本身的属性分配任务：如果两个园丁到达一个客户家，一个修剪草坪，另一个铲除杂草。修剪草坪和铲除杂草是两个被分开的功能。

要完成这两个功能，园丁们需要确保他们之间相互协调，这样铲除杂草的园丁就不会坐在待修剪草坪的中间。

举个编程的例子，一个任务分解的典型案例是文字处理软件，譬如微软的Word。当用户打开一个很长的文档的时候，他（她）能够马上开始输入文字。当用户输入文字时，文档分页在后台发生，于是他（她）能够很容易地看到状态栏中页数的增加。

文档输入和分页是两个独立的任务，程序员按功能将它们分开来并行运行。如果程序员没有这样设计，用户将不得不在能够输入任何文字之前等待整个文档被分页。有些朋友可能回忆起这种现象在早期的个人电脑文字处理器中非常常见。数据分解

数据分解，也被认为是数据级并行，将任务按它们处理的数据进行分解，而不是按照任务本身的性质。使用数据分解的程序通常有许多线程在执行同样的任务，只是处理的数据项不同。

举个例子，假设在一个大的电子数据表里计算值。相比一个线程执行所有的计算，数据分解会建议有两个线程，每个执行一半的计算量，或者n个线程执行1/n的工作量。

如果园丁应用数据分解来分解他们的任务，他们两个会同时修剪一半的草坪，然后两个人分别铲除一半的杂草。在计算领域，决定哪一种分解形式更高效取决于系统的限制。

举例说，如果需要修剪草坪的地块非常小以至于没必要有两个人来修剪草坪，修剪草坪这个任务最好只被分配给一个园丁做，那么任务分解在这一步是最好的选择。数据分解或许适用于其它的任务序列，譬如当修剪草坪完成后，两个园丁并行地来铲除杂草。

随着处理器核心数目的增加，数据分解使得任务处理规模增加。这允许在同样的时间内做更多的工作。3)负载均衡表示任务在多个线程间的分配，因此他们都处理基本同样的工作量。4)可扩展性是当软件在更先进的系统上运行时高效利用许多线程的挑战。譬如，如果一个程序被编写来充分利用四核处理器，当它在一个八核处理器上运行时它是否能适当地扩展？

上述每个问题都必须被仔细地处理来最大化程序的性能。并行编程模式

对于多年编写面向对象程序的程序员，他们使用设计模式来逻辑地设计他们的应用程序。并行编程和面向对象编程没有什么不同，并行编程问题通常对应于许多知名的编程模式之一。

下面的表格显示了一些常见的并行编程模式和他们对应的上述分解类型。模式分解任务级并行任务分离并战胜任务/数据几何分解数据流水线数据流波阵面数据流常见的并行编程模式

在这部分，我们将提供每种模式及其适用的问题种类的简要概述，包括：1)任务级并行编程模式。在许多情况下，完成并行执行的最佳方法是直接关注任务本身。在这种情况下，任务级并行模式最合适。这种模式下，问题被分解成一组独立操作的任务。通常移除任务间的依赖性或使用复制来分离依赖性是必要的。适合这种模式的问题包括线程间没有依赖性，或线程间的依赖性可从每一个线程中移除。2)分而治之模式。在分而治之模式中，问题被分成许多并行的子问题。每个子问题被单独解决。当每个子问题被解决时，结果合计到最后的结果中。因为每个子问题都能被单独解决，这些子问题有可能被并行执行。分而治之的方法被广泛应用于诸如合并分类的算法。这些算法非常容易被并行化。这种模式很好地处理了负载均衡，这点对缓存的有效利用非常重要。3)几何分解模式。几何分解模式基于正在解决问题的数据结构的并行化。在几何分解中，每个线程负责操作数据块。这种模式可能适用于诸如热流和声波传播之类的问题。4)流水线模式。流水线模式的意思类似于一条工厂的产品装配线。这种寻找并发的方式使计算被分割成一系列阶段，每个线程在不同的阶段同时工作。5)波阵面模式。波阵面模式在处理二维网格中延对角线的数据元素时非常有用。如下图