串 行 程 序 的 并 行 化 处 理=论文关键词：并行计算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，BP，AB；c令 d取 R 中一个二元组 r=(A，B)，令 R：=R-r，若 A 或者 B，那么，令 ：= UA，B( )，否则令：= UA，B；e若 R 。则转 d 实际上，大多数的串行程序根据算法 PDMA 划分所产生的并行划分模型的基为 1，也就是说，大多数串行程序不能被划分成多个互不相关的程序段定义 3 程序段的相关程度 ，若 B A 为真，则 V(B A 为 1，否则为 03 基于降低相关程度的并行划分算法 RPDMA实际上，串行程序中各个序段相互之间存在着相关性，也就是说，串行程序 G，通过算法 PDMA 产生的并行划分模， 的情况很少，即可以毫无相关地划分到多个处理机上并行执行的串行程序很少划相互之间存在一定的相关性显然，若可以使得各个分划之间的相关程度降低，那么，并行行的加速比就会提高因此，并行分划的问题转化为“如何将一个集合划分为几个分划，使得这些分划相互之间的相关性最少”基于此，提出了一个降低相关程度的并行划分算法 RPDMARPDMA 的主要思路是把划分后的程序段之间的相关程度转化成为各个节点之间的通信，而通信是并行处理的瓶颈 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，BP；v= ，令 TEMPO：=TEMP；c取 mv TEMP，使得 sTEMP，smv，s mv,s.vmv.vd令 RP：= ；e取 r TEMP，令 TEMP：TEMP-r，令 rv：=rv-mv,令 RP：=RP rf若 TEMP，则转 e；g令 ：= ；h取 rpRP，rp=A，B，v，令 RP：=RP-rp，若 A 或者 B ，则令 ：= UA，B( )，否则，令 ：= UA，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 x5 THEN; x=x*x ELSE x=x-1;