CH5 存储器层次结构习题集 01

题 1：全相联映射的 Tag、Index 与 Offset

题目

设某主存地址为 32 位，Cache 共有 4096 个块，采用全相联映射。若每个块大小为 4 个字，求：

1. Cache 的总组数是多少？
2. 地址中的 Tag、Index、Offset 各占多少位？

默认按字节寻址理解；如果题目明确是按字寻址，也给出对应结果。

解题

1. 全相联表示整个 Cache 只有 1 组，所以 Index = log2(1) = 0。
2. 若按字节寻址，1 字 = 4 字节，则块大小为 4 × 4 = 16 字节，所以 Offset = log2(16) = 4。
3. 此时 Tag = 32 - 0 - 4 = 28。
4. 若按字寻址，则块大小就是 4 个可寻址单位，所以 Offset = log2(4) = 2，进一步得到 Tag = 32 - 0 - 2 = 30。

答案

• 按字节寻址：总组数 = 1，Tag = 28，Index = 0，Offset = 4
• 按字寻址：总组数 = 1，Tag = 30，Index = 0，Offset = 2

易错点

• 4096 = 2^12 不能直接当成全相联里的 Index 位数；那是直接映射才会用到的思路。
• 全相联没有“按地址直接定位某一行”的过程，所以地址划分里没有 Index。
• 这类题先判断映射方式，再求 Offset，最后再算 Tag，会更稳。

相似题提醒

• 如果题目改成直接映射，才会出现 Index = 12，此时 Tag 会变成 32 - 12 - Offset。
• 如果题目改成组相联，先算组数，再用 Index = log2(组数)，不要把“总块数”直接塞进公式。

题 2：直接映射 Cache 的总容量

题目

设某 Cache 的数据容量为 16KB，采用直接映射，主存地址为 32 位，块大小为 4 个字，按字节寻址，且每个 Cache 块包含 Tag + Valid bit + Data。求：

1. 每个 Cache 块总共多少位？
2. 整个 Cache 的总位数和总字节数是多少？

解题

1. 块大小为 4 字 = 16B，所以 Offset = log2(16) = 4；块数为 16KB / 16B = 1024 = 2^10，所以 Index = 10。
2. Tag = 32 - 10 - 4 = 18；每块数据区为 16 × 8 = 128 位，再加 Tag 18 位和 Valid 1 位，所以每块共 147 位。
3. 整个 Cache 总位数为 1024 × 147 = 150528 位，总字节数为 150528 / 8 = 18816B。
4. 这里只算了 Tag + Valid + Data；如果题目说明是写回法，还要再给每块多加 1 位 Dirty bit。

答案

• 每块总位数 = 147 位
• 总位数 = 150528 位
• 总字节数 = 18816B
• 相对 16KB = 16384B 的数据区，实际硬件容量约为 1.148 倍

易错点

• 16KB 通常指的是数据区容量，不是包括 Tag 和有效位在内的总硬件容量。
• 先算块数，再算 Index；不要把 16KB 直接拿去和地址位数做减法。
• 题目如果额外给出 Dirty bit、替换位或组相联条件，总容量都要跟着改。

相似题提醒

• 如果题目问的是“Cache 名义容量”，通常只报数据区，也就是这里的 16KB。
• 如果题目改成组相联，Index 会减少、Tag 会增加，因此每块控制位会略微上升。

题 3：直接映射 Cache 的地址划分与访存序列分析

题目

某直接映射 Cache 的 32 位地址划分为：31~10 为标记位，9~5 为索引位，4~0 为偏移量。求：

1. Cache 块大小为多少个字？
2. Cache 有多少项？
3. Cache 总位数与实际数据位数之比为多少？

对访存字节地址序列
0，4，16，132，232，160，1024，30，140，3100，180，2180

继续求：

4. 有多少块被替换？
5. 命中率是多少？
6. 列出 Cache 的最终状态。

小题 1：结构参数

解题

1. 偏移量有 5 位，所以块大小为 2^5 = 32B；若 1 字 = 4B，则每块是 8 个字。
2. 索引位有 5 位，所以 Cache 有 2^5 = 32 项。
3. 每项数据区为 32 × 8 = 256 位，标记位为 22 位，再加 Valid 1 位，所以每项共 279 位；因此比值为 279 / 256 ≈ 1.09。

答案

• 块大小 = 32B = 8 个字
• Cache 项数 = 32
• 总位数 / 实际数据位数 = 279 / 256 ≈ 1.09

小题 2：访存序列

解题

1. 块号序列为 0，0，0，4，7，5，32，0，4，96，5，68，对应索引分别为 0，0，0，4，7，5，0，0，4，0，5，4。
2. 命中发生在地址 4，16，140，180，共 4 次；总访问次数为 12，所以命中率为 4 / 12 = 1 / 3 ≈ 33.3%。
3. 发生替换的是地址 1024，30，3100，2180，因为这些访问落到的索引项当时已经有效且 Tag 不同，所以共替换 4 块。
4. 最终有效项只剩索引 0，4，5，7 四项。

答案

• 被替换的块数 = 4
• 命中率 = 4 / 12 = 33.3%
• 最终状态
  • <0, 3, 块[3072~3103]>
  • <4, 2, 块[2176~2207]>
  • <5, 0, 块[160~191]>
  • <7, 0, 块[224~255]>

易错点

• Offset = 5 位说明块大小是 32 字节，不是 32 个字。
• “有多少块被替换”只统计替换有效块，首次装入空项不算替换。
• 最终状态里的 Tag 不是完整地址高位，而是 块号 >> 5 之后的结果。

相似题提醒

• 这类题最好先把块号序列写出来，再做命中/替换判断，会比直接盯着原地址稳。
• 如果题目改成组相联，不能再直接按“一个索引只对应一项”的方式判断替换。