Page 57 - 《软件学报》2024年第6期
P. 57

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


                 言, 算法首先使用     CMC  问题理论下界对应的分配方案作为初始方案. 然后, 通过考虑顶点的邻接关系和变量的位
                 宽, 计算每个顶点的优先度. 最后, 按照优先度的顺序进行求解, 以实现高效的寄存器绑定.
                    • 我们在  LLVM  编译器   [14] 中实现了上述算法, 并在    MiBench [15] 与  Rosetta [16] 测试集上对算法进行了实验评估.
                 评估结果表明, 在     MiBench  测试集中  CMC-h  算法的绑定结果接近理论最优解, 在           96.72%  的样例中  CMC-h  的绑
                 定方案是最优的, 相比于       Cong  算法  [11] 和  Swap  算法  [13] 分别将这一比例提高了  31.5%  和  25.1%; 在  Rosetta 测试集
                 中, CMC-h  的绑定方案在所有测试样例中均表现为最优解, 而               Swap  算法和  Cong  算法仅在  93.10%  和  93.12%  的
                 样例中达到最优解.

                 1   相关工作

                    本节旨在详细介绍与寄存器绑定问题相关的研究工作. 寄存器绑定是高层次综合过程中一项基础优化问题,
                 其也可视为寄存器分配问题的一种变体. 首先, 我们将介绍高层次综合过程中相关的优化方法和常用工具. 随后,
                 我们将探讨寄存器绑定问题与寄存器分配问题以及寄存器打包问题之间的相似性和差异性, 并评估各种算法在解
                 决这些问题时的适用性. 最后, 我们还将讨论位宽分析在寄存器绑定问题中的重要影响.
                 题时, 可以借鉴其他关联问题的方法进行求解.

                 1.1   高层次综合
                    高层次综合     (HLS) 是一种将高级语言描述的逻辑结构自动转换成硬件描述语言表达的电路模型的过程. 该技
                 术已经成为一种关键的使能技术, 尤其对于              FPGA  设计而言. 通过    HLS, 设计者可以在软件层面上描述组件的功
                 能, 并自动生成相应的硬件代码, 从而实现软硬件解决方案的快速部署. 相较于传统的电路设计方法, HLS                              使得设
                 计者不必了解电路设计的细节, 从而可以将注意力更多地专注于算法逻辑结构的设计与设计空间的探索上. 已有
                 的研究表明, HLS   可以提高    FPGA  设计的开发效率和可维护性         [2,4,17] .
                    传统的   HLS  过程主要分为    3  个基本步骤: 调度, 分配与绑定       [5] . 其中分配过程确定可供使用的硬件资源量, 调
                 度过程将程序中的每个操作分配给特定的时钟周期, 并生成有限状态机. 绑定过程通过在操作之间共享功能单元
                 以及在变量之间共享寄存器或存储器来节省面积. HLS                 在给定的计算任务和硬件资源约束下, 将计算任务映射到
                 可用的硬件资源上, 以实现最优的性能和资源利用率. 这                 3  个过程相互影响, 根据解决它们的顺序, 每个问题都有
                 不同的解决方案. 其中绑定问题通常是在分配和调度之后制定和解决的                       [6,7] .
                    目前, HLS 工具已经在某些情况下能够生成与手工优化电路相媲美的电路质量                        [2] . 经过多年的发展, 已经涌现
                 出超过   30  种不同的  HLS  工具  [18] , 其中多个工具基于开源编译器框架       LLVM/GCC  等进行开发. 例如, 多伦多大学
                 研发的   LegUp [19] 利用 LLVM 编译器作为前端编译器, 能够将输入的           C  语言自动转换为适用于 FPGA 的 Verilog
                                        [6]
                 语言. 另一个开源工具 Bambu 也采用 LLVM/GCC          的标准   IR  作为输入, 实现了广泛的转换和优化范围, 为            EDA
                 领域的研究人员提供了探索和集成新方法的机会.

                 1.2   寄存器绑定问题关联问题
                    寄存器绑定问题通常被拿来与寄存器分配问题和寄存器打包问题相互比较. 寄存器绑定对电路中的寄存器资
                 源进行共享, 提高资源的利用率. 寄存器分配确定如何将程序中的变量分配给有限数量的寄存器, 以最小化内存访
                 问次数并提高执行效率. 而寄存器打包则涉及如何将变量组合在一起, 并分配给不同的寄存器集合, 以最大程度地
                 利用寄存器容量. 虽然这些问题在具体细节上存在差异, 但它们都涉及优化寄存器的使用, 因此在解决某个特定问


                    寄存器分配问题通常被认为是一个              NP  完全问题, 因此在实际应用中常采用图着色算法进行求解                  [20] . 然而,
                 在  2005–2006 年间, 基于静态单赋值   (SSA) 形式的程序, 寄存器分配问题被证明可以在多项式时间内获得最优解                    [21−23] .
                 寄存器绑定问题与寄存器分配的主要区别在于: 寄存器绑定问题中的寄存器大小是任意长度, 相较于通常的架构,
                 对寄存器的访问更加灵活         [24] . 因此, 若采用传统的寄存器分配算法来解决寄存器绑定问题, 则会引入过多传统架
                 构的限制, 导致绑定的结果较差.
                    寄存器打包问题试图通过变量合并的方式                [25] 将多个变量分配到同一寄存器的不同位中, 从而解决可变位宽
   52   53   54   55   56   57   58   59   60   61   62