高速缓冲存储器（Cathe）简述

一、Cache 的基本工作原理

Cace位于存储器层次结构的顶层，通常由SRAM构成。
Cache和主存都被分成若干大小相等的块(Cache块又称为Cache行)，每块由若干字节组成，块的长度称为块长(Cache行长)。由于Cache的容量远小于主存的容量，所以Cache中的块数要远少于主存中的块数，它仅保存主存中最活跃的若干块的副本。故而Cache按照某种策略，预测CPU在未来一段时间内欲访存的数据，将其装入Cache。

当CPU发出读请求时，如果访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cache进行读操作，与主存无关；如果Cache不命中，则仍需访问主存，并把此字所在的块一次从主存调入Cache内。若此时Cache已满，则需根据某种替换算法，用这个块替换掉Cache中原来的某块信息。值得注意的是，CPU与Cache之间的数据交换以字为单位，而Cache与主存之间的数据交换则是以Cache块为单位。

二、Cathe的实现依据

高速缓冲技术就是利用程序访问的局部性原理，把程序中正在使用的部分存放在一个高速的、容量较小的 Cache 中，使 CPU 的访存操作大多数针对 Cache 进行，从而使程序的执行速度大大提高。

程序访问的局部性原理包括时间局部性和空间局部性。前者是指在最近的未来要用到的信息，很可能是现在正在使用的信息，这是因为程序存在循环。后者是指在最近的未来要用到的信息，很可能与现在正在使用的信息在存储空间上是邻近的，这是因为指令通常是顺序存放、顺序执行的，数据一般也是以向量、数组、表等形式簇聚地存储在一起的。

三、Cache 和主存的映射方式

1.直接映射

主存数据块只能装入Cache中的唯一位置。若这个位置已有内容，则产生块冲突，原来的块将无条件地被替换出去（无需使用替换算法）。直接映射实现简单，但不够灵活，即使Cache存储器的其他许多地址空着也不能占用，这使得直接映射的块冲突概率最高，空间利用率最低。

2.全相联映射

可以把主存数据块装入Cache中的任何位置。全相联映射方式的优点是比较灵活，Cache块的冲突概率低，空间利用率高，命中率也高；缺点是地址变换速度慢，实现成本高，通常需采用昂贵的按内容寻址的相联存储器进行地址映射。

3.组相连映射

将Cache 空间分成大小相同的组，主存的每个数据块可以装入到一组内的任何个位置，即组间采取直接映射，而组内采取全相联映射，它是对直接映射和全相联映射的一种折中。

四、Cathe中主存块的替换算法

在采用全相联映射和组相联映射方式时，从主存向Cache传送一个新块，当Cache中的空间已被占满时，就需要使用替换算法置换Cache行。而采用直接映射时，一个给定的主存块只能放到一个唯一的固定Cache行中，所以，在对应Cache行已有一个主存块的情况下，新的主存块毫无选择地把原先已有的那个主存块替换掉，因而无需考虑替换算法。

常用的替换算法有随机算法、先进先出(FIFO)算法、近期最少使用(LRU)算法和最不经常使用(LFU)算法。

1)随机算法：随机地确定替换的Cche块。它的实现比较简单，但没有依据程序访问的局部性原理，故可能命中率较低。

2)先进先出算法：选择最早调入的行进行替换。它比较容易实现，但也没有依据程序访问的局部性原理，可能会把一些需要经常使用的程序块（如循环程序）也作为最早进入Cache的块替换掉。

3)近期最少使用算法：依据程序访问的局部性原理选择近期内长久未访问过的存储行作为替换的行，平均命中率要比FIFO要高，是堆栈类算法。

4)最不经常使用算法：将一段时间内被访问次数最少的存储行换出。