组相联缓存 | Codeboy's Blog

形式陈述

$W$ 路组相联缓存把每个组扩为W个候选行。若数据容量为C、块大小为B、组数为S，则 $C=BSW$ 。这里B、S为正的二次幂，W为正整数，C只计数据字节。对地址分解，仍有

q=\lfloor a/B\rfloor,\quad index=q\bmod S,\quad tag=\lfloor q/S\rfloor.

一次查找只比较指定组内W个有效tag。命中时选择匹配way；缺失时优先使用无效way，否则由替换策略在该组内选victim。way编号是放置结果，不是从地址固定切出的一段位。

W=1是直接映射，S=1是全相联。增加W而保持C、B不变，会减少组数S，因而改变index和tag的划分；不是在原有每组之外免费添加空间。

直觉

直接映射像每个对象只能住指定的一间房；组相联允许它在指定楼层里选房。冲突因此有了缓冲空间，但如果同组活跃块超过W，仍要有人被逐出。

两份tag相同也不能脱离index判断地址。缓存块的身份由tag和组号共同恢复，而offset只定位块内字节。

例子与边界

固定32位地址、C=32 B、B=8 B：

配置	W	S	offset位	index位	tag位
D	1	4	3	2	27
A	2	2	3	1	28

在D中，0x00与0x20只能争同一行。在A中，两者仍映到同一组，但tag分别为0和2，可以分住两个way。再来0x40，tag为4，第三个块就迫使这一组替换。

共同终点程序产生11次word访问，两配置均冷启动、write-back/write-allocate、LRU。D得到1次命中、10次缺失、3次需求触发的脏写回；A得到3次命中、8次缺失、2次需求脏写回，但末尾仍有一个脏块。

A的需求写回较少不等于全部修改已写入下层。若要求末尾flush，A还需写回该块，两个配置的总脏写回次数均为3。命中、填入和完成边界必须分开统计。

A中先写块0，再读块4，再读块8。若LRU选择块0为victim，必须先按写策略保存脏数据。增加相联度不会自动解决写回正确性；替换了tag却漏写旧dirty块，后面重新读块0会丢失之前的写入。

推论与应用

替换策略只在允许的候选way内作选择。让LRU在整个缓存跨组选择，看似更会保留热块，却已经把组相联模型改成了另一种结构。

相联度提高可能减少某些冲突，同时增加比较、选择和元数据成本。只用命中率不能推断真实CPU快慢；还需命中延迟、缺失代价和并行访问条件。

参考资料

UC Berkeley CS61C，Set-Associative Cache，课程笔记，访问于 2026-10-08。
David A. Patterson and John L. Hennessy, Computer Organization and Design RISC-V Edition, 2nd ed., 2021，Ch. 5。两配置的完整轨迹与终末flush口径由本文任务明确指定。