《《高级程序设计》实验报告2018(共6页).doc》由会员分享，可在线阅读，更多相关《《高级程序设计》实验报告2018(共6页).doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上信息与通信工程学院高级程序设计实验报告学 号：S姓 名：王世督专 业：信息与通信工程现场演示（7分）实验结果（7分）实验报告（6分）实验成绩实验一（共20分）实验二（共20分）总成绩（共40分）2018年3月实验一 使用二维动态数组实现大矩阵乘法一、任务描述（1）使用二维动态数组，实现N*N矩阵的乘法，其中N=1K。（2）测试不同的循环嵌套方式，分析运算时间差异的原因。二、设计方案普通矩阵乘法程序（为简单起见，以 n阶方阵举例）有内外 3 层循环，计算模式是 A 矩阵和 B 矩阵分别按照行访问和列访问。由于 C 语言按行存储二维数组，因此程序访问 Bkj 的数据分散在
2、内存上。当 n的规模较大时，这种循环访问、间隔存放的内侧列数据的模式导致 Cache 不命中情况频繁发生，需要每次从主存读取，严重影响程序效率。核心程序代码如下：for (i=0; in; i+) for (j=0; jn; j+) for (k=0; kn; k+) Cij += Aik*Bkj;调整顺序矩阵乘法：研究上述普通矩阵乘法，发现变量值之间没有相关性，因此可以把内层的 j循环和 k 循环颠倒次序而不影响程序正确性。这种顺序调整的好处是程序访问 Bkj 的数据分布在连续的内存区域，当第一次访问某个主存单元后，相邻的多个单元装入多级高速缓存中（根据不同处理器 Cache 大小和数据带宽
3、而不同），下次访问直接 Cache 命中，大大降低了 Cache 未命中率，发挥了 Cache 存取比主存存取速度快的优势。三、主要程序#define N 1024int *malloc2Dint(int a, int b)/连续型int i;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; i a; i+) ppi = p + b * i;return pp;void clear(int
4、*a)int i, j;for (i = 0; i N; i+) for (j = 0; j N; j+) aij = 0;int compare(int *a, int *b)int i, j, k;k = 0;for (i = 0; i N; i+) for (j = 0; j N; j+) if (aij != bij) k = 1;break;return k;int main()long int clk_0, clk_1;/计时float clk;int *A, *B, *C, *D, flag;/矩阵A = malloc2Dint(N, N);B = malloc2Dint(N,
5、N);C = malloc2Dint(N, N);D = malloc2Dint(N, N);int i, j, k;cout.setf(ios:fixed);for (i = 0; i N; i+) for (j = 0; j j=kclear(C);flag = 0;clk_0 = clock();/msfor (i = 0; i N; i+) for (j = 0; j N; j+) for (k = 0; k N; k+) Cij += Aik * Bkj;clk_1 = clock();clk = (float)(clk_1 - clk_0) / 1000;for (i = 0; i
6、 N; i+) for (j = 0; j N; j+) Dij = Cij;flag = compare(C, D);cout j=k时所需时间： setw(6) fixed setprecision(3) clk s t flag endl;四、测试结果及分析调整循环执行次序后，可以看出不同的循环顺序对运算时间的影响非常大。最优顺序与最差顺序相比执行效率相差3.5倍。实验二 大矩阵乘法的优化一、任务描述在实验一的基础上，选出最快的一种实现方式，在同等的运行环境下进一步优化，减少运算时间。二、设计方案通常优化程序效率的方式有两种：降低算法复杂度和减少存取数据所花费的时间。针对矩阵乘法而言，有
7、许多降低计算复杂度的研究，但计算机编程实现比较困难，而且优化效率不高。这类计算密集型应用的访存开销是影响程序效率的瓶颈，计算机科学家解决类似问题的思考方式是抓住主要矛盾，结合计算机系统结构特点，利用高速缓存提升效率，利用并行部件分而治之。三、主要程序clear(C);flag = 0;int keep2, a11, a21, a12, a22;clk_0 = clock();/msfor (i = 0; i N; i = i + 2) for (k = 0; k N; k = k + 2) a11 = Aik;a21 = Ai + 1k;a12 = Aik + 1;a22 = Ai + 1k
8、+ 1;for (j = 0; j N; j+) keep0 = Bkj;keep1 = Bk + 1j;Cij += a11 * keep0 + a12 * keep1 ;Ci + 1j += a21 * keep0 + a22 * keep1 ;clk_1 = clock();clk = (float)(clk_1 - clk_0) / 1000;flag = compare(C, D);cout 优化后所需时间： setw(6) fixed setprecision(3) clk s t flag c;四、测试结果及分析Cache命中率大幅提升，执行效率比普通矩阵乘法提高 5 倍；进一步进行内层循环展开，执行效率提高 8 倍；采用简单分块的矩阵乘法比普通矩阵乘法提高 4 倍；采用 4 线程并行乘法比普通矩阵乘法提高 2.6 倍。理论上双核并行高 2 倍，多线程能进一步提高 20%30%，符合 Intel 公司该款处理器的设计参数。从计算思维逐步求精的方专心-专注-专业