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

2632 软件学报 2024 年第 35 卷第 6 期

by 7.41% and 7.39% respectively.
Key words: high-level synthesis; register binding; resource sharing

近年来, 由于摩尔定律 [1] 的逐渐失效, 晶体管规模扩展的成本正以指数级的方式变得更加昂贵 [2] , 从前主要依
赖晶体管的规模扩大来提升硬件性能的方法也逐渐变得难以实现. 为了继续提高程序性能, 新的体系结构设计开
始向特定领域架构 (DSA) 方向发展 [3] . 这种转变也导致了当前超大规模集成电路设计 (VLSI) 的流程发生了重要
的变化, 特别是对于专用硬件加速器的设计. 为了实现高效快速的硬件加速器设计, 采用高层次综合 (HLS) 作为基
于低级硬件描述语言 (例如 Verilog 或 VHDL) 的传统 VLSI 设计的替代方案 [2,4] 开始逐渐获得关注.
高层次综合 (high-level synthesis, HLS) 是一种将高级语言描述的逻辑结构自动转换成硬件描述语言表达的电
路模型的技术. 传统的 HLS 过程主要分为 3 个基本步骤: 调度, 分配与绑定 [5] . 其中调度过程将程序中的每个操作
分配给特定的时钟周期, 并生成有限状态机, 以确保操作的顺序和时间满足计算需求. 分配过程确定可供使用的硬
件资源数量, 包括处理器单元, 存储器等, 并为每个操作分配适当的资源. 绑定过程则通过在操作之间共享功能单
元以及在变量之间共享寄存器或存储器来节省面积, 从而实现资源的高效利用. 在给定的计算任务和硬件资源约
行细粒度建模. 在此基础上, 我们权衡了权重与顶点的度的双重影响, 提出一种基于优先度的启发式算法, 该算法
束下, HLS 通过将计算任务映射到可用的硬件资源上, 以实现最优的性能和资源利用率 [6,7] .
本文主要研究寄存器资源绑定问题, 即如何将程序的输入, 输出和临时变量映射到可用的寄存器单元上, 以最
小化所需寄存器资源的问题. Brisk 等人 [8] 证明了静态单赋值 (SSA) 形式的程序的寄存器绑定问题可以在多项式
时间内计算出最优解. 学术界的进一步研究工作可以分为两个不同的方向: (1) 通过与电路设计流程中的其他问题
协同研究, 寻找电路设计的全局最优解. 典型的如 Rim 等人 [9] 将布图规划问题纳入绑定问题中进行协同考虑, 从而
探索全局最优的布局与绑定方案. (2) 在寄存器绑定问题中引入位宽考量, 由于 Brisk 等人 [8] 的研究限制了寄存器
的大小必须完全一致, 而在电子设计领域, 寄存器可以具有不同的长度. 通过消除电路中的冗余位宽, 可以降低电
路的资源消耗, 这为进一步优化寄存器绑定问题提供了潜在的机会和可能性. 如 Kum 等人 [10] , Cong 等人 [11] 在传
统图着色算法与团划分算法 [12] 中加入位宽选择策略, 实现位宽感知的寄存器绑定算法研究, Canesche 等人 [13] 通过
插入额外的复制和交换指令进行数据交换, 以减少寄存器资源的开销.
寄存器绑定问题和寄存器分配问题存在着诸多的相似性, 两个问题的核心思路都是依据变量的活跃信息实现
寄存器共享, 这也启发现有的方法 [11] 将寄存器分配的图着色抽象引入到解决寄存器绑定当中. 但是两个问题存在
着一个明显的差异: 寄存器分配的目标是在寄存器数量固定的前提下将变量映射到寄存器中, 而寄存器绑定则需
要生成所需的寄存器和连线. 这种差异性使得直接将寄存器分配的图着色抽象应用于寄存器绑定问题时可能会引
发多种问题. 首先, 寄存器分配问题的抽象会给寄存器绑定问题引入不必要的约束限制, 如 Cong 等人 [11] 将寄存器
绑定问题映射为加权区间图着色问题 (weighted-interval-graph coloring, WIGC) 进行求解, 在此过程中需要对变量
进行对齐限制, 这增加了变量的位宽和活跃区间, 从而导致了寄存器空间的浪费; 其次, 寄存器分配中的一些优化
技巧并不适用于电路设计, 如 Canesche 等人 [13] 的算法在寄存器绑定过程中引入了寄存器分配中常见的活跃区间
分割技巧, 然而, 在硬件中频繁地移动数据会增加电路控制逻辑的复杂度, 反而可能会增加综合后电路的面积.
针对上述问题, 本文提出一种针对寄存器绑定问题的多重图着色抽象. 由于 HLS 可以根据绑定生成所需的
寄存器与对应连线, 无需划分为寄存器组, 因此不需要遵循对齐等寄存器分配问题中常见的约束. 针对这些特性,
我们将寄存器绑定问题映射为连续多重着色 (consecutive multi-coloring, CMC) 问题, 对变量的位宽和活跃区间进

无需插入额外的复制与交换指令来进行数据交换, 并能够进一步减少寄存器数量. 本文的主要贡献包含以下 3 个
方面.
• 我们将寄存器绑定问题映射为连续多重着色问题, 并提出一种在多项式时间内计算理论下界的方法. 与传统
方法中将该问题映射为加权区间图着色问题不同 [11] , 我们的方法无需引入额外的对齐约束, 更准确地建模了寄存
器绑定问题中的变量位宽和活跃区间信息, 从而可以实现更节省寄存器资源的分配方案.
• 为了求解连续多重着色问题, 我们提出一种基于顶点的度与权重感知的图着色算法 (CMC-h 算法). 具体而