Cache

局部性原理

程序的局部性原理分为时间局部性与空间局部性。

• 时间局部性 -- 对于某个对象，当前时刻与接下来若干时刻可能都会发生，即在相邻时间访问概率高，则称这个对象的时间局部性好
• 空间局部性 -- 对于连续内存对象，访问当前的地址后相邻的地址在相邻访问中被访问的概率大，则称这个对象的空间局部性好

Cache的基本工作原理

Cache由若干个数据块和数据块地址构成，每一行都只有一段数据块地址与数据块。

Cache的数据块和主存的某一个数据块一一匹配，但是Cache的数据块数目远小于主存的数据块数量。Cache 的数据块地址的第一段标记地址指向主存内匹配数据块的地址。

Cache的数据块地址内的后段为块内地址。数据块通常为长数据，块内地址指向这个数据块。块内地址的长度取决于数据块的编码方式，当数据块编码方式为字节编码且数据块大小为 $2^n \,\text{B}$, 则块内地址的长度为 $n$

Cache 的命中率

CPU访问Cache的时候，如果目标内容在Cache中找到吗，则称为Cache 命中，否则称为Cache 未命中。相对应的命中概率称为命中率

设Cache 命中次数为$N_c$, 访问主存次数为$N_m$ , 则命中率定义为

$$H = \frac{N_c}{N_c+N_m}$$

Cache命中时，CPU读取数据的时间称为命中时间$T_c$ ; Cache未命中时，从CPU读取Cache数据到再次访问主存找到数据的整个时间为$T_m+T_c$, 其中$T_m$ 为缺失损失，表示访问主存的时间

访存时间期望为

$$T = HT_c+(1-H)(T_c+T_m)$$

Cache 和 主存之间的映射方式

Cache的行数据块与主存数据块之间以以某种方式建立一个映射，核心的选择算法有模运算与随机存入，这两种方法引申出三种映射方式。

全相联映射

每一个Cache都能存入主存的任意块，通过标记地址进行块地址的标记。当主存的数据块数为$2^m$, Cache地址中的标记的地址位数为 $m$

每一个Cache行都设置一个比较器进行地址匹配，基于标记的字段匹配进行访存。全相联映射的时间与硬件开销都比较大，不适合制作大容量Cache

Cache地址结构与数据块的最小结构为

|有效位|(脏位)|标记地址|块内地址|数据块|

直接映射

直接映射的每一行都视为规则存入的独立单位进行地址编码，当Cache数据块有$2^c$行时， Cache行有$c$位。每一个Cache行根据模运算与主存数据块进行匹配,对应主存块$a_0$, 对应的Cache行号$b_0$满足

$$b_0 \equiv a_0 \pmod{2^c}$$

Cache数据块相对主存数据块的编码量为$\frac{2^m}{2^c} = 2^{m-c}$, 对应标记位的位数为 $m-c$

Cache地址结构与数据块的最小结构为

|有效位|(脏位)|标记地址|Cache行地址|块内地址|数据块|

r路组相联映射

将Cache分为$Q$个大小相同的组,每一组有$r$个地位等价的行，遵循 组内随机，组间取模 的访问方式，组内对主存数据块的映射方式为全相联映射，组间通过模运算匹配

对于cache组号$g$, 主存块号$a$, 满足

$$g\equiv a \pmod{Q}$$

标记地址的位数为 $\lceil\log_2 \frac{2^m}{Q}\rceil$, 组号为组数的编码 $\lceil \log_2Q\rceil$。

Cache地址结构与数据块的最小结构为

|有效位|(脏位)|标记地址|组号地址|块内地址|数据块|

主存块替换算法

Cache内的数据根据访存的频率和时间需要高频更新以保证效率。Cache存储块和主存存储块之间的替换有四种常见算法

• 随机(RAND)算法
• 先进先出(FIFO)算法
• 最近最早使用(LRU)算法
• 最不经常使用(LFU)算法

LRU算法基于局部性原理，更新最近最久未访问的Cache行，通过计数器统计LRU值，每一轮访存后，计数器$+1$, 命中元素计数器归零。

LFU算法在每一次访存的时候都将计数器$+1$, 将计数器最小的数据块更新

Cache一致性问题

Cache写命中

• 全写法
  全写法在每一次CPU写命中时都同步更新Cache和主存的数据块，始终维持同步。同时增设一个写缓冲平衡Cache与主存的写入速度导致的时间差。高频操作时，过多主存写入同步也可能导致写缓存溢出。

• 回写法
  回写法中，CPU在写入Cache时不同步写入主存，而是维护一个脏位以表示这个Cache行被写入过。因此回写法的Cache行地址相比全写法多一个脏位，在Cache容量计算中需要考虑。

Cache写未命中

• 写分配法
  先写入主存再写入Cache的空闲行

• 非写分配法
  只写入主存，不进行Cache同步，只根据替换算法维护Cache存储块