高速缓冲存储器

本节导读

大纲对 Cache 列了四项：基本原理、Cache 和主存之间的映射方式、替换算法、写策略。这一部分的题目计算量大：地址怎样划分成标记、组号（行号）、块内地址，Cache 一共要多少位，某个地址映射到哪一行，一段访问序列命中几次，一段程序的命中率是多少。

学完你应该能按固定步骤完成地址划分和容量计算，能逐步模拟直接映射和组相联下的命中情况，并能从 C 程序的数组访问方式判断命中率高低。

Cache 的基本原理

Cache 位于 CPU 和主存之间，用 SRAM 做成，存放主存中最近用到的部分内容，依靠程序访问的局部性提高速度。Cache 和主存都划分成大小相同的块（Cache 的块也叫行），两者之间以块为单位交换数据。CPU 要访问的数据在 Cache 中叫命中，否则叫缺失，缺失时要把主存中对应的整块调入 Cache。

命中率 $H = \dfrac{N_c}{N_c + N_m}$H=Nc​+Nm​Nc​​（$N_c$Nc​、$N_m$Nm​ 分别是命中和缺失的次数）。设 Cache 访问时间为 $t_c$tc​、主存访问时间为 $t_m$tm​，平均访问时间有两种算法，做题前看清题目的约定：

约定	平均访问时间
先访问 Cache，缺失后再访问主存	$T = t_c + (1-H)t_m$T=tc​+(1−H)tm​
同时启动 Cache 和主存，命中就停止主存访问	$T = Ht_c + (1-H)t_m$T=Htc​+(1−H)tm​

例如 $t_c = 4$tc​=4 ns、$t_m = 100$tm​=100 ns、H = 0.95 时，第一种为 4 + 0.05 × 100 = 9 ns，第二种为 3.8 + 5 = 8.8 ns。Cache—主存系统的效率 $e = \dfrac{t_c}{T}$e=Ttc​​。

映射方式与地址划分

映射方式	主存块放在哪里	地址划分	特点
直接映射	只能放在第（块号 mod 行数）行	标记、行号、块内地址	比较一次，简单；冲突缺失多
全相联	可以放在任意一行	标记、块内地址	冲突最少；要同时比较所有行的标记，硬件贵
组相联（k 路）	放在第（块号 mod 组数）组的任意一行	标记、组号、块内地址	折中，组数 = 行数 ÷ k

划分的步骤：块内地址位数 = $\log_2$log2​（块大小）；行号（组号）位数 = $\log_2$log2​（行数或组数）；其余高位都是标记。每个 Cache 行除了数据，还要存：有效位 1 位；标记；采用回写法时的脏位（修改位）1 位；组相联或全相联采用 LRU 时的替换控制位（k 路组相联用计数器实现 LRU 时每行 $\log_2 k$log2​k 位）。Cache 的总容量 = 行数 ×（数据位 + 标记 + 各控制位）。

替换算法

Cache 满了（或组满了）又要调入新块时，选一行换出。直接映射每块只有一个位置，不需要选择；全相联和组相联才用替换算法：

算法	换出哪一行	说明
随机（RAND）	随机选一行	实现简单，没有利用局部性
先进先出（FIFO）	最早调入的行	不一定是最久没用的；行数增加时命中率可能反而下降
近期最少使用（LRU）	最久没有被访问的行	利用了时间局部性，命中率较高，要记录访问的先后
最不经常使用（LFU）	一段时间内访问次数最少的行	要为每行设计数器