棋盘划分下的矩阵—向量乘法

*******************实践教学*******************大学理学院2016年春季学期并行计算课程设计专业班级：_____________________姓名：_____________________学号：______________________指导教师：______________________成绩：_______________________棋盘划分下的矩阵—向量乘法摘要并行计算是计算机科学中重要研究内容，已有几十年的发展历程，它是在串行计算的基础上演变而来的。创建和应用并行计算的最主要原因是因为它是解决单处理机速度瓶颈的最好的方法之一。并行计算的发展是大型复杂科学、工程问题的计算需求以及与当代社会相关问题的需求。并行计算的研究需要并行计算机系统、并行算法和并行程序设计等专家以及并行应用领域专家的共同参与。矩阵—向量乘法同样可以有带状划分和棋盘划分下两中并行算法。所谓棋盘划分（CheckerBoardPartitioning）就是将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时任意处理器均不包含整行或整列。1目录一、题目及要求.............................................................................................................................................2二、设计算法、算法原理.............................................................................................................................2三、算法描述、设计流程...........................................................................................................................33.1算法描述..........................................................................................................................................33.2设计流程图.......................................................................................................................................4四、源程序代码及运行结果.........................................................................................................................54.1源代码..............................................................................................................................................54.2题目运行结果示意图....................................................................................................................12五、算法分析、优缺点...............................................................................................................................125.1算法分析........................................................................................................................................125.2优缺点............................................................................................................................................12六、总结.....................................................................................................................................................13七、参考文献...............................................................................................................................................142一、题目及要求棋盘划分的矩阵-向量乘法已知47511321,7778711925320234101247329XA，求AXY二、设计算法、算法原理所谓棋盘划分（CheckerBoardPartitioning）就是将方阵划分成若干子方阵，每个子方阵指派给一个处理器，此时任一处理器均不包含整行整列。和带状划分类似，棋盘划分可分为块棋盘划分（Block-CheckerBoardPartitioning）和循环棋盘划分（Cycile-CheckerBoardPartitioning）。如图一所示：（a．块棋盘划分）（b.循环棋盘划分）图一两种棋盘划分矩阵划分成棋盘状可和处理器连成二维网孔相对应。对与一个nn的方阵和pp的二维处理器，每个处理器均匀的分配有npnpn//2/p个矩阵元素。值得指出的是，和带状划分相比，棋盘划分可开发出更高的并行度。例如，对于一个nn的方阵，棋盘划分最多可以使用n2个处理器进行并行计算，但使用带状划分可用的处理器不能多于n个。3三、算法描述、设计流程3.1算法描述划分(块棋盘划分):Pij存放ai,j,xi置入Pi,i中算法:对p=n2情形①每个Pi,i向Pj,i播送xi(一到多播送)；②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi；注:对pn2情形,p个处理器排成pp的二维网孔，算法中Pi,i向Pj,i播送X中相应的pn/个分量(1)网孔连接的计算时间Tp(CT):pttpnthws.X中相应分量置入Pi,i的通讯时间:1logptptpnthws.按列一到多播送时间:1logptptpnthws.按行单点积累的时间:ptptpnptpnThwsp3loglog2示例如图二所示：图二p2n时棋盘划分的矩阵—向量乘法43.2设计流程图图三程序流程设计图5四、源程序代码及运行结果4.1源代码#includestdio.h#includestdlib.h#includempi.h#defineintsizesizeof(int)#definefloatsizesizeof(float)#defineA(x,y)A[x*N+y]#defineB(x)B[x]#defineC(x)C[x]#definea(x)a[x]#defineb(x)b[x]#definec(x)c[x]float*a,*b,*c;float*A,*B,*C;intM,N,K,P;intm,n;intmyid;FILE*dataFile;MPI_Statusstatus;doubletime1;doublestarttime,endtime;voidreadData(){inti,j;starttime=MPI_Wtime();6dataFile=fopen(dataIn.txt,r);fscanf(dataFile,%d%d,&M,&N);A=(float*)malloc(floatsize*M*N);for(i=0;iM;i++){for(j=0;jN;j++){fscanf(dataFile,%f,A+i*N+j);}}fscanf(dataFile,%d,&K);if(N!=K){printf(theinputiswrong\n);exit(1);}B=(float*)malloc(floatsize*K);for(i=0;iK;i++){fscanf(dataFile,%f,B+i);}fscanf(dataFile,%d,&P);fclose(dataFile);printf(InputoffiledataIn.txt\n);printf(%d\t%d\n,M,N);for(i=0;iM;i++){for(j=0;jN;j++){printf(%f\t,A(i,j));7}printf(\n);}printf(%d\n,K);for(i=0;iK;i++){printf(%f\t,B(i));}printf(\n);C=(float*)malloc(floatsize*M);}voidprintfResult(){inti;printf(\nOutputofMatrixC=AB\n);for(i=0;iM;i++){printf(%f\t,C(i));printf(\n);}endtime=MPI_Wtime();printf(\n);printf(Wholerunningtime=%fseconds\n,endtime-starttime);printf(Distributedatatime=%fseconds\n,time1-starttime);printf(Parallelcomputetime=%fseconds\n,endtime-time1);}intmain(intargc,char**argv)8{inti,k,group_size,p;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&group_size);MPI_Comm_rank(MPI_COMM_WORLD,&myid);p=group_size;if(myid==0){readData();}if(myid==0){for(i=0;ip;i++){MPI_Send(&M,1,MPI_INT,i,i,MPI_COMM_WORLD);MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD);MPI_Send(&K,1,MPI_INT,i,i,MPI_COMM_WORLD);}}else{MPI_Recv(&M,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status);MPI_Recv(&N,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status);MPI_Recv(&K,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status);}if(myidp){9a=(float*)malloc(floatsize*N);b=(float*)malloc(floatsize*K);c=