存储层次与缓存

存储层次与访问局部性

处理器寄存器、片上缓存、主存和持久存储具有不同容量与访问成本。程序执行时通常反复使用其中一小部分数据，存储系统利用这种访问分布，把近期或相邻的数据保留在更靠近处理器的位置。分析缓存效果需要知道访问顺序、数据布局和缓存组织，单独知道数组总大小不足以确定命中率。

时间局部性指近期访问过的数据可能在不久后再次使用，空间局部性指访问一个地址后可能访问附近地址。顺序扫描数组通常具有空间局部性，反复使用少量参数通常具有时间局部性。局部性是工作负载的特征，缓存容量和替换策略则决定这些访问能否转化为命中。

缓存块与命中

缓存按固定长度的块保存数据。请求地址对应的块已存在于缓存且状态允许读取时，称为命中；否则称为缺失，需要访问下一级存储。块内的字节偏移只选择当前块中的位置，不参与区分不同主存块。

这里区分字节与位，容量使用 KiB 时每单位为一千零二十四字节。块大小、组数和相联度共同决定数据容量；标记、有效位和替换状态还需要额外空间。题目若只给数据容量，应按数据部分计算块数，再单独计入这些管理信息。

地址分解与直接映射

设缓存块长为 $B$ 字节，组数为 $S$，两者都是二的幂。字节地址 $a$ 的块号为 $q=\lfloor a/B\rfloor$，块内偏移为 $a\bmod B$。组号是 $q\bmod S$，标记是 $\lfloor q/S\rfloor$。直接映射缓存每组只保存一个块，因此组号相同的不同块会相互替换。

缓存地址字段计算

一个直接映射缓存的数据容量为 $4\,\mathrm{KiB}$，块长为十六字节，地址宽度为三十二位。共有 $4096/16=256$ 组，因此块内偏移占四位，组索引占八位，标记占二十位。对地址 0x1234，十进制值为四千六百六十，块号为二百九十一，偏移为四，组号为三十五，即 0x23，标记为一。我们重新组合得到 $(1\times256+35)\times16+4=4660$，与原地址一致。若管理信息仅计二十位标记和一位有效位，则还需 $256\times21=5376$ 位，即六百七十二字节，不包含其他状态和纠错信息。

组相联缓存允许每组保存多个块，组内位置称为路。增加相联度能减少部分映射冲突，但同一组的多路标记需要比较，替换策略也更复杂。全相联缓存只有一组，所有块都能放在任意路，容量仍然有限；访问工作集超过容量时依然会缺失。

访问轨迹与冲突缺失

我们先把地址转换为块号，再按顺序更新缓存状态，逐次记录命中或缺失。首次访问一个块时的缺失称为强制缺失；工作集超过容量造成的缺失与相联度不足造成的冲突需要通过对照模型区分。不同教材对缺失分类的具体分析口径可能略有差异，计算时应说明所用缓存和替换规则。

直接映射缓存的访问序列

设缓存有四个块位置，每块十六字节，初始为空，按直接映射组织。依次读取字节地址 $0,4,64,0,16,20$。对应块号为 $0,0,4,0,1,1$。第一次装入块零，为缺失；第二次仍在块零，命中；第三次块四映射到组零，替换块零，为缺失；第四次重新装入块零，为缺失；第五次把块一装入组一，为缺失；第六次命中块一。总共两次命中、四次缺失，命中率为 $2/6=1/3$。缓存总容量足以放下这三个不同块，但直接映射使块零和块四发生冲突，说明容量与映射需要同时考虑。

如果把同样四个块的位置改成两组两路，并采用适当的替换规则，块零与块四能够同时保留在组零，这条轨迹中的第四次访问会命中。比较相联方式时应固定总数据容量和块长，否则观察到的变化可能同时来自容量差异。预取、写策略和多核干扰也会改变真实硬件上的访问结果。

平均访问时间与写入策略

对单级缓存的阻塞访问模型，设命中检查时间为 $t_h$，缺失率为 $m$，缺失后额外等待为 $p$，则平均访问时间为

$t_{avg}=t_h+mp.$

额外代价 $p$ 不包含已经花费的命中检查时间；若资料中的缺失总时间包含检查阶段，必须先统一口径。以一纳秒检查、百分之五缺失率、五十纳秒额外代价为例，平均值为三点五纳秒。这个平均值适合描述给定请求分布，真实处理器可能并行处理多个缺失，程序总时间还取决于依赖关系与重叠程度。

写直达在更新缓存时同时向下一级发出写入，写回则先标记缓存块已修改，待替换或特定维护操作时再写到下一级。写缺失时还要决定是否先把块装入缓存，这一选择称为写分配策略。描述写行为时应同时给出这两个维度，不能只说采用缓存写入就推断总线流量。

脏块表示内容与下一级副本存在差异。写回缓存替换脏块前必须保证更新被正确传递，否则数据会丢失。缓存一致性与持久化还涉及其他机制：多个核心各自持有副本时要维持规定的可见性，断电后的数据保留则依赖持久存储和刷新协议。单核命中率模型不包含这些完整保证。

数组布局与循环访问

矩阵按行连续保存时，内层循环沿行扫描通常连续访问相邻地址；内层循环跨行访问则具有较大的步长。调整循环次序或分块会改变访问轨迹，但必须保持计算依赖和结果语义。块大小选择过大时工作集可能超出缓存，过小时循环控制和边界处理成本可能上升。

分析一个优化时，我们可以先写出小矩阵的地址序列，用确定的缓存模型统计访问，再在真实程序中测量。测试应覆盖冷缓存和热缓存情形，并明确矩阵尺寸、数据类型和编译选项。缓存命中次数的变化解释局部原因，运行时间给出整体效果，两类结果共同帮助判断优化是否值得保留。

数组的起始地址也会影响缓存块边界。同样大小的数据若从块中间开始，可能跨越更多块；多个数组若按相同索引模式映射到同一组，还可能相互替换。构造性能实验时，应同时记录元素大小、访问步长和地址对齐，改变一个因素后再观察命中统计，避免把对齐变化归因于循环算法本身。

缓存计算练习

练习标记完成

所属知识

容量组织

难度

2/5

一个 $32\,\mathrm{KiB}$、四路组相联缓存，块长六十四字节，求块数、组数、偏移位数和组号位数。

查看解答

数据容量为三万二千七百六十八字节，除以六十四字节块长得到五百一十二块，再除以四路得到一百二十八组。块内偏移六位，组号七位。

练习标记完成

所属知识

访问轨迹

难度

2/5

两组直接映射缓存每块八字节，初始为空，依次访问地址 $0,7,8,0$，记录命中情况。

查看解答

块号依次为零、零、一、零，分别映射到组零、组零、组一、组零。初始空缓存下第一次和第三次缺失，其余命中，命中率为二分之一。

练习标记完成

所属知识

平均时间

难度

2/5

命中时间两纳秒、缺失率百分之十、额外缺失代价八十纳秒，求平均访问时间及缺失率减半后的结果。

查看解答

平均访问时间为二加零点一乘八十，等于十纳秒。若缺失率减半，则为二加零点零五乘八十，等于六纳秒。两次都把八十纳秒作为额外缺失代价。

练习标记完成

所属知识

写回

难度

2/5

说明写回缓存替换干净块与脏块时分别需要完成什么操作，并给出丢弃脏块会造成的后果。

查看解答

干净块与下一级数据一致，直接替换即可；脏块含有尚未下传的修改，需要先写回或放入能够保证最终写回的缓冲结构，再复用对应位置。

存储层次阅读资料

14 Caches and the Memory Hierarchy: Computation Structures

Chris Terman · 2017 · Massachusetts Institute of Technology

打开官方来源

CS 61 Textbook Reading Guide

2026 · Harvard University

打开官方来源

MIT 6.004 的缓存课程提供映射、地址分解和缺失计算材料。哈佛 CS 61 的存储单元阅读指引对应数据局部性、处理器缓存和文件输入输出，便于把本章地址轨迹与程序数据布局联系起来。