Cache 高速缓冲存储器，是
解决 CPU 和主存之间
速度不匹配而采用的一项重要技术。
Cache 由高速的 SRAM 组成，其全部功能都由硬件实现。
Cache 除了 SRAM 外还需要逻辑控制。
- 若 Cache 在 cpu 外，则其逻辑控制一般与内存的逻辑控制合成， 成为主存/cache控制器。
- 若cache在CPU内，则由CPU提供它的控制逻辑。
Cache 的几个基本概念
- 以字为单位与CPU进行数据交换。
- 以块为单位与主存进行数据交换。
- cache 中的数据以行为单位存储
一个字包含一个或若干个字节。
一个块有多个字组成，定长。
一个行的大小等于块的大小。
需要注意，cache 的行的大小通常是指 cache 中的数据部分。而地址存储在标记部分中。
当cpu读取一个字时，首先通过cache判断是否在cache中，如果是则cache命中，否则为cache缺失
由此引出 Cache 的性能指标：
命中率
cache的命中率
$$ h = \frac{N_{c}}{N_{c} + N_{m}} $$- $N_{c}$ cache完成的存取次数
- $N_{m}$ 内存完成的存取次数
平均访问时间
$$ t_{a} = ht_{c} + (1-h)t_{m} $$其中：
- $t_{c}$ 为命中时 cache 的访问时间
- $t_{m}$为未命中时主存的访问时间
访问效率:
$$ e = \frac{t_{c}}{t_{a}} = \frac{1}{r+(1-r)h} $$地址变换
为了做到对CPU而言，cache的透明性。需要特定的地址变换方式。
cache 的地址变换方式存在三种方式：
- 全相连方式
- 直接方式
- 组相连方式
cache 数据块大小称为行，主存的数据块大小称为块。
行与块等长，每个块都若干个连续的字组成。
全相连映射方式
全相连方式中，主存一个块的地址与块的内容一起存在cache中，
块地址存于 cache 行的 tag 部分中。
可以将主存的一个块直接复制在cache的一行上，非常灵活。
直接映射方式
多对一的映射关系，cache的行号 $l$ 和块号$b$ 函数关系
$$ l = b~mod~m $$其中$m$为cache的总行数。
组相连映射关系
把cache的行分为若干个组，块到组的映射是确定的，但是在某一行上是灵活的。
例子
某主存包含 4k 个块，每块 128 字，cache 由 64 行组成。
要求分别写出全相连、直接映射、2路、4路组相连中，cache 的行内地址格式。
$4k$个块，即为$2^{12}$个块，每块$2^7$字。cache 有 $2^6$行。
全相连：
| 标记 | 字地址 |
|---|---|
| 12 | 7 |
直接映射：
| 标记 | 行 | 字地址 |
|---|---|---|
| 6 | 6 | 7 |
2路组相连映射
| 标记 | 组号 | 字地址 |
|---|---|---|
| 7 | 5 | 7 |
4路组相连映射
| 标记 | 组号 | 字地址 |
|---|---|---|
| 8 | 4 | 7 |
替换策略
对于组相连和全相连映射，需要有替换算法。
- LFU 最不常用算法
- LRU 近期最少使用算法
- 随机替换
- FIFO 先进先出
LFU 和 LRU
- LFU 每行设置计数器，新行调入后以0开始计数，每访问一次，被访问行 + 1
- LRU 每命中一次，该行计数器清零，其他 + 1
写策略
cache只是主存的副本，需要保持一致性。
1. 写回法
只修改cache内容，而不直接写入内存。只有当该行被换出的时候才需要写入内存。
2. 全写法
主存和cache同时修改。
3. 写一次法
与写回法基本相同，但是
第一次命中时要写入主存