矩阵乘法运算效率

矩阵乘法运算效率 摘要 近年来，处理器运行速度的增长和存储器访问速度的增长之间存在着巨大的差距，这使得两者之间的速度差距 越来越大，现代计算机体系结构中广泛采用高速缓冲存储器(Cache)来缓解这两者之间的速度差距。 本文根据矩阵乘法运算的六种不同程序代码，构建了矩阵乘法运算时间的测试程序，得到矩阵乘法运算六种不 同版本的运行时间;并通过 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 六种不同矩阵乘法运算程序代码中的空间局部性与时间局部性，得出由于高速缓冲 存储器和程序访问的局部性差异，同一算法的不同程序代码运行时间相差很大。为了充分利用高速缓冲存储器，提 高程序运行效率，在编写程序时需要考虑程序和数据的空间局部性和时间局部性。 为了充分利用高速缓冲存储器，论文又给出了分块矩阵乘法运算程序，它可以进一步提高矩阵乘法运算效率。 关键字:高速缓冲存储器;矩阵乘法;分块矩阵;局部性原理;时间局部性;空间局部性 Abstract Recent years, there has been a big gap between the growth of processor and memory runs access speed, which makes the speed difference between them is more and more big . In modern computer system structure, Cache is widely used to alleviate the speed gap. Based on the six different program code of matrix multiplication, constructs the matrix multiplication time test procedures, obtaining the running time of matrix multiplication six different versions; And through the analysis of space localized and time localized in six different program code of matrix multiplication, it is concluded that due to the cache memory and the local differences of programs access, there is a huge difference in the running time of the same algorithm of different program code. In order to make full use of cache memory and improve program efficiency, it is needed to consider the space and time localized when programming. In order to make full use of cache memory, paper gives the program of partitioned matrix multiplication, which could further improve the matrix multiplication efficiency. Key words: Cache; matrix multiplication; block matrix; principle of locality; temporal locality; spatial locality 1 目录 摘要 ........................................................................................................................................................................................... 0 Abstract ..................................................................................................................................................................................... 0 第一章 概述 ............................................................................................................................................................................. 3 1.1 研究背景及意义 ........................................................................................................................................................ 3 1.2 研究内容 .................................................................................................................................................................... 4 第二章 基础知识 ..................................................................................................................................................................... 5 2.1 矩阵乘法运算 ............................................................................................................................................................ 5 2.2 高速缓冲存储器 ........................................................................................................................................................ 6 2.2.1 设置Cache的理论依据 ............................................................................................................................... 6 2.2.2 Cache的体系结构 ........................................................................................................................................ 8 2.2.3 Cache的相关知识 ........................................................................................................................................ 8 2.3 开发平台 .................................................................................................................................................................... 9 第三章 测试程序 ................................................................................................................................................................... 10 3.1.数据区的设定 ........................................................................................................................................................... 10 3.2.程序执行时间的计算方法 ....................................................................................................................................... 10 3.3.测试程序的运行结果保存方式 ............................................................................................................................... 11 3.4.测试程序代码 ........................................................................................................................................................... 12 第四章 结果和分析 ............................................................................................................................................................... 16 4.1实验结果图 ............................................................................................................................................................... 16 4.2实验结果分析 ........................................................................................................................................................... 17 第五章 改进的矩阵乘法运算 ............................................................................................................................................... 18 5.1分块的矩阵乘法运算 ............................................................................................................................................... 18 5.2分块的矩阵乘法运算实验结果和分析 ................................................................................................................... 19 21 第六章 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ...........................................................................................................................................................................参考文献 ................................................................................................................................................................................. 23 致谢 ......................................................................................................................................................................................... 25 2 第一章 概述 1.1 研究背景及意义 在应用程序中，如何提高程序的效率,这是很现实的问题。应用程序作为人们与计算机“ 交谈” 的工具, 其运行速度是一个十分重要的指标。人们总是希望应用程序执行速度快些, 以便达到最佳的运行效果。 随着计算机硬件的发展，微机的速度越来越快，运行软件的能力也越来越强。计算机中程序的运行速度主要受计算机硬件和软件影响，提高计算机程序的运行速度，一般可以从以下几个方面着手: 1.改进算法 要想提高程序运行效率，改进算法是最关键的。算法是影响程序运行效率的主要因素，在编写不同程序时要选择适当的算法。算法是计算机求解特定问题的方法和步骤，是指令的有限序列。通常一个问题可以有多种算法，而一个好的算法通常应该具有下列5个基本特性:正确性、健壮性(鲁棒性)、可读性、高效率、低存储空间。 2.改进程序 同一个算法，实现的程序因为书写不同，其程序的运行效率也是不一样。而提高程序效率的方法又有很多。以C/ C+ +语言为例，可以通过以下方法来提高程序的运行效率: (1)采用自加和自减运算 说到对C/ C+ +语言的优化, 人们马上会想起X+ + 和X ――( 或+ + X、―― X) , 它们的功能虽与X= X+ 1、X= X- 1 相同, 但二者的运行效率却截然不同。前者不仅运算速度快, 而且占用RAM 的时间更少。 (2)巧用寄存器变量 寄存器变量是保存在CPU 内部寄存器中的, 其访问速度要比内存变量快得多。若将寄存器变量用于关键的内层循环控制变量, 就会大大提高程序的运行速度。 (3)适当采用指针和数组下标 指针是C/ C+ + 语言的一个重要特色, 正确使用指针, 可以使程序简洁、高效、紧凑。利用指针变量比直接利用数组下标来访问数组程序运行要快得多。 (4)合理使用内联函数 在C+ + 中, 为了解决一些频繁调用的小函数大量消耗栈空间的问题, 特别地引入了inline 修饰符, 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为内联函数。内联函数和宏很类似, 其区别在于, 宏是由预处理器对宏进行替代, 而内联函数则是通过编译器控制来实现的, 而且内联函数是真正的函数, 只是在需要用到的时候, 像宏一样地展开, 所以取消了函数的参数压栈, 减少了调用的开销。你可以像调用函数一样来调用内联函数, 而不必担心会产生类似处理宏的一些问题。 (5) 采用位运算 C/ C+ + 语言可以用来开发系统软件, 因此具有汇编语言所能完成的一些功能。所谓位运算是指进行二进制位的运算, 这项功能不仅有着其他高级语言无法相比的优越性, 而且位运算速度快,在某些应用中还有着意想不到的作用。 3 3.硬件环境 除了上述方法之外，结合硬件环境也可以提高程序的运行效率。在计算机硬件对计算速度的影响上，计算机的硬件是提高应用程序计算速度和运行效率的重要途径之一。程序员在设计程序时，应当充分认识到计算机系统的重要性及实现细节，设计出高效、健壮、可移植的程序，从而能提高程序的运行速度。 众所周知，内存的存取速度极大地制约着计算机的处理能力。目前，CPU的速度越来越快，尽管内存的速度也不断提高，但远远落后于CPU的处理速度。因而，CPU 要花大量的时间等待内存访问延迟，因而内存存取速度是计算机速度的一个瓶颈。为了提高内存的存储速度，越来越多的计算机采用高速缓存Cache技术。因而，如何有效地利用Cache的特性，提高程序的运行效率，已经成为一个热点问题。 本文通过矩阵乘法运算相关代码的运行时间，讨论高速缓冲存储器对程序运行速度的影响。 1.2 研究内容 本文根据矩阵乘法运算的六种不同程序代码，构建了矩阵乘法运算时间的测试程序，得到矩阵乘法运算六种不同版本的运行时间;并通过分析六种不同矩阵乘法运算程序代码中的空间局部性与时间局部性，得出由于高速缓冲存储器和程序访问的局部性差异，同一算法的不同程序代码运行时间相差很大。为了充分利用高速缓冲存储器，提高程序运行效率，在编写程序时需要考虑程序和数据的空间局部性和时间局部性。 为了充分利用高速缓冲存储器，论文又给出了分块矩阵乘法运算程序，它可以进一步提高矩阵乘法运算效率。 本文共分为6章，其具体组织如下: 第一章是绪论。简要介绍了高速缓冲存储器对程序运行速度的影响分析研究的研究背景和意义，并且介绍了以C语言为例的提高程序运行效率的方法，在总结这些工作的基础上提出本文的研究思路与内容。 第二章基础知识。简要介绍了与本文研究相关的矩阵乘法运算和高速缓存Cache的有关知识，主要包括矩阵乘法运算的六个不同程序版本，Cache的工作原理，Cache的命中率等，并在最后对实验的开发环境Visual C++ 6.0做一个简单的介绍。 第三章测试程序。首先对构成矩阵的数组做一个说明，其次介绍4种用于测试程序运行时间的方法及函数，接着说明了程序实验结果的存放形式和方法，最后给出了完整的测试程序代码。 第四章结果及分析。以表格形式呈现实验结果，根据实验结果，绘制图表。对程序从空间局部性和时间局部性两方面进行分析，以验证实验结果。 第五章改进的矩阵乘法运算。针对程序的空间局部性和时间局部性随着数组的增大而降低的情况，提出了分块的思想，并且根据分块思想构建矩阵乘法运算的程序，相应的实验证明分块能够较好的提高程序的局部性，提高程序的运行效率。 第六章总结。总结本文所做的主要研究工作，并且对利用局部性原理和高速缓存提高程序的运行效率提出了建议。 4 第二章 基础知识 2.1 矩阵乘法运算 考虑两个矩阵的乘法问题C=。假设输入是两个规模为的矩阵A和B，输出为的矩阵C。例A，Bn，nn，n 如，n=2，那么 aaccbb，，，，，，111211121112 ,,,,,,A=， B=， C= bbaacc212221222122，，，，，， 其中 : c,ab，ab1111111221 c,ab，ab1211121222 c,ab，ab2121112221 c,ab，ab2221122222 矩阵乘法通常使用三个嵌套的循环来实现的，分别用i，j，k来标识。 for(i=0;i 声明 无利益冲突声明中华医学会杂志社职业健康检查不够规范教育部留学服务中心亲友住房声明 : BOOL QueryPerformanceCounter (LARGE INTEGER 3 lpPerformance2 Count) 4.clock()函数 C/C++中的计时函数是clock()，而与其相关的数据类型是clock_t。在MSDN中，查得对clock函数定义如下: clock_t clock( void ); 这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元(clock tick)数，在MSDN中称之为挂钟时间(wal-clock)。其中clock_t是用来保存时间的数据类型，在time.h文件中，我们可以找到对它的定义: #ifndef _CLOCK_T_DEFINED typedef long clock_t; 10 #define _CLOCK_T_DEFINED #endif 很明显，clock_t是一个长整形数。在time.h文件中，还定义了一个常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，每过千分之一秒(1毫秒)，调用clock()函数返回的值就加1。其定义如下: #define CLOCKS_PER_SEC ((clock_t)1000) 本文测试程序的运行时间使用的clock()函数，精度是毫秒级。由于测试数据受计算机操作系统等影响，每次执行程序所得的测试数据不尽相同，所以采取的方法是让每段程序运行N次，用运行N次的总时间除以运行次数N，得到平均每次的运行时间。在程序开始运行时用begin=clock()记录时间，结束时用end=clock()记录，得到运行时间time=(double) (end-begin)/CLOCKS_PER_SEC/N 。 3.3.测试程序的运行结果保存方式 测试程序的运行结果用程序写入文本文件result.txt中。代码如下: FILE *fp; if((fp=fopen("result.txt","wb+"))==NULL) { printf("Cannot open file !Print any key exit!"); getchar(); exit(0); } fprintf(fp,"数组大小:%d\",n); for (i=0;i<7;i++) fprintf(fp,"%f\n",time[i]); fclose(fp); 运行结果存放形式如图2.3所示 11 图2.3 运行结果存放图 3.4.测试程序代码 #include #include #include #define L 200 //定义数组最大为200*200 #define N 1000 void main() { double A[L][L],B[L][L]; double c[L][L]={0.0}; double time[6] = {0.0}; //数组time用于存储相应的运行时间 int i,j,k,n,choice; time_t begin,end,begin1,end1,begin2,end2,begin3,end3,begin4,end4,begin5, end5 //用于记录程序开始和结束的时间 double sum; srand(clock()); for (i=0; i