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

提交新文章

2009年04月12日 10:00


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

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

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

设计线程

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

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

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

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

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

      一个问题有许多分解方式: 按任务，数据，或者按数据流。下面的表总结了这些分解的形式。您将很快看到，这些不同分解形式对应了不同的编程行为。

分解类型

设计

评论

任务

不同的行为分配给不同的线程

通常在GUI应用

数据

多个线程对不同的数据集执行同样的操作

通常在音频处理，做图和科学编程

数据流

一个线程的输出是第二个线程的输入

需要特别关注消除开始和结束的延迟

主要的分解形式总结

任务分解

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

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

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

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

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

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

数据分解

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

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

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

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

      随着处理器核心数目的增加，数据分解使得任务处理规模增加。这允许在同样的时间内做更多的工作。

      举园丁的例子，假设有另外两个园丁加入了工作。相比分配所有四个园丁到一个地块工作，我们不如分配两个新的园丁去另一个地块，非常有效地增加我们总的任务处理量。

      假设两位新园丁和两位老园丁能够做同样多的工作，两个地块的大小也是一样的，我们已经在同样的时间内把工作量翻倍了。

数据流分解

      许多时候，当分解一个问题时，关键不是任务应该做什么事情，而是数据在不同任务中怎样传递。在这些情况下，数据流分解将问题按数据在任务中传递的方式来分解。

      生产者/消费者问题是数据流影响程序并行执行能力的著名例子。这里，一个生产者任务的输出，成为另一个消费者的输入。两个任务被不同的线程执行，直到生产者完成他的部分工作，消费者不能开始工作。

      依然引用园丁的例子，一个园丁准备工具，譬如他承担为割草机加油，清扫剪刀等类似的任务来提供这些工具给另两个园丁使用。直到这个准备步骤基本结束，其他园丁的园艺工作才能开始。

      由第一个任务引起的延迟为第二个任务产生一个暂停，在此之后两个任务才能并行运行。在计算机领域这样的模式经常发生。

     在常见的编程任务里，生产者/消费者问题在多个典型的场景发生。譬如，必须对读文档做回应的程序就符合这种场景：文件的输入/输出结果成为下一步可能被线程化的工作的输入。下一步直到读完或读到其他处理需要的足够信息才会开始执行。另一个编程的例子是分析：一个输入文件必须在后端操作之前被分析或者语义分析，譬如编译器的代码生成。

生产者/消费者问题有许多需要注意的方面：

1) 如果这种模式没有正确地执行，消费者和生产者间产生的依赖性会引起重大的延迟。一个性能敏感的设计需要充分理解依赖关系的性质以减小延迟的影响。这也是为了避免消费者线程空闲等待生产者线程的情况。

2) 在完美的情况下，生产者和消费者间的传递是完全"清洁"的，就像在文件分析器的例子中一样。输出是上下文相关的，消费者不需要知道生产者的任何事情。然而在很多时候，生产者和消费者并不享受如此干净的任务分割，安排他们间的互动需要非常仔细的计划。

3) 如果当生产者完全做好后消费者开始加工，那么当其他线程忙着工作时一个线程就保持空闲。这个问题破坏了一个并行处理的重要目标，那就是负载均衡以使得所有能用的线程保持忙碌。由于线程间的逻辑关系，要保持线程平等地被占用非常困难。

      下面，我们看看流水线模式，它允许开发者以可升级的模式解决生产者/消费者问题。

不同分解的含义

      不同的分解具有不同的优势。如果目标是使编程简便，任务能够清楚地按功能分割，那么任务分解通常更合适。

      数据分解增加了一些额外的代码级复杂度，因此他专供数据非常容易分解而性能又非常重要的情况使用。

      线程化程序的最常见原因就是性能。在这种情况下，分解方式的选择就更加困难。在许多情况下，选择依赖于问题的领域：一些任务明显更适合于其中一种分解方式。

      但是一些任务没有明显的偏向。譬如视频流中的图像处理。在帧与帧间没有依赖的格式，你需要作出分解模式的选择。他们应该选择任务分解么，那样一个线程解码，另一个线程配色，诸如此类？或者选择数据分解，每个线程做一帧上的所有工作，然后一起开始处理新的一帧？

      回到园丁的例子：如果两个园丁需要修整两块草坪和铲除两块花园的杂草，他们应该怎样工作？是应该一个园丁只修剪草坪，也就是他们选择基于任务的分解呢？还是两个人应该同时修剪草坪然后同时铲除杂草？

      在一些情况下，答案很快显现。例如当一个资源限制存在，譬如只有一个割草机。其它情况下每一个园丁都有一个割草机，答案只能通过仔细分析行为要素来得出。在园丁的例子中，任务分解看起来更好，因为如果只有一个割草机在使用，开始的割草时间就被节省了。

      最终，你通过仔细的计划和测试来为你的应用程序使用并行编程作出正确的选择。 根据经验估计在你决定并行程序设计时比标准的单线程编程中扮演更加重要的角色。

你将面对的挑战

      使用线程通过允许两个或多个行为同时发生使得你显著改进性能。然而，开发者不能不认识到线程增加了复杂性度量，需要细致的考虑来正确引导。

      这种复杂度源于程序中多于一个行为发生的自身性质。管理同步行为和他们可能的交互使你面对下面四种问题：

1) 同步是两个或多个线程协调他们行为的过程。譬如，一个线程在继续运行前等待另一个完成任务。

2) 交互代表与线程间交换数据相关的带宽和延迟问题。

3) 负载均衡表示任务在多个线程间的分配，因此他们都处理基本同样的工作量。

4) 可扩展性是当软件在更先进的系统上运行时高效利用许多线程的挑战。譬如，如果一个程序被编写来充分利用四核处理器，当它在一个八核处理器上运行时它是否能适当地扩展？

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

并行编程模式

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

      下面的表格显示了一些常见的并行编程模式和他们对应的上述分解类型。

模式

分解

任务级并行

任务

分离并战胜

任务/数据

几何分解

数据

流水线

数据流

波阵面

数据流

常见的并行编程模式

      在这部分，我们将提供每种模式及其适用的问题种类的简要概述，包括：

1) 任务级并行编程模式。在许多情况下，完成并行执行的最佳方法是直接关注任务本身。在这种情况下，任务级并行模式最合适。这种模式下，问题被分解成一组独立操作的任务。

通常移除任务间的依赖性或使用复制来分离依赖性是必要的。适合这种模式的问题包括线程间没有依赖性，或线程间的依赖性可从每一个线程中移除。

2) 分而治之模式。在分而治之模式中，问题被分成许多并行的子问题。每个子问题被单独解决。当每个子问题被解决时，结果合计到最后的结果中。因为每个子问题都能被单独解决，这些子问题有可能被并行执行。

分而治之的方法被广泛应用于诸如合并分类的算法。这些算法非常容易被并行化。这种模式很好地处理了负载均衡，这点对缓存的有效利用非常重要。

3) 几何分解模式。几何分解模式基于正在解决问题的数据结构的并行化。在几何分解中，每个线程负责操作数据块。这种模式可能适用于诸如热流和声波传播之类的问题。

4) 流水线模式。流水线模式的意思类似于一条工厂的产品装配线。这种寻找并发的方式使计算被分割成一系列阶段，每个线程在不同的阶段同时工作。

5) 波阵面模式。波阵面模式在处理二维网格中延对角线的数据元素时非常有用。如下图所示。

bozhenmian.bmp
波阵面数据模式

      上图中的数字解释了数据元素被处理的顺序。譬如对角线的元素包括数字3是独立于之前被处理的数字元素1和2的。

      上图中阴影中的数据元素表示数据已经被处理。在这种模式下，减小每个线程的空闲时间非常关键。负载均衡在此种模式中非常关键。

      更加详细的并行编程设计模式的介绍请参考"并行编程模式"(Mattson 2004) 一书。

*本文观点引自英特尔公司系统架构师Shameem Akhter和高级软件工程师Jason Roberts的文章