当前位置: 首页 >> 程序设计 >> cache和代码优化(1)

cache和代码优化(1)

作者：来源：xyiceberg.cublog.cn 发表时间：2007-11-19 浏览次数：字号：大 中 小

1. 使用cache的原因
    所谓Cache即高速缓冲存储器，它位于CPU与主存即DRAM之间，是通常由SRAM（Static RAM静态存储器）构成的规模较小但存取速度很快的存储器。目前计算机主要使用的内存为DRAM，它具有价格低、容量大等特点，但由于使用电容存储信息，存取速度难以提高，而CPU每执行一条指令都要访问一次或多次主存，DRAM的读写速度远低于CPU速度，因此为了实现速度上的匹配，只能在CPU指令周期中插入wait状态，高速CPU处于等待状态将大大降低系统的执行效率。SRAM由于其采用了与CPU相同的制作工艺，因此与DRAM相比，它的存取速度快，但体积大、功耗大，价格很高，不可能所有的内存都采用SRAM。因此为了解决速度与成本的矛盾就产生了一种分级处理的方法，即在主存和CPU之间加装一个容量相对较小的SRAM作为高速缓冲存储器；当采用Cache后，在Cache中保存着主存中部分内容的副本（称为存储器映象），CPU在读写数据时，首先访问Cache（由于Cache的速度与CPU相当，所以CPU可以在零等待状态下完成指令的执行），只有当Cache中无CPU所需的数据时（这称之"未命中"，否则称为"命中"），CPU才去访问主存。而目前大容量Cache能使CPU访问Cache命中率高达90％－98％，从而大大提高了CPU访问数据的速度，提高了系统的性能。
    对大量的典型程序的运行情况分析结果表明，在一个较短的时间内，由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内。在多数情况下，指令是顺序执行的，因此指令地址的分布就是连续的，再加上循环程序段和子程序段要重复执行多次，因此对这些地址的访问就自然具有时间上集中分布的趋向。数据的这种集中倾向不如指令明显，但对数组的访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址的频繁访问，而对此范围以外的地址则访问甚少的现象称为程序访问的局部性。根据程序的局部性原理，在主存和CPU之间设置Cache，把正在执行的指令地址附近的一部分指令或数据从主存装入Cache中，供CPU在一段时间内使用，是完全可行的。

2. cache结构
    一般来说，Cache的内容以块为单位组织，每块的大小是32字节。这是CPU所能操作Cache的最小单元，也是存储器跟Cache之间进行数据传输的最小单元。存储器的数据调入Cache时以突发的方式，突发的次数视数据总线的宽度而定。Cache块的内容包括标签(TAG)、状态位(V,D,L)、数据等。
    假设一个256K Bytes的Cache，8K块，每块32字节，512M Bytes的内存分成16M块，每块32字节，设m=8K,n=16M。
    CACHE为每一行设置一个标签，这个标签记录着该缓存行对应哪个存储行的(部分)信息。上面的图示中内存大小512MB，用以表示存储行的地址为A28~A5。标签的内容就与这24位相关，标签的具体位数取决于如下的三种映射关系：
    直接映射：根据CACHE的行数把内存分为n/m个区，每个区有m行。每个区中的0～m－1行都对应到CACHE中的0～m－1行，这样标签只要包含区号信息就能唯一确定CACHE与内存的映射关系。采用这种方式比较简单和固定，标签所需的位数较少。按照上面的约定，CACHE是8K行，需13位地址寻址；内存是16M行需24位地址寻址，标签所需的地址位是24－13＝11位。采用这种映射方式，标签与存储地址只比较一次，搜索快且搜索电路简单。当CPU发出内存访问时，以A17~A5作为行索引，寻址到一缓存行，检测该行的标签，若标签与剩下的地址A28~A15匹配则CACHE命中，否则未命中。但是这种方式的冲突概率较高，当程序往返访问两个相互冲突的块中的数据时，Cache的命中率将急剧下降，因为这时即使Cache中有其他空闲块，也因为固定的地址映像关系而无法应用。如果一个信息项正在被访问，那么近期内它很可能还会被访问。但是通常不会被立即访问，所以，再次访问该信息项时，仍然可能失效。
    全相联映射：由于在直接映射里对内存进行分区，这样做固然有它的优点，但是CACHE行的利用率不高，往往导致仍有空闲CACHE行的情况下还要频频从内存读数据。全相联映射方式就克服了这个缺点：它不对内存分区，所以内存里的任一行可以缓存在任一CACHE块里。这样做的缺点是所需标签过多，且搜索电路复杂。因为没有了CACHE的Index，所以标签里要包含所有的高位地址信息，即A28~A5；当访问一个块中的数据时，块地址要与Cache块表中的所有地址标记进行比较以确定是否命中。这种方式只有当Cache中的块全部装满后才会出现冲突，所以冲突的概率低，可达到很高的Cache命中率，但实现很复杂。在数据块调入时存在着一个比较复杂的替换问题。为了达到较高的速度，全部比较和替换都要用硬件实现。
    N路相连映射：组相联映射方式吸取了直接映射和全相联映射各自的优点。只付出多搜索几个标签的代价换来更高的命中率和CACHE的使用效率，所以大多数CACHE都采用方式。把CACHE行分成若干组，每个组里的各行之间的关系是并列的。跟直接映射方式一样，它们是用一个行地址来寻址；不同的是，直接映射方式里一个行地址(A17~A5)只能寻址到一行数据，而组相联映射方式里寻址到的却是多行数据。在这多个缓存标签里只要有一个(而且只会有一个)标签与高位地址(A28~A18)匹配就算命中。组相联映象方式是直接映象和全相联映象的一种折衷方案。这种方法将存储空间分为若干组，各组之间是直接映像，而组内各块之间则是全相联映像。它是上述两种映像方式的一般形式，如果组的大小为1，即Cache空间分为2N组，就变为直接映像；如果组的大小为Cache整个的尺寸，就变为了全相联映像。组相联方式在判断块命中及替换算法上都要比全相联方式简单，冲突的概率比直接映像的低，其命中率也介于直接映像和全相联映像方式之间。N路相连Cache相比直接映射Cache缺点：需要多个比较器，输出数据增加了额外的多路选择延迟。在判断失效/命中时，才可以得到数据；直接映射Cache可以在命中/失效前就可以得到，可以假设命中并继续执行，如果以后发现失效再恢复。