串行程序的并行划分算法研究

卢成浪

(温州大学瓯江学院，浙江温州 325035)

串行程序的并行划分算法研究

卢成浪

(温州大学瓯江学院，浙江温州 325035)

给出了一个将串行程序进行并行划分的算法，并对算法的有效性进行了理论分析和实验验证．结果表明，该算法能有效地并行划分串行程序，提高串行程序的执行效率．

串行程序；并行划分模型；计算复杂度；相关度

并行算法的设计分为四个阶段：任务划分（Partitioning）、通信分析（Communication）、任务组合（Agglomeration）和处理器映射（Mapping），统称PCAM设计过程[1]．在PCAM过程中，首要问题是如何把任务划分为若干个功能独立且计算量均衡的子模块[2]，从而有效减少任务的并行执行开销．文献[2-6]对这个问题进行了研究，提出了一些有效的串行程序并行划分方法，其中最具代表性的为 RPDMA算法[4-5]，它是以程序块之间的相关度尽可能小为准则对串行程序进行并行划分的．但是，假如由RPDMA得到的并行划分模型为若存在程序块其计算量远大于其它的程序块，则根据Ω设计得到的并行程序的执行开销受iP支配，若再考虑通信等开销，那么该并行程序的执行开销将大于原有的串行程序，这种情况下采用RPDMA算法是无法提高串行程序的执行效率的．有鉴于此，本文改进了RPDMA算法，引入了程序块计算复杂度等概念，并据此给出了新的串行程序并行划分算法，称作PPA算法．

1 并行划分模型

文献[6]定义了程序块之间的控制相关∇C、流相关∇F、输出相关∇O和反相关∇U等概念．本文基于以上这些概念，定义一个新的并行划分模型，该模型主要涉及程序块相关、相关度和计算复杂度等概念．

定义1 若Θ表示程序块的集合，则Θ上的相关二元关系∇定义如下：

若任意程序块的对偶∈∇，则称作A相关于B，并记作A∇B．

定义1表明：任意两个串行程序块之间存在相关关系，当且仅当这两个程序块之间存在控制相关关系、流相关关系、输出相关关系或反相关关系．

定义2表明：任意两个串行程序块的相关度不仅与它们的输入输出集有关，并且还与它们之间的控制相关度有关．采用基本程序块的相关关系（即定义1）来划分串行程序块，很难将串行程序块划分为多个可并行的程序块．考虑基本程序块之间总是存在相关关系，本文引入了程序块相关度的概念，这样，在进行并行划分时，不要求程序块之间的相关度为零，只要它们之间的相关度足够小（小于一个给定的阈值），就可对它们进行划分．

定义3 若Q为串行程序语句的集合，且P⊆Q，则程序块P的计算复杂度δ定义为：

为了更好地衡量串行程序块的计算复杂度，定义3将程序块中的基本语句划分为三类：基本语句、循环语句和函数调用语句，然后采用不同的方法来分别计算这三类语句的复杂度．对于基本语句，为方便处理，本文把它的计算复杂度简单地设定为一个常数（称作计算量常数）；对于循环语句，其计算复杂度被设定为计算量常数与循环次数的乘积；对于函数调用语句，它的执行将引入一个新的程序块，该新程序块也是由基本语句、循环语句和函数调用语句组成，所以其计算复杂度可以由定义3递归地进行计算．串行程序块的所有语句计算复杂度的累加和构成该串行程序块的计算复杂度．

定义4 程序块集合Θ的并行划分模型Ω是集合Θ上的一个划分，并且

其中，ξ为计算复杂度上限阈值，ζ为相关度上限阈值．

定义4表明：在并行划分模型Ω中，任意两个基本程序块均不相关或相关度低于给定的相关度上限阈值．也就是说，对于Ω中任意基本程序块若其计算复杂度高于给定的复杂度上限阈值，则该程序块必不可再次划分为两个相关度小于相关度上限阈值的子程序块．因此，并行划分模型Ω综合考虑了程序块的相关度和计算复杂度，其目标是，在保证各程序块的计算复杂度基本平衡的条件下，使各程序块之间的相关度尽可能小．把Ω中的各程序块调度到不同的处理机上并行处理，以提高任务的执行效率．

性质1 程序块集Θ的并行划分模型Ω满足以下性质：并行划分模型的该性质保证了串行程序的任何一个子程序块不会被执行多于一次，也保证了程序的每一个子程序块都可以被执行．

2 并行划分算法

根据本文第一部分所描述的并行划分模型，我们可以设计对应于该模型的并行划分算法，并称之为PPA算法．PPA算法的输入是一个串行程序P，而输出是并行划分模型Ω．PPA算法与复杂度上限阈值ξ和相关度上限阈值ζ相关．复杂度上限阈值ξ限定了程序块的最大允许复杂度，如果程序块的复杂度大于ξ，则该程序块需要再次划分．相关度上限阈值ζ限定了程序块允许划分的最大相关度，如果两个程序段的相关度大于ζ，则这两个程序段只能属于同一程序块而不允许划分．

PPA算法的主要思路是把划分后的程序段之间的相关程度转化成为各个节点之间的通信，而通信是并行处理的瓶颈，PPA的目标是尽量降低各个节点之间的通信量，并同时考虑各节点的计算量，尽量均衡各节点的计算复杂度．为此，PPA算法可以简要描述如下：

1）由给定的串行程序P，生成一个基本程序块的集合．

2）根据各程序块之间的相关性生成一个带权图G，图的节点是程序块，图的任意边AB的权表示基本程序块A和B之间的相关度．

3）找出G中权最小的边，然后让每一条边的权都减去该边的权．如果产生的新图是非连通图，则表明串行程序可以划分为两个或两个以上的带有一定相关性的子程序．如果新图是连通图，那么再按照上述的方法进行划分，直到产生的新图为非连通图．

4）计算得到的划分的各程序块的计算复杂度．如果各程序块的计算复杂度均小于ξ，则可以认为划分合理．否则，重新划分计算复杂度大于ξ的程序块．在划分程序块时，如果发现两个程序段的相关度大于ζ，则不再划分这两个程序段．直到所有计算复杂度大于ξ的程序块都被处理完毕．

重新计算划分模型Ω的各程序块的计算复杂度，如果仍有程序块的计算复杂度大于ξ，则认为该串行程序并行化代价太大，从而不能并行化．

更加具体的PPA算法描述如下所示：

算法：PPA

输入：一个串行程序P和复杂度上限阈值ξ及相关度上限阈值ζ

输出：并行划分模型Ω

据以上算法描述，若以n表示输入串行程序的基本程序块数，经过PPA算法并行划分后的基本程序块数为|Ω|，则PPA算法的计算时间复杂度为：

3 实验比较

下面将通过实验来检查PPA算法对串行程序的并行划分效果．实验采用PPA算法与传统的RPDMA算法相比较的方式进行．步骤简要如下：

7）根据步骤5）和步骤6）记录的运行时间绘图，见图1．

图1 程序运行时间比较Fig 1 Comparison of Program Running Time

通常，根据RPDMA算法得到的并行划分模型Ω的基数大于1，并保证各基本程序块之间的相关度尽可能小．但RPDMA算法的缺点也是明显的，如基本程序块的计算量相差很大，会导致并行程序加速比很低．

从图1可以看出，相比于原有的串行程序，由RPDMA得到的并行划分模型的加速比改善效果有限．此外，对于有些并不能并行化或者需要花费巨大的代价才能实现并行化的串行程序，RPDMA算法仍能给出其并行划分结果，这是有误导性的，会导致并行划分后的效果更差（见图1的第3次实验）．

从图1还可以看出，通过并行划分，PPA算法能够有效地提高串行程序的执行效率．这是因为，由PPA算法得到的并行划分模型Ω，各程序块的计算复杂度都不超过ξ，这保证了各程序块的计算量相对均衡，有效地弥补了RPDMA算法的缺陷，提高了并行划分模型的正确性．此外，通过调整复杂度上限参数ξ和相关度上限参数ζ，PPA算法能完全兼容RPDMA算法．

4 结束语

本文提出了一个串行程序并行划分算法（PPA），它综合考虑了程序块的相关度和计算量两个因素，得到的并行划分模型有更好的效果．与传统的RPDMA算法相比，该算法能对串行程序进行更有效的并行划分，且拥有良好的时间复杂度．

[1] Lin C, Synder L. 并行程序设计原理[M]. 陆鑫达, 林新华, 译. 北京: 机械工业出版社, 2009: 101-195.

[2] 黄其军, 杨建武, 余华山. 基于规范划分集的并行循环计算划分[J]. 软件学报, 2003, (3): 75-82.

[3] 严胜祥, 吴绍春, 吴耿锋. 一种基于纵向划分数据集的并行决策树分类算法[J]. 计算机工程与科学, 2004, (7): 85-92.

[4] 江文毅, 庞丽萍, 高兰, 等. 串行程序的并行划分算法研究[J]. 华中科技大学学报: 自然科学版, 2000, (12): 30-32.

[5] 刘键, 谢卫, 朱晓梅, 等. 一种关于Do-loop并行划分的新观点与新方法[J]. 计算机学报, 1999, (7): 520-530.

[6] 张宇亮, 张立臣, 李代平. 并行算法的任务粒度与映射方法的分析[J]. 计算机工程与应用, 2005, (20): 45-47.

Study on Parallel Partitioning Algorithm for Serial Program

LU Chenglang
(Oujiang College, Wenzhou University, Wenzhou, China 325035)

An effective parallel partitioning algorithm for serial programs was offered in this paper. Then theoretical analysis and experiment were carried out to validate the validity of the algorithm. Results showed that the algorithm is an effective one for partitioning serial programs and improving execution efficiency of serial programs.

Serial Program; Parallel Partitioning Model; Computational Complexity; Correlation

TP301.6

：A

：1674-3563(2010)04-0021-06

10.3875/j.issn.1674-3563.2010.04.005 本文的PDF文件可以从xuebao.wzu.edu.cn获得

(编辑：王一芳)

2009-12-17

温州大学瓯江学院教师科研项目(JSKY09016)

卢成浪(1982- )，男，浙江苍南人，助教，硕士，研究方向：并行程序设计