计算机组成与体系结构：组相联映射（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 为例）

1. 地址 77 → 二进制：1001101

   • Block offset: 01（第2个字节）

   • Set index: 11 → Set 3

   • Tag: 100

2. 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 个集合中的任意行
冲突未命中	高	极低	低
硬件复杂度	最低	最高	中等
查找时间	最快	最慢	中等
替换策略	无需	需要	每个集合内部需要