## 位图 (Bitmap) 实现本质上是一个 FreeMask。 - **结构**: 用一个N位的寄存器，其中N是物理寄存器的数量。每一位代表一个物理寄存器，1 表示空闲，0 表示已分配。 - **分配**: - 需要一个优先编码器来查找第一个（或任何一个）值为 1 的位。 - 找到后，将该位清零。 - **优点**: 可以实现不同的分配策略（如最低索引优先、分区策略）。可以并行查找多个空闲位（如果需要一次分配多个）。 - **缺点**: 优先编码器自己可能成critical path，特别当N很大时。如果需要循环分配（round-robin策略），逻辑会更复杂。 - **释放**: - 将对应物理寄存器索引位设 1。 - **优点**: 非常简单直接。 - **缺点**: 无。 - **检查点**: - **保存**: 直接复制整个位图。 - **恢复**: 直接用保存的位图覆盖当前位图。 - **优点**: 非常简单，状态完整。 - **缺点**: 如果N很大，保存/恢复的数据量也大（N位）。 - **资源利用**: - 需要N位存储。 - 需要一个N输入的优先编码器。 - **并行性**: - 释放多个寄存器可以并行完成（但是要写端口支持，几个写就是几个并行）。 - 分配多个寄存器需要多个优先编码器或更复杂的逻辑。 - **调试**: - 直观，直接打出来看。 ## FIFO 实现本质上是一个循环队列。 - **结构**: - **选项A (基于RAM/RegFile + 指针)**: 使用一个存储物理寄存器索引的RAM或RegFile。维护一个头指针（用于分配/pop）和一个尾指针（用于释放/push），以及一个计数器。 - **选项B (基于移位寄存器)**: 对于较小的N，可以使用一系列寄存器，并通过移位操作实现FIFO。不适合N大。 - **分配**: - 从FIFO头部读取一个物理寄存器索引。 - 递增头指针。 - 递减计数器。 - **优点**: 分配快（O(1)）。 - **缺点**: 分配策略固定FIFO顺序。 - **释放**: - 将要释放的物理寄存器索引写入FIFO尾部。 - 递增尾指针。 - 递增计数器。 - **优点**: 释放操作非常快（O(1)）。 - **缺点**: 无。 - **检查点**: - **保存**: 需要保存FIFO中的所有有效条目、头指针、尾指针和计数器。如果FIFO基于RAM，则需要读取RAM中的相关部分。 - **恢复**: 需要将保存的条目写回FIFO（或RAM），并恢复指针和计数器。 - **优点**: 如果FIFO中空闲寄存器的数量远小于N，保存的数据量可能比完整位图小。 - **缺点**: 保存/恢复逻辑比位图复杂。需要处理FIFO在保存/恢复期间的读写。 - **资源利用 (基于RAM/RegFile)**: - 一个大小为N，宽度为 log2Up(N) 的RAM/RegFile。 - 头/尾指针寄存器。 - 计数器寄存器。 - 加法器/减法器。 - **并行性**: - 并不了一点。 - **调试**: - 不如 bitmap 但其实也还行。 ## 总结 | 特性 | 位图 (Bitmap) | FIFO (基于RAM/RegFile) | | ----------- | ------------------ | ---------------------------------------------- | | **分配逻辑** | 优先编码器 (N大就慢) | 简单指针操作 (快，O(1)) | | **分配策略** | 灵活 (最低/最高索引优先等) | 固定FIFO顺序 | | **释放逻辑** | 简单位操作 | 简单指针操作 | | **检查点** | 简单 (复制N位位图) | 较复杂 (复制条目、指针、计数器) | | **状态大小** | N位 | FIFO内容 (count * log2Up(N)) + 指针 + 计数器 | | **资源** | N位Reg, N输入优先编码器 | N x log2Up(N) RAM/RegFile, 指针Regs, 计数器Reg, 加法器 | | **并行分配/释放** | 释放易，分配难 | 串行 | | **调试直观性** | 高 | 中 | | **局部性** | 可能重复分配刚释放的寄存器，不够均匀 | 倾向分配较早释放的寄存器 (cooldown更足一点) | 要补充一点，就是位图实现循环分配也不是很麻烦，原理如下： - 维护一个“下一个要分配的起始点”指针（last_allocated_index）。 - 当需要分配一个寄存器时，从 (last_allocated_index + 1) % numPhysRegs 开始搜索空闲寄存器，找到第一个空闲的就分配它，并更新 last_allocated_index 为这个新分配的寄存器的索引。搜索是环形的，如果从 last_allocated_index + 1 到末尾没找到，就从头开始搜索到 last_allocated_index。然而，你都这么实现了，某种意义上你就是搞了个循环队列。不如直接用 FIFO。超标量的情况：在一个4路超标量处理器的重命名阶段，可能需要同时为最多4条指令分配目标物理寄存器。如果用 Bitmap 方案，使用一个优先编码器在每个周期最多只能找到并分配**一个**空闲物理寄存器。这个可能会导致分配比较慢。这个时候可能需要多个优先编码器，但也导致面积功耗都上来了。而且可能会形成较长的组合逻辑路径，影响时序。解决办法有这些： 1. 行前缀网络（parallel prefix network）批量计算每个位置之前有多少个空闲位 2. banked freeList：负载均衡，FreeList分成多个独立的“bank”。 --- 一个简单的选择方法：对于非常多的物理寄存器（几百个）——用 FIFO 需要频繁、快速、状态完整的检查点——用位图，直接复制 --- 有没有其它方法？有！ - CAM+ 指针/计数器: 比大型优先编码器更快，比纯FIFO更灵活一点。但是更消耗资源。 - 混入 LRU：优先选择最早释放的空闲寄存器。提高均匀性。 --- Q：为什么要追求均匀性？ A：频繁重用少数几个物理寄存器会增加资源冲突的概率；避免局部热点、物理退化等等。

【寄存器重命名】FreeList 实现对比：位图 (Bitmap) vs. FIFO

abel2002

位图 (Bitmap) 实现

本质上是一个 FreeMask。

结构: 用一个N位的寄存器，其中N是物理寄存器的数量。每一位代表一个物理寄存器，1 表示空闲，0 表示已分配。
分配:
- 需要一个优先编码器来查找第一个（或任何一个）值为 1 的位。
- 找到后，将该位清零。
- 优点: 可以实现不同的分配策略（如最低索引优先、分区策略）。可以并行查找多个空闲位（如果需要一次分配多个）。
- 缺点: 优先编码器自己可能成critical path，特别当N很大时。如果需要循环分配（round-robin策略），逻辑会更复杂。
释放:
- 将对应物理寄存器索引位设 1。
- 优点: 非常简单直接。
- 缺点: 无。
检查点:
- 保存: 直接复制整个位图。
- 恢复: 直接用保存的位图覆盖当前位图。
- 优点: 非常简单，状态完整。
- 缺点: 如果N很大，保存/恢复的数据量也大（N位）。
资源利用:
- 需要N位存储。
- 需要一个N输入的优先编码器。
并行性:
- 释放多个寄存器可以并行完成（但是要写端口支持，几个写就是几个并行）。
- 分配多个寄存器需要多个优先编码器或更复杂的逻辑。
调试:
- 直观，直接打出来看。

FIFO 实现

本质上是一个循环队列。

结构:
- 选项A (基于RAM/RegFile + 指针): 使用一个存储物理寄存器索引的RAM或RegFile。维护一个头指针（用于分配/pop）和一个尾指针（用于释放/push），以及一个计数器。
- 选项B (基于移位寄存器): 对于较小的N，可以使用一系列寄存器，并通过移位操作实现FIFO。不适合N大。
分配:
- 从FIFO头部读取一个物理寄存器索引。
- 递增头指针。
- 递减计数器。
- 优点: 分配快（O(1)）。
- 缺点: 分配策略固定FIFO顺序。
释放:
- 将要释放的物理寄存器索引写入FIFO尾部。
- 递增尾指针。
- 递增计数器。
- 优点: 释放操作非常快（O(1)）。
- 缺点: 无。
检查点:
- 保存: 需要保存FIFO中的所有有效条目、头指针、尾指针和计数器。如果FIFO基于RAM，则需要读取RAM中的相关部分。
- 恢复: 需要将保存的条目写回FIFO（或RAM），并恢复指针和计数器。
- 优点: 如果FIFO中空闲寄存器的数量远小于N，保存的数据量可能比完整位图小。
- 缺点: 保存/恢复逻辑比位图复杂。需要处理FIFO在保存/恢复期间的读写。
资源利用 (基于RAM/RegFile):
- 一个大小为N，宽度为 log2Up(N) 的RAM/RegFile。
- 头/尾指针寄存器。
- 计数器寄存器。
- 加法器/减法器。
并行性:
- 并不了一点。
调试:
- 不如 bitmap 但其实也还行。

总结

特性	位图 (Bitmap)	FIFO (基于RAM/RegFile)
分配逻辑	优先编码器 (N大就慢)	简单指针操作 (快，O(1))
分配策略	灵活 (最低/最高索引优先等)	固定FIFO顺序
释放逻辑	简单位操作	简单指针操作
检查点	简单 (复制N位位图)	较复杂 (复制条目、指针、计数器)
状态大小	N位	FIFO内容 (count * log2Up(N)) + 指针 + 计数器
资源	N位Reg, N输入优先编码器	N x log2Up(N) RAM/RegFile, 指针Regs, 计数器Reg, 加法器
并行分配/释放	释放易，分配难	串行
调试直观性	高	中
局部性	可能重复分配刚释放的寄存器，不够均匀	倾向分配较早释放的寄存器 (cooldown更足一点)

要补充一点，就是位图实现循环分配也不是很麻烦，原理如下：

维护一个“下一个要分配的起始点”指针（last_allocated_index）。
当需要分配一个寄存器时，从 (last_allocated_index + 1) % numPhysRegs 开始搜索空闲寄存器，找到第一个空闲的就分配它，并更新 last_allocated_index 为这个新分配的寄存器的索引。搜索是环形的，如果从 last_allocated_index + 1 到末尾没找到，就从头开始搜索到 last_allocated_index。
然而，你都这么实现了，某种意义上你就是搞了个循环队列。不如直接用 FIFO。

超标量的情况：

在一个4路超标量处理器的重命名阶段，可能需要同时为最多4条指令分配目标物理寄存器。如果用 Bitmap 方案，使用一个优先编码器在每个周期最多只能找到并分配一个空闲物理寄存器。这个可能会导致分配比较慢。这个时候可能需要多个优先编码器，但也导致面积功耗都上来了。而且可能会形成较长的组合逻辑路径，影响时序。解决办法有这些：

行前缀网络（parallel prefix network）批量计算每个位置之前有多少个空闲位
banked freeList：负载均衡，FreeList分成多个独立的“bank”。

一个简单的选择方法：

对于非常多的物理寄存器（几百个）——用 FIFO
需要频繁、快速、状态完整的检查点——用位图，直接复制

有没有其它方法？有！

CAM+ 指针/计数器: 比大型优先编码器更快，比纯FIFO更灵活一点。但是更消耗资源。
混入 LRU：优先选择最早释放的空闲寄存器。提高均匀性。

Q：为什么要追求均匀性？

A：频繁重用少数几个物理寄存器会增加资源冲突的概率；避免局部热点、物理退化等等。