串行算法并行化.doc

西南大学第三届大学生数学建模竞赛

承 诺 书

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

我们的参赛报名号为： 题目：串行算法并行化

参赛队员 (签名)
队员1：陈艳青
队员2：税萍
队员3：孙伟霞
日期：2009-5-3
串行算法并行化

摘 要
本文针对cpu串行算法并行处理的高效率性问题，建立了一个简单的数学模型，即n*n矩阵的乘法。通过串行算法和并行算法时间复杂度的比较，串行算法的时间复杂度为O （n^3），而并行算法的时间复杂度为2logn-1+log(n／logn)，在n比较大时近似为O(logn)，阐述了串行的并行化处理算法的高效性，并进入深入地分析，得到串行算法并行化的方法。

1、问题重述
从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。由于实际应用对高性能、低价格和持续生产力日益增长的要求，并行处理技术已经成为现代计算机科研与发展的关键技术。并行计算，是将一个计算任务分摊到多个处理器上并同时运行的计算方法，双核CPU从外部看起来是一个CPU，但是内部有两个运算核心，它们可以独立进行计算工作。在同时处理多个任务的时候，多核处理器可以自然地将不同的任务分配给不同的核心。但只运行一个以常规的串行代码写成的程序时，如何将计算任务拆分成多个部分并分解到多个核心上同时运行，是我们要考虑的问题。由于并不是所有的程序都是易并行的，所以我们需要解决的问题是：
a) 设计一种方法，能将一个常规的串行程序分解成两个部分，使之能够在CPU的两个核心上并行运算，并且尽量使双核的运算力被充分的利用起来；
b) 假设算法使用C语言写成，代码里只有顺序执行、分支、循环三种结构；
c) 假设只对整形变量和整形数组进行操作，不需要调用已有的库函数
d) 程序中所有的语句只包括简单的代数运算、赋值、条件分支语句、循环语句，不包括其他语句。
2、问题分析
此问题要求对现成的串行算法进行并行化处理，代码里只涉及顺序、分支、循环三种结构，所以我们只需要建立一个简单的C程序算法，将能够使用双核心并行处理的部分分解开，使之在cpu的两个乃至多个核心上并行运算，其中关键是如何通过分析简单的代码，从总的计算任务中尽量识别可独立运算的部分，并估计每部分的计算量从而达到合理的把任务分配到各个处理器上。最大的一个问题就是模型求解，考虑一些改进的近似算法求解是得到结果的关键。
3、模型建立、求解及结果分析
为了具体说明串行算法的并行化处理，就以”n*n”矩阵的乘法为例建立模型：
常规串行算法就是把数据存在数组里面，然后根据嵌套的for循环来求解n*n矩阵的乘法，代码如下：
有A、B、C三个矩阵；C为A、B相乘的结果
double sum;
 for(i=0;i<n;i++)
{
  for(j=0;j<n;j++)
{
  sum = 0;
  for(k=0;k<n;k++)
{
  sum += A[i*n+k]*B[j*n+k];
  }
  C[i*col+colpos+j] = sum;
  }
 }
它的时间复杂度为O(n^3)。但是如果在一台处理机数为n^3／logn的PRAM上，用O(logn)时间就可以完成两个n*n矩阵的乘法。
设A和B为输入矩阵，假定最初可用的PE数为n^3个，后来降为n^3／logn个。
假设内存由三维阵列组成，将A、B存入其中两个平面。
假设了PE的三维地址指标。PE(i，j，k)，0≤k≤n-1可用来计算输出矩阵的第(i，j)项，0≤i，j≤n-1，n是2的幂。
第一步，对应于每个输出的n乘积项用n个PE在O(1)时间内进行计算。
第二步，这些乘积项用O(logn)时间相加产生一个输出。所用的PE总数为n^3，结果存在C(i，j，0)中(0≤i，j≤n-1)。
假定这里的PRAM采用的是CREW策略。
Step 1：
1．Read A(i，k)
2．Read B(k，j)
3．Compute A(i，k)×B(k,j)
4．Store in C(I,j,k)
Step 2：
1．L←n
2．Repeat L←L／2
If (k<1)then
begin
Read A(i，k)
Read A(i，k)
Compute C(i,j,k)+C(i,j,k,k+l)
Store in C(i,j,k)
End
Until (l=1)
上述是每个PE(i，j，k)要执行的程序。所有n^3个PE对n^3乘法进行并行运算。但对完成(n^3- n^2 )加法最多只有n^3／2个PE处于工作状态。
为了将PE数降为n^3／logn，可采用nXnXn／logn的PE阵列。
每个PE负责计算logn个乘积项并将它们求和。
第一步很容易改写产生n／logn个部分和，每一个部分和由logn次乘法和(logn-1)次加法完成。
我们有数组C(i，j，k)，0≤i，j≤n-1，0≤k≤n／logn-1，它们可在log(n／logn)时间内完成求和，所以将第一步和第二步所花的时间相加，我们就得到总执行时间为2logn-1+log(n／logn)，在n比较大时近似为O(logn)。
由上述可以明显得知，并行化处理要比串行处理更高效，如果串行算法并行化了，那么，即使并行的效率只有一半，实际效率就会由0.05%提高到50%，即实际计算能力提高了1000倍！即便并行化的效率只有十分之一，实际效率也会由0.05%提高到10%，即实际计算能力提高了200倍！

参考文献：
[1] 胡玥，高庆狮，高小宇，《串行算法并行化基础》，科学出版社，2008-6-1
[2] 陈国良，《并行算法实践》，高等教育出版社，2004-1-1
[3] S.S.lyengar，《并行算法导论》，机械工业出版社，2004-2-1
[4] 安徽师范大学数学系 芜湖241000，《数学研究与评论》1992年03期，1992-03-026
[5] 姜启源，《数学模型》，高等教育出版社，2003.8

4