串行程序的并行化处理论文

《串行程序的并行化处理论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、串行程序的并行化处理论文论文关键词：并行计算DAG数据依赖串行程序并行划分模型等价关系论文摘要：目前在并行计算研究领域中很大一部分工作是将串行程序并行化，本文根据题目的要求，在合理的假设下，首先发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务（DAG）图，论文分析了串行程序中存在的数据依赖关系，并以此为根据，提出了一种由现有的串行程序构造对应的并行任务（DAG）图的算法.freelp=I；i=j;j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不

2、随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。在实际应用中，我们一般都是使用渐近时间复杂度代替实际时间复杂度来进行算法效率分析。5.模型的建立与求解首先构造DAG图发掘串行程序中存在的并行性.然后对剩余的串行程序进行提出并行划分模型,基于这个模型提出了一种并行划分算法PDMA和其改进了的并行划分算法RPDMA.最后,通过计算此方案的时间复杂度和串行运行下的时间复杂度,进行比较,得出了此方案的可行性.5

3、.1：发掘串行程序中的存在的并行性如何发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务(DAG)图。本文分析了串行程序中存在的依赖关系，并以此为依据，提出了一种由现有的串行程序或者串行解决方案构造对应的并行任务数据依赖的(DAG)图的算法。算法的描述对给定的事务（）(x)进行如下步骤来构造其DAG图。步骤1如果没有定义，则构造一个标记为的叶节点，并定义为这个叶节点。如果，则转步骤2.1否则对如果没有定义,则构造一个标记为的叶子节点，同时定义为这个节点，转步骤2.2步骤2步骤2.1如果实标记为常量的叶子节点,.freelv，然后让每一条边的权都减去mv的权，

4、也就是相关节点之间的通信量增加mv，如果产生的新图是非连通图，则表明串行程序可以划分为两个或两个以上的带有一定相关性的子程序；如果新图是连通图，那么再按照上述的方法进行划分，直到产生的新图为非连通图．RPDMA的输入为串行程序G，输出为并行划分模型．先给出算法的符号定义：TEMP,TEMPO和RP是一个集合，集合中每个元素是一个三元组(A，B，v)，A和B是G的程序段，v是A和B的相关程度．算法描述如下：a．调用算法PDMA产生并行划分模型若，则结束；b．生成TEMP={(A，B，v)

5、A，B∈P；v=}，令TEMPO：=TEMP；c．取mvTEMP，使得s∈TEMP，s

6、≠mv，smv,s.v>mv.vd．令RP：=；e．取rTEMP，令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)

7、(A，B，v+mv.v)TEMPO}，并令TEMPO：=TEMP，转c，否则结束．/5.3在此，我们给出了一个串行程序的实例:设为常量L:=5,=10,=20；：temp0=+++10;x=tem

8、p0*temp1;Ifx>5THEN;x=x*xELSEx=x-1;利用上面的算法得到图１图1由算法构造的上段程序的DAG图图2删去没有标有任务的结点后得到图２,:=３０,=３５；:;x=temp0*temp1;for(x=x;x