Cache原理解析-章节详解

高速缓存技术的基础是程序的访问局部性原理。对存储器的访问是由处理机对指令和数据的存取而引起的，这些存取在时间、空间和顺序上往往集中在一定范围内进行。程序的访问局部性表现在三个方面。

1）时间局部性：最近的访问项很有可能在不久的将来被再次访问。这通常由特殊的程序结构所引起，如迭代循环、进程堆栈、临时变量或子程序调用。一旦进入某个循环或调用某个子程序，一小段代码会被重复多次。所以时间局部性往往集中在最近访问的代码和数据段。

2）空间局部性：指进程趋向于访问地址接近的信息项。例如：对表和数据的操作就会引起对某一地址空间的集中访问，而子程序和宏等程序段也往往会存储在临近的存储器空间内。

3）顺序局部性：对一般的程序而言，除了跳转指令会导致执行顺序的打乱之外，指令的执行总是按照一定的串行次序进行的，称为程序顺序（Program Order）。一般按序执行和乱序执行的比例大致是5：1。此外，对大型数据输入的存取也经常按序进行，如对矩阵元素进行按行访问等。

程序的访问局部性为高速、小容量的高速缓存技术提供了理论基础。根据程序的局部性原理，可以在主存储器和处理器的通用寄存器之间设置一个高速的容量相对较小的存储器，把正在执行的指令地址附近的一部分指令或数据从主存调入这个存储器，供CPU在一段时间内使用。这种用于高速缓冲的小容量高速存储器就被称作高速缓存，或者Cache。

当CPU对存储器进行数据请求时，通常先访问Cache。局部性原理不能保证所请求的数据百分之百地在Cache中，被访问数据在Cache中的时候，数据就可以以比较快的速度传送到处理器中。否则处理器就必须对访问速度相对较低的主存储器进行访问以获得数据，数据的访问时间也就比较长了。被访问数据在Cache中的概率被称为Cache的命中率，命中率越高，在Cache中直接获取数据的可能性就越大，相应的存储系统平均访问时间也越小，存储系统的访问速度越快。在局部性原理的保护下，Cache的存储容量可以比主存的容量小得多。

Cache容量的大小直接关系着Cache的命中率和Cache的成本。Cache的容量不能太小，太小会使命中率下降。也没有必要过大，过大不仅会增加成本，而且当Cache容量超过一定值后，命中率随容量的增加将不会再有明显的增长。只要Cache的空间与主存空间在一定范围内保持适当比例的映射关系，Cache的命中率还是相当高的。一般情况下可以选择Cache与内存的空间比为4：1000，即128 KB Cache可映射32 MB内存，256 KB Cache可映射64 MB内存。在这种情况下，命中率都在90%以上。至于没有命中的数据，CPU只好直接从内存获取。获取的同时，也把它复制到Cache，以备下次访问。

Cache通常由相联存储器实现。Cache与主存都分成块（常常将Cache块说成Cache行），每块由多个字节组成，大小相等，由于Cache数据块和主存块大小相同，因此主存地址的低地址部分（块内地址）可作为Cache数据块的块内地址。在Cache和主存储器之间的数据交换都是以存储块为单位进行的。在一个时间段内，Cache的某块中放着主存某块的全部信息，即Cache的某一块是主存某块的副本（或叫映像）。Cache中的每一个存储块都具有额外的存储信息，称为标签（Tag），用来表示该存储块是主存中哪个存储块的映像。当访问相联存储器时，将地址和每一个标签同时进行比较，从而对标签相同的存储块进行访问。根据Cache和主存储器之间存储块映射关系的不同，Cache可分为三种不同的基本结构。

●全相联

在全相联Cache中，对主存储器中的存储块和Cache中的存储块之间的映射没有任何限制，也就是说主存储器中的一个存储块可以被保存在Cache中的任何存储块之中。Cache保存着很多互不相关的数据块，Cache必须对每个块和块自身的地址加以存储。当请求数据时，Cache控制器要把请求地址同Cache中所有数据块的地址加以比较，进行确认。全相联Cache结构的主要优点是，Cache中的存储块和主存储器之间的存储块没有限定的映射关系，Cache的利用率比较高，命中率高。缺点是在每一次请求数据时Cache控制器必须将目的地址同Cache中所有存储块的地址进行比较，比较工作量大，需要较长时间，速度较慢。(www.xing528.com)

●直接映射

在直接映射Cache中，每个主存储器的块在Cache中仅存在一个可能的位置，两者之间通过块号的低位相关联。由于每个主存储器的块在Cache中的位置是确定的，每次访问存储器时只需要对相关联的Cache块的地址进行比较，地址的比较次数被减少为一次。其做法是，为Cache中的每个块位置分配一个索引字段，用Tag字段区分存放在该Cache位置上的不同的块。由于直接映射Cache每次访问存储器只需要进行一次地址比较，其比较工作量小，速度比较快。但是，由于存储器中每个存储块在Cache中只有唯一可能的位置，多个存储块之间可能会因为在Cache中映射的块位置相同而发生冲突。而且，主存储器中的存储块和Cache中的存储块之间的直接映射关系经常造成Cache中存在很多空行，但需要的存储块对应位置却被占用的情况，从而造成Cache空间上的浪费和Cache命中率的降低。

●组相联

组相联Cache是介于全相联Cache和直接映像Cache之间的一种结构。这种类型的Cache使用了几组直接映像的块，每组块内部采用全相联的映射策略。对于某一个给定的索引号，可以允许有几个块位置，因而可以增加命中率和系统效率。

在程序的局部性原理的支持下，小规模、高速度的Cache极大地提升了存储系统的访问速度。假设Cache的命中率为p，Cache的访问时间为t₁，主存的访问时间为t₂，则相应的存储系统的平均访问时间：

t=p×t₁+（1-p）×t₂。

一般情况下Cache的命中率都在90%以上，即p≥0.9。而一般情况下t₁和t₂之间的差别都在10倍左右甚至更大，也就是说，一般情况下t₂≥10×t₁。假设p=0.9，t₂=10×t₁，则t=1.9×t₁，这就意味着整个存储系统的平均访问时间只是Cache访问时间的二倍，是主存储器访问时间的五分之一。当Cache的命中率更高、Cache访问速度和主存储器访问速度的差距更大的时候，Cache对整个存储系统性能的提升作用会更加明显。

随着半导体技术的不断发展，处理器的速度和主存储器的速度之间的差距也越来越大，单一的Cache逐渐无法满足提高存储系统性能的需求，多级Cache开始得到广泛的使用。多级Cache的核心思想就是在处理器的通用寄存器和主存储器之间加入多级不同访问速度和不同规模的高速缓存，距离处理器越近，Cache的规模越小而速度越快，借此达到以比较低的成本提高存储系统整体性能的目标。当前的处理器通常将一级和二级Cache集成到处理器芯片之中，以获得更高的访问带宽和更低的访问时延。

在传统的Cache技术中，指令和数据是被相同对待的，这在一定程度上导致了指令和数据两种不同性质的缓存互相干扰，降低了Cache的性能。为此，在绝大多数的现代微处理器中，一级Cache被分成指令Cache（I-Cache）和数据Cache（D-Cache）两部分。为了适合指令和数据两者不同的访问特性，I-Cache和D-Cache可以采用不同的映射方式和替换算法，从而提高其命中率。除此之外，Trace Cache等技术也被广泛用于现代微处理器中，进一步提高存储系统的整体性能。