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

高猛 等: 位宽感知的寄存器绑定算法 2645

的电路比 Cong 算法少用两个多路复用器. 图 10 展示了本文 CMC-h 算法所生成代码的寄存器级 (RTL) 电路图.
根据上述分析, 触发器的 D 端口与 R 端口 (复位) 共需要 8 个 LUT, 由于控制逻辑较为简单, CE 端口只产生 1 个
LUT. 计算单元需要 10 个 LUT, 状态机需要 1 个 LUT, 因此共需 20 个 LUT. 相比之下, Swap 算法插入复制与拷贝
指令使得数据共享的状况变得更为复杂, 因此寄存器的 D 端口与 CE 端口将需要更多的 LUT, 从而让电路变得更为
复杂.

R_i_0
a [4:0] S=1′b1 l0 [14:0]
5:0==4:0.05
b [5:0] 3:0==14:11 S=default l1 [14:0] O [14:0]
c [3:0]
S RTL_MUX
R_reg [14:0]
clk
>C 4:0 l0 [4:0] out0_i out_i
fsm_i R_i_1 CE Q 2:0 l1 [2:0] + O [5:0] l0 [5:0] O [7:0]
l1 [6:0]
S=2′b00 l0 [1:0] S=2′b00 l0 [14:0] S=1′b1 l0 [14:0] R_i_2 D + out [7:0]
S=2′b01 l1 [1:0] fsm_reg [1:0] S=2′b01 l1 [14:0] O [14:0] 14:0 RTL_ADD RTL_ADD
S=2′b10 l2 [1:0] O [1:0] 1:0 RST S=2′b10 l2 [14:0] O [14:0] S=default l1 [14:0] RTL_REG
S=default l3 [1:0] >C Q 1:0 S=default l3 [14:0] 14:0 S RTL_MUX
D
S [1:0] RTL_MUX RTL REG SYNC S [1:0] RTL_MUX
1:0
1:0
rst
l2 R0_i R_i
2:0 l0 [5:0] O [2:0] 2:0 O [14:0] 14:0
l1 [1:0] >> S=2′b00 l0 [14:0]
RTL_RSHIFT S=2′b01 l1 [14:0]
S [1:0] RTL_MUX
R0_i_0 1:0
l0 [3:0]
l1 [3:0] O [6:0]

*
RTL_MULT
图 10 CMC-h 算法分配例 1 代码对应 RTL 电路

5 总 结
本文提出了一种基于图的连续多重着色的寄存器绑定抽象, 新的抽象可以突破原有算法的理论下界, 最大限
度地减少寄存器空泡的产生, 且无需插入额外的指令. 我们在不考虑区间约束的条件下给出了一个新的理论下界,
该下界可以作为我们的算法的理论边界提供重要的参考依据. 我们提出了一种基于优先度的启发式方法, 尽管我
们的方法目前还不是最优解, 但实验表明, 在所有的测试集中该方法相比于最优解平均仅多用了 0.13% 的寄存器
资源, 在 96.72% 的样例中我们的绑定方案是最优的, 相比于其他的方法我们将这一比例提升了 25.1%.
本文的工作在高层次综合领域表现出了潜力, 本文的连续多重着色算法不仅可以应用于寄存器绑定问题, 同
样也可以应用于加法器, 进位保留加法器等其他无需对齐约束的硬件资源绑定中. 本文给出的理论下界对应的离
散寄存器分配方案, 也可以作为具有参考意义的解生成有效的电路在 FPGA 等场景下应用. 然而在实际的综合过
程中, 当前已有的寄存器绑定算法均存在一些问题. 首先, 当前算法仅考虑寄存器的位宽, 而没有考虑互连单元与
控制路径的复杂性, 因此无法直接在全局的电路设计中取得面积功耗的最优解. 其次, 位宽分析并没有考虑同一变
量在不同程序点的位宽变化. 然而, 在绑定问题中增加更多的考虑因素可能使得算法的设计变得更为复杂, 反而拖
累实际的优化效果. 因此我们下一步的工作准备在寄存器绑定中加入更多的分析与考虑, 以便于在实际的综合过
程中得到更好的效果.
References:
[1] Moore GE. Cramming more components onto integrated circuits. Proc. of the IEEE, 1998, 86(1): 82–85. [doi: 10.1109/JPROC.1998.
658762]
[2] Schafer BC, Wang Z. High-level synthesis design space exploration: Past, present, and future. IEEE Trans. on Computer-aided Design of
Integrated Circuits and Systems, 2020, 39(10): 2628–2639. [doi: 10.1109/TCAD.2019.2943570]
[3] Hennessy JL, Patterson DA. A new golden age for computer architecture. Communications of the ACM, 2019, 62(2): 48–60. [doi: 10.
1145/3282307]
[4] Cong J, Lau J, Liu G, Neuendorffer S, Pan PC, Vissers K, Zhang ZR. FPGA HLS today: Successes, challenges, and opportunities. ACM
Trans. on Reconfigurable Technology and Systems, 2022, 15(4): 51. [doi: 10.1145/3530775]
[5] Coussy P, Gajski DD, Meredith M, Takach A. An introduction to high-level synthesis. IEEE Design & Test of Computers, 2009, 26(4):
8–17. [doi: 10.1109/MDT.2009.69]
[6] Ferrandi F, Castellana VG, Curzel S, Fezzardi P, Fiorito M, Lattuada M, Minutoli M, Pilato C, Tumeo A. Invited: Bambu: An open-