第二章 基础知识
2.1 矩阵乘法运算
考虑两个矩阵的乘法问题C=A?B。假设输入是两个规模为n?n的矩阵A和B，输出为n?n的矩阵C。例如，n=2，那么
?a11A=??a21a12??b11， B=?a22???b21b12??c11c12?? ， C=?ccb22??2122??其中 ： c11?a11b11?a12b21
c12?a11b12?a12b22
c21?a21b11?a22b21 c22?a21b12?a22b22
矩阵乘法通常使用三个嵌套的循环来实现的，分别用i，j，k来标识。 for(i=0;i for(j=0;j sum+=A[i][k]*B[k][j]; c[i][j]+=sum; } 如果改变循环的次序，对代码进行一些其他的小改动，就能得到矩阵乘法的六个在功能上等价的版本,每个版本以循环的顺序唯一标识。其他五个版本的算法描述分别如下： for(j=0;j for(i=0;i sum+=A[i][k]*B[k][j]; c[i][j]+=sum; } for(j=0;j for(k=0;k word文档 可自由复制编辑 { r=B[k][j]; for(i=0;i for(k=0;k for(j=0;j for(k=0;k for(i=0;i for(i=0;i for(k=0;k 以上六个版本非常相似，因为加法具有结合律，从矩阵运算的角度，每个版本的计算结果完全一样。A和B中的n?n个元素每一个都要读n次，C中的每一个元素都对n个值求和。以ijk版本为例，该矩阵乘法版本是逐项计算Cij ，计算一个Cij需要( n - 1) 次加法和n 次乘法，因而逐项计算n个Cij共需执行n( n - 1) 次加法和n 次乘法，所以算法的时间复杂度是O(n) 。我们可以很容易的分析出，矩阵乘法运算六个版本的工作复杂度都为O(n) 。 332232.2 高速缓冲存储器 2.2.1 设置Cache的理论依据 在计算机技术发展过程中，主存储器存取速度一直比中央处理器操作速度慢，尤其近年来，CPU的运行速度 word文档 可自由复制编辑 每年以40%的速度上升，而主存储器的存取速度每年仅上升10%左右，不能充分发挥中央处理器的高速处理能力，使得整个计算机系统的工作效率受到影响。有很多方法可以用来缓和中央处理器和主存储器之间速度不匹配的问题，常用的方法之一是在存储层次上采用高速缓冲存储器，如图2.1所示，利用高速缓存Cache来缩小处理器和存储器之间的速度差距。 图2.1 存储系统的多级层次结构 高速缓冲存储器能缓和中央处理器和主存储器之间速度不匹配的问题的原因是程序的局部性原理。程序的局部性原理是指在一段时间内，程序的执行仅限于访问存储器的某一区域。Hennessy和Patterson提出了90—10规则，典型程序在其10%的代码上可能要消耗其执行时间的90%，其90％的访存集中在10％的区域，这就是程序的局部性。 产生局部性原理的原因是: （1）除了调用和转移指令(它们在整个程序中只占很小的一部分)以外，程序的执行是顺序的，从而，在大多数情况下，下一条指令可以在当前指令之后立即读入处理器。 （2）大多数情况下，程序中的连续过程调用深度较小，程序中出现一连串不间断的过程调用后跟着相应的一连串过程返回的操作是十分罕见的。这样，在较短时间内，访问的指令将集中在少数几个过程中。 （3）大部分迭代过程由相对很少的几条指令重复执行来实现。在迭代期间，计算集中在一段很短的连续程序内。 （4）在许多程序内，很多计算涉及到处理数据结构，例如数组和记录，连续的访问这些数据结构也能体现出访存的局部性。 程序的局部性原理又分为时间局部性和空间局部性。时间局部性是指如果程序中的某条指令被执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。空间局部性是指如果程序访问了某个存储单元，则不久之后其附近的存储单元也将可能被访问。 word文档 可自由复制编辑 2.2.2 Cache的体系结构 根据局部性原理，上世纪五十年代就引入了存储层次的概念，在一些计算机中采用容量较小但是访问较快的存储器来缓存部分经常使用的指令或数据，与主存储器构成一个有机的整体，从而弥补主存储器速度上的不足，提高整个系统性能。 自从第一次在IBM／360商用计算机中采用高速缓冲存储器，并且提出Cache这个名词之后，Cache由于其管理能够自动由硬件实现，逐渐发展并成为降低处理器和存储器之间速度差距的一种重要方法。随着Cache的发展，其层次变锝越来越复杂，多级Cache逐渐成Cache层次的主流。图2.2给出来目前体系结构中一种典型的Cache层次结构图，整个Cache层次分为两级：一级Cache一般速度较快，但容量较小，用于存储指令的Cache和用于存储数据的Cache各自分开；二级Cache一般容量较大，但速度较慢，在这一级Cache指令和数据通常混合存储。 图2.2 一种典型的Cache层次结构图 2.2.3 Cache的相关知识 Cache在计算机系统中是按块管理的，Cache和主存被分割成大小相同的块，指令或者数据以块为单位调入Cache。Cache能容纳多个信息块，若CPU发出读请求，则将含有指定单元的一个信息块从主存送入Cache中。当CPU读取该信息块中的任何单元时，就可以直接从中取出，这称为命中。当访问的单元不在Cache中，这称为不命中或失效。在程序执行期间，设Nc表示读写Cache的次数，Nm表示读写主存的次数，则Cache的命中率H的计算如下： H=Nc/(Nc+Nm) 若t1表示命中时的Cache访问时间，t2表示未命中时的主存访问时间，1-H表示未命中率，则平均访问时间T为： T=H×t1+（1-H）×t2 word文档 可自由复制编辑 理解Cache的工作原理需要明白Cache的关联规则、查找方法、替换算法和写策略。 1. 关联规则 在一般的系统中，主存容量远远大于Cache的容量，当将主存中一个块的内容调入Cache的时候，如何选择相应的Cache块是首先需要决定的问题，关联规则就是用来解决这个问题的。 2. 查找方法 在访问Cache时如何确定Cache中是否存在相应的块，并且如果存在时怎样找到该块的位置，这都需要查找方法来解决。实际中一般通过查找目录表来实现，在Cache中留出一部分空间，设置一个目录表，记录每一个Cache块的信息，包含该Cache块是否放置有效信息和放置的块在主存中的地址(当该块放置了有效信息时)。 3. 替换算法 一般主存中块的数目远远大于Cache中块的数目，当Cache不命中需要将主存中的块调入Cache时，就会出现该块可能的位置都已经被别的块占用，这时候就需要将这些块中的某一块调出，以便新的块调入。替换算法就是用来如何选择被调出的块，常用的替换算法有下面三种： (1)随机法：选择被调出的块时，随机地从可选择的块中选择出一块。这种方法的优点是简单，便于硬件实现，但是不考虑过去的使用情况，反应不了程序的局部性。 (2)先进先出法(FIFO，First In First Out)：选择被调出的块时，从可选择的块中选择最早调入的块。这种方法利用各块调入的“历史”信息，较容易实现，但是也不能反应程序的局部性。 (3)最近最少使用法(LRU，Least Recently Used)：选择被调出的块时，从可选择的块中选择最近最少使用的那一块。由于实现困难，通常都是选择最久没有被访问过的块，这种方法能够较好的反应程序的局部性。 4. 写策略 由于Cache块中的内容是主存中块的内容的一个副本，处理器执行写指令时，需要更新Cache块中的内容和主存块中的内容，怎么样执行这个两个更新则是Cache写策略需要解决的问题。 根据局部性原理知道，局部性比较好的程序更容易有较高的命中率，而命中率较高的程序倾向于比命中率低的程序运行的更快。Cache的存在，使得程序员面对一个既有Cache速度又有主存容量的存储系统，在编程中应该充分利用程序访问局部性原理，提高cache的命中率，从而提高程序的执行效率。 2.3 开发平台 Visual C++ 6.0 是Microsoft公司提供的在Windows环境下进行程序开发的C/C++编译器，是Microsoft Visual Stutio套装软件的一个有机组成部分。Visual Stutio把所有的Visual C++工具结合在一起，集成为一个整体，通过一个由窗口、对话框、菜单、工具栏、快捷键及宏组成的和谐系统，可以观察和控制整个开发过程。 本文进行实验的测试环境采用Visual C++ 6.0平台，运用C语言构建测试程序。 word文档 可自由复制编辑