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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(6):2631−2647 [doi: 10.13328/j.cnki.jos.007097] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
位宽感知的寄存器绑定算法

高 猛 1,2 , 赵家程 1,2 , 崔慧敏 1,2 , 冯晓兵 1,2

1
(中国科学院 计算技术研究所, 北京 100190)
2
(中国科学院大学, 北京 100049)
通信作者: 赵家程, E-mail: zhaojiacheng@ict.ac.cn

摘 要: 寄存器绑定是高层次综合中的一个基础优化问题, 主要目标是在保证电路功能的同时最小化寄存器资源
的使用. 传统的方法尝试将编译器的寄存器分配算法应用于寄存器绑定中, 但却忽略了分配问题与绑定问题的差
异性, 因此在绑定过程中引入了额外的资源约束, 或采用了不适合电路设计的编译优化技巧, 从而导致资源浪费.
为解决这些问题, 将寄存器绑定问题转化为连续多重着色问题, 并提出一种基于位宽与顶点度结合的启发式求解
overhead compared to existing methods, without the insertion of additional instructions. Meanwhile, a comparison is conducted between
方法. 所提方法通过对变量的位宽和活跃区间等信息的细粒度刻画和建模, 能够进一步优化寄存器资源的开销, 同
时无需插入额外的指令. 将该算法与两种典型算法进行比较, 实验结果表明, 所提算法在 MiBench 测试集的
96.72% 的测试用例中达到理论最优解, 比其他两种方法分别提高 31.5% 和 25.1%; 在 Rosetta 测试集的所有测试用
例中均表现为最优解, 比其他两种方法分别提高 7.41% 和 7.39%.
关键词: 高层次综合; 寄存器绑定; 资源共享
中图法分类号: TP314

中文引用格式: 高猛, 赵家程, 崔慧敏, 冯晓兵. 位宽感知的寄存器绑定算法. 软件学报, 2024, 35(6): 2631–2647. http://www.jos.org.
cn/1000-9825/7097.htm
英文引用格式: Gao M, Zhao JC, Cui HM, Feng XB. Bitwidth-aware Register Binding Algorithm. Ruan Jian Xue Bao/Journal of
Software, 2024, 35(6): 2631–2647 (in Chinese). http://www.jos.org.cn/1000-9825/7097.htm

Bitwidth-aware Register Binding Algorithm
1,2
1,2
1,2
GAO Meng , ZHAO Jia-Cheng , CUI Hui-Min , FENG Xiao-Bing 1,2
1
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China)
2
(University of Chinese Academy of Sciences, Beijing 100049, China)
Abstract: Register binding is a fundamental optimization problem in high-level synthesis, primarily aiming to minimize the number of
employed registers while ensuring circuit functionality. Conventional approaches attempt to apply register allocation algorithms from
compilers to register binding, but they often overlook the inherent disparities between the allocation and binding problems. Finally, this
introduces additional resource constraints during the binding and utilizes compilation optimization techniques that are unsuitable for digital
circuit design, causing resource waste. To this end, this study transforms the register binding problem into a continuous multicoloring one
and proposes a heuristic solving method that combines the bit width and vertex degrees. This method provides a more fine-grained
characterization and modeling of variables in information such as the bit width and live intervals, which further reduces register resource

the proposed algorithm and two typical algorithms. Experimental results demonstrate that the proposed algorithm yields a theoretically
optimal solution in 96.72% of the test cases in the MiBench benchmark, improving 31.5% and 25.1% over other methods respectively. In
the Rosetta benchmark, this algorithm consistently exhibits the optimal solution across all test cases, outperforming the other two methods

* 本文由“编译技术与编译器设计”专题特约编辑冯晓兵研究员、郝丹教授、高耀清博士、左志强副教授推荐.
收稿时间: 2023-09-10; 修改时间: 2023-10-30; 采用时间: 2023-12-14; jos 在线出版时间: 2024-01-05
CNKI 网络首发时间: 2024-03-23