并行处理实验报告：用MPI实现的矩阵乘法的加速比分析

华中科技大学课程名称并行处理实验名称矩阵乘法的实现及加速比分析考生姓名李佩佩考生学号M201372734系、年级计算机软件与理论2013级类别硕士研究生考试日期2014年1月3日一.实验目的1)学会如何使用集群2)掌握怎么用并行或分布式的方式编程3)掌握如何以并行的角度分析一个特定的问题二.实验环境1)硬件环境：4核CPU、2GB内存计算机；2)软件环境：WindowsXP、MPICH2、VS2010、XmanagerEnterprise3；3)集群登录方式：通过远程桌面连接211.69.198.2，用户名：pppusr，密码：AE2Q3P0。三.实验内容1.实验代码编写四个.c文件，分别为DenseMulMatrixMPI.c、DenseMulMatrixSerial.c、SparseMulMatrixMPI.c和SparseMulMatrixSerial.c，用于比较并行和串行矩阵乘法的加速比，以及稀疏矩阵和稠密矩阵的加速比。这里需要说明一下，一开始的时候我是把串、并行放在一个程序中，那么就只有两个.c文件DenseMulMatrix.c和SparseMulMatrix.c，把串行计算矩阵乘的部分放到了主进程中，即procsID=0的进程，但是结果发现执行完串行后，再执行并行就特别的慢。另外，对于稀疏矩阵的处理方面可能不太好，在生成稀疏矩阵的过程中非0元素位置的生成做到了随机化，但是在进行稀疏矩阵乘法时没有对矩阵压缩，所以跟稠密矩阵乘法在计算时间上没多大区别。方阵A和B的初始值是利用rand()和srand()函数随机生成的。根据稀疏矩阵和稠密矩阵的定义，对于稀疏矩阵和稠密矩阵的初始化方法InitMatrix(int*M,int*N,intlen)会有所不同。这里需要说明一下，一开始对于矩阵A和B的初始化是两次调用InitMatrix(int*M,intlen)，生成A和B矩阵，但是随后我发现，由于两次调用方法InitMatrix的时间间隔非常短，又由于srand()函数的特点，导致生成的矩阵A和B完全一样；然后，我就在两次调用之间加入了语句“Sleep(1000)；”，加入头文件“#includewindows.h”，这样生成的A、B矩阵就不一样了，但很快问题又出现了，在Xshell中不能识别头文件“#includewindows.h”。所以，最后决定用下面的方法生成矩阵A和B，B是A的转置。//稠密矩阵的生成方法voidInitMatrix(int*M,int*N,intlen){srand((unsigned)time(NULL));for(i=0;ilen*len;i++){M[i]=rand()%2;}for(i=0;ilen;i++){for(j=0;jlen;j++){N[i*len+j]=M[j*len+i];}}}//稀疏矩阵的生成方法voidInitMatrix(int*M,int*N,intlen){for(i=0;ilen*len;i++)M[i]=0;srand((unsigned)time(NULL));for(m=0;m224;m++){for(n=0;n224;n++){i=rand()%len;j=rand()%len;M[i*len+j]=1;}}for(i=0;ilen;i++){for(j=0;jlen;j++){N[i*len+j]=M[j*len+i];}}}输入：并行执行的进程数procsNum，对于串行计算，只需要np=1；输出：程序的执行时间。在WindowsXP下使用MicrosoftVisualStudio2010编程，由于稀疏矩阵和稠密矩阵的代码只是初始化部分不同，所以以稠密矩阵乘法为例，列出并行和串行的源代码。并行计算的矩阵乘法源代码：DenseMulMatrixMPI.c#includestdio.h#includestdlib.h#includempi.h#includetime.h#defineLength1000int*A,*B,*C,*buffer,*ans;inttemp,i,j,k;intprocsID,procsNum,line;doublestartTime,endTime,totalTime;voidInitMatrix(int*M,int*N,intlen);//实现部分见上面voiddel(){free(A);free(B);free(C);free(buffer);free(ans);}intmain(intargc,char*argv[]){MPI_Statusstatus;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&procsID);//获取当前进程号MPI_Comm_size(MPI_COMM_WORLD,&procsNum);//获取进程数目line=Length/procsNum;//将数据分为（进程数）个块A=(int*)malloc(sizeof(int)*Length*Length);B=(int*)malloc(sizeof(int)*Length*Length);C=(int*)malloc(sizeof(int)*Length*Length);buffer=(int*)malloc(sizeof(int)*Length*line);ans=(int*)malloc(sizeof(int)*Length*line);if(procsID==0){InitMatrix(A,B,Length);startTime=MPI_Wtime();for(i=1;iprocsNum;i++){MPI_Send(B,Length*Length,MPI_INT,i,0,MPI_COMM_WORLD);}for(i=1;iprocsNum;i++){MPI_Send(A+(i-1)*line*Length,Length*line,MPI_INT,i,1,MPI_COMM_WORLD);}for(k=1;kprocsNum;k++){MPI_Recv(ans,line*Length,MPI_INT,k,3,MPI_COMM_WORLD,&status);for(i=0;iline;i++){for(j=0;jLength;j++){C[((k-1)*line+i)*Length+j]=ans[i*Length+j];}}}for(i=(procsNum-1)*line;iLength;i++){for(j=0;jLength;j++){temp=0;for(k=0;kLength;k++)temp+=A[i*Length+k]*B[k*Length+j];C[i*Length+j]=temp;}}endTime=MPI_Wtime();totalTime=endTime-startTime;printf(并行稠密矩阵乘法过程总共花的时间:%.4fs\n,totalTime);}//ifelse{MPI_Recv(B,Length*Length,MPI_INT,0,0,MPI_COMM_WORLD,&status);MPI_Recv(buffer,Length*line,MPI_INT,0,1,MPI_COMM_WORLD,&status);for(i=0;iline;i++){for(j=0;jLength;j++){temp=0;for(k=0;kLength;k++)temp+=buffer[i*Length+k]*B[k*Length+j];ans[i*Length+j]=temp;}}MPI_Send(ans,line*Length,MPI_INT,0,3,MPI_COMM_WORLD);}//elseMPI_Finalize();del();return0;}串行计算的矩阵乘法源代码：DenseMulMatrixSerial.c#includestdio.h#includestdlib.h#includetime.h#defineLength1000int*A,*B,*C;inti,j,k;clock_tstartTime,endTime;doubletotalTime;voidInitMatrix(int*M,int*N,intlen);//实现部分见上面voiddel(){free(A);free(B);free(C);}intmain(){A=(int*)malloc(sizeof(int)*Length*Length);B=(int*)malloc(sizeof(int)*Length*Length);C=(int*)malloc(sizeof(int)*Length*Length);InitMatrix(A,B,Length);startTime=clock();for(i=0;iLength;i++){for(j=0;jLength;j++){C[i*Length+j]=0;for(k=0;kLength;++k){C[i*Length+j]+=A[i*Length+k]*B[k*Length+j];}}}//forendTime=clock();totalTime=(double)(endTime-startTime)/CLOCKS_PER_SEC;printf(串行稠密矩阵乘法过程总共花的时间:%.4fs\n,totalTime);del();return0;}2.执行时间截图代码部分完成后，就要传到集群上去运行。以下的截图是我在集群上运行程序的时间。DensMulMatrixSerial.c：图1稠密矩阵串行乘法DenseMulMatrixMPI.c，np=2：图2np=2的稠密矩阵并行乘法DenseMulMatrixMPI.c，np=4：图3np=4的稠密矩阵并行乘法DenseMulMatrixMPI.c，np=8：图4np=8的稠密矩阵并行乘法DenseMulMatrixMPI.c，np=16：图5np=16的稠密矩阵并行乘法DenseMulMatrixMPI.c，np=32：图6np=32的稠密矩阵并行乘法SparseMulMatrixSerial.c图7稀疏矩阵串行乘法SparseMulMatrixMPI.c，np=2：图8np=2的稀疏矩阵并行乘法SparseMulMatrixMPI.c，np=4：图9np=4的稀疏矩阵并行乘法SparseMulMatrixMPI.c，np=8：图10np=8的稀疏矩阵并行乘法SparseMulMatrixMPI.c，np=16：图11np=16的稀疏矩阵并行乘法SparseMulMatrixMPI.c，np=32：图12np=32的稀疏矩阵并行乘法3.统计数据分析矩阵相乘程序的执行时间、加速比：方阵阶固定为1000，为减少误差，每项实验进行5次，取平均值作为实验结果（一切时间数据均以以上截图为准）。所用到的公式：加速比=顺序执行时间/并行执行时间(1)稠密矩阵乘法串行执行平均时间T=(12.8000+13.0900+13.3500+12.8200+14.6200)/5=13.498s；并行执行时间如表1：表1不同进程数目下的并行执行时间（秒）进程数时间(s)2481632第1次19.53095.26393.45443.560417.0224第2次20.76785.20253.61143.359112.1877第3次19.14355.55993.08762.843115.2895第4次18.63765.67902.72052.245812.3578第5次17.47245.42113.61763.815213.5320平均值19.11045.42533.29833.164714.0779加速比如表2：表2不同进程数目下的加速比进程数2481632加速比0.70632.48804.09244.26520.9588图13不