局部性、Cache 与主存¶
一次读取为什么顺手取来邻居¶
程序依次读取地址 100、104、108,每次读 4 字节。设教学缓存初始为空,每次总是以 16 字节为一块取数据,且块起始地址只能是 16 的倍数,这叫按 16 字节对齐。包含地址 100 的块从 96 到 111。第一次读取找不到这一块,叫未命中,硬件把整块从下一层取回来。只要该块还在,读取 104 和 108 都能用同一份副本,叫命中。
块起点 96 读 100 读 104 读 108 下一块起点 112
| 96–99 | 100–103 | 104–107 | 108–111 | 112–127 ...
第一次取块 复用这块 复用这块
如果下次读的是 112,就进入另一块。一次取 16 字节比只取 4 字节多搬了数据,顺序访问时这笔成本能由后面的读取分担。假如程序每次都跳到远处,顺带取回的字节可能完全没用。实际处理器的块大小和驻留情况视实现与工作负载而定。
为什么小 cache 能代表大内存¶
程序访问并非均匀随机:
- 时间局部性:刚访问的数据很可能再次访问,如循环变量;
- 空间局部性:附近地址很可能很快访问,如顺序数组和连续指令。
cache 以块为单位搬运相邻字节,利用空间局部性;把近期块保留在快速层,利用时间局部性。若访问位置几乎随机,且这一段时间反复或集中访问的数据(工作集)远大于 cache,命中率会显著下降。
层次结构¶
离计算部件最近的寄存器由指令直接读写。访问内存时,处理器通常先查第一级缓存(L1),没有再查第二级(L2)或更低层,必要时从主存读取。主存常用动态随机存储器(DRAM),掉电会丢失。固态硬盘(SSD)一般用来持久保存数据。当程序所需的一页还没进入主存时,可能需要由操作系统把内容从硬盘加载回来。这个过程见地址翻译与缺页。
上层缓存保存下层的块,有些机器允许先更新缓存,之后再送回下层。这种做法称为写回。已改过、还没写回下层的块叫脏块(dirty block)。
每次读取都要先查缓存,未命中时才需要额外等待。把多次访问的耗时取平均,得到平均存储访问时间(AMAT)。在一层缓存的例子里,\(T_{hit}\) 是先查缓存所花的时间,\(R_{miss}\) 是没找到的比例,\(P_{miss}\) 是一次没找到之后额外等待的时间。
假设每次先查缓存要 1 纳秒(ns),一百次查找有五次没找到,这五次各额外等 60 纳秒。平均每次用时为:
这里一百次只有五次没找到,这五次仍把平均用时从 1 纳秒抬到了 4 纳秒。
块、组与 tag¶
假设缓存分成几个组,每组中每个能放一块数据的位置叫一路。用地址中的组索引先选组,再用标记(tag)区分同一组里来自不同地址的块。命中之后,靠块内偏移取出块里需要的字节。地址的三部分如下。
若块大小为 \(B\) 字节,块内偏移位数是 \(\log_2B\);若有 \(S\) 组,组索引位数是 \(\log_2S\),其余是 tag。
最小完整例子¶
如果同一组内任意一路都可以放进该组的块,就叫组相联。现在设缓存有 32 KiB,总容量按块里可存的数据计算,每块 64 B,每组能放 8 路。
因此块内偏移占 6 位,组索引占 6 位。32 位的物理地址还剩 20 位用作标记。访问时先选组,并行比较组内 8 个标记。如果某一路的标记一致,再用偏移从那一块取出所需字节。
找到组以后,怎样找到命中的那一路?¶
设 Cache 有 2 组,每组 2 路,每块 16 字节。一“路”就是组内一个可以放数据块的位置。先用地址除以 16 得到块号和块内偏移,再用块号除以 2,余数是组号,商是标记(tag)。选中组后,只在这组里找有效且标记相同的路。有效表示这一位确实放着可用的数据块,空路不能碰巧因为标记相同就算命中。表中的 LRU 指优先换掉最近一次使用最早的块。
| 读取地址 | 块号 | 组号 | 标记 | 组 0 里发生什么 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 未命中,取回 0–15,放进一条空路 |
| 32 | 2 | 0 | 1 | 未命中,取回 32–47,放进另一条空路 |
| 0 | 0 | 0 | 0 | 比较组内标记,命中第一份数据 |
| 64 | 4 | 0 | 2 | 两路都已用满,若采用 LRU,就换掉更久没用的 32–47 |
画完会发现,第 1 组还是空的。即使整个 Cache 尚有空间,同组的块仍会争用该组的路。再读地址 69,块号和标记与 64 相同,偏移为 5,因此可以从刚填好的那一路取第 5 个偏移位置上的字节。
这个问题来自读者对组内比较与替换的追问。上述表格采用空路优先和 LRU 的教学设定,具体硬件的替换策略可以不同。B 站讨论 · CS 61C Cache 设计
映射方式的权衡¶
- 直接映射:每块只能进一个位置,命中快、硬件小,但冲突多;
- 全相联:可放任意位置,冲突少,但要比较所有 tag;
- 组相联:限制在一组的若干 way,折中速度与冲突。
每组可以放多少路,叫相联度。多留几路,有些本来争同一位置的块就能一起留住。查找时也要比较更多标记,可能增加硬件面积、功耗和查找时间。
三类 miss¶
- 强制 miss:块第一次被访问;
- 容量 miss:工作集超过 cache 总容量;
- 冲突 miss:容量足够,但映射限制让多个热块争同一位置。
增大块可利用空间局部性,却减少可容纳块数并增加无用数据传输。提高相联度缓解冲突,不能解决容量不足。
写策略¶
写直达同时更新 cache 和下层,状态简单但写带宽压力大,常配写缓冲。写回只改 cache 并标记 dirty,替换时才写下层,减少流量但控制更复杂。
写入时如果所需块还不在缓存里,写分配会先取整块回来再改,适合之后会再用这块数据的情况。非写分配会直接把修改交给下一级,适合程序持续写新位置、很少回头读的情况。多个核心各有一份缓存时,还要约定哪份副本有效,见缓存一致性。
替换与预取¶
组满时需选择牺牲块。LRU 试图替换最久未用者,路数大时精确维护昂贵,常用近似 LRU 或随机策略。预取器依据地址模式提前拉取数据,命中未来需求就隐藏延迟;预测错误则浪费带宽、污染 cache,甚至干扰其他核心。
主存并非“平坦数组”¶
DRAM 用电容保存位,需要定期补充电荷(刷新)。可以把一个存储阵列想成许多行和列。访问时先把整行打开到行缓冲,再取对应的列。同一行里连续读两列,可以省掉第二次打开行的时间。DRAM 还有多个相对独立的阵列,称为 bank,可以交叠处理不同请求。
因此地址映射和访问顺序会影响 bank 并行与行缓冲命中。顺序访问通常友好,随机大步长访问可能同时破坏 cache 和 DRAM 局部性。
同样遍历数组,为什么交换循环会变慢¶
一个按行存放的二维 C 数组,每个元素占 4 字节。设缓存行(即前面说的缓存块)为 64 字节、第一行按 64 字节对齐。一行内顺序读取前 16 项,装入的同一个缓存块就能服务后续读取。如果每行有 1024 项,从上一行第一个元素读到下一行第一个元素就跨了 4096 字节,这两次读取会用不同的块。
两种写法都要读遍相同数量的元素,但每次取来的缓存块能用上多少字节,会因顺序而不同。实测时应该用同一份数组、同样的编译选项,并报告数组尺寸和运行次数。数组很小、已有缓存、编译器改写循环或硬件预取时,差异会改变。可对照 CS:APP 的矩阵拷贝例子。
自测¶
- 直接映射 cache 中两个热块反复冲突属于哪类 miss?
- 写回策略为何需要 dirty 位?
- 预取提升性能需要哪些条件,又可能伤害哪些共享资源?