存储系统（4）Cache缓存

课程来源：华中科技大学 计算机组成原理公开课

计算机各个部件的速度存在差异，慢速的内存会让快速的CPU性能严重下降。缓存就是用来解决这种类型的问题。根据局部性原理，程序下一次访问的地址在上一次访问地址的旁边。把访问地址附近的数据装入缓存，下一次访问时，CPU大概率能从缓存中找到数据，速度大大提升。

Cache的工作过程：如果CPU访问的数据在Cache中，则从Cache中读取数据。如果CPU访问的数据不在Cache中；如果CPU访问的数据不在Cache中，则从内存中读取数据，然后在把内存相关块区域复制到缓存中。

这里有一些问题：如何判断数据是否在Cache中？ 如何判断数据是否有效？这就和Cache地址映射机制有关。

首先要把Cache分行，内存分块；一行的容量等于一块的容量，这样就可以把内存中的某一块调入Cache的某一行。再把内存地址分为两个部分：块地址+块内偏移，或者进一步划分为：tag+index+offset。tag判断数据是否在Cache中，index表示在Cache中哪一行读写数据。Offset是一行或一块内的地址。

Cache的结构：CPU地址总线一部分连接到相联存储器，用来判断地址是否在Cache中。相联存储器剥离地址作为key，以key为关键字全局硬件并发比较。

Cache 地址映射与变换方法

内存数据如何迁至Cache才能实现快速查找？有常见的三种映射方式：全相连、直接相连、组相连。这三种方式都要把内存分块、Cache分行。

全相连映射：内存地址表示为块号+块内地址，映射算法是内存的数据块可映射到Cache任意行，同时将该数据块地址对应行的标记存储体中保存。特点：Cache利用率高、块冲突率低、淘汰算法复杂。应用场合：小容量Cache。

直接映射：内存分块后再按照Cache行数分区，内存地址表示为：区号+区内块号+块内地址，内存的数据映射到Cache的特定行。特点：Cache利用率低、块冲突率高、淘汰算法简单，应用场合：大容量Cache。

组相连映射：Cache分成k组，内存每k块分成一组。内存地址：内存组号+Cache组号+块内地址。它既有直接映射的特点也有全相连的特点。

程序运行一段时间后，Cache存储控件被占满，当再有新数据要调入时，就需要通过某种机制决定替换的对象。有几种常见的替换算法：先进先出法、最不经常使用法、近期最少使用法、随机替换法。

先进先出算法：每行Cache有一个计数器，调入时置0，每次加1。Cache装满后计数器最大的行被替换。

最不经常使用：每行Cache有一个计数器，调入时置0，命中此行计数器加1。Cache装满后计数器最小的行被替换。

近期最少使用法：每行Cache有一个计数器，调入时置0，每次加1，命中此行计数器置0。Cache装满后计数器最大的行被替换。