2022年2022年矩阵乘法的OpenMP实现及性能分析 .pdf

一. 实验目的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 , 1nnnnnnna1,.,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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - gettimeofday(&start,NULL); gettimeofday(&end,NULL); coutexecution time: (end.tv_sec-start.tv_sec)+(double)(end.tv_usec-start.tv_usec)/ 1000000seconds endl; 答：在 windows 下使用 Microsofe Visual Studio编程，源代码如下：#include #include #include #define NN 2000 int aNNNN, bNNNN; longlong cNNNN; void solve(int n, int num_thread) int i, j, t, k, time; clock_t startTime, endTime; longlong sum; omp_set_num_threads(num_thread); for (i=0;in;i+)/ 对矩阵 a和矩阵 b进行初始化 t=i+1; for(j=0;jn;j+) aij=t+; bij=1; startTime=clock(); sum=0; #pragma omp parallel shared(a,b,c) private(i,j,k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - #pragma omp for schedule(dynamic) for (i=0;in;i+) for(j=0;jn;j+) cij=0; for(k=0;kn;k+) cij+=aik*bkj; for (i=0;in;i+)for(j=0;jn;j+) sum+=cij; endTime=clock(); time=endTime-startTime; printf(sum=%lld time=%dmsn,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 加速比 =顺序执行时间 /并行执行时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 效率 =加速比 /节点数表 1 不同节点数下程序的执行时间（秒）节点数实验结果1 2 4 8 16 32 第 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 不同节点数下程序的执行时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 图 2 不同节点数下程序的加速比图 3 不同节点数下程序的效率名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 执行时间的分析：随着节点数的增加，程序的执行时间减少，大概可以从结果中得出，随着节点书的增加一倍，执行时间减少一半加速比的分析：随着节点数的增加，程序的加速比增加，大概可以从结果中得出，随着节点书的增加一倍，加速相应的增加接近一倍效率的分析：随着节点数的增加，程序的效率逐渐减少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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 图 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 的行数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 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_sizerow_a*col_b) return; int i,j,k; /#pragma omp for private(i,j,k) for(i = 0;irow_a;i+) int row_i=i*col_a; int row_c=i*col_b; for(j=0;jcol_b;j+) crow_c+j=0; for(k=0;krow_b;k+) crow_c+j+=arow_i+k*bk*col_b+j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 如果在外层循环前面加上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;indexborder;index+) i=index/col_b; j=index%col_b; int row_i=i*col_a; int row_c=i*col_b; crow_c+j=0; for(k=0;krow_b;k+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - crow_c+j+=arow_i+k*bk*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+ ；上面这种优化，省去了除法，效率高，但是只能在串行代码中使用，因为它存在循环迭代间的依赖关系，无法将其正确地并行名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -