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

Bitwidth-aware Register Binding Algorithm

作　　者：高猛 赵家程[1,2] 崔慧敏 冯晓兵[1,2] GAO Meng;ZHAO Jia-Cheng;CUI Hui-Min;FENG Xiao-Bing(Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院大学,北京100049

出　　处：《软件学报》2024年第6期2631-2647,共17页Journal of Software

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

关 键 词：高层次综合 寄存器绑定 资源共享 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]