计算机组成与体系结构：组相联映射（Set-Associative Mapping）
目录
🧩 映射方式问题回顾
🏗️ 组相联映射
工作流程
地址结构
♻️ 替换策略
示例：
优点
⚖️ 与其他映射方式对比
🧩 映射方式问题回顾
直接映射的问题：
-
优点：实现简单，查找速度快（单一比较器）
-
缺点：
-
冲突未命中（Conflict Miss）严重：即使缓存没满，某些块也只能映射到唯一行，造成不必要的替换
-
例子：如果地址 A 和地址 B 都映射到第 3 行，则每次访问都会把对方替换掉，即使缓存中还有空位。
全相联映射的问题：
-
优点：消除了冲突未命中（Conflict Miss 几乎为 0）
-
缺点：
-
查找成本高：需要并行比较所有缓存行的 Tag → 成本高、功耗大、速度慢
-
不易扩展到大容量 Cache
-
🏗️ 组相联映射
组相联映射 是一种折中策略，它将 Cache 分为多个 集合（sets），每个集合中包含 多条 Cache 行。
每个主存块根据其地址映射到 唯一一个集合，但在这个集合中，它可以存储在 任意一行中。
工作流程
-
地址分解：将地址拆分为 Tag, Set Index, Block Offset
-
定位集合：使用 Set Index 定位到 Cache 中的一个集合
-
并行比较：在这个集合中并行比较所有行的 Tag 字段
-
命中判断：
-
如果某一行的 Tag 匹配且 Valid Bit = 1，则 Hit
-
否则 Miss，需要替换策略
-
地址结构
设：
-
主存地址长度 = 32 bits
-
Cache 有 2ⁿ 个集合，每个集合有
k行（称为 k-way set-associative）
那么地址被分为以下几部分：
| 部分 | 中文 | 功能 |
|---|---|---|
| Tag | 标记位 | 用于与 Cache 中存储的 tag 比较 |
| Set Index | 集合索引 | 确定该块应映射到哪个集合 |
| Block Offset | 块内偏移 | 定位块内数据位置 |
如果 Cache 是 4-way set-associative，共有 256 sets，则需要：
-
log₂(256) = 8 位用于 Set Index
-
Block Size = 64 Bytes → Block Offset = 6 位
-
剩余 32 - 6 - 8 = 18 位为 Tag
♻️ 替换策略
当一个 Set 中所有 Cache Line 都被占满，需要替换一个块，策略包括：
| 策略 | 中文 | 特点 |
|---|---|---|
| LRU (Least Recently Used) | 最近最少使用 | 最常用，也最能提高命中率 |
| Random | 随机替换 | 简单但命中率较低 |
| FIFO (First-In First-Out) | 先进先出 | 实现简单，性能一般 |
每个集合内部相当于是一个 小型的全相联 Cache。
示例：
访问示例（以地址 77 为例）
-
地址 77 → 二进制：
1001101-
Block offset:
01（第2个字节） -
Set index:
11→ Set 3 -
Tag:
100
-
-
Cache 会在 Set 3 的两个 line 中，查找是否有 tag = 100 的块。
-
若某一行中 tag 匹配 → 命中（Hit）
-
否则 → 未命中（Miss），触发替换策略（如 LRU）
-
映射过程：
优点
| 优点 | 说明 |
|---|---|
| ⭐ 更低的冲突失效（Conflict Miss） | 比 Direct-Mapped Cache 更灵活，一个 Set 内多个行减少映射冲突 |
| ⭐ 接近 Fully Associative 的命中率 | 特别是当 k 比较大时 |
| ⭐ 查找效率适中 | 只需比较一个 Set 中的多个行，而不是所有行（比 Fully Associative 更快） |
| ⭐ 适配性强 | 可调节“k-way”来平衡速度和命中率 |
⚖️ 与其他映射方式对比
| 特性 | Direct Mapping | Fully Associative | Set-Associative |
|---|---|---|---|
| 映射方式 | 每块 → 1 行 | 每块 → 任意行 | 每块 → 1 个集合中的任意行 |
| 冲突未命中 | 高 | 极低 | 低 |
| 硬件复杂度 | 最低 | 最高 | 中等 |
| 查找时间 | 最快 | 最慢 | 中等 |
| 替换策略 | 无需 | 需要 | 每个集合内部需要 |