并行计算矩阵分块乘法

目录一、题目及要求...............................................................................................................................11、题目.....................................................................................................................................12、要求.....................................................................................................................................1二、设计算法、算法原理...............................................................................................................1三、算法描述、设计流程...............................................................................................................23.1算法描述............................................................................................................................23.2设计流程....................................................................................................................4四、源程序代码及运行结果...........................................................................................................61、超立方.................................................................................................................................61.1超立方的源程序代码................................................................................................61.2运行结果..................................................................................................................112、网孔连接...........................................................................................................................112.1源程序代码..............................................................................................................112.2运行结果..................................................................................................................183、在数学软件中的计算结果...............................................................................................19五、算法分析、优缺点.................................................................................................................191、简单的并行分块乘法的过程为.......................................................................................192、使用Cannon算法时的算法分析.....................................................................................203、算法的优缺点...................................................................................................................21六、总结.........................................................................................................................................22参考文献.........................................................................................................................................231一、题目及要求1、题目简单并行分块乘法：（1）情形1:超立方连接；（2）情形2：二维环绕网孔连接已知,177511195310135411274329,75638957123142120143321BA求BAC。2、要求（1）题目分析、查阅与题目相关的资料；（2）设计算法；（3）算法实现、代码编写；（4）结果分析和性能分析与改进；（5）论文撰写、答辩；二、设计算法、算法原理要考虑的计算问题是C=AB,其中A与B分别是nn矩阵。①A、B和C分成ppp的方块阵ijA,ijB和ijC,大小均为pnpn，p个处理器编号为1,1,....,1,0,....,0,0pppppp,ijP存放ijA,ijB和ijC。②通讯:每行处理器进行A矩阵块的多到多播送(得到ikA,k=0~1p)每列处理器进行B矩阵块的多到多播送(得到kjB,k=0~1p)③乘-加运算:ijP做kjpkikijBAC102三、算法描述、设计流程3.1算法描述超立方情形下矩阵的简单并行分块算法输入：待选路的信包在源处理器中输出：将原处理器中的信包送至其目的地Begin（1）fori=1tondo11iiidsrendfor(2)SVi,1(3)whilenido(3.1)if1irthen从当前节点V选路到节点为V1（3.2）1iiendwhileEnd二维网孔情形下矩阵的简单并行分块算法输入：待选路的信包处于源处理器中输出：将各信包送至各自的目的地中Begin（1）沿x维将信包向左或向右选路至目的地的处理器所在的列（2）沿y维将信包向上或向下选路至目的地的处理器所在的行分块乘法算法//输入:nnA,nnB;子快大大小小均均为为pnpn输出:nnCn3Begin(1)fori=0to1pdoforallpar-doijpifikthenijAmod,1jiAendififjkthenijBB(i+1)mod,jendifendforendforfori=0to1pdoforallijppar-doijC=ijA+ijBendforEndforEnd43.2设计流程以下是二维网孔与超立方连接设计流程。如图3-1二维网孔步骤：(1)先进行行播送;(2)再同时进行列播送;图3-1二维网孔示意图376251498044444444422333311112131415105超立方步骤：依次从低维到高维播送,d-立方,d=0,1,2,3,4…;算法流程如图所示：图3-2算法流程包括mpi的头文件相关变量声明MPI_INIT()MPI_COMM_RANK()MPI_COMM_SIZE()进入MPI系统矩阵内部的通信应用控制实体：矩阵内部的计算程序MPI_FINALIZE()退出MPI系统结束开始循环直至结束6四、源程序代码及运行结果1、超立方1.1超立方的源程序代码#includestdio.h#includestdlib.h#includempi.h#defineintsizesizeof(int)#definefloatsizesizeof(float)#definecharsizesizeof(char)#defineA(x,y)A[x*K+y]#defineB(x,y)B[x*N+y]#defineC(x,y)C[x*N+y]#definea(x,y)a[x*K+y]#defineb(x,y)b[x*n+y]#definebuffer(x,y)buffer[x*n+y]#definec(l,x,y)c[x*N+y+l*n]float*a,*b,*c,*buffer;ints;float*A,*B,*C;intM,N,K,P;intm,n;intmyid;intp;FILE*dataFile;MPI_Statusstatus;doubletime1;doublestarttime,endtime;voidreadData(){inti,j;starttime=MPI_Wtime();dataFile=fopen(yin.txt,r);fscanf(dataFile,%d%d,&M,&K);A=(float*)malloc(floatsize*M*K);for(i=0;iM;i++){for(j=0;jK;j++){fscanf(dataFile,%f,A+i*K+j);}7}fscanf(dataFile,%d%d,&P,&N);if(K!=P){printf(theinputiswrong\n);exit(1);}B=(float*)malloc(floatsize*K*N);for(i=0;iK;i++){for(j=0;jN;j++){fscanf(dataFile,%f,B+i*N+j);}}fclose(dataFile);printf(Inputoffile\yin.txt\\n);printf(%d\t%d\n,M,K);for(i=0;iM;i++){for(j=0;jK;j++)printf(%f\t,A(i,j));printf(\n);}printf(%d\t%d\n,K,N);for(i=0;iK;i++){for(j=0;jN;j++)printf(%f\t,B(i,j));printf(\n);}C=(float*)malloc(floatsize*M*N);}intgcd(intM,intN,intgroup_size){inti;for(i=M;i0;i--){if((M%i==0)&&(N%i==0