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

包括各种执行时间截图和表格

华 中 科 技 大 学

课程名称 并行处理

实验名称 矩阵乘法的实现及加速比分析 考生姓名 李佩佩 考生学号 M201372734 系、年级 计算机软件与理论2013级 类 别 硕士研究生 考试日期 2014年1月3日

包括各种执行时间截图和表格

一. 实验目的

1) 学会如何使用集群

2) 掌握怎么用并行或分布式的方式编程 3) 掌握如何以并行的角度分析一个特定的问题

二. 实验环境

1) 硬件环境：4核CPU、2GB内存计算机；

2) 软件环境： Windows XP、MPICH2、VS2010、Xmanager Enterprise3； 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,int len)会有所不同。这里需要说明一下，一开始对于矩阵A和B的初始化是两次调用InitMatrix(int *M ,int len)，生成A和B矩阵，但是随后我发现，由于两次调用方法InitMatrix的时间间隔非常短，又由于srand()函数的特点，导致生成的矩阵A和B完全一样；然后，我就在两次调用之间加入了语句“Sleep(1000)；”，加入头文件“#include <windows.h>” ，这样生成的A、B矩阵就不一样了，但很快问题又出现了，在Xshell中不能识别头文件“#include <windows.h>”。所以，最后决定用下面的方法生成矩阵A和B，B是A的转置。 //稠密矩阵的生成方法

void InitMatrix(int *M,int *N,int len) {

srand((unsigned)time( NULL)); for(i=0; i < len*len; i++)

包括各种执行时间截图和表格

{

M[i] = rand() % 2; }

for(i=0;i<len;i++){ for(j=0;j<len;j++){

N[i*len+j]=M[j*len+i]; } } }

//稀疏矩阵的生成方法

void InitMatrix(int *M, int *N, int len) {

for(i=0;i<len*len;i++) M[i]=0;

srand((unsigned)time( NULL)); for(m=0;m<224;m++){ for(n=0;n<224;n++){ i=rand()%len; j=rand()%len; M[i*len+j]=1; } }

for(i=0;i<len;i++){ for(j=0;j<len;j++){

N[i*len+j]=M[j*len+i]; } } }

输入：并行执行的进程数procsNum，对于串行计算，只需要np=1； 输出：程序的执行时间。

在Windows XP下使用Microsoft Visual Studio2010编程，由于稀疏矩阵和稠密矩阵的代码只是初始化部分不同，所以以稠密矩阵乘法为例，列出并行和串行的源代码。

并行计算的矩阵乘法源代码：DenseMulMatrixMPI.c #include <stdio.h> #include <stdlib.h> #include <mpi.h> #include <time.h> #define Length 1000

int *A,*B,*C,*buffer,*ans; int temp,i,j,k;

int procsID,procsNum,line;

包括各种执行时间截图和表格

double startTime,endTime,totalTime;

void InitMatrix(int *M,int *N,int len);//实现部分见上面 void del(){ free(A); free(B); free(C);

free(buffer); free(ans); }

int main(int argc,char *argv[]) {

MPI_Status status;

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;i<procsNum;i++) {

MPI_Send(B,Length*Length,MPI_INT,i,0,

MPI_COMM_WORLD);

}

for (i=1;i<procsNum;i++) {

MPI_Send(A+(i-1)*line*Length,Length*line, MPI_INT,i,1,MPI_COMM_WORLD);

}

for (k=1;k<procsNum;k++) {

MPI_Recv(ans,line*Length,MPI_INT,k,3, MPI_COMM_WORLD,&status);

for (i=0;i<line;i++) {

包括各种执行时间截图和表格

for (j=0;j<Length;j++) {

C[((k-1)*line+i)*Length+j] =

ans[i*Length+j];

} } }

for (i=(procsNum-1)*line;i<Length;i++) {

for (j=0;j<Length;j++) {

temp=0;

for (k=0;k<Length;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); }//if

else {

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;i<line;i++) {

for (j=0;j<Length;j++) {

temp=0;

for(k=0;k<Length;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);

}//else

MPI_Finalize();

del();

包括各种执行时间截图和表格

return 0; }

串行计算的矩阵乘法源代码：DenseMulMatrixSerial.c #include <stdio.h> #include <stdlib.h> #include <time.h> #define Length 1000

int *A,*B,*C; int i,j,k;

clock_t startTime, endTime; double totalTime;

void InitMatrix(int *M,int *N,int len);//实现部分见上面 void del(){ free(A); free(B); free(C); }

int main() {

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; i < Length; i ++) {

for(j = 0; j < Length; j ++) {

C[i * Length + j] = 0;

for (k = 0; k < Length; ++k) { C[i * Length + j] += A[i * Length + k] *

B[k * Length + j];

} } }//for

endTime = clock(); totalTime = (double)(endTime - startTime) / CLOCKS_PER_SEC; printf("串行稠密矩阵乘法过程总共花的时间:%.4fs\n",

totalTime); del();

包括各种执行时间截图和表格

return 0; }

2.执行时间截图

代码部分完成后，就要传到集群上去运行。以下的截图是我在集群上运行程序的时间。

DensMulMatrixSerial.c：

图1 稠密矩阵串行乘法

DenseMulMatrixMPI.c，np=2：

图2 np=2的稠密矩阵并行乘法

DenseMulMatrixMPI.c，np=4：

图3 np=4的稠密矩阵并行乘法

包括各种执行时间截图和表格

DenseMulMatrixMPI.c，np=8：

图4 np=8的稠密矩阵并行乘法

DenseMulMatrixMPI.c，np=16：

图5 np=16的稠密矩阵并行乘法

DenseMulMatrixMPI.c，np=32：

图6 np=32的稠密矩阵并行乘法

包括各种执行时间截图和表格

SparseMulMatrixSerial.c

图7稀疏矩阵串行乘法

SparseMulMatrixMPI.c，np=2：

图8 np=2的稀疏矩阵并行乘法

SparseMulMatrixMPI.c，np=4：

图9 np=4的稀疏矩阵并行乘法

包括各种执行时间截图和表格

SparseMulMatrixMPI.c，np=8：

图10 np=8的稀疏矩阵并行乘法

SparseMulMatrixMPI.c，np=16：

图11 np=16的稀疏矩阵并行乘法

SparseMulMatrixMPI.c，np=32：

图12 np=32的稀疏矩阵并行乘法

包括各种执行时间截图和表格

3.统计数据

分析矩阵相乘程序的执行时间、加速比：方阵阶固定为1000，为减少误差，每项实验进行5次，取平均值作为实验结果（一切时间数据均以以上截图为准）。所用到的公式：加速比=顺序执行时间/并行执行时间 (1)稠密矩阵乘法

串行执行平均时间T = (12.8000+13.0900+13.3500+12.8200+14.6200)/5=13.498s； 并行执行时间如表1：

表1 不同进程数目下的并行执行时间（秒）

第1次 第2次 第3次 第4次 第5次 平均值

19.5309 5.2639 20.7678 5.2025 19.1435 5.5599 18.6376 5.6790 17.4724 5.4211 19.1104 5.4253

3.4544 3.6114 3.0876 2.7205 3.6176 3.2983

3.5604 3.3591 2.8431 2.2458 3.8152 3.1647

17.0224 12.1877 15.2895 12.3578 13.5320 14.0779

加速比如表2：

表2 不同进程数目下的加速比

2 0.7063

4 2.4880

8

4.0924

16 4.2652

32 0.9588

进程数 加速比

图13 不同进程数下程序的执行时间

包括各种执行时间截图和表格

(2)稀疏矩阵乘法

图14 不同进程数下程序的加速比

串行执行平均时间T = (12.9000+13.0400+14.2200+12.8000+12.2900)/5=13.0200s； 并行执行时间如表3：

第1次 第2次 第3次 第4次 第5次 平均值

13.6194 5.9733 15.2204 6.0063 13.0875 5.7812 12.8630 5.8452 15.2022 5.8014 13.9985 5.8815

3.1526 3.8717 3.6125 3.4547 3.1572 3.4497

2.6904 3.0452 2.3989 2.5145 2.7927 2.6883

10.9137 7.7873 8.0696 9.2154 10.4716 9.2915

加速比如表4：

进程数 加速比

2 0.9301

4 2.2137

8 3.7742

16 4.8432

32 1.4013

稀疏矩阵乘法程序在不同进程数目下的执行时间和加速比的图跟稠密矩阵差不多，在此就不画了。

四. 实验结论

1. 稠密矩阵串并行乘法

执行时间分析：并行时，随着进程数目的增多，并行计算的时间越来越短；当达到一定的进程数时，执行时间小到最小值；然后再随着进程数的增多，执行时间反而越来越长。串行时，程序的执行时间基本上趋于稳定。

包括各种执行时间截图和表格

加速比分析：根据并行计算的执行时间的分析及加速比的公式，可知随着进程数的增大，加速比也是逐渐增大到最大值；再随着进程数的增大，加速比就逐渐减小。

结论：并行计算时并不是进程数越多，执行的时间就越短，加速比也就越大。执行时间是从大到小，小到最小值再越来越大；加速比跟执行时间刚好相反变化。 1. 稠密、稀疏并行乘法

从统计的数据中可以看出，无论是串行还是并行计算，稀疏矩阵乘法执行时间要小于稠密矩阵乘法时间。但是由于本程序的稀疏矩阵没有压缩，所以有的数据有点偏差，执行时间的差别不是很大。

五. 附加内容

本实验的源代码及本报告在网上均有上传，下载网址如下： 源代码 报告

本文来源：https://www.bwwdw.com/article/jv8j.html