题一：把地址拆开看
题目
计算机具有 8 位地址空间，cache 为直接映射（direct mapped）， 容量 64 bytes，每个缓存块（cache block）为 16 bytes。
请用字母 B、S、T 填写 8 位地址中每一位的作用：
- B：块偏移（Block offset）
- S：组索引（Set index）
- T：缓存标记（Cache tag）
解题思路
直接映射缓存的地址被切成三段，从高位到低位依次是 T → S → B。 关键是先把后两段的位数算出来——因为它们决定了一个块有多少字节、一共有多少组。
第一步：算块偏移 B 的位数
一个块 16 字节，要在块内定位到具体某个字节，需要：
log₂(16) = 4 位
所以 B 占 4 位。
第二步：算组索引 S 的位数
缓存总容量 64 字节，每块 16 字节，所以总块数（也就是组数，因为直接映射一组只有一块）：
64 ÷ 16 = 4 组
要在 4 组里定位，需要：
log₂(4) = 2 位
所以 S 占 2 位。
第三步：剩下的都是 T
8 - 4 - 2 = 2 位
答案
| 位号 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| 作用 | T | T | S | S | B | B | B | B |
| 位数 | ← 2 位 → | ← 2 位 → | ← 4 位 → |
💡 记法：先算 B（块内寻址需要几位），再算 S（组数需要几位）， 剩下的全归 T。T 的位数 = 总位数 − S − B。这个方法对任何直接映射题都通用。
题二：跟着访问序列走一遍
题目
下表是一系列访存操作，cache 初始为空。 请填出每行的组索引号以及是否命中（H 命中 / M 不命中）。
已知地址格式：T T S S B B B B
答案解析
| 加载顺序 | 二进制地址 | T | S | 组索引 | 命中 |
|---|---|---|---|---|---|
| 0 | 0100 0011 |
01 | 00 | 0 | M |
| 1 | 1011 0010 |
10 | 11 | 3 | M |
| 2 | 0100 0000 |
01 | 00 | 0 | H |
| 3 | 1111 1001 |
11 | 11 | 3 | M |
| 4 | 1011 0010 |
10 | 11 | 3 | M |
| 5 | 1001 0011 |
10 | 01 | 1 | M |
| 6 | 1101 0000 |
11 | 01 | 1 | M |
| 7 | 1011 0000 |
10 | 11 | 3 | H |
| 8 | 0110 0111 |
01 | 10 | 2 | M |
| 9 | 0000 0111 |
00 | 00 | 0 | M |
逐行说明
第 0 行 0100 0011 → 组 0，初始为空，不命中。
把整块装入组 0，记录其标记 T = 01。
第 1 行 1011 0010 → 组 3，初始为空，不命中。组 3 记录 T = 10。
第 2 行 0100 0000 → 组 0，组 0 里已有标记 01，标记相同 → 命中。
⚠️ 这里容易错。地址和第 0 行只差低 4 位（块偏移）， 块偏移不参与比较——只要在同一个块里，就是命中。
第 3 行 1111 1001 → 组 3，组 3 里是 10，来了个 11，标记不同 → 不命中，
并把组 3 的标记替换成 11。旧数据被直接踢掉，这就是直接映射的特点。
第 4 行 1011 0010 → 又是组 3，标记 10。但组 3 刚被换成了 11，
标记不同 → 不命中。
🔥 这两行是本题的精髓：和第 1 行完全相同的地址， 第 1 次访问不命中，第 2 次访问还是不命中——因为中间被第 3 行挤掉了。 直接映射的"冲突"就是这么发生的。
第 5 行 1001 0011 → 组 1，空，不命中。组 1 记录 T = 10。
第 6 行 1101 0000 → 组 1，标记 11 ≠ 10，不命中，组 1 标记换成 11。
第 7 行 1011 0000 → 组 3，标记 10。组 3 现在是 10（第 4 行装进去的），
命中。
第 8 行 0110 0111 → 组 2，空，不命中。
第 9 行 0000 0111 → 组 0，标记 00。组 0 里是 01，不命中。
最终 cache 状态
| 组号 | 标记 T | 内容 |
|---|---|---|
| 0 | 00 |
第 9 行装入 |
| 1 | 11 |
第 6 行装入 |
| 2 | 01 |
第 8 行装入 |
| 3 | 10 |
第 7 行装入 |
题三：向量点积的命中率分析
题目
int x[8];
int y[8];
int dotprod(float *x, float *y){
int sum = 0;
for(int i = 0; i < 8; i++){
sum += x[i] * y[i];
}
}
问：在以下两种缓存配置下，命中率分别是多少？需要优化吗？
情况一：64 字节缓存，每行 16 字节
先算能放下几行：
64 ÷ 16 = 4 行
每个 float 占 4 字节，于是一行（16 字节）能放 4 个元素。
数组都是 8 个元素，所以：
x[0]~x[3]占第 1 行，x[4]~x[7]占第 2 行y[0]~y[3]占第 3 行，y[4]~y[7]占第 4 行
4 行刚好把缓存占满，不冲突。 逐次分析：
| i | 访问 | 情况 |
|---|---|---|
| 0 | x[0] | 不命中 → 装入第 1 行 |
| 0 | y[0] | 不命中 → 装入第 3 行 |
| 1~3 | x[1..3], y[1..3] | 全部命中 |
| 4 | x[4] | 不命中 → 换到第 2 行（跨行了） |
| 4 | y[4] | 不命中 → 换到第 4 行 |
| 5~7 | x[5..7], y[5..7] | 全部命中 |
统计：
总访问次数 = 8 次循环 × 2 次访问 = 16 次
不命中次数 = 4 次（i=0 的两次 + i=4 的两次）
命中率 = (16 - 4) / 16 = 12/16 = 75%
结论：命中率 75%，不需要优化。
💡 注意这里容易漏掉
i=4的不命中。 数组有 8 个元素，但一行只装得下 4 个——跨行时要重新加载。
情况二：32 字节缓存，每行 16 字节
能放下几行：
32 ÷ 16 = 2 行
只有 2 行，但我们要同时用到 x 和 y 两个数组。这里就要冲突了。
关键是看映射关系：直接映射下，地址决定它只能待在唯一一个固定的行里。
由于 x 和 y 大小相同（都是 32 字节）且相邻存放，
它们会映射到同样的两组行上。
于是每次循环变成这样：
| i | 访问 | 情况 |
|---|---|---|
| 0 | x[0] | 不命中 → 装入第 1 行 |
| 0 | y[0] | 不命中 → 把第 1 行挤掉，装入 |
| 1 | x[1] | 第 1 行现在是 y 的数据 → 不命中，把 y 挤掉 |
| 1 | y[1] | 又被挤掉了 → 不命中 |
每次访问都把上一次的数据踢出去，下一次又得重新加载。
统计：
总访问次数 = 16 次
不命中次数 = 16 次
命中率 = 0%
结论：命中率 0%，必须优化。
这就是所谓 cache 抖动（thrashing）： 缓存不是不够大，而是两个数组互相把对方挤出去， 每次访问都是冷启动。
优化方案
把 x 的声明从 8 改成 12：
int x[12]; // ← 从 8 改成 12
int y[8];
这样 x 占 48 字节（3 行），y 从第 4 行开始，
两个数组不再争抢同一组行，冲突消失。
优化后的访问情况：
| i | 访问 | 情况 |
|---|---|---|
| 0 | x[0] | 不命中 → 装入 |
| 0 | y[0] | 不命中 → 装入另一行，不冲突 |
| 1~3 | x[1..3], y[1..3] | 全部命中 |
| 4 | x[4] | 不命中（跨行） |
| 4 | y[4] | 不命中（跨行） |
| 5~7 | 全部命中 |
命中率恢复到 75%，和情况一相同。
💡 优化的本质不是"扩大缓存"，而是"调整数据布局、消除冲突"。 这在真实工程里叫 padding（填充）—— 用一点内存空间，换取大幅减少的 cache miss。
小结
这三道题其实在讲同一件事的三个侧面：
| 题目 | 考的是什么 |
|---|---|
| 地址划分 | 缓存的结构：地址的每一位分别归谁管 |
| 访问序列 | 缓存的行为：装入、命中、被替换 |
| 点积优化 | 缓存的性能影响：冲突如何拖垮程序 |
最值得记住的一点是第三题——0% 的命中率。
它说明了一个反直觉的事实：
缓存容量够不够，和缓存好不好用，是两回事。 32 字节放下 2 行，装一个 8 元素数组绰绰有余， 但两个数组一冲突，性能就归零了。
📌 本文由大学时期的课程作业整理而来，已移除姓名、学号、班级等个人信息。