当前位置：文档之家› 矩阵乘法的OpenMP实现及性能分析

矩阵乘法的OpenMP实现及性能分析

一. 实验目的

1) 用OpenMP 实现最基本的数值算法“矩阵乘法” 2) 掌握for 编译制导语句 3) 对并行程序进行简单的性能

二. 实验环境

1) 硬件环境：32核CPU 、32G 内存计算机；

2) 软件环境：Linux 、Win2003、GCC 、MPICH 、VS2008；

4) Windows 登录方式：通过远程桌面连接192.168.150.197，用户名和初始密码都是自己的学号。

三. 实验内容

1. 用OpenMP 编写两个n 阶的方阵a 和b 的相乘程序，结果存放在方阵c 中，其中乘法用for 编译制导语句实现并行化操作，并调节for 编译制导中schedule 的参数，使得执行时间最短，写出代码。方阵a 和b 的初始值如下：

??????????

?????????

?-++++=12,...,2,1,..2,...,5,4,31,...,4,3,2,...,3,2,1n n n n n n n a ??

?????????????????

1,...,1,1,1..1,...,1,1,11,...,1,1,11,...,

1,1,1b 输入：

方阵的阶n 、并行域的线程数输出：

c 中所有元素之和、程序的执行时间提示：

a,b,c 的元素定义为int 型，c 中所有元素之各定义为long long 型。 Windows 计时:

用中的clock_t clock( void )函数得到当前程序执行的时间 Linux 计时: #include timeval start,end;

gettimeofday(&start,NULL);

gettimeofday(&end,NULL);

cout<<"execution time:"<< (https://www.doczj.com/doc/88894503.html,_https://www.doczj.com/doc/88894503.html,_sec)+(double)(https://www.doczj.com/doc/88894503.html,_https://www.doczj.com/doc/88894503.html,_usec)/ 1000000<<"seconds" <

答：

在windows下使用Microsofe Visual Studio编程，源代码如下：

#include

#define NN 2000

int a[NN][NN], b[NN][NN];

long long c[NN][NN];

void solve(int n, int num_thread)

{

int i, j, t, k, time;

clock_t startTime, endTime;

long long sum;

omp_set_num_threads(num_thread);

for(i=0;i

{

t=i+1;

for(j=0;j

{

a[i][j]=t++;

b[i][j]=1;

}

startTime=clock();

sum=0;

#pragma omp parallel shared(a,b,c) private(i,j,k)

{

#pragma omp for schedule(dynamic)

for(i=0;i

{

for(j=0;j

{

c[i][j]=0;

for(k=0;k

{

c[i][j]+=a[i][k]*b[k][j];

}

for(i=0;i

endTime=clock();

time=endTime-startTime;

printf("sum=%lld time=%dms\n",sum,time);

}

int main()

{

int n, num_thread;

while(scanf("%d%d",&n,&num_thread)!=EOF)

{

solve(n,num_thread);

}

return 0;

}

2.分析矩阵相乘程序的执行时间、加速比和效率：方阵阶固定为1000，节点数分别取1、2、4、8、16和32时，为减少误差，每项实验进行5次，取平均值作为实验结果。

答：串行执行时程序的执行时间为：T = 15.062s

加速比=顺序执行时间/并行执行时间

效率=加速比/节点数

表1 不同节点数下程序的执行时间（秒）

第1次 16.640 8.172 4.078 2.125 1.093 0.594 第2次 16.422 8.156 4.172 2.141 1.078 0.578 第3次 16.406 8.266 4.078 2.125 1.094 0.563 第4次 16.781

8.172 4.079 2.109 1.094 0.563 第5次 16.422

8.171

4.078 2.125 1.093 0.578 平均值

16.5342 8.1874

4.0970

2.1250

1.0904

0.5752

图1 不同节点数下程序的执行时间

图2 不同节点数下程序的加速比

图3 不同节点数下程序的效率

执行时间的分析：

随着节点数的增加，程序的执行时间减少，大概可以从结果中得出，随着节点书的增加一倍，执行时间减少一半

加速比的分析：

随着节点数的增加，程序的加速比增加，大概可以从结果中得出，随着节点书的增加一倍，加速相应的增加接近一倍

效率的分析：

随着节点数的增加，程序的效率逐渐减少

3.分析矩阵相乘程序的问题规模与效率的关系：固定节点数为4，让方阵阶从200到1600之间变化，每隔100取一个值。（为了减少时间，每项实验可只执行1次）

答：

表2 相同节点数下不同问题规模程序的执行时间与效率

方阵阶数并行执

行时间

串行执

行时间

效率

200 0.015 0.047 0.783333 300 0.016 0.109 1.703125 400 0.063 0.297 1.178571 500 0.156 0.657 1.052885 600 0.406 1.64 1.009852 700 0.907 3.578 0.986218 800 1.609 6.36 0.988191 900 2.578 10.109 0.980314 1000 3.812 14.891 0.976587 1100 5.39 21.032 0.97551 1200 7.344 28.734 0.978145 1300 9.688 37.937 0.978969 1400 12.422 48.64 0.978908 1500 15.656 60.938 0.973077 1600 19.234 74.829 0.972614

图3.1 不同问题规模下程序的效率

问题规模与效率的关系分析：

随着问题规模的增加，程序的效率趋于稳定，但是略微有点下降。

嵌套循环中,如果外层循环迭代次数较少时,如果将来CPU核数增加到一定程度时,创建的线程数将可能小于CPU核数。另外如果内层循环存在负载平衡的情况下，很难调度外层循环使之达到负载平衡。

下面以矩阵乘法作为例子来讲述如何将嵌套循环并行化，以满足上述扩展性和负载平衡需求。

一个串行的矩阵乘法的函数代码如下：

/**矩阵串行乘法函数

@param int*a -指向要相乘的第个矩阵的指针

@param int row_a -矩阵a的行数

@param int col_a -矩阵a的列数

@param int *b –指向要想成的第个矩阵的指针

@param int row_b -矩阵b的行数

@param int col_b -矩阵b的列数

@param int *c -计算结果的矩阵的指针

@param int c_size -矩阵c的空间大小（总元素个数）@return void –无

void Martrix_Multiply(int *a, int row_a,int col_a,

int*b,int row_b,int col_b,

int*c,int c_size)

{

If(col_a!=row_b||c_size

{

return;

}

int i,j,k;

//#pragma omp for private(i,j,k)

for(i = 0;i

{

int row_i=i*col_a;

int row_c=i*col_b;

for(j=0;j

{

c[row_c+j]=0;

for(k=0;k

{

c[row_c+j]+=a[row_i+k]*b[k*col_b+j];

}

如果在外层循环前面加上OpenMP的for语句时，它就变成了一个并行的矩阵乘法函数，但是这样简单地将其并行化显然无法满足前面所述的扩展性需求。

其实可以采用一个简单地方法将最外层循环和第2层循环合并成一个循环，下面便是采用合并循环后的并行实现。

void Parallel_Matrix_Multiply(int *a,int row_a,int col_a,

int *b,int row_b,int col_b,

int *c,int c_size)

{

If(col_a!=row_b)

{

return;

}

int i,j,k;

int index;

int border=row_a*col_b;

i=0;

j=0;

//#pragma omp parallel private(i,j,k) num_threads(dtn(border,1))

for(index = 0;index

{

i=index/col_b;

j=index%col_b;

int row_i=i*col_a;

int row_c=i*col_b;

c[row_c+j]=0;

for(k=0;k

{

c[row_c+j]+=a[row_i+k]*b[k*col_b+j];

}

从上面代码可以看出，合并后的循环便捷border=row_a*col_b；即等于原来的两个循环边界之积，然后再循环中计算出原来的外层循环和第2层循环的迭代变量i和j，采用除法和取余来求出i和j的值。

需要值得注意的是，上面求i和j的值必须要保证循环迭代的独立性，即不能有循环迭代间的依赖关系。不能讲求i和j的值得过程优化成如下的形式

if(j==col_b)

{

j=0;

i++;

}

//.......此处代表实际的矩阵乘法代码

j++；

上面这种优化，省去了除法，效率高，但是只能在串行代码中使用，因为它存在循环迭代间的依赖关系，无法将其正确地并行

_矩阵的Kronecker乘积的性质与应用

矩阵Kronecker乘积的性质与应用摘要按照矩阵乘法的定义，我们知道要计算矩阵的乘积AB，就要求矩阵A的列数和矩阵B的行数相等，否则乘积AB是没有意义的。那是不是两个矩阵不满足这个条件就不能计算它们的乘积呢？本文将介绍矩阵的一种特殊乘积B A ，它对矩阵的行数和列数的并没有具体的要求，它叫做矩阵的Kronecker积（也叫直积或张量积）。本文将从矩阵的Kronecker积的定义出发，对矩阵的Kronecker 积进行介绍和必要的说明。之后，对Kronecker积的运算规律，可逆性，秩，特征值，特征向量等性质进行了具体的探究，得出结论并加以证明。此外，还对矩阵的拉直以及矩阵的拉直的性质进行了说明和必要的证明。矩阵的Kronecker积是一种非常重要的矩阵乘积，它应用很广，理论方面在诸如矩阵方程的求解，矩阵微分方程的求解等矩阵理论的研究中有着广泛的应用，实际应用方面在诸如图像处理，信息处理等方面也起到重要的作用。本文讨论矩阵的Kronecker积的性质之后还会具体介绍它在矩阵方程中的一些应用。关键词：矩阵；Kronecker积；矩阵的拉直；矩阵方程；矩阵微分方程Properties and Applications of matrix Kronecker

product Abstract According to the definition of matrix multiplication, we know that to calculate the matrix product AB, requires the number of columns of the matrix A and matrix B is equal to the number of rows, otherwise the product AB makes no sense.That is not two matrices not satisfy this condition will not be able to calculate their product do?This article will describe a special matrix product B A , the number of rows and columns of a matrix and its no specific requirements, it is called the matrix Kronecker product (also called direct product or tensor product). This paper will define the matrix Kronecker product of view, the Kronecker product matrix are introduced and the necessary instructions. Thereafter, the operation rules Kronecker product, the nature of reversibility, rank, eigenvalues, eigenvectors, etc. specific inquiry, draw conclusions and to prove it. In addition, the properties of the stretch of matrix and its nature have been described and the necessary proof. Kronecker product matrix is a very important matrix product, its use is very broad, theoretical research, and other matrix solving differential equations, such as solving the matrix equation matrix theory has been widely applied in practical applications such as image processing aspects of information processing, also play an important role. After the article discusses the nature of the matrix Kronecker product it will introduce a number of specific applications in the matrix equation. Keywords: Matrix; Kronecker product; Stretch of matrix; Matrix equation; Matrix Differential Equations 目录

矩阵分析实验报告

矩阵分析实验报告学院：电气学院专业：控制工程姓名：XXXXXXXX 学号：211208010001

矩阵分析实验报告实验题目利用幂法求矩阵的谱半径实验目的与要求 1、熟悉matlab 矩阵实验室的功能和作用； 2、利用幂法求矩阵的谱半径； 3、会用matlab 对矩阵分析运算。实验原理理念谱半径定义：设n n A C ?∈，1λ，2λ，3λ，，j λ， n λ是A 的n 个特征值，称 ()max ||j j A ρλ= 为关于A 的谱半径。关于矩阵的谱半径有如下结论：设n n A C ?∈，则（1）[]()()k k A A ρρ=；（2）2 2()()()H H A A AA A ρρ==。由于谱半径就是矩阵的主特征值，所以实验换为求矩阵的主特征值。算法介绍定义：如果1λ是矩阵A 的特征值，并且其绝对值比A 的任何其他特征值的绝对值大，则称它为主特征值。相应于主特征值的特征向量1V 称为主特征向量。定义：如果特征向量中最大值的绝对值等于单位值（例如最大绝对值为1），则称其为是归一化的。

通过形成新的向量' 12=c n V （1/）[v v v ]，其中c=v 且1max {},j i n i ≤≤=v v 可将特征向量 '12n [v v v ]进行归一化。设矩阵A 有一主特征值λ，而且对应于λ有唯一的归一化特征向量V 。通过下面这个称为幂法（power method ）的迭代过程可求出特征对λ，V ，从下列向量开始： []' 0=111X （1）用下面递归公式递归地生成序列{}k X ： k k Y AX = k+11 1 k k X Y c += （2）其中1k c +是k Y 绝对值最大的分量。序列{}k X 和{}k c 将分别收敛到V 和λ： 1lim k X V =和lim k c λ= （3）注：如果0X 是一个特征向量且0X V ≠，则必须选择其他的初始向量。幂法定理：设n ×n 矩阵A 有n 个不同的特征值λ1，λ2，···，，λn ，而且它们按绝对值大小排列，即： 123n λλλλ≥≥≥???≥ (4) 如果选择适当的X 0，则通过下列递推公式可生成序列{[() ()( ) ]}12k k k k n X x x x '=???和 {}k c ： k k Y AX = (5) 和： 11 1k k k X Y c ++= (6) 其中： () 1k k j c x +=且{} ()()1max k k j i i n x x ≤≤= (7) 这两个序列分别收敛到特征向量V 1和特征值λ1。即： 1lim k k X V →∞ =和1lim k k c λ→∞ = (8) 算法收敛性证明证明：由于A 有n 个特征值，所以有对应的特征向量V j ，j=1，2，···n 。而且它们是

实现稀疏矩阵(采用三元组表示)的基本运算实验报告

实现稀疏矩阵（采用三元组表示）的基本运算实验报告一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；（3）输出a + b 的三元组；（4）输出 a * b 的三元组；三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={ | 1≤i≤m , 1≤j ≤n-1} Col ={| 1≤i≤m-1,1≤j ≤n} 基本操作:

CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在