并行计算论文总结

*******************实践教学*******************兰州理工大学理学院2016年春季学期并行计算课程设计专业班级：13级信息与计算科学姓名：田兴福学号：13540231指导教师：孟新友郭秀婷成绩：2摘要本文主要设计了MIMD（多指令流多数据）异步并行的Gauss一Seidel迭代法，并利用MPI消息传递模型实现了该算法并实际测试了求解所花费的时间和进行了算法的理论评估。算法的主要过程如下：首先，主进程在数据域对线性方程组的增广矩阵进行带状化分，并将划分的结果广播到其他处理器，然后，各个处理器按照自己的指令流进行计算，并利用存储转发的方式进行消息传递，最后，满足精度要求后，通过设置同步路障使得各个处理器的结果归约至主进程，由主进程并输出求解结果。关键词：异步并行Gauss一Seidel迭代法消息传递同步路障3目录摘要..................................................................................................................................................2一．题目及要求...............................................................................................................................41.1题目....................................................................................................................................41.2要求....................................................................................................................................4二．算法设计原理...........................................................................................................................42.1设计算法............................................................................................................................42.2算法原理............................................................................................................................5三．算法描述及设计流程...............................................................................................................63.1算法描述............................................................................................................................63.2设计流程............................................................................................................................7四．源程序代码及运行结果...........................................................................................................94.1源程序代码........................................................................................................................94.2运行结果..........................................................................................................................16五．算法分析及优缺点.................................................................................................................175.1算法分析..........................................................................................................................175.2优缺点..............................................................................................................................17总结................................................................................................................................................18参考文献.........................................................................................................................................194一．题目及要求1.1题目迭代求解的高斯-赛德尔法（MIMD异步并行算法）求解方程组1352422532132321xxxxxxxx的解1.2要求本次课程设计的题目是利用高斯-赛德迭尔求解方程组，在求解过程中要求用MIMD异步并行算法求解。二．算法设计原理2.1设计算法求解线性方程组的高斯—赛德尔法（Gauss-SeidelMethod），实际上是迭代法，不仅稠密矩阵性系适用，而且稀疏矩阵性系也适用。下面是他的主要原理：在求解错误!未找到引用源。,可以将系数矩阵错误!未找到引用源。分解为错误!未找到引用源。,其中错误!未找到引用源。均为错误!未找到引用源。的矩阵，具体的定义如下：[2]这样，错误!未找到引用源。可以换成错误!未找到引用源。。如果给定初始解错误!未找到引用源。,则第错误!未找到引用源。次迭代可计算如下：错误!未找到引用源。(1)由于在迭代的算法中需要判断是否在第错误!未找到引用源。次收敛，这里利用向量的1范数去判断是否终止迭代过程，计算公式如下：错误!未找到引用源。(2)(1)式能够加快顺序计算速度，因此当依次计算错误!未找到引用源。时，第错误!未找到引用源。次迭代的错误!未找到引用源。值，一部分可以用本次迭代的值5（相应于上三角部分），而一部分可用本次迭代的值（相应于下三角部分）。2.2算法原理对于以上的分析，该算法无法直接并行化，为此通过分析，将线性方程组错误!未找到引用源。的增广矩阵错误!未找到引用源。按行划分如图1。图1增广矩阵的划分对于高斯-塞德尔迭代，计算ix的新值时，使用11,,inxx的旧值和01,,ixx的新值。计算过程中ix与01,,ixx及11,,inxx的新值会在不同的处理器中产生，因此可以考虑采用时间偏移的方法，使各个处理器对新值计算的开始和结束时间产生一定的偏差。编号为my_rank的处理器一旦计算出(_(_1))ixmyrankmimyrankm的新值，就立即广播给其余处理器，以供各处理器对x的其它分量计算有关ix的乘积项并求和。当它计算完x的所有分量后，它还要接收其它处理器发送的新的x分量，并对这些分量进行求和计算，为计算下一轮的ix作准备。计算开始时，所有处理器并行地对主对角元素右边的数据项进行求和，此时编号为0的处理器（简称为0p）计算出0x然后广播给其余处理器，其余所有的处理器用0x的新值和其对应项进行求和计算，接着0p计算出12,,,xx当0p完成对1mx的计算和广播后，1p计算出mx，并广播给其余处理器，其余所有的处理器用mx的新值求其对应项的乘积并作求和计算。然后1p6计算出12,,,mmxx当1p完成对2*1mx的计算和广播后，2p计算出2*mx，如此重复下去，直至1nx在1pp中被计算出并广播至其余的处理器之后，0p计算出下一轮的新的0x，这样逐次迭代下去，直至收敛为止。[1]三．算法描述及设计流程3.1算法描述通过在第二小节的分析，我们才用类程序语言对MIMD异步并行算法的Guass一Seidel法进行描述：输入：输入矩阵nnA，常数项1nb，初始解)0(1)0(1)0(0)0(,...,,nxxxx，精度。输出：解向量nxxx,...,1,0。对所有处理器my_rank(my_rank=)同时执行如for(i=my_rankm;(my_rank+1)m；i++)//所有处理器并行的对主对角线元素右边的数据求和sum[i]=0.0for(j=i+1;jn-1;j++)sum[i]=sum[i]+A[i,j]*x[j]total=0endforendforwhile(totaln){//total为新旧值之差小于的分量个数（2.1）iteration=0//iteration为本处理器中新旧值之差小于的分量个（2.2）for(j=0;j=n-1;j++)//依次以第0,1,…,n-1行为主行(i)q=j/m(ii)if(my_rank=q)//表示朱行所在的处理器//产生的新值Temp=x[j],x[j]=(b[j]-sum[j])/a[I,j]7EndifIf(|x[j]-temp|)Iteration++Endif将x[j]的新值广播到其他的n-1个处理器S[j]=0For(i=my_rank*m;i=(my_rank+1)*m;i++)If(j)Sum[i]=sum[i]+A[I,j]*x[j]Else//其他处理器接受广播来的x[j]新值endif//对所存在各行计算x[j]所对应的内积项累加For（i=my_rank*m;i=((my_rank+1)*m-1）;i++）Sum[i]=sum[i]+A[I,j]*x[j]endforendfor求出所有处理器中iteration和total的值并广播到所有处理器endforendwhile3.2设计流程为了实现MIMD异步并行算法的Guass一Seidel法，采用的消息传模型进行实现。具体的实现流程如图28图2.程序设计流程消息传递中所使用的相关函数如表1函数名功能MPI_Init(&argc,&argv)启动MPIMPI_Comm_rank(MPI_COMM_WORLD,int*rank)获取进程编号MPI_Comm_size(MP