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

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

定义 1. 寄存器绑定问题. 给定程序 P 的变量集合 V , 及其权重映射 w : V → N , 假设每个变量 v ∈ V 都存在对
I
应活跃区间 l v , 映射 为每个变量 v ∈ V 分配一个区间 I(v) , 且满足如下约束:
a) (区间约束) ∀v ∈ V, |I(v)| = w(v) .
b) (冲突关系) ∀a,b ∈ V , 若 l a ∩l b , ∅ , 则 I(a)∩ I(b) = ∅ ,
其中, N 代表自然数集, 权重映射 w 代表每个变量的位宽. 该定义与 Cong 等人提出的绑定问题定义 [11] 是一致的,
I 会单独考虑变量的每个比特分配情况. 与传统的寄存器分配问题将每个寄存器视为固定
但这里强调了绑定方案
的位宽不同, 寄存器绑定问题允许根据变量的位宽灵活地调整寄存器的位宽. 这种灵活性有助于减少所需的寄存
器数量, 从而最大程度地利用寄存器资源.
例 1: 图 1 左侧是一段简单的程序源码示例, 在该样例中我们忽略调度等其他 HLS 过程, 图 1 右侧对该示例
的寄存器绑定问题进行了更加详细的展示 [13] . 图的横向每个方框表示 1 比特位, 例如变量 a 需要至少 5 位的寄存
器; 图的纵向的每条横线标记了不同的程序点, 用于表示变量的活跃区间. 每个变量的位宽与活跃区间构成了一个
矩形, 因此, 可以简化地说寄存器绑定问题的解决方案应尽可能紧密地打包所有的矩形, 而不允许重叠.

a, b, c=... ;
U i =
a b c
d=b>>3;
d
e=8*c;
e
return a+d+e;
图 1 样例例源码与变量位宽-活跃区间示意图

2.3 加权区间图着色抽象

Cong 等人 [11] 将寄存器绑定问题转化为加权区间图着色问题进行求解, 从而允许寄存器以任意位宽进行绑定,
我们首先给出其基本定义.
对于给定程序 P , 可以导出区间图 G(V,E) . 其中每个顶点 v ∈ V 对应于程序中的变量, 边 (a,b) ∈ E , 当且仅当
G 的每个顶点 赋予一
v
两个顶点 a,b ∈ V 对应变量的生命周期相互重叠, 即它们不能绑定到同一个寄存器中. 给图
个权重 w(v) 表示对应变量的位宽, 我们称该图为加权图, 并记为 G(V,E,W) . 独立集是指图中互不相邻的顶点构成
k
的集合. 假设 C = {c 1 ,c 2 ,...,c k } 是图 G(V,E) 的某一着色方案, 该方案将顶点集合 V 划分为 个独立集 V 1 ,V 2 ,...,V k ,
i
其中 V i 表示第 个独立集, c i 表示 V i 中的变量所着的颜色. 若定义独立集 S 的权重为 w(s) = max{w(v)|v ∈ S } , 颜色
c i 的权重定义为 w(V i ) , 则着色方案 C 的权重可以定义为:

∑
k
Φ(G,C) = w(V i ).
i=1
基于以上定义, 位宽感知的寄存器分配问题可以映射为加权区间图着色问题, 定义如下.
定义 2. 加权区间图着色问题. 给定加权区间图 G(V,E,W) , 求解使得权重函数 Φ(G,C) 最小化的着色方案 C .
WIGC 问题在某些研究工作中也被称为区间图的最大着色问题 (max-coloring problem) [36] . 当顶点的权重一致
时, 这个问题可以在多项式时间内解决, 然而对一般问题而言, 该问题已被证明是 NPC 问题 [36,37] . WIGC 问题的理
论下界可以通过子图的色数进行估计. 我们将图 G 按照顶点的权重划分子图, 并按权重从大到小排序为 G 1 ,G 2 ,...,
∪ i
G m , 子图 G i 的顶点对应的权重记为 w i , 记 G j , k i = χ(U i )−χ(U i−1 ) k 1 = χ(G 1 ) . 则 WIGC 下界可以通过
,
j=1
如下公式进行估计:

∑ m
L(G) = w i ·k i .
i=1
Cong 等人 [11] 提出了一种基于 WIGC 抽象的启发式算法, 我们称之为 Cong 算法. 该算法首先将变量按位宽降
序排列, 通过启发式方法将位宽相近的变量合并装入同一个寄存器中进行分配. 图 2(b) 显示了 Cong 算法对例 1
b 和变量 共享一个 位寄存器, 而其余变量则分别使用与它们的位宽相同的寄存
e
的解决方案. 在该方案中, 变量 7
器, 总共需要分配 19 位寄存器.