高斯-塞德尔迭代并行算法.doc

高斯-塞德尔迭代并行算法在并行计算中，高斯-塞德尔迭代采用与雅可比迭代相同的数据划分。对于高斯-塞德尔迭代，计算的新值时，使用的旧值和的新值。计算过程中与及的新值会在不同的处理器中产生，因此可以考虑采用时间偏移的方法，使各个处理器对新值计算的开始和结束时间产生一定的偏差。编号为my_rank的处理器一旦计算出的新值，就立即广播给其余处理器，以供各处理器对x的其它分量计算有关的乘积项并求和。当它计算完x的所有分量后，它还要接收其它处理器发送的新的分量，并对这些分量进行求和计算，为计算下一轮的作准备。计算开始时，所有处理器并行地对主对角元素右边的数据项进行求和，此时编号为0的处理器（简称为）计算出,然后广播给其余处理器，其余所有的处理器用的新值和其对应项进行求和计算,接着计算出当完成对的计算和广播后，计算出，并广播给其余处理器，其余所有的处理器用的新值求其对应项的乘积并作求和计算。然后计算出当完成对的计算和广播后，计算出，如此重复下去，直至在中被计算出并广播至其余的处理器之后，计算出下一轮的新的，这样逐次迭代下去，直至收敛为止。具体算法框架描述如下：算法1求解线性方程组的高斯-塞德尔迭代并行算法输入：系数矩阵，常数向量，ε，初始解向量输出：解向量Begin对所有处理器my_rank(my_rank=0,…,p-1)同时执行如下的算法:fori=my_rank*mto(my_rank+1)*m-1do/*所有处理器并行地对主对角元素右边的数据求和*/(1.1)sum[i]=0.0(1.2)forj=i+1ton-1dosum[i]=sum[i]=+a[i,j]*x[j]endforendfor(2)while(total<n)do/*total为新旧值之差小于ε的x的分量个数*/(2.1)iteration=0/*iteration为本处理器中新旧值之差小于ε的x的分量个数*/(2.2)forj=0ton-1do/*依次以第0,1,…,n-1行为主行*/(i)q=j/m(ii)ifmy_rank=qthen/*主行所在的处理器*//*产生的新的值*/if()theniteration=iteration+1endif将x[j]的新值广播到其它所有处理器中/*对其余行计算x[j]所对于的内积项并累加*/sum[j]=0fori=my-rank*mto(my-rank+1)*m-1doif(j≠i)thenendifendforelse/*其它处理器*/接收广播来的x[j]的新值/*对所存各行计算x[j]所对于的内积项并累加*/fordoendforendifendfor(2.3)用Allreduce操作求出所有处理器中iteration值的和total并广播到所有处理器中endwhileend若取一次乘法和加法运算时间或一次比较运算时间为一个单位时间。在算法开始阶段，各处理器并行计算主对角线右边元素相应的乘积项并求和,所需时间，进入迭代计算后，虽然各个处理器所负责的的分量在每一轮计算中的开始时间是不一样的，但一轮迭代中的计算量都是相等的，因此不妨取0号处理器为对象分析一轮迭代计算的时间，容易得出0号处理器计算时间为；另外它在一轮迭代中做广播操作n次，通信量为1，归约操作1次，通信量为1，所有的通信时间为，因此高斯-塞德尔迭代的一轮并行计算时间为。源程序如下：1.源程序seidel.c#include"stdio.h"#include"stdlib.h"#include"mpi.h"#include"math.h"#defineE0.0001#definea(x,y)a[x*size+y]#defineb(x)b[x]#definev(x)v[x]/*A为size*size的系数矩阵*/#defineA(x,y)A[x*size+y]#defineB(x)B[x]#defineV(x)V[x]#defineintsizesizeof(int)#definefloatsizesizeof(float)#definecharsizesizeof(char)intsize,N;intm;float*B;float*A;float*V;intmy_rank;intp;MPI_Statusstatus;FILE*fdA,*fdB,*fdB1;voidEnvironment_Finalize(float*a,float*b,float*v){free(a);free(b);free(v);}intmain(intargc,char**argv){inti,j,my_rank,group_size;intk;float*sum;float*b;float*v;float*a;float*differ;floattemp;intiteration,to