Page 68 - 《软件学报》2024年第6期

2644 软件学报 2024 年第 35 卷第 6 期

1 000.000 1 000.000
Cong Swap CMC-h Cong Swap CMC-h
100.000 100.000
10.000
10.000
时间 (ms) 1.000 时间 (ms) 1.000
0.100
0.100
0.010 0.010
0.001 0.001
0 100 200 300 400 500 600 0 5 000 10 000 15 000 20 000
函数数量 函数数量
(a) MiBench 测试集 (b) Rosetta 测试集
图 9 绑定算法运行时间

2
CMC-h 算法需要重新构建干涉图进行着色分配, 这一过程时间复杂度为 O(|V| ) , 相较于其他分配方案 O(|V|+|E|)
的时间复杂度略高. 但这种时间付出是完全值得的, 首先, CMC-h 算法本质上仍然是多项式时间复杂度的算法, 除
去构建干涉图部分, 算法在时间复杂度上并未高于其他算法. 其次, 在高层次综合领域, 由于编译开销是一次性的,
• Swap
通过一定程度的编译时间换取更优的功耗和面积设计是常见的处理方法, CMC-h 算法在给定的最大样例中仍然
处于秒级时间, 而逻辑综合所需的时间往往长达数分钟甚至更久 [38] , 寄存器绑定占用编译时间通常不足 1%. 因此
我们能够通过有限的搜索显著提升绑定算法中达到最优解的样例比例.

4.5 样例综合分析
本文所讨论的技术旨在用于高层次综合领域. HLS 工具将用 C/C++或 SystemC 等高级语言编写的程序转换
为寄存器传输级 (RTL) 结构. 我们熟悉的常用工具有 LegUp, Intel HLS 和 Vivado 等. 它们可以将变量分组并对齐
到特定比特位宽 (如 1/2/4/8/16 等) 的寄存器中, 但不支持一般的位宽分配. 因此, 为了演示我们的绑定算法运用于
高层次综合的可行性, 我们将 LLVM 实现产生的解决方案手动映射到 Verilog 上, 并由此导出具体的 RTL 级电路
代码. 我们使用 Vivado 工具针对 Zynq-7000 后端架构, 对 3 种算法映射出的电路代码进行逻辑综合.
表 3 展示了 3 种算法对例 1 分配结果所产生的电路实际消耗的硬件资源数量. 其中表资源 (LUT) 本质是随机
存取存储器 (RAM), 是 FPGA 上实现的组合逻辑电路的主要方式. 触发器资源 (FF) 可存储 1 比特数据, 是寄存器
的基本存储单元, 在本例中状态机 (FSM) 需要固定存储 2 比特的状态. 输入/输出单元 (IO) 是芯片与外界电路的
接口. Swap 算法插入的额外指令采用了非阻塞赋值的方式实现 [13] , 在本样例中由于指令的并行性, 该插入指令在
实际生成电路中并未产生额外的代价. 由此我们得出了如下结论.

表 3 各算法为例 1 生成 Verilog 代码综合后的资源使用量 (LUT 合并前)

资源 Cong Swap CMC-h
LUT 22 24 20
FF 21 18 17
IO 25 26 25

• 比特粒度的寄存器绑定, 生产的逻辑电路是可综合的, 且分配的寄存器数量能够准确反映出实际生产电路的
寄存器数目.
算法产生了最多的 LUT, 这是由于该算法频繁的数据移动使得数据的分布更为零散, 从而使物理寄存
器的复用逻辑变得极为复杂.
• CMC-h 算法相比于其他算法使用的 3 种资源数目均为最少.
值得注意的是, 在本样例中 CMC-h 算法并未产生比 Cong 算法更复杂的寄存器绑定关系. 如图 2 所示, Cong
b 和 之间共 7 d 在第 2 拍写入, 因此控制逻辑共需要插入
e
算法仅在变量 比特寄存器复用, 但电路需要控制变量
10 个二选一多路复用器, 而 CMC-h 算法将会在变量 b, c, d, e 之间共 10 比特寄存器复用, 同样需要插入 10 个二
选一多路复用器. 在本样例中, 变量 e 的低 3 位为 0, 可以通过触发器的复位端口实现置 0, 因此 CMC-h 算法产生