串行程序的并行化处理

发布时间：2014-07-27 06:32

                                                                                                                                                                                      

摘要： 目前在并行计算研究领域中很大一部分工作是将串行程序并行化，本文根据题目的要求，在合理的假设下，首先发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务（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图的时候, 主要的一个问题就是发现任务之间的依赖关系. 本文首先对任务之间存在的一种依赖关系作一个简单的介绍。
 

 

本文编号：7617