如何根据缓存开销计算缓存块大小？16位地址2路组相联例题

首先明确核心前提：题目给出的缓存总开销，指的是除了存储用户数据的数据阵列之外，所有标记、控制、替换逻辑需要的存储比特总和，这也是缓存硬件成本计算的通用定义。

已知条件梳理 #

• 内存地址宽度16位，字节寻址
• 缓存结构：2路组相联映射
• 写策略：写回（Write Back）
• 替换策略：完美LRU
• 总开销比特数：4352bit

开销组成拆解 #

2路组相联、写回+LRU的缓存，开销由三部分构成，无额外冗余项：

1. 标记位（Tag）：每个缓存块存储对应的地址标记，用于判断访问是否命中。16位地址会被拆分为标记位、组索引位、块内偏移位三个部分。
2. 块状态位：每个缓存块独立配置2个状态位
   • 有效位（Valid）：1bit，标记当前块存储的数据是否有效
   • 脏位（Dirty）：1bit，写回策略必备，标记当前块是否被修改、替换时是否需要写回内存
3. LRU跟踪位：2路组相联下每组仅需1bit即可实现完美LRU——每组只有2个块，1个比特足够标记哪一块是最近最少使用的，替换时直接选择该块即可。

变量定义与公式推导 #

定义如下变量：

• 块大小为B字节，块内偏移位长度b = log2(B)（字节寻址下，块内偏移位数由块大小直接决定）
• 缓存共有S个组，组索引位长度s = log2(S)（组索引是地址的连续位，因此组数S一定是2的整数次幂）
• 因为是2路组相联，总缓存块数为2*S
  单块的标记位长度为地址总长减去组索引位、块内偏移位，即16 - s - b，因此所有块的标记位总长度为2*S*(16 - s - b)。
  把所有开销加总等于题目给出的4352bit，列等式：

标记位总比特 + 有效位总比特 + 脏位总比特 + LRU位总比特 = 4352

代入各部分的计算逻辑：

2*S*(16 - s - b) + 2*S*1 + 2*S*1 + S*1 = 4352

化简等式：

2*S*(16 - s - b) + 5S = 4352
S*(37 - 2s - 2b) = 4352

数值求解 #

首先对4352做质因数分解：4352 = 2^8 * 17
观察化简后的等式：

• 左边S是2的整数次幂（组数必须为2的幂）
• 括号内37 - 2s - 2b中，2s和2b都是偶数，37是奇数，因此括号内的计算结果一定是奇数
  两个数相乘等于4352，其中一个是2的整数次幂，另一个是奇数，而4352的奇因子只有1和17两个：

1. 若括号内值为1：则S=4352，但4352包含因子17，不是2的整数次幂，不符合组数要求，直接排除
2. 若括号内值为17：则S=4352/17=256，256是2^8，符合组数为2的整数次幂的要求
   代入计算：

• S=256，因此s = log2(256) = 8
• 代入括号等式：37 - 2*8 - 2b =17，解得b=2
• 块大小B=2^b=2^2=4字节

结果校验 #

反向核算总开销验证正确性：

• 总块数=2*256=512块
• 单块标记位长度=16-8-2=6bit，标记位总开销=512*6=3072bit
• 有效位总开销=512*1=512bit
• 脏位总开销=512*1=512bit
• LRU位总开销=256*1=256bit
• 总开销=3072+512+512+256=4352bit，和题目给出的数值完全一致。

最终缓存块大小为4字节。

内容的提问来源于stack exchange，提问作者Yuri Teixeira Mendes