多核时代：并行程序设计探讨（8）——任务分解模式Task Decomposition

Task Decomposition

从本章开始我们就正式来介绍每个模式了，参考设计模式的做法，每个模式我们都按照如下的内容进行介绍：问题（Problem）、上下文（context）、考虑因素（Forces）、解决方法（Solutions）。至于样例，就请各位看官直接看原文了。

1.1 问题

如何将待解决的问题分解为能够并行运行的“任务（task）”？

“任务”这个词本身是比较概念化的，没法精确衡量，因此分解得是否合理、是否优秀就要看设计师的水平了，但以我个人的经验，分解时至少要保证任务是一个级别的。例如建房子，你可以分解为设计、建造、装修三个任务，建造又可以分为打地基、框架建造、砌墙（仅供举例用，专业人士勿笑）等任务，但不要把设计和打地基甚至安装煤气管道都算作一个级别的任务。

1.2 上下文

所有的并行算法设计都开始于同一个起点：对问题很好的理解。设计师必须理解问题中计算强相关的部分、关键数据结构，以及数据如何用作问题的解决的。

接下来就是识别出组成问题的任务、以及任务包含的数据，本质上来说每个并行算法都包含一组能够并行运行的任务，关键的挑战就在于找到这些任务然后设计出一个算法让这些任务并行运行。

有的情况下，问题本身就天然的分解为一组相互独立的任务，这种情况就比较容易采用基于任务分解（task-based decomposition）的方式开始进行分解；而有的情况下，问题很难分解为独立的任务，这种情况下采用基于数据分解（Data-Based decomposition）是更好的选择。

通常情况下并不是很容易看出应该采用哪种方法，这个时候就要两种都考虑。但无论哪种情况，最后都要输出能够并行运行的任务。

1.3 考虑因素

1.3.1 灵活

此时考虑灵活性主要是为了能够让设计能够满足不同的实现需求，这里的实现就是具体采用的技术，例如采用Java编程，采用多CPU的小型机运行等，如果客户不强制要求，在这个阶段就不要限制这些。当然如果问题里面本身已经包含了这种实现，那就必须考虑这种实现的限制了。例如客户要求只能运行在小型机上面，那么设计的时候就需要考虑小型机的特点对人物分解的影响了。

1.3.2 有效

并行程序只有在随着并行计算机的规模增大时效率能够按比例增长才有意义。对于任务分解来说，这就意味着我们需要足够的任务来使得所有计算机都处于忙碌的状态。

通过使每个任务有足够的工作（Work）来弥补管理任务间的依赖带来的效率损失才能达到这点。当然，效率提升会带来灵活性的降低。

1.3.3 简单

再怎么好的程序也要人维护吧，所以再怎么复杂怎么好都要考虑怎么维护。

以上三种因素互相制约，具体怎么平衡，还是要看设计师的水平。

1.4 解决方法

任务分解的两个关键点：

1、保证任务间足够独立，这样花费很小的代价就可以管理任务间的依赖关系；

2、保证任务能够均匀的分布在所有的可执行单元上，这样能够充分利用系统性能；

任务分解的步骤：

1）首先识别尽可能多的任务，因为识别出很多任务后再合并比识别很少的任务再分解要容易得多。

2）识别出任务后，接下来就要分析任务中包含的数据的分解了，数据的分解在下一篇介绍。

那么，哪些地方能够发现任务呢？

1）函数调用：调用函数的地方就是一个任务，如果每个函数调用都作为一个任务，则这种分解方式又叫“函数分解”。这里的函数是算法级的，不是代码级的，例如书中给的样例采用蒙特卡罗算法来进行图像分析合成，其中蒙特卡罗算法就是一个函数，也可以理解为功能（英文都是function）。ss

2）算法循环：另外一个能够找到函数的地方就是算法中的循环了。如果很多循环彼此独立，这样可以采用每个循环一个任务的分解方法，这种分解方法又叫做“循环分解”。

3）数据分解：若一个大的数据结构的不同部分分别被更新，则可以根据不同的数据块来划分任务，这种分解方法又叫做“数据分解”，后面会详细讲解数据分解的方法。