串行程序的并行化处理
关键词：并行 DAG 数据依赖 串行程序 并行划分模型 等价关系
论文摘要： 目前在并行计算研究领域中很大一部分工作是将串行程序并行化，本文根据题目的要求，在合理的假设下，首先发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务（DAG）图，论文分析了串行程序中存在的数据依赖关系，并以此为根据，提出了一种由现有的串行程序构造对应的并行任务（DAG）图的算法，然后再对剩下的串行程序分段，提出并行划分模型，基于这种模型提出了一种并行划分算法PDMA；并根据程序段的相关程度提出了一种对PDMA进行改进的并行划分算法RPDMA。然后再通过一个串性程序的实例，运用此方案对其进行运算，最后对串行程序运算下的时间复杂度和进行此方案运算下的时间复杂度进行比较，得出此方案的优越。
1.问题的重述
并行计算是将一个计算任务分摊到多个处理器上并同时运行的计算方法。由于单个CPU的运行速度难以显著提高，所以计算机制造商试图将多个CPU联合起来使用。在计算机上早已采用专用的多处理器设计，台式机和笔记本电脑现在也已广泛地采用了双核或多核CPU。双核CPU从外部看起来是一个CPU，但是内部有两个运算核心，它们可以独立进行计算工作。在同时处理多个任务的时候，多核处理器可以地将不同的任务分配给不同的核心。最容易被并行化的计算任务称为“易并行”的，它可以直观地立即分解成为多个独立的部分，并同时执行计算问题。
要求：
（1）运行一个以常规的串行代码写成的程序时，如何将计算任务拆分成多个部分并分解到多个核心上同时运行。
（2）建立合理有效的模型，并依据模型对现成的串行算法进行处理。将能够使用双核心并行处理的部分分解开，并分配到两个核心上同时运行。以期达到比单核CPU处理更快速的目的。
2.模型的假设
1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。
2.对算法的时间复杂度并不考虑其精确度量,而只是关心其量级
3.双核及多核CPU在运算时,互不干扰.
4.设文中的算法最终得到的DAG图中消除了原有的反依赖和输出依赖.
3.问题分析
由于单个CPU的运行速度难以显著提高，所以现在广泛采用了双核或多核CPU,如何将一个常规的串行程序分解成两部分，使之能够同时采用了双核或多核CPU，双核CUP内部的两个运算核心可以独立进行工作，并且希望能够充分发挥双核心的计算能力。首先我们根据任务之间存在的数据依赖以及控制依赖关系，将先发掘串行程序中存在的并行性，从而减少了直接将串行程序并行化的复杂度，也提高了效率。然后再针对剩下的串行程序进行并行化处理，从而使它的效率达到更理想的状态．
现在的问题是：
（１）如何找到一个好的方法去发掘串行程序中的存在的并行性；
（２）设计一种将串行程序并行划分的模型，再基于这个模型提出一种并行划分算法．
4.建模前的准备
4.1对于一个输入的串行程序, 我们首先发掘串行程序中存在的并行性构造其对应的并行任务DAG图. 构造DAG图的时候, 主要的一个问题就是发现任务之间的依赖关系. 本文首先对任务之间存在的一种依赖关系作一个简单的介绍.
1.任务之间的数据依赖关系
所谓数据依赖, 也就是在运行的多个执行过程同时访问相同的数据, 结合相关知识给出了下面的数据相关的形式化定义:
在上面所列出的依赖中，流依赖也称为真数据相关是真实的数据流之间的流通过程，因此如果两个任务间存在流依赖是没有办法将这两个任务进行并行或改变两个任务的执行顺序的。反依赖和输出依赖也称作名字相关或冲突，他们实际上并没有任何真实的数据流的关系，只是在要使用一个存储资源的过程中，由于被别的任务使用而造成的，他实际上也是资源依赖。通过重复设置资源或者使用其它的资源，便可以解决这些依赖，而不影响并行性的开发。
4.2算法时间复杂度定义
定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
例：Temp=I；
i=j;
j=temp;
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。
在实际应用中，我们一般都是使用渐近时间复杂度代替实际时间复杂度来进行算法效率分析。
5.模型的建立与求解
首先构造DAG图发掘串行程序中存在的并行性.然后对剩余的串行程序进行提出并行划分模型,基于这个模型提出了一种并行划分算法PDMA和其改进了的并行划分算法RPDMA.最后,通过计算此方案的时间复杂度和串行运行下的时间复杂度,进行比较,得出了此方案的可行性.
5.1：发掘串行程序中的存在的并行性
如何发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务(DAG)图。本文分析了串行程序中存在的依赖关系，并以此为依据，提出了一种由现有的串行程序或者串行解决方案构造对应的并行任务数据依赖的(DAG)图的算法。
算法的描述
对给定的事务（
）
(x)进行如下步骤来构造其DAG图。
步骤1 如果
没有定义，则构造一个标记为
的叶节点，并定义 为这个叶节点。
如果
，则转步骤2.1
否则对
如果没有定义,则构造一个标记为 的叶子节点，同时定义 为这个节点，转步骤2.2
步骤2
步骤2.1 如果实标记为常量的叶子节点,则转步骤2.3,否则转步骤3.2．
步骤２.2 如果
都是标有常量的节点,则转步骤2.4,否则转步骤3.2。
步骤2.3 对执行T,得到新的常量数据集P.如果NODE(
)是处理当前DAG图新构选出来的节点,则删除它．如果NODE(p)没有定义,则构造一个用p做标记的叶节点记作n，并定义NODE(p)指向它．转步骤4．
步骤2.4 对{
}执行T,得到新的常数p。如果NODE（）（
=1,2,
n）是处理DAG图新构造出来的节点,则删除它。如果NODE（p）没有定义,则构造一个用p做标记的叶节点记作n，并定义NODE(p)指向它．转步骤4．
步骤3
步骤3.1 检查DAG图是否已有一个节点，其唯一的前继为NODE（）且其标记为Ｔ．如果没有，则构造该节点记作n．转步骤4．
步骤3.２ 检查DAG图是否已有一个节点，其前继分别为NODE（ ），NODE（
） NODE（
）且其标记为Ｔ．如果没有，则构造该节点记作n．转步骤4．
步骤４ 如果NODE(x)没有定义,则把x附加到节点n上，并令NODE(x)=n;否则先把n从NODE(x)=n．转而处理下一个任务．直到此任务集中的所有人物处理结束 后，转步骤５．
步骤５ 将图中没有标记任务的节点删掉，就求得了任务DAG图。
5.2：串行程序的进一步并行化分:
1并行划分模型
假设
，也就是说
中N个元素，对于中的每一个P的子集
，把中的程序段全部放在一台处理机上运行，根据 的定义知，每两台处理机上执行的程序段都不存在相关性，所以在程序运行的过程中，不需要任何的消息传递和相互等待，一直到各个处理机上的程序段执行完毕．性质a保证了程序中的任何一个程序段不会被执行多于一次，性质b保证了程序中每一个程序段都可以被执行．
2并行划分算法PDMA及相关程度
根据以上描述的并行划分模型，可以写出构造该模型的算法PDMA，PDMA的输入是一个串行程序G，输出是并行划分模型．先给出算法中所使用的符号的定义，P为程序段集，其中每个元素
为序中的一行代码；R为P上的关系
的值域．算法描述如下：
a．由G生成P：{L1，L2，…，L}；
b．生成R={(A，B)| A，B∈P，AB}；
c．令
d．取R中一个二元组r=(A，B)，令R：=R-{r}，若A
或者B，那么，令
：= U{A，B}(
)，否则令：= U{{A，B}}；
。则转d． 实际上，大多数的串行程序根据算法PDMA划分所产生的并行划分模型的基为1，也就是说，大多数串行程序不能被划分成多个互不相关的程序段．
定义3 程序段的相关程度
，若B
A为真，则V(B
A为1，否则为0．
3基于降低相关程度的并行划分算法RPDMA
实际上，串行程序中各个序段相互之间存在着相关性，也就是说，串行程序G，通过算法PDMA产生的并行划分模，
的情况很少，即可以毫无相关地划分到多个处理机上并行执行的串行程序很少划相互之间存在一定的相关性．显然，若可以使得各个分划之间的相关程度降低，那么，并行行的加速比就会提高．因此，并行分划的问题转化为“如何将一个集合划分为几个分划，使得这些分划相互之间的相关性最少”．基于此，提出了一个降低相关程度的并行划分算法RPDMA．RPDMA的主要思路是把划分后的程序段之间的相关程度转化成为各个节点之间的通信，而通信是并行处理的瓶颈RPDMA的目标是尽量降低各个节点之间的通信量。RPDMA对算法PDMA产生的基为1的并行划分模型作进一步的划分．它根据程序段的合以及它们相互之间的相关性生成一个带权图TEMP，图的节点是程序段，图的任意边AB的权是程序段A和B之间的相关程度，RPDMA首先找到TEMP中权最小的边mv，然后让每一条边的权都减去mv的权，也就是相关节点之间的通信量增加mv，如果产生的新图是非连通图，则表明串行程序可以划分为两个或两个以上的带有一定相关性的子程序；如果新图是连通图，那么再按照上述的方法进行划分，直到产生的新图为非连通图．RPDMA的输入为串行程序G，输出为并行划分模型 ．先给出算法的符号定义：TEMP,TEMPO和RP是一个集合，集合中每个元素是一个三元组(A，B，v)，A和B是G的程序段，v是A和B的相关程度．算法描述如下：
a．调用算法PDMA产生并行划分模型 若
，则结束；
b．生成TEMP={(A，B，v)|A，B∈P；v=
}，令TEMPO：=TEMP；
c．取mv
TEMP，使得
s∈TEMP，s≠mv，s mv,s.v>mv.v
d．令RP：= ；
e．取r TEMP，令TEMP：TEMP-{r}，令r．v：=r．v-mv,令RP：=RP
{r}
f．若TEMP
，则转e；
g．令 ：= ；
h．取rp∈RP，rp={A，B，v}，令RP：=RP-{rp}，若A 或者B∈ ，则令 ：= U{A，B}( ∈ )，否则，令
：= U{{A，B}}；i．若RP，则转h；
i．若
=1，则令TEMP：={(A，B，v)|(A，B，v+mv.v) TEMPO}，并令TEMPO：=TEMP，转c，否则结束．
/
5.3在此，我们给出了一个串行程序的实例:
设 为常量
L
: =5, =10, 
=20；
：temp0= + + +10;
x=temp0*temp1;
If x>5 THEN;
x=x*x
ELSE
x=x-1;
利用上面的算法得到图１
图1 由算法构造的上段程序的DAG图
图2 删去没有标有任务的结点后得到图２,
: 
=３０, 
=３５；
: 
;
x=temp0*temp1;
for(x=x;x<=S;x++)
y=2*x;
利用上面的算法得到图3
图3 由算法构造的上段程序的DAG图
图4删去没有标有任务的结点后得到图4
6. 模型的检验
通过以上的过程，我们可以通过比较其串行程序处理下和并行化划分处理后的时间复杂度。
n是输入的串行程序的行数，在构造DAG图时，其相应的各步骤时间复杂度都是O(n);而在后续的并行划分算法RPDMA下,其各步(L4-L7和L11-L14)的时间复杂度如下:L4.L5.L6.L7.L11.L13时间复杂度是O(1);L12的时间复杂度是O(s);L14的时间复杂度是
，因此，整个并行化划分算法下的时间复杂度是。
然而，在对该程序直接进行串行处理时，其时间复杂度是。
因此，上面的结果表明我们的方案令人满意，即此并行化算法下比串行下工作的更快。
[1]刘 键. 并行分布式程序设计. 武汉：华中理工大学出版社，1997；
[2]洪 帆. 离散数学基础. 武汉：华中理工大学出版社，1994；
[3]江文毅 庞丽萍 等. 华中理工大学学报 ，2000；
[4]刘键，鄢勇，谢卫等，顺序程序并行转换系统HZPARA的总体设计思想。机工程与应用，1993（3）：55~57；
[5]郭龙，陈闳中，叶青，〈计算机工程与应用〉2007年第43卷第1期。
[6] Almeida V A F,Vasconcelos I M,Arable J N C,et al..Using random task graphs to investigate the potential of heterogeneity in parallel in parallel systems[c]//proc super2 computing 1992.
[7] Hwang Yuan-shin,Saltz J H.Identifying parallelism in programs with cyclic graphs[J].Journal of Parallel and Distriduted computing,2003.
[8] Zhao jian-jun Dependence analysis of Java bytecode[C]//24th Internatianal Computer and Applicatians Computer Software and Applicatians Conference,2000-10.
[9]z曾国荪. 异构计算环境中循环级并行行提取及调度[J].计算机工程,2006,26（3）.
[10]陈火旺. 刘春林. 程序设计语言编译原理[M]北京：国防出版社,2000.
