并行化程序设计的四步走

《并行化程序设计的四步走》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、并行化程序设计的四步走并行化程序设计的四步走SelwynYou(Intel)星期四,21/05/2009-11:24发布多核计算平台的普及化使得并行（Parallel）或者并发（Concurrent）程序设计（这里不妨称它们为并行化程序设计）成为一种编程技术主流。其实并行计算的软件技术早已存在了几十年，然而其原来主要服务于高性能计算一类的应用，所以并行化编程一直也都为阳春白雪的光环笼罩。现在谈到多核编程，讨论较多的是各种软件或者并行编程模型的使用；对于初学者而言却仍可能难以循其径而入。其实，并行化的程序设计

2、是有章可循的。按照开发流程的顺序，可以把并行化程序设计分为以下四个阶段：1.可行算法（解决方案）的描述与分析2.工作分解（Decomposition）--依赖性和同步与通信开销分析3.选择编程（实现）模型4.性能检查及优化在设计的初始阶段，开发者应当针对要解决的问题先找到一个可行的解决方案或者算法。比如，排序问题的解决方案有气泡排序，快速排序，二叉树排序等已知可行的方法可以作为并行化的基础算法。而在进行具体的并行化设计之前，有一个很重要的分析（或者评估）要做，那就是并行化的必要性分析；即，应该估计一下目标问

3、题的计算量。如果需要解决的问题计算量并不是很大，比如只需要对30个整数进行排序，即使采用传统串行程序也不会占用太多时间，那么就可能没有为之设计并行化程序的必要，因为并行化也是要付出其它计算的代价的。另外，基础算法的选择也很有讲究。有些算法本身就不具备太多的并行性，比如图论算法中最小生成树/MinimumSpanningTree（MST）的Kruskal算法；而有些算法则具有很好的可扩展性（Scalability），比如MST的Boruvka算法（关于MST算法并行化的例子可参见ISN学术社区课件）。为确定算

4、法的并行性，一般需要借助一些理论和工具的帮助。Amdal'slaw是大多数设计者所采用的估计并行化加速比上限的定理；而Gustafson'slaw则是分析并行程序可扩展性的有力理论指导。而为了能够使用这些定理给出指导，还需要一些软件工具（ProfilingTools）的辅助，从而确定理论所需的一些参数（如串行程序的并行量p）。提供这一种功能的常用的工具有Intel性能分析器Vtune，Windows里面的PerfMon等。对于理论和软件工具的使用可以参照学术社区的课件。基础算法的确定需要开发者结合下一步进行

5、综合考虑，反复尝试几次。当候选的基础算法确定后，开发人员就需要进行一个并行化编程中非常重要的步骤--工作分解（Decomposition）。分解是对基础算法分析，将之分解为若干相对独立的部分（或者操作）；进而可以通过后面一步（选择适当编程模型）把这些相对独立的部分分配到多个执行（处理）单元执行。工作分解的手段一般可以分为任务分解（TaskDecomposition）和数据分解（DataDecomposition）。任务分解就是把一个算法按照操作的相关性（依赖性）分解为若干可以同时执行的子任务，比如下图中的函

6、数h，q和r或者s是可以并行的。数据分解则是将一个比较大的待处理的数据集，如数组分割为若干子集，从而可以的不同部分的成员实施同时的运算或操作。此外还有一种常用的工作分解方法是流水线（Pipeline）方式，其基本原理是仿照生产流水线的操作，把一个大任务分解为若干紧密相连的阶段，从而提高每个阶段工作单元的运行效率。学术社区的在线课件有对工作分解的具体讲解，这里就不再赘述。对于分解方法的应用，需要开发者进行大量的分析实践，积累经验，提高分解的正确性和效率；另一方面，也还是有一些通用的经验可以借鉴。比如，算法中有

7、循环体的，一般意味着可能可以采用数据分解，将不同的迭代（如果它们之间没什么依赖性的话）划分为不同的执行子集，分配给不同的线程或者进程执行；类似的，过程和函数是程序员把通用操作打包，从而便于阅读和维护有效手段，这也就暗示了函数体也是很好的数据分解的候选人；而在媒体流处理这类应用中，流水线是常用的分解手段。有心的读者可能注意到我们前面介绍分解方法是多次提到相关性或者依赖性（Dependence）。这是在进行工作分解时要面对的一个重要指标，因为分解部分之间的依赖性直接影响它们的可并行性。比如下图中，我们使用依赖性

8、图（DependenceGraph）进行分析，就会发现各个循环迭代中对于变量a[i]具有读写依赖，那么这个循环体是不能被通过数据分解而并行化的，从而这种分解方案是不可行的（当然也有一些依赖性通过优化手段可以去除，由于篇幅的缘故，关于依赖性分析请参照学术社区的课件）。应当指出的是，大多数的应用（算法）是不可能分解为完全独立的部分，这些部分多少都需要一定的依赖和协调来完成工作。分解所要达到的目的应该是把基础算法分解为