Bitwidth-aware Register Binding Algorithm
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 10,2023
  • Revised:October 30,2023
  • Adopted:
  • Online: January 05,2024
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063