位宽感知的寄存器绑定算法
作者:
作者单位:

作者简介:

高猛(1995-), 男, 博士生, CCF学生会员, 主要研究领域为异构编译, 高层次综合.
赵家程(1989-), 男, 博士, 副研究员, 主要研究领域为异构编译.
崔慧敏(1979-), 女, 博士, 研究员, 博士生导师, CCF专业会员, 主要研究领域为并行计算, 并行编译, 并行编程.
冯晓兵(1969-), 男, 博士, 教授, 博士生导师, CCF 杰出会员, 主要研究领域为编程与编译, 程序分析.

通讯作者:

赵家程, E-mail: zhaojiacheng@ict.ac.cn

中图分类号:

基金项目:

国家自然科学基金(62232015);


Bitwidth-aware Register Binding Algorithm
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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 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.

    参考文献
    相似文献
    引证文献
引用本文

高猛,赵家程,崔慧敏,冯晓兵.位宽感知的寄存器绑定算法.软件学报,2024,35(6):2631-2647

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-09-10
  • 最后修改日期:2023-10-30
  • 录用日期:
  • 在线发布日期: 2024-01-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号