论文关键词：并行计算 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