矩阵乘法的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,1nnnnnnna1,...,1,1,1..1,...,1,1,11,...,1,1,11,...,1,1,1b输入：方阵的阶n、并行域的线程数输出：c中所有元素之和、程序的执行时间提示：a,b,c的元素定义为int型，c中所有元素之各定义为longlong型。Windows计时:用time.h中的clock_tclock(void)函数得到当前程序执行的时间Linux计时:#includesys/time.htimevalstart,end;gettimeofday(&start,NULL);gettimeofday(&end,NULL);coutexecutiontime:(end.tv_sec-start.tv_sec)+(double)(end.tv_usec-start.tv_usec)/1000000secondsendl;答：在windows下使用MicrosofeVisualStudio编程，源代码如下：#includeomp.h#includestdio.h#includetime.h#defineNN2000inta[NN][NN],b[NN][NN];longlongc[NN][NN];voidsolve(intn,intnum_thread){inti,j,t,k,time;clock_tstartTime,endTime;longlongsum;omp_set_num_threads(num_thread);for(i=0;in;i++)//对矩阵a和矩阵b进行初始化{t=i+1;for(j=0;jn;j++){a[i][j]=t++;b[i][j]=1;}}startTime=clock();sum=0;#pragmaompparallelshared(a,b,c)private(i,j,k){#pragmaompforschedule(dynamic)for(i=0;in;i++){for(j=0;jn;j++){c[i][j]=0;for(k=0;kn;k++){c[i][j]+=a[i][k]*b[k][j];}}}}for(i=0;in;i++)for(j=0;jn;j++)sum+=c[i][j];endTime=clock();time=endTime-startTime;printf(sum=%lldtime=%dms\n,sum,time);}intmain(){intn,num_thread;while(scanf(%d%d,&n,&num_thread)!=EOF){solve(n,num_thread);}return0;}2.分析矩阵相乘程序的执行时间、加速比和效率：方阵阶固定为1000，节点数分别取1、2、4、8、16和32时，为减少误差，每项实验进行5次，取平均值作为实验结果。答：串行执行时程序的执行时间为：T=15.062s加速比=顺序执行时间/并行执行时间效率=加速比/节点数表1不同节点数下程序的执行时间（秒）节点数实验结果12481632第1次16.6408.1724.0782.1251.0930.594第2次16.4228.1564.1722.1411.0780.578第3次16.4068.2664.0782.1251.0940.563第4次16.7818.1724.0792.1091.0940.563第5次16.4228.1714.0782.1251.0930.578平均值16.53428.18744.09702.12501.09040.5752图1不同节点数下程序的执行时间图2不同节点数下程序的加速比图3不同节点数下程序的效率执行时间的分析：随着节点数的增加，程序的执行时间减少，大概可以从结果中得出，随着节点书的增加一倍，执行时间减少一半加速比的分析：随着节点数的增加，程序的加速比增加，大概可以从结果中得出，随着节点书的增加一倍，加速相应的增加接近一倍效率的分析：随着节点数的增加，程序的效率逐渐减少3.分析矩阵相乘程序的问题规模与效率的关系：固定节点数为4，让方阵阶从200到1600之间变化，每隔100取一个值。（为了减少时间，每项实验可只执行1次）答：表2相同节点数下不同问题规模程序的执行时间与效率方阵阶数并行执行时间串行执行时间效率2000.0150.0470.7833333000.0160.1091.7031254000.0630.2971.1785715000.1560.6571.0528856000.4061.641.0098527000.9073.5780.9862188001.6096.360.9881919002.57810.1090.98031410003.81214.8910.97658711005.3921.0320.9755112007.34428.7340.97814513009.68837.9370.978969140012.42248.640.978908150015.65660.9380.973077160019.23474.8290.972614图3.1不同问题规模下程序的效率问题规模与效率的关系分析：随着问题规模的增加，程序的效率趋于稳定，但是略微有点下降。嵌套循环中,如果外层循环迭代次数较少时,如果将来CPU核数增加到一定程度时,创建的线程数将可能小于CPU核数。另外如果内层循环存在负载平衡的情况下，很难调度外层循环使之达到负载平衡。下面以矩阵乘法作为例子来讲述如何将嵌套循环并行化，以满足上述扩展性和负载平衡需求。一个串行的矩阵乘法的函数代码如下：/**矩阵串行乘法函数@paramint*a-指向要相乘的第个矩阵的指针@paramintrow_a-矩阵a的行数@paramintcol_a-矩阵a的列数@paramint*b–指向要想成的第个矩阵的指针@paramintrow_b-矩阵b的行数@paramintcol_b-矩阵b的列数@paramint*c-计算结果的矩阵的指针@paramintc_size-矩阵c的空间大小（总元素个数）@returnvoid–无*/voidMartrix_Multiply(int*a,introw_a,intcol_a,int*b,introw_b,intcol_b,int*c,intc_size){If(col_a!=row_b||c_sizerow_a*col_b){return;}inti,j,k;//#pragmaompforprivate(i,j,k)for(i=0;irow_a;i++){introw_i=i*col_a;introw_c=i*col_b;for(j=0;jcol_b;j++){c[row_c+j]=0;for(k=0;krow_b;k++){c[row_c+j]+=a[row_i+k]*b[k*col_b+j];}}}}如果在外层循环前面加上OpenMP的for语句时，它就变成了一个并行的矩阵乘法函数，但是这样简单地将其并行化显然无法满足前面所述的扩展性需求。其实可以采用一个简单地方法将最外层循环和第2层循环合并成一个循环，下面便是采用合并循环后的并行实现。voidParallel_Matrix_Multiply(int*a,introw_a,intcol_a,int*b,introw_b,intcol_b,int*c,intc_size){If(col_a!=row_b){return;}inti,j,k;intindex;intborder=row_a*col_b;i=0;j=0;//#pragmaompparallelprivate(i,j,k)num_threads(dtn(border,1))for(index=0;indexborder;index++){i=index/col_b;j=index%col_b;introw_i=i*col_a;introw_c=i*col_b;c[row_c+j]=0;for(k=0;krow_b;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++；上面这种优化，省去了除法，效率高，但是只能在串行代码中使用，因为它存在循环迭代间的依赖关系，无法将其正确地并行