串行算法并行化

1、西南大学第三届大学生数学建模竞赛承诺书我们仔细阅读了西南大学第三届大学生数学建模竞赛的竞赛规则.我们完全明白，虽然本次竞赛采取分散自行答卷的机制，但在竞赛开始 后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队夕卜 的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或 其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述 方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有 违反竞赛规则的行为，我们将受到严肃处理。我们的参赛报名号为：题目：串行算法并行化参赛队

2、员（签名）队员1:陈艳青队员2：税萍队员3:孙伟霞日期：2009-5-3串行算法并行化摘 要本文针对cpu串行算法并行处理的高效率性问题，建立了一个简单的数学模型， 即n*n矩阵的乘法。通过串行算法和并行算法时间复杂度的比较，串行算法的时间复杂 度为O (n人3)，而并行算法的时间复杂度为2logn-1+log(n / logn),在n比较大时近 似为O(logn)，阐述了串行的并行化处理算法的高效性，并进入深入地分析，得到串行 算法并行化的方法。1、问题重述从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行 计算时代、并行计算时代。由于实际应用对高性能、低价格和持续生

3、产力日益增长的要 求，并行处理技术已经成为现代计算机科研与发展的关键技术。并行计算，是将一个计 算任务分摊到多个处理器上并同时运行的计算方法，双核CPU从外部看起来是一个 CPU，但是内部有两个运算核心，它们可以独立进行计算工作。在同时处理多个任务的 时候，多核处理器可以自然地将不同的任务分配给不同的核心。但只运行一个以常规的 串行代码写成的程序时，如何将计算任务拆分成多个部分并分解到多个核心上同时运 行，是我们要考虑的问题。由于并不是所有的程序都是易并行的，所以我们需要解决的 问题是：a）设计一种方法，能将一个常规的串行程序分解成两个部分，使之能够在CPU 的两个核心上并行运算，并且尽量使双

4、核的运算力被充分的利用起来；b）假设算法使用C语言写成，代码里只有顺序执行、分支、循环三种结构；c）假设只对整形变量和整形数组进行操作，不需要调用已有的库函数d）程序中所有的语句只包括简单的代数运算、赋值、条件分支语句、循环语句， 不包括其他语句。2、问题分析此问题要求对现成的串行算法进行并行化处理，代码里只涉及顺序、分支、循环 三种结构，所以我们只需要建立一个简单的C程序算法，将能够使用双核心并行处理的 部分分解开，使之在cpu的两个乃至多个核心上并行运算，其中关键是如何通过分析简 单的代码，从总的计算任务中尽量识别可独立运算的部分，并估计每部分的计算量从而 达到合理的把任务分配到各个处理器

5、上。最大的一个问题就是模型求解，考虑一些改进 的近似算法求解是得到结果的关键。3、模型建立、求解及结果分析为了具体说明串行算法的并行化处理，就以”n*n ”矩阵的乘法为例建立模型：常规串行算法就是把数据存在数组里面，然后根据嵌套的for循环来求解n*n矩阵 的乘法，代码如下：有A、B、C三个矩阵；C为A、B相乘的结果double sum;for(i=0;in;i+)for(j=0;jn;j+)sum = 0;for(k=0;kn;k+)sum += Ai*n+k*Bj*n+k;Ci*col+colpos+j = sum;它的时间复杂度为0(抄3)。但是如果在一台处理机数为M3 / logn的P

6、RAM上，用 O(logn)时间就可以完成两个n*n矩阵的乘法。设A和B为输入矩阵，假定最初可用的PE数为n人3个，后来降为n人3 / logn个。假设内存由三维阵列组成，将A、B存入其中两个平面。假设了 PE的三维地址指标。PE(i，j，k)，0kn-1可用来计算输出矩阵的第(i， j)项，0忍i，j忍n-1，n是2的幕。第一步，对应于每个输出的n乘积项用n个PE在0(1)时间内进行计算。第二步，这些乘积项用O(logn)时间相加产生一个输出。所用的PE总数为M3, 结果存在C(i，j，0)中(0忍i，j忍n-1)。假定这里的PRAM采用的是CREW策略。Step 1：Read A(i，k)

7、Read B(k，j)Compute A(i， k)XB(k,j)Store in C(I,j,k)Step 2：LnRepeat LL / 2If (k1)thenbeginRead A(i, k)Read A(i, k)Compute C(i,j,k)+C(i,j,k,k+l)Store in C(i,j,k)EndUntil (l=1)上述是每个PE(i, j, k)要执行的程序。所有nA3个PE对nA3乘法进行并行运算。 但对完成(抄3-抄2 )加法最多只有nA3/2个PE处于工作状态。为了将PE数降为n人3 / logn，可采用nXnXn / logn的PE阵列。每个PE负责计算lo

8、gn个乘积项并将它们求和。第一步很容易改写产生n / logn个部分和，每一个部分和由logn次乘法和(logn-1) 次加法完成。我们有数组 C(i, j, k), 0忍i, j忍n-1, Okn / logn-1，它们可在 log(n / logn) 时间内完成求和，所以将第一步和第二步所花的时间相加，我们就得到总执行时间为 2logn-1+log(n / logn),在 n 比较大时近似为 O(logn)。由上述可以明显得知，并行化处理要比串行处理更高效，如果串行算法并行化了, 那么，即使并行的效率只有一半，实际效率就会由0.05%提高到50%，即实际计算能力 提高了 1000倍！即便并行化的效率只有十分之一，实际效率也会由0.05%提高到10%, 即实际计算能力提高了 200倍！参考文献：胡明，高庆狮，高小宇，串行算法并行化基础，科学出版社，2008-6-1陈