《高级程序设计》实验报告2018

信息与通信工程学院《高级程序设计》实验报告学号：S317080092姓名：王世督专业：信息与通信工程现场演示（7分）实验结果（7分）实验报告（6分）实验成绩实验一（共20分）实验二（共20分）总成绩（共40分）2018年3月实验一使用二维动态数组实现大矩阵乘法一、任务描述（1）使用二维动态数组，实现N*N矩阵的乘法，其中N=1K。（2）测试不同的循环嵌套方式，分析运算时间差异的原因。二、设计方案普通矩阵乘法程序（为简单起见，以n阶方阵举例）有内外3层循环，计算模式是A矩阵和B矩阵分别按照行访问和列访问。由于C语言按行存储二维数组，因此程序访问B[k][j]的数据分散在内存上。当n的规模较大时，这种循环访问、间隔存放的内侧列数据的模式导致Cache不命中情况频繁发生，需要每次从主存读取，严重影响程序效率。核心程序代码如下：for(i=0;in;i++)for(j=0;jn;j++)for(k=0;kn;k++)C[i][j]+=A[i][k]*B[k][j];调整顺序矩阵乘法：研究上述普通矩阵乘法，发现变量值之间没有相关性，因此可以把内层的j循环和k循环颠倒次序而不影响程序正确性。这种顺序调整的好处是程序访问B[k][j]的数据分布在连续的内存区域，当第一次访问某个主存单元后，相邻的多个单元装入多级高速缓存中（根据不同处理器Cache大小和数据带宽而不同），下次访问直接Cache命中，大大降低了Cache未命中率，发挥了Cache存取比主存存取速度快的优势。三、主要程序#defineN1024int**malloc2Dint(inta,intb)//连续型{inti;int**pp=(int**)malloc(sizeof(int*)*a);int*p=(int*)malloc(sizeof(int)*a*b);if(pp==NULL||p==NULL)exit(-1);for(i=0;ia;i++){pp[i]=p+b*i;}returnpp;}voidclear(int**a){inti,j;for(i=0;iN;i++){for(j=0;jN;j++){a[i][j]=0;}}}intcompare(int**a,int**b){inti,j,k;k=0;for(i=0;iN;i++){for(j=0;jN;j++){if(a[i][j]!=b[i][j]){k=1;break;}}}returnk;}intmain(){longintclk_0,clk_1;//计时floatclk;int**A,**B,**C,**D,flag;//矩阵A=malloc2Dint(N,N);B=malloc2Dint(N,N);C=malloc2Dint(N,N);D=malloc2Dint(N,N);inti,j,k;cout.setf(ios::fixed);for(i=0;iN;i++){for(j=0;jN;j++){A[i][j]=rand()%(100);B[i][j]=rand()%(100);}}//1:i=j=kclear(C);flag=0;clk_0=clock();//msfor(i=0;iN;i++){for(j=0;jN;j++){for(k=0;kN;k++){C[i][j]+=A[i][k]*B[k][j];}}}clk_1=clock();clk=(float)(clk_1-clk_0)/1000;for(i=0;iN;i++){for(j=0;jN;j++){D[i][j]=C[i][j];}}flag=compare(C,D);couti=j=k时所需时间：setw(6)fixedsetprecision(3)clks\tflagendl;四、测试结果及分析调整循环执行次序后，可以看出不同的循环顺序对运算时间的影响非常大。最优顺序与最差顺序相比执行效率相差3.5倍。实验二大矩阵乘法的优化一、任务描述在实验一的基础上，选出最快的一种实现方式，在同等的运行环境下进一步优化，减少运算时间。二、设计方案通常优化程序效率的方式有两种：降低算法复杂度和减少存取数据所花费的时间。针对矩阵乘法而言，有许多降低计算复杂度的研究，但计算机编程实现比较困难，而且优化效率不高。这类计算密集型应用的访存开销是影响程序效率的瓶颈，计算机科学家解决类似问题的思考方式是抓住主要矛盾，结合计算机系统结构特点，利用高速缓存提升效率，利用并行部件分而治之。三、主要程序clear(C);flag=0;intkeep[2],a11,a21,a12,a22;clk_0=clock();//msfor(i=0;iN;i=i+2){for(k=0;kN;k=k+2){a11=A[i][k];a21=A[i+1][k];a12=A[i][k+1];a22=A[i+1][k+1];for(j=0;jN;j++){keep[0]=B[k][j];keep[1]=B[k+1][j];C[i][j]+=a11*keep[0]+a12*keep[1];C[i+1][j]+=a21*keep[0]+a22*keep[1];}}}clk_1=clock();clk=(float)(clk_1-clk_0)/1000;flag=compare(C,D);cout优化后所需时间：setw(6)fixedsetprecision(3)clks\tflagendl;intc;cinc;}四、测试结果及分析Cache命中率大幅提升，执行效率比普通矩阵乘法提高5倍；进一步进行内层循环展开，执行效率提高8倍；采用简单分块的矩阵乘法比普通矩阵乘法提高4倍；采用4线程并行乘法比普通矩阵乘法提高2.6倍。理论上双核并行高2倍，多线程能进一步提高20%~30%，符合Intel公司该款处理器的设计参数。从计算思维逐步求精的方