CSAPP

Chapter 06 层次结构存储系统

Cache 主存地址分段

[ Tag ] [ Set ] [ Offset ]

主要概念：

1. 总位数：就是内存地址的总长度的位数。
2. 块内地址：就是块的总长度的位数。
3. Cache 组号：看组的数量的位数。
4. 组数量：行数 / 组相连路数。
5. Tag：总位数 - 块内地址 - Cache 组号。

最终的分段为：

1. Tag
2. Cache 组号
3. 块内地址

例题：

某计算机主存地址空间大小为 256KB，按字节编址，Cache 的数据区有 16 行，每行 64B,与主存按每组 2 行构成组相联映射。

• Cache 组号：$ 16 / 2 = 8 = 2^3 $ -> 3
• 块内地址：$ 64B = 2^6B $ -> 6
• 总位数：$ 256KB = 2^{18}B $ -> 18
• Tag：$ 18 - 3- 6 = 9 $

Cache 容量

Chache 是一个二位的表，因此 Cache 容量就是每行的大小 * 行数。

每行的结构是： [有效位] [Tag] [数据位]。

1. 算 Tag 位数：$ Tag=总位数 - 块内地址 - Cache 组号$

2. 算单行总位数：$ 单行 bits = 有效位(1) + Tag位 + [脏位] + 数据位(Byte×8) $

3. 算 Cache 总大小：$ 总容量 = 总行数 × 单行 bits $

例题：

题目参数：

• 总行数：16 行
• 块大小：64 B
• Tag：我们算出是 9 位

计算过程：

1. 数据转 Bits： 数据块是 $ 64 Bytes $，也就是 $ 64×8=512 bits $。

2. 算一行的总宽度：

   $ 1 (有效位)+9 (Tag)+512 (数据)=522 bits $

3. 算 16 行的总容量：

   $ 16 行×522 bits/行=8352 bits $

4. 换算成 Bytes (为了和答案对齐)：

   $ 8352÷8=1044 Bytes $

Cache 地址映射

流程：物理地址 -> （除法）块号 -> （取模）组号 -> 行号

由于主存分段是这样的结构：

[ Tag ] [ Set ] [ Offset ]

因此这个操作实际上就是去掉头部的 Tag 和 尾部的 Offset 拿到中间的 Set。

也就是说每个地址对应一个块号，这个块号就是 [ Tag ] [ Set ]，可以通过除法得到。

每个块地址又映射到若干组，这个组号就是 [ Set ]，可以通过取模得到。

我们计算时，先准备：

1. 元素大小：int 通常是 4B。
2. 块大小 (Block Size)：题目给定（本题是 64B）。
3. 组数 (Sets)：总行数÷路数（本题 16÷2=8）。
4. 起始地址：本题是 480

第一步：算物理地址 (Physical Address)

• 口诀：起始 + 下标 × 大小

• 公式：$ Addr=Start+(index×siz) $

第二步：算主存块号 (Block Number)

• 口诀：地址整除块

• 公式：$ Block=Addr÷BlockSize $

第三步：算 Cache 组号 (Set Index)

• 口诀：块号模组数，余数是组号

• 公式：$ Set=Block \mod Sets $

第四步：算 Cache 行号 (Line Number)

• 口诀：组号乘路数，占坑连着数
• 公式：
  • 起始行 = Set × 组相连数
  • 结束行 = 起始行 + 组相连数 − 1

答案：

1. 地址：480+5×4=500
2. 块号：500÷64=7 (余数不看)
3. 组号：7(mod8)=7
4. 行号：7×2=14→L14,L15

Cache 命中

1. 按 LRU (最近最少使用) 替换算法

   规则： 谁最久没被访问过，就替换谁。每次 Hit (命中) 或新入库，该块都会变成“最新鲜”的（MRU），排到队尾，不会被替换。

2. 按 FIFO (先进先出) 替换算法

   规则： 谁先进入 Cache，谁就先被替换掉（不管它中间有没有被再次访问过，只看“进门”的时间）。